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

Schemeの解答がなかったので投稿

(use srfi-1)
(use util.match)
(use util.combinations)

(define (solve expr)
  (define (op-apply expr stack)
    (match expr
     (()
      (car stack))
     (('not rest ...)
      (op-apply rest (cons (not (car stack)) (cdr stack))))
     ((op 'not rest ...)
      (op-apply (cons op rest) (list* (car stack) (not (cadr stack)) (cddr stack))))
     (('and rest ...)
      (op-apply rest (cons (and (car stack) (cadr stack)) (cddr stack))))
     (('or rest ...)
      (op-apply rest (cons (or (car stack) (cadr stack)) (cddr stack))))))
  (filter (cut op-apply expr <>) (cartesian-product (make-list 4 '(#t #f)))))

手抜きをしてパラメータ(x1, x2, x3, x4)の個数が4個限定だったのを修正しました。

(use srfi-1)
(use util.match)
(use util.combinations)

(define (solve expr)
  (define (op-apply expr stack)
    (match expr
     (()
      (car stack))
     (('not rest ...)
      (op-apply rest (cons (not (car stack)) (cdr stack))))
     ((op 'not rest ...)
      (op-apply (cons op rest) (list* (car stack) (not (cadr stack)) (cddr stack))))
     (('and rest ...)
      (op-apply rest (cons (and (car stack) (cadr stack)) (cddr stack))))
     (('or rest ...)
      (op-apply rest (cons (or (car stack) (cadr stack)) (cddr stack))))))
  (filter (cut op-apply expr <>)
          (cartesian-product (make-list
                              (+ (length (filter (cut memq <> '(and or)) expr)) 1)
                              '(#t #f)))))

DouKaku?

与えた条件を満たす候補

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq