weakref_bug.rb

Makoto Kishimoto, 09/22/2011 06:48 AM

Download (583 Bytes)

 
1
require "weakref"
2

    
3
class IntValue
4
  def initialize value
5
    @value = value
6
  end
7

    
8
  def value
9
    @value
10
  end
11
end
12

    
13
MEMO = {}
14

    
15
def part n, k
16
  return 1 if n < 2
17
  #puts "part #{n}, #{k}"
18
  begin
19
    if it = MEMO[[n, k]] then
20
      return it.value
21
    end
22
  rescue WeakRef::RefError
23
    MEMO.delete([n, k])
24
  end
25
  # part(n - 1, 1) + part(n - 2, 2) + ... + part(n - k, k)
26
  r = 1
27
  (n - 2).downto(n - k).each {|nn|
28
    break if nn < 0
29
    r += part(nn, n - nn)
30
  }
31
  r %= 1_000_000
32
  MEMO[[n, k]] = WeakRef.new IntValue.new r
33
  return r
34
end
35

    
36
(0 .. 60).each {|n|
37
  #p n
38
  part n, n
39
}