Rubyでたまたま再帰的な配列 [[...]] に出会って、何かに使ってみたくなった。

再帰的な配列の例

a = []
a << a << a << a   #=> [[...], [...], [...]]
a[0][1][2][1][0]   #=> [[...], [...], [...]]
a.flatten(1)       #=> ArgumentError: tried to flatten recursive array

いくら深掘りしても終わらない配列で何ができるか考えた結果、閏年の判定くらいは比較的簡単にできるだろうと思い実行した。

閏年のおさらい

閏年の規則をWikipediaより抜粋。

グレゴリオ暦では、次の規則に従って400年間に97回の閏年を設ける。

西暦年が4で割り切れる年は閏年。

ただし、西暦年が100で割り切れる年は平年。

ただし、西暦年が400で割り切れる年は閏年。

この通りに判定を作れば year % 4 == 0 && !(year % 100 == 0 && !(year % 400 == 0)) となる。再帰的どころか普通の配列も使う必要がない。

一方で、これからする方法は逆に計算を必要としない。

コード

相互再帰な7つの配列を使う。

leap_year.rb

A, B, C, D, E, F, G = Array.new(7) { [] }
#          0  1  2  3  4  5  6  7  8  9
A.replace [D, A, C, A, B, A, C, A, B, A]
B.replace [E, A, B, A, C, A, B, A, C, A]
C.replace [C, A, B, A, C, A, B, A, C, A]
D.replace [F, A, B, A, C, A, B, A, C, A]
E.replace [G, A, B, A, C, A, B, A, C, A]
F.replace [G, A, B, A, C, A, B, A, C, A]
G.replace [C, A, B, A, C, A, B, A, C, A]

# $stderr.puts G.inspect[0,60]
#=> [[[...], [[[[...], [...], [[[...], [...], [...], [...], [...

def leap_year?(str)
	digits = str.each_char.map(&method(:Integer))
	result = digits.inject(G, :[])
	result.equal?(C) || result.equal?(E)
end

if $0 == __FILE__
	while (str = gets)
		str.strip!
		puts "#{str}\t#{leap_year?(str)}"
	end
end

terminal

$ seq 2001 2400 | ruby leap_year.rb
2001	false
2002	false
2003	false
2004	true
2005	false
2006	false
2007	false
2008	true
2009	false
2010	false
...
2400	true
$ seq 2001 2400 | ruby leap_year.rb | grep -c true
97

digits を逆順にしたバージョンも作れる。直接 Integer#digits を使っているので、Ruby 2.4以上が必要。
こちらも配列は7つだが、T, Zが自己再帰なだけであり単純すぎて物足りない。

leap_year_rev.rb

T, U, V, W, X, Y, Z = Array.new(7) { [] }
#          0  1  2  3  4  5  6  7  8  9
T.replace [T, T, T, T, T, T, T, T, T, T]
U.replace [T, Z, T, Z, T, Z, T, Z, T, Z]
V.replace [W, T, U, T, Y, T, U, T, Y, T]
W.replace [X, T, Z, T, Z, T, Z, T, Z, T]
X.replace [Y, T, U, T, Y, T, U, T, Y, T]
Y.replace [Z, T, Z, T, Z, T, Z, T, Z, T]
Z.replace [Z, Z, Z, Z, Z, Z, Z, Z, Z, Z]

# $stderr.puts V.inspect[0,60]
#=> [[[[[[...], [...], [...], [...], [...], [...], [...], [...],

def leap_year?(str)
	result = Integer(str).digits.inject(V, :[])
	[W, X, Y, Z].any?(&result.method(:equal?))
end

if $0 == __FILE__
	while (str = gets)
		str.strip!
		puts "#{str}\t#{leap_year?(str)}"
	end
end

仕組み

配列の作り方からバレている可能性もあるが、ただ単に閏年を判定できる決定性有限オートマトン（Deterministic Finite Automaton; DFA）をコード化している。DFAについて知らなくても、以下の状態遷移図を実際にたどってみれば意味するところは分かると思う。

「閏年判定機」の状態を初期状態G（外からの矢印が書いてあるもの）にセットして、1桁入力される度に図に従って対応する矢印をたどり機械の状態を変化させる。

2, 0, 1, 7 と入力すると、G → B → E → A → A と状態が移っていく。一重丸の状態で終わるとfalse、つまり2017年は閏年でない。
2, 0, 0, 0 と入力すると、G → B → E → G → C と状態が移っていく。二重丸の状態で終わるとtrue、つまり2000年は閏年。

コードに出てくる配列は、オブジェクト自身はDFAの各状態を、格納要素は入力毎の遷移先を表している。連続した入力列 [2, 0, 1, 7] に対する遷移は G[2][0][1][7] という風に次々と参照していけばよく、それを #inject で短く実装している。再帰的な配列を「無限の入れ子構造」と捉えてしまうと理解が難しいが、実際には有限個の配列の間を行き来しているだけである。

なお、入力する桁を反転させたほうのDFAの状態遷移図は以下の通り。閏年は400で割った余りで判定でき、遅くとも下4桁目を入力した段階で確実に真偽が決まるので、状態T, Zに達するまでループしない。

ハッシュで汎用的に

DFAなら数字だけでなく文字を入力して遷移できたほうがいい。なので配列でなくハッシュを使うよう直してみる。

毎回状態遷移をコード化するのは大変なので、別のファイルにDFAの設計だけ書いておいてそれを読み込むようにした。（ファイルを指定しない場合はコード末尾のテキストを読み込む。）

hash_dfa.rb

null_state = Hash.new.tap { |state| state.default = state }.freeze
states = Hash.new { |list,name| list[name] = Hash.new(null_state) }

f = ARGV[0] ? File.open(ARGV[0]) : DATA
begin
	initial_state = states[f.gets.split[0]]
	accept_states = f.gets.split.map { |name| states[name] }

	f.each_line do |l|
		from, to, chrs = l.chomp.split(nil, 3)
		state1 = states[from]
		state2 = states[to]
		chrs.each_char { |c| state1[c] = state2 }
	end
ensure
	f.close
end

while (str = $stdin.gets)
	str.chomp!   # delete "\n"
	final_state = str.each_char.inject(initial_state, :[])
	bool = accept_states.any?(&final_state.method(:equal?))
	puts "#{str}\t#{bool}"
end

__END__
G
C E
A	A	13579
A	B	48
A	C	26
A	D	0
B	A	13579
B	B	26
B	C	48
B	E	0
C	A	13579
C	B	26
C	C	048
D	A	13579
D	B	26
D	C	48
D	F	0
E	A	13579
E	B	26
E	C	48
E	G	0
F	A	13579
F	B	26
F	C	48
F	G	0
G	A	13579
G	B	26
G	C	048

Hash は未登録のキーを参照したときにデフォルト値を返したりできるので、その点でも配列より便利。

states : 状態名からオブジェクトを参照するためのリスト。新しい状態名が来たらオブジェクトを新規作成する。
states[name] : 個々の状態。配列のときと異なり、遷移の定義されない文字を受け取ると null_state という特別な状態に飛ばす。
null_state : 一旦この状態になると、以降は何を入力してもこの状態のままで、falseと判定される。ブラックホール。