金貨と銅貨と空箱の「うそつき問題」（Ruby）

rsc.hatenablog.comまたまた rsc さんのブログから問題を拝借して、Ruby で解いてみました。
　

問題

コピペさせてもらいます。

　A～Eの五つの箱があり、これらの箱は、金貨の入った箱、銅貨の入った箱、空箱の3種類の場合がある。
　また、それぞれの箱にはラベルが付いているが、そのラベルの記述の内容は、金貨の入った箱のものは真(真実に一致している)であるが、銅貨の入った箱のものは偽(真実に反している)であり、空箱のものは真の場合も偽の場合もあるという。
　このとき、銅貨の入った箱が二つあるとすると、確実に銅貨の入った箱はどれか。
[ラベル]
A:「Bのラベルの記述の内容は真である。」
B:「Aが空箱ならば、この箱も空箱である。」
C:「この箱は、銅貨の入った箱である。」
D:「AかEの少なくとも一方は、銅貨の入った箱である。」
E:「この箱は、金貨の入った箱である。」

解答例

問題が少し曖昧で、空箱の場合、「真の場合も偽の場合もある」というのは「真でも偽でもどちらでも可」なのか、「真の場合も偽の場合も両方とも満たさないといけない」のかわかりませんが、まあ前者だろうと解釈して解きました。

コード。

N = 5
TBL = [*0...N]

box = Array.new(N)

imp = ->(p, q) {!p || q}

label = Array.new(N)
label[0] = ->{label[1].()}
label[1] = ->{imp.(!box[0], !box[1])}
label[2] = ->{box[2] == :copper}
label[3] = ->{box[0] == :copper || box[4] == :copper}
label[4] = ->{box[4] == :gold}

judgement = ->(i) {
  return true unless box[i]
  f = label[i].()
  (box[i] == :gold) ? f : !f
}

output = ->{
  puts (0...N).map {|i| "#{%W(A B C D E)[i]}=>#{box[i].inspect}"}.join(", ")
}

TBL.combination(2) do |cp2|
  cp2.each {|c| box[c] = :copper}
  (0..3).each do |n|
    (TBL - cp2).combination(n) do |golds|
      golds.each {|g| box[g] = :gold}
      (TBL - cp2 - golds).each {|e| box[e] = nil}
      output.() if (0...N).all? {|i| judgement.(i)}
    end
  end
end

　
結果。

A=>nil, B=>:copper, C=>nil, D=>:copper, E=>nil
A=>nil, B=>:copper, C=>nil, D=>:copper, E=>:gold
A=>nil, B=>:copper, C=>nil, D=>nil, E=>:copper
A=>nil, B=>:copper, C=>nil, D=>:gold, E=>:copper

つまり答えは B ということになります。
　

簡単な解説

箱は A ~ E ということですが、コードでは 0 ~ 4 に置き換えています。

基本的に「総当り法」で、まず「銅」の箱を2つ選び、残りは適当に「金」か「空」を割り当てます。全部「金」になったり、全部「空」になる場合もあります（と解釈して解いたのですが、それも問題では曖昧です）。箱は box[] で、:gold, :copper, nil が入るということです（nil は「空」）。

ラベルの条件は label[] に Proc オブジェクトで記述しています。「p ならば q」という論理包含（IMP）は、「p の否定と q との論理和」と必要十分なので、それを imp という Proc で表現しています。

箱の中身とラベルのマッチングを判断しないといけないので、それは judgement.() で記述しています。すべての箱で judgement.() が真になった場合に、その組み合わせを出力（ output.() ）します。

Proc （ここでは lambda ですが）のクロージャの機能を使いまくっているコードになっています。