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

こんな感じ。
*Main> f ["and","or","not","and"]
(True,True,True,True)
(True,True,False,True)
(True,False,False,True)
(False,True,False,True)
(False,False,False,True)

t :: (Bool -> Bool) -> [Bool] -> [String] -> Bool
t prev (x:[]) _ = prev x
t prev (x:xs) (op:ops) | op == "not" = t prev (not x:xs) ops
                       | op == "and" = t ((&&) (prev x)) xs ops
                       | op == "or"  = t ((||) (prev x)) xs ops

f :: [String] -> IO ()
f ops = mapM_ print [(b1,b2,b3,b4) | bs@(b1:b2:b3:[b4]) <- bss, test bs ops]
  where bss = sequence $ replicate 4 [True,False]
        test = t id

Main> f ["and","or","not","and"]
[True,True,True,True]
[True,True,False,True]
[False,True,False,True]
[True,False,False,True]
[False,False,False,True]

解を直接構成。"and"を100個並べて入力してもすぐ終わる(もちろん"or"だと無理です)。

f = mapM_ (print . reverse) . g . reverse
g [] = [[True]]
g ("not":ops) = [not b:bs | (b:bs)<-g ops]
g ("and":ops) = map (True:) (g ops) 
g ("or":ops) = map (False:) (g ops) ++ map (True:) anybs
 where anybs = sequence $ (replicate.length.head.g) ops [True,False]

guard をつかってみた

import Control.Monad

starling f g x = f x (g x)

f :: [String] -> [[Bool]]
f cs = sequence (replicate 4 [False,True])
   >>= starling ((>>) . guard . flip (t id) cs) return

t :: (Bool -> Bool) -> [Bool] -> [String] -> Bool
t prev [x]    _           = prev x
t prev (x:xs) ("not":ops) = t prev (not x:xs) ops
t prev (x:xs) ("and":ops) = t (prev x &&) xs  ops
t prev (x:xs) ("or" :ops) = t (prev x ||) xs  ops

{-
*Main> f ["and","or","not","and"]
[[False,False,False,True]
,[False,True,False,True]
,[True,False,False,True]
,[True,True,False,True]
,[True,True,True,True]]
-}

関数型っぽいですね。
foldl を使って写経。（test の部分のみ）

test xs ops = p x where
  (p, x:_) = foldl f (id, xs) ops
  f (prev, x:xs) op
    | op == "not" = (prev, not x:xs)
    | op == "and" = (((&&) (prev x)), xs)
    | op == "or" = (((||) (prev x)), xs)

効率良さそうですね。
foldl を使って写経。

f = mapM_ (print . reverse) . snd . foldl g  (1, [[True]]) where
  g (l,bs) "not" = (l, [not b:bs' | (b:bs')<-bs])
  g (l,bs) "and" = (l+1, map (True:) bs) 
  g (l,bs) "or" = (l+1, map (False:) bs ++ sequence ([True]: replicate l [True,False]))

DouKaku?

与えた条件を満たす候補

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq