与えた条件を満たす候補 in Clean 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にした場合に、答えが…と色々悩みどころでした。

post comment

Posted feedbacks - Clean

module xop
import StdEnv;($) infixr 1;($) a b :== a b;(>>.) infixl 0;(>>.) a b = \ w -> (\ (_, w) -> b w) (a w);(>>=) infixl 0;(>>=) a b = \ w -> (\ (x, w) -> b x w ) (a w);liftM m :== \ lst -> \ w ->  (m lst, w);join del [x:xs]= (toString x) +++ del +++ (join del xs);join _ [] = "";putStr str = \w -> (stdio >>= liftM ( fwrites str) >>= fclose) w;Start w =snd $ main w;
main = putStr $ join "\n" $ map (join ",") $ xop [And, Or, Not, And]
tf = [True, False]
:: XopOp = And |Or |Not
xopisNot Not = True
xopisNot _ = False
xop :: [XopOp] -> [[Bool]]
xop oplis = foldl (\ knil x  -> if (xopSatisfaction oplis x ) [x:knil] knil) [] $ crossProduct $ take n $ repeat tf  where
    n = length oplis  +  1  -  length (filter xopisNot oplis)
xopSatisfaction x org= lp x org where
    lp [And:Not:xs] [y:y2:ys] = lp xs [y && (not y2):ys]
    lp [And:xs] [y:y2:ys] = lp xs [y && y2:ys]
    lp [Or:Not:xs]  [y:y2:ys] = lp xs [y || (not y2):ys]
    lp [Or:xs]  [y:y2:ys] = lp xs [y || y2:ys]
    lp []  [y:ys]         = y
    lp _  [] = abort "test"
crossProduct x :== cp [] x where
    cp knil [[x:xs]:ys] = (cp knil [xs:ys]) ++ cp [x:knil] ys
    cp knil [[]:ys] =  []
    cp knil [] =  [knil]

DouKaku?

与えた条件を満たす候補

Posted feedbacks - Clean

Index

Feed

Other

Link

Pathtraq