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

イマイチ。

#light
type ListBuilder () =
    member l.Bind (v,f) = List.concat (List.map f v)
    member l.Return x = [x]
    member l.Let(v,f) = f v

let guard c = if c then [()] else []

let doList = new ListBuilder()

let rec all_comb = function
    | 0 -> [[]]
    | n -> doList { let! rest = all_comb (n-1)
                    let! result = [(true::rest);(false::rest)]
                    return result }

let num_args cmds =
    List.filter ((<>) "not") cmds
    |> List.length
    |> (+) 1

let rec satisfy (cmds:string list) (bools:bool list) =
    match cmds,bools with
    | [],b::[]            -> b
    | "not"::[],b::[]     -> not b
    | "not"::cs,b::bs     -> satisfy cs ((not b)::bs)
    | "and"::"not"::cs,b::b'::bs -> satisfy cs ((b && (not b'))::bs)
    | "or"::"not"::cs,b::b'::bs  -> satisfy cs ((b || (not b'))::bs)
    | "and"::cs,b::b'::bs -> satisfy cs ((b && b')::bs)
    | "or"::cs,b::b'::bs  -> satisfy cs ((b || b')::bs)

let get_combs cmds =
    doList { let! cont = all_comb (num_args cmds)
             do! guard (satisfy cmds cont)
             return cont }

do get_combs ["and";"or";"not";"and"]
   |> (print_any >> print_newline)

nskj77さんのコードを参考に修正してみました。

see:

#light
type ListBuilder () =
    member l.Bind (v,f) = List.concat (List.map f v)
    member l.Return x = [x]
    member l.Let(v,f) = f v

let guard c = if c then [()] else []

let doList = new ListBuilder()

let rec satisfy prev bs cmds =
    match bs, cmds with
    | b::[], _     -> prev b
    | b::bs, cmd::cmds ->
            match cmd with
            | "not" -> satisfy prev ((not b)::bs) cmds
            | "and" -> satisfy ((&&) (prev b)) bs cmds
            | "or"  -> satisfy ((||) (prev b)) bs cmds

let rec all_comb = function
    | 0 -> [[]]
    | n -> doList { let! rest = all_comb (n-1)
                    let! result = [(true::rest);(false::rest)]
                    return result }

let get_combs cmds =
    let len = 1 + (List.length (List.filter ((<>) "not") cmds))
    doList { let! bs = all_comb len
             do! guard (satisfy (fun x -> x) bs cmds)
             return bs }

do get_combs ["and";"or";"not";"and"]
   |> (print_any >> print_newline)

さらにモナドを使わずに書き直してみました。

#light
let rec satisfy prev bs cmds =
    match bs, cmds with
    | b::[], _     -> prev b
    | b::bs, cmd::cmds ->
            match cmd with
            | "not" -> satisfy prev ((not b)::bs) cmds
            | "and" -> satisfy ((&&) (prev b)) bs cmds
            | "or"  -> satisfy ((||) (prev b)) bs cmds

let rec all_comb = function
    | 0 -> [[]]
    | n -> [ for res in all_comb (n-1) ->> [true::res;false::res] ]

let get_combs cmds =
    let len = 1 + (List.length (List.filter ((<>) "not") cmds))
    [for bs in all_comb len when satisfy (fun x -> x) bs cmds -> bs]

do get_combs ["and";"or";"not";"and"]
   |> (print_any >> print_newline)

DouKaku?

与えた条件を満たす候補

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq