Memoized recursion in Crystal

Crystalでメモ化再帰を行う

• In Ruby, to perform memoized recursion, we usually declare $memo={}.
• Crystal also accepted this method (actually type config is required, so like $memo={} of Int32 => Int64).
• However, this stopped working in 0.19.0. @memo and @@memo are also invalid at top-level.
  • https://github.com/crystal-lang/crystal/issues/3139
• The best way for memoized recursion is now to use class.
• https://yukicoder.me/submissions/144799

yukicoder287_class.cr

class Solve
	@memo={} of Tuple(Int32,Int32) => Int64
	def perform(n,d,u)
		if d==1
			0<=n&&n<=u ? 1 : 0
		else
			@memo[{n,d}]||=(0..u).reduce(0_i64){|s,i|s+perform(n-i,d-1,u)}
		end
	end
	def run
		n=gets.not_nil!.to_i
		p perform(6*n,8,n)
	end
end
Solve.new.run

• However, this is a little bit over-work for competitive programming.
• With checking the issue, the most problematic point is initializing. Now we can utilize the fact that in (Ruby and) Crystal, contants are just un-reassignable and destructive updating is possible. In short, we use Memo.
• Now we are able to build the program.
• https://yukicoder.me/submissions/144800

yukicoder287_const.cr

Memo={} of Tuple(Int32,Int32) => Int64
def perform(n,d,u)
	if d==1
		0<=n&&n<=u ? 1 : 0
	else
		Memo[{n,d}]||=(0..u).reduce(0_i64){|s,i|s+perform(n-i,d-1,u)}
	end
end
n=gets.not_nil!.to_i
p perform(6*n,8,n)

---

• Rubyでメモ化再帰を行うには、先頭で$memo={}とするのが一般的である。
• Crystalでもこの方法は以前は有効であった(実際には型指定が必要なので、$memo={} of Int32 => Int64などとする)。
• しかし、この方法は0.19.0で使えなくなった。@memoや@@memoも効かない。
  • https://github.com/crystal-lang/crystal/issues/3139
• 現在メモ化再帰を行うのに最も良い方法はクラスで囲うことであろう。
• しかし、競技プログラミングでは、これは多少オーバーワークである。
• このissueを見ると、初期化に問題があることがわかる。そこで、(Rubyや)Crystalでは、定数とは再代入不可なものであり破壊的変更は可能であることを利用する。つまり、Memoを宣言する。
• これでコンパイルを通すことができた。