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]]