Actions
Bug #9932
closed
Permutation - Segment fault
Description
Execute the following program with the inputs
######################################################################################
# hash.rb
t = gets.chomp.to_i
def hash str
res = str.count "A"
if str.size > 1
s1 = str[0..(str.size/2 - 1)]
s2 = str[(str.size/2)..-1]
#p "#{s1}, #{str}"
res += [hash(s1), hash(s2)].max
end
res
end
#puts hash("AAEAAE")
t.times do |x|
a = gets.chomp.to_i
e = gets.chomp.to_i
v = gets.chomp.to_i
pos = ("A"*a + "E"*e).split('').permutation.map(&:join).uniq
r = 0
pos.each do |y|
r += 1 if(hash(y)==v)
end
puts (r % 1000000007)
end
######################################################################################
$ ruby hash.rb
$ 1
$ 234234
$ 224
$ 754674567
Then the follwing error is produced
[siva@siva chef]$ ruby hash.rb
1
234234
224
754674567
hash.rb:22: [BUG] Segmentation fault
ruby 1.9.3p545 (2014-02-24 revision 45159) [x86_64-linux]
-- Control frame information -----------------------------------------------
c:0009 p:---- s:0027 b:0027 l:000026 d:000026 CFUNC :permutation
c:0008 p:---- s:0025 b:0025 l:000024 d:000024 CFUNC :each
c:0007 p:---- s:0023 b:0023 l:000022 d:000022 CFUNC :map
c:0006 p:0114 s:0020 b:0020 l:0007f8 d:000019 BLOCK hash.rb:22
c:0005 p:---- s:0012 b:0012 l:000011 d:000011 FINISH
c:0004 p:---- s:0010 b:0010 l:000009 d:000009 CFUNC :times
c:0003 p:0052 s:0007 b:0007 l:0007f8 d:0014b0 EVAL hash.rb:17
c:0002 p:---- s:0004 b:0004 l:000003 d:000003 FINISH
c:0001 p:0000 s:0002 b:0002 l:0007f8 d:0007f8 TOP
-- Ruby level backtrace information ----------------------------------------
hash.rb:17:in `<main>'
hash.rb:17:in `times'
hash.rb:22:in `block in <main>'
hash.rb:22:in `map'
hash.rb:22:in `each'
hash.rb:22:in `permutation'
-- C level backtrace information -------------------------------------------
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(+0x17dc97) [0x7f2796e84c97] vm_dump.c:796
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(+0x5eda4) [0x7f2796d65da4] error.c:258
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(rb_bug+0xb8) [0x7f2796d65f48] error.c:277
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(+0x10cb4d) [0x7f2796e13b4d] signal.c:644
/lib64/libpthread.so.0() [0x3f4980f710]
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(+0x2ec40) [0x7f2796d35c40] array.c:4102
/usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9(+0x2eca7) [0x7f2796d35ca7] array.c:4107
(snip same 1017 lines)
-- Other runtime information -----------------------------------------------
* Loaded script: hash.rb
* Loaded features:
0 enumerator.so
1 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/encdb.so
2 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/trans/transdb.so
3 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/rbconfig.rb
4 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/compatibility.rb
5 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/defaults.rb
6 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/deprecate.rb
7 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/errors.rb
8 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/version.rb
9 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/requirement.rb
10 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/platform.rb
11 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/basic_specification.rb
12 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/stub_specification.rb
13 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/util/stringio.rb
14 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/specification.rb
15 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/exceptions.rb
16 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/core_ext/kernel_gem.rb
17 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/thread.rb
18 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/monitor.rb
19 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems/core_ext/kernel_require.rb
20 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/site_ruby/1.9.1/rubygems.rb
* Process memory map:
00400000-00401000 r-xp 00000000 08:02 4497252 /usr/local/rvm/rubies/ruby-1.9.3-p545/bin/ruby
00600000-00601000 rw-p 00000000 08:02 4497252 /usr/local/rvm/rubies/ruby-1.9.3-p545/bin/ruby
011e3000-01f8e000 rw-p 00000000 00:00 0 [heap]
3f48c00000-3f48c20000 r-xp 00000000 08:02 524316 /lib64/ld-2.12.so
3f48e1f000-3f48e20000 r--p 0001f000 08:02 524316 /lib64/ld-2.12.so
3f48e20000-3f48e21000 rw-p 00020000 08:02 524316 /lib64/ld-2.12.so
3f48e21000-3f48e22000 rw-p 00000000 00:00 0
3f49400000-3f4958b000 r-xp 00000000 08:02 524318 /lib64/libc-2.12.so
3f4958b000-3f4978a000 ---p 0018b000 08:02 524318 /lib64/libc-2.12.so
3f4978a000-3f4978e000 r--p 0018a000 08:02 524318 /lib64/libc-2.12.so
3f4978e000-3f4978f000 rw-p 0018e000 08:02 524318 /lib64/libc-2.12.so
3f4978f000-3f49794000 rw-p 00000000 00:00 0
3f49800000-3f49817000 r-xp 00000000 08:02 524340 /lib64/libpthread-2.12.so
3f49817000-3f49a17000 ---p 00017000 08:02 524340 /lib64/libpthread-2.12.so
3f49a17000-3f49a18000 r--p 00017000 08:02 524340 /lib64/libpthread-2.12.so
3f49a18000-3f49a19000 rw-p 00018000 08:02 524340 /lib64/libpthread-2.12.so
3f49a19000-3f49a1d000 rw-p 00000000 00:00 0
3f49c00000-3f49c02000 r-xp 00000000 08:02 524450 /lib64/libdl-2.12.so
3f49c02000-3f49e02000 ---p 00002000 08:02 524450 /lib64/libdl-2.12.so
3f49e02000-3f49e03000 r--p 00002000 08:02 524450 /lib64/libdl-2.12.so
3f49e03000-3f49e04000 rw-p 00003000 08:02 524450 /lib64/libdl-2.12.so
3f4a000000-3f4a083000 r-xp 00000000 08:02 524681 /lib64/libm-2.12.so
3f4a083000-3f4a282000 ---p 00083000 08:02 524681 /lib64/libm-2.12.so
3f4a282000-3f4a283000 r--p 00082000 08:02 524681 /lib64/libm-2.12.so
3f4a283000-3f4a284000 rw-p 00083000 08:02 524681 /lib64/libm-2.12.so
3f4a400000-3f4a407000 r-xp 00000000 08:02 524372 /lib64/librt-2.12.so
3f4a407000-3f4a606000 ---p 00007000 08:02 524372 /lib64/librt-2.12.so
3f4a606000-3f4a607000 r--p 00006000 08:02 524372 /lib64/librt-2.12.so
3f4a607000-3f4a608000 rw-p 00007000 08:02 524372 /lib64/librt-2.12.so
3f4cc00000-3f4cc16000 r-xp 00000000 08:02 525285 /lib64/libgcc_s-4.4.7-20120601.so.1
3f4cc16000-3f4ce15000 ---p 00016000 08:02 525285 /lib64/libgcc_s-4.4.7-20120601.so.1
3f4ce15000-3f4ce16000 rw-p 00015000 08:02 525285 /lib64/libgcc_s-4.4.7-20120601.so.1
3f56c00000-3f56c71000 r-xp 00000000 08:02 524481 /lib64/libfreebl3.so
3f56c71000-3f56e70000 ---p 00071000 08:02 524481 /lib64/libfreebl3.so
3f56e70000-3f56e72000 r--p 00070000 08:02 524481 /lib64/libfreebl3.so
3f56e72000-3f56e73000 rw-p 00072000 08:02 524481 /lib64/libfreebl3.so
3f56e73000-3f56e77000 rw-p 00000000 00:00 0
3f57600000-3f57607000 r-xp 00000000 08:02 524483 /lib64/libcrypt-2.12.so
3f57607000-3f57807000 ---p 00007000 08:02 524483 /lib64/libcrypt-2.12.so
3f57807000-3f57808000 r--p 00007000 08:02 524483 /lib64/libcrypt-2.12.so
3f57808000-3f57809000 rw-p 00008000 08:02 524483 /lib64/libcrypt-2.12.so
3f57809000-3f57837000 rw-p 00000000 00:00 0
7f27904ad000-7f2790678000 rw-p 00000000 00:00 0
7f2790678000-7f2790870000 rw-p 00000000 00:00 0
7f27908ce000-7f2790908000 rw-p 00000000 00:00 0
7f2790942000-7f2790944000 r-xp 00000000 08:02 5642115 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/trans/transdb.so
7f2790944000-7f2790b44000 ---p 00002000 08:02 5642115 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/trans/transdb.so
7f2790b44000-7f2790b45000 rw-p 00002000 08:02 5642115 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/trans/transdb.so
7f2790b45000-7f2790b47000 r-xp 00000000 08:02 5642141 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/encdb.so
7f2790b47000-7f2790d46000 ---p 00002000 08:02 5642141 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/encdb.so
7f2790d46000-7f2790d47000 rw-p 00001000 08:02 5642141 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/ruby/1.9.1/x86_64-linux/enc/encdb.so
7f2790d47000-7f2790d48000 ---p 00000000 00:00 0
7f2790d48000-7f2790e4c000 rw-p 00000000 00:00 0
7f2790e4c000-7f2796cdd000 r--p 00000000 08:02 4492532 /usr/lib/locale/locale-archive
7f2796cdd000-7f2796ce3000 rw-p 00000000 00:00 0
7f2796d07000-7f2796f21000 r-xp 00000000 08:02 4497254 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9.1
7f2796f21000-7f2797120000 ---p 0021a000 08:02 4497254 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9.1
7f2797120000-7f2797128000 rw-p 00219000 08:02 4497254 /usr/local/rvm/rubies/ruby-1.9.3-p545/lib/libruby.so.1.9.1
7f2797128000-7f2797145000 rw-p 00000000 00:00 0
7fff2a3a4000-7fff2afa3000 rw-p 00000000 00:00 0 [stack]
7fff2afb5000-7fff2afb6000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
[NOTE]
You may have encountered a bug in the Ruby interpreter or extension libraries.
Bug reports are welcome.
For details: http://www.ruby-lang.org/bugreport.html
Aborted (core dumped)
Updated by nobu (Nobuyoshi Nakada) over 10 years ago
- Description updated (diff)
- Assignee deleted (
wanabe (_ wanabe)) - Priority changed from 5 to 3
It's a stack overflow, and it results SystemStackError as expected on recent 2.0.0 or later.
Updated by calamitas (Peter Vanbroekhoven) over 10 years ago
On Wed, Jun 11, 2014 at 1:12 PM, tak2siva@gmail.com wrote:
Execute the following program with the inputs
###################################################################################### # hash.rb t = gets.chomp.to_i def hash str res = str.count "A" if str.size > 1 s1 = str[0..(str.size/2 - 1)] s2 = str[(str.size/2)..-1] #p "#{s1}, #{str}" res += [hash(s1), hash(s2)].max end res end #puts hash("AAEAAE") t.times do |x| a = gets.chomp.to_i e = gets.chomp.to_i v = gets.chomp.to_i pos = ("A"*a + "E"*e).split('').permutation.map(&:join).uniq r = 0 pos.each do |y| r += 1 if(hash(y)==v) end puts (r % 1000000007) end ######################################################################################$ ruby hash.rb $ 1 $ 234234 $ 224 $ 754674567Then the follwing error is produced
This looks a lot like a solution to a programming contest problem. Can you
provide a link to the problem statement?
The number of permutations you are asking for is humongous: (234234 + 224)!
which, if my calculations are right, is between 10 ** 1157233 and 10 **
1157234. There won't be a computer that can calculate and store that many
permutations for a long time (if ever).
Peter
Updated by nobu (Nobuyoshi Nakada) over 10 years ago
- Status changed from Open to Closed
- % Done changed from 0 to 100
Applied in changeset r46426.
array.c: non-recursive permute0
- array.c (permute0): remove recursion, by looping with indexes
stored inp. [ruby-core:63103] [Bug #9932]
Actions
Like0
Like0Like0Like0