DouKaku?

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。 ご投稿ありがとうございました。
元ネタの 充足可能性問題 - Wikipedia は、 同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、 今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

こんな感じ。prodloop のところはもう少しましにしたかったけど、うーん。

> solve(['and', 'or', 'not', 'and'])
[true, true, true, true]
[true, true, false, true]
[true, false, false, true]
[false, true, false, true]
[false, false, false, true]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def prodloop(count, arg=[])
  if count > 0
    (prodloop count-1, arg + [true]) + (prodloop count-1, arg + [false])
  else
    [arg]
  end
end

def solve(list)
  expression = ""
  idx = 0
  list.each do |op|
    if op == "not"
      expression += " not "
    else
      expression += " arg[#{idx}] #{op} "
      idx += 1
    end
  end
  expression += " arg[#{idx}] "
  prodloop(idx+1).each do |arg|
    p arg if eval(expression)
  end
end