Rubyで非決定性計算
以前ここで有名なBaker, Cooper…の非決定性計算をRubyで解いてみました。コードはこんな感じです。
#!/usr/bin/env ruby module Enumerable def distinct? table = {} each do |e| return false if table[e] table[e] = true end return true end end solve = [] [1, 2, 3, 4, 5].each do |baker| [1, 2, 3, 4, 5].each do |cooper| [1, 2, 3, 4, 5].each do |fletcher| [1, 2, 3, 4, 5].each do |miller| [1, 2, 3, 4, 5].each do |smith| next unless [baker, cooper, fletcher, miller, smith].distinct? next unless baker != 5 next unless cooper != 1 next unless fletcher != 1 and fletcher != 5 next unless miller > cooper next unless (smith - fletcher).abs != 1 next unless (fletcher - cooper).abs != 1 solve << [baker, cooper, fletcher, miller, smith] end end end end end p solve
このeachが続く部分がもうちょっと何とかならないものかと思って、下のコードを書いてみました。combメソッドの引数は、eachに反応できれば何でも(RangeでもArrayでも)よいです。acc + [e]の配列コピーがいやな人はpush、popを使って破壊的にするとよいと思います。
def comb(*args, &block) _comb_([], *args, &block) end def _comb_(acc, *args, &block) return if args.empty? a, *as = args a.each do |e| if as.empty? block[acc + [e]] else _comb_(acc + [e], *as, &block) end end end
このメソッドを使うと、組合せがこんな風に求められます。
comb(1 .. 3, 11 .. 13, 21 .. 23) do |a| p a end # => [1, 11, 21] # [1, 11, 22] # [1, 11, 23] # [1, 12, 21] # [1, 12, 22] # [1, 12, 23] # [1, 13, 21] # [1, 13, 22] # [1, 13, 23] # [2, 11, 21] # [2, 11, 22] # [2, 11, 23] # [2, 12, 21] # [2, 12, 22] # [2, 12, 23] # [2, 13, 21] # [2, 13, 22] # [2, 13, 23] # [3, 11, 21] # [3, 11, 22] # [3, 11, 23] # [3, 12, 21] # [3, 12, 22] # [3, 12, 23] # [3, 13, 21] # [3, 13, 22] # [3, 13, 23]
Baker, Cooper…の非決定性計算はこんな風になります。おお。なかなかシンプルになりました。ここまでくるとHaskell並かな。
solve = [] comb(*([1 .. 5] * 5)) do |a| baker, cooper, fletcher, miller, smith = *a next unless [baker, cooper, fletcher, miller, smith].distinct? next unless baker != 5 next unless cooper != 1 next unless fletcher != 1 and fletcher != 5 next unless miller > cooper next unless (smith - fletcher).abs != 1 next unless (fletcher - cooper).abs != 1 solve << [baker, cooper, fletcher, miller, smith] end p solve # => [[3, 2, 4, 5, 1]]