素人がプログラミングを勉強していたブログ

プログラミング、セキュリティ、英語、Webなどのブログ since 2008

連絡先: twitter: @javascripter にどうぞ。

非決定性計算

scheme

4つの数字から10になる式を探すプログラム(切符の問題とも呼ばれる)を書いた。choose関数とfail関数は、404 Not Foundをypsilon上で動くように少し直した物。

(define *paths* '())
(define *fail* (gensym))
(define (choose choices)
  (if (null? choices)
    (fail)
    (call/cc
      (lambda (cc)
        (set! *paths*
          (cons (lambda ()
                  (cc (choose (cdr choices))))
                *paths*))
        (car choices)))))

(define fail #f)

(call/cc
  (lambda (cc)
    (set! fail
      (lambda ()
        (if (null? *paths*)
          (cc *fail*)
          (let ((p1 (car *paths*)))
            (set! *paths* (cdr *paths*))
            (p1)))))))

(define (calc10 a b c d)
  (define (// a b)
    (if (zero? b) (fail) (/ a b)))
  (define (choose-op x)
    (choose
      (if (zero? x) `(,+ ,- ,*)
        `(,+ ,- ,* ,//))))
  (set! *paths* '())
    (let ((op1 (choose-op b)) (op2 (choose-op c)) (op3 (choose-op d)))
    (define (infix str)
      (define op-table (make-eq-hashtable))
        (for-each
          (lambda (lis)
            (hashtable-set! op-table (car lis) (cadr lis)))
          `((,+ +)
            (,- -)
            (,* *)
            (,// /)))
      (format
        str a (hashtable-ref op-table op1 #f)
        b (hashtable-ref op-table op2 #f)
        c (hashtable-ref op-table op3 #f) d))
    (cond
      ((= (op3 (op2 (op1 a b) c) d) 10)
       (infix "((~a ~a ~a) ~a ~a) ~a ~a"))
      ((= (op2 (op1 a b) (op3 c d)) 10)
       (infix "(~a ~a ~a) ~a (~a ~a ~a)"))
      ((= (op2 (op1 a b) (op3 c d)) 10)
       (infix "(~a ~a (~a ~a ~a)) ~a ~a"))
      ((= (op1 a (op3 (op2 b c) d)) 10)
       (infix "~a ~a ((~a ~a ~a) ~a ~a) "))
      ((= (op1 a (op2 b (op3 c d))) 10)
       (infix "~a ~a (~a ~a (~a ~a ~a))"))
      (else (fail)))))

#|
> (calc10 3 3 3 3)
"(3 * 3) + (3 / 3)"
> (calc10 3 8 8 8)
"(3 + 8) - (8 / 8)"
> (calc10 4 4 4 4) ; *fail*の値になる
\x2E;G38.497c0e53.ed795
|#

バックトラックするため、分岐点でcall/ccでcontinuationを保存し、failが呼ばれた時にその地点から別の値を選び直す。On Lispに載っているコードのバグだ(と思う)けど、(eq? (calc10 4 4 4 4) *fail*)が*fail*の値になってしまう。failがトップレベルまで大域脱出してしまうからだと思う。
関連：

参考：