3 NOT problem

和田先生が紹介されていた3 NOT problemを解こうといろいろ考えましたが、結局できませんでした。orz

答えが分らないと、気になって次の仕事に進めないので、検索して答えを見つけました。

Haskell でアルゴリズムを書いておきます。

import Data.Bits

input = map triple [0..7]
    where
      triple :: Int -> (Bool,Bool,Bool)
      triple n = (testBit n 2,testBit n 1,testBit n 0)

output = map (\(x,y,z) -> (not x, not y, not z)) input

threeNot (x,y,z) = let aa =  y && z
                       ab =  x && z
                       ac =  x && y
                       ad =  y || z
                       ba =  x && aa
                       bc =  x || aa
                       ca = bc && ad
                       da = not ca
                       ea =  z && da
                       eb =  y && da
                       ec = ba || da
                       fa =  y || ea
                       fb =  x || ea
                       fc =  x || eb
                       ga = fa && da
                       fd =  x || ga
                       gb = fb && da
                       gc = fc && da
                       gd = fd && ec
                       ha = not gd
                       ia = ha || ga
                       ib = ha || gb
                       ic = ha || gc
                       ja = ia && da
                       jb = ib && da
                       jc = ic && da
                       ka = aa || ja
                       kb = ab || jb
                       kc = ac || jc
                       x' = ka && ia
                       y' = kb && ib
                       z' = kc && ic
                   in (x',y',z')

実行するとこんな感じ。

> input
[(False,False,False),(False,False,True),(False,True,False),(False,True,True),(True,False,False),(True,False,True),(True,True,False),(True,True,True)]
> map threeNot input
[(True,True,True),(True,True,False),(True,False,True),(True,False,False),(False,True,True),(False,True,False),(False,False,True),(False,False,False)]
> (map threeNot input) == output
True