Project

General

Profile

Download (583 Bytes)

Bug #5350 » weakref_bug.rb

metanest (Makoto Kishimoto), 09/22/2011 06:48 AM

 
require "weakref"

class IntValue
def initialize value
@value = value
end

def value
@value
end
end

MEMO = {}

def part n, k
return 1 if n < 2
#puts "part #{n}, #{k}"
begin
if it = MEMO[[n, k]] then
return it.value
end
rescue WeakRef::RefError
MEMO.delete([n, k])
end
# part(n - 1, 1) + part(n - 2, 2) + ... + part(n - k, k)
r = 1
(n - 2).downto(n - k).each {|nn|
break if nn < 0
r += part(nn, n - nn)
}
r %= 1_000_000
MEMO[[n, k]] = WeakRef.new IntValue.new r
return r
end

(0 .. 60).each {|n|
#p n
part n, n
}
(1-1/3)