Bug #9932: Permutation - Segment fault

• Status: Closed
• Assignee: -
• Target version: 2.2.0
• ruby -v: 1.9.3p545
• Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN

[tak2siva (siva kumar)]

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)

[nobu (Nobuyoshi Nakada)]

• 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.

[calamitas (Peter Vanbroekhoven)]

On Wed, Jun 11, 2014 at 1:12 PM, [e-mail] 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
$ 754674567

Then 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

[nobu (Nobuyoshi Nakada)]

• 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 in p. [ruby-core:63103] [Bug #9932]