SICP 読み (206) 4.3.2 非決定性プログラムの例

SICP scheme

微妙な問題が続きます。テキストに鉛筆書きで「むが」とか「ぐげ」とか殴り書きしてあります。何故にコンピュータがあるのに手動でパズルを解かせるのだ、と。

問題 4.39

ええと、例示されている手続きは

(1 1 1 1 1)
(1 1 1 1 2)
(1 1 1 1 3)
(1 1 1 1 4)
(1 1 1 1 5)
(1 1 1 2 1)
(1 1 1 2 2)
;; 以下略

という方法で順に値が割り当てられて制限というフィルタにかけられる。次の問題なナニなんでしょうが、全ての可能性を列挙して同じレベルでフィルタしてる、という事は順番を入れかえても解にも処理時間にも影響は無いと考えます。
ただ、人間様が考える時には

    ;; 絶対位置の判定
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    ;; 相対位置の判定
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- smith fletcher)) 1)))

なソレはまず相対位置の判定からだろ、と。直前エントリでも無意識のうちに相対位置の判定からやってました。でもこれは人間様の横着であって、コンピュータ君にとってはあまり関係ないのではないか、と思います。
この問題はこの位でスルーさせて下さひ。(何

問題 4.40

ざくっと計算してみました。あってるかどうかは不明です。次の問題で答えは出るはず。以下にざっくり計算を。

まず、要素が二つのケイスだと以下。

(1 1) (1 2)
(2 1) (2 2)

割り当ての組は全部で 4 つですが、制限でフィルタされて出てくるのは 2 つ。次は要素が三つのケイス

(1 1 1) (1 1 2) (1 1 3)
(1 2 1) (1 2 2) (1 2 3) ;; 1
(1 3 1) (1 3 2) (1 3 3) ;; 1
(2 1 1) (2 1 2) (2 1 3) ;; 1
(2 2 1) (2 2 2) (2 2 3)
(2 3 1) (2 3 2) (2 3 3) ;; 1
(3 1 1) (3 1 2) (3 1 3) ;; 1
(3 2 1) (3 2 2) (3 2 3) ;; 1
(3 3 1) (3 3 2) (3 3 3)

割り当ての組は (* 3 3 3) で 27 通り。_階の割り当てが相異る_のは 6 通り。これを踏まえて例示されているソレをチェックしてみると

  • 1 で開始
    • 2 で続く (3 4 5) (3 5 4) (4 3 5) (4 5 3) (5 3 4) (5 4 3)
    • 3 で続く → 6 通り

(以下略

てコトは OK なソレは (* 5 (* 6 4)) ;; -> 120
# 微妙。重複はないんだろうか。大丈夫か。
filter しないと何通りなんだろうか。
(* 5 (* 5 (* 5 25))) ;;?? -> 3125??

うーん。stack overflow も仕方無いって感じもします。let の入れ子をヒントに無理矢理でっち上げてみたのが以下です。

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5)))
    (require (not (= baker 5)))
    (let ((cooper (amb 1 2 3 4 5)))
      (require (not (= cooper 1)))
      (let ((fletcher (amb 1 2 3 4 5)))
	(require (not (= fletcher 5)))
	(require (not (= fletcher 1)))
	(require (not (= (abs (- fletcher cooper)) 1)))
	(let ((miller (amb 1 2 3 4 5)))
	  (require (> miller cooper))
	  (let ((smith (amb 1 2 3 4 5)))
	    (require (not (= (abs (- smith fletcher)) 1)))
	    (list (list 'baker baker)
		  (list 'cooper cooper)
		  (list 'fletcher fletcher)
		  (list 'miller miller)
		  (list 'smith smith))))))))

これベースで 4.41 の解を検討すれば guile で動く実装がヒリ出せるかも。って答えとして正しいかどうかは微妙な上にこれをどうやって scheme な手続きとして書くのか、も (以下略

追記

次の日、ぼさっとエントリを見ててボケをぶちカマしている事に気づく。distinct? がヌけている。正しくは以下なつもりでした。

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5)))
    (require (not (= baker 5)))
    (let ((cooper (amb 1 2 3 4 5)))
      (require
       (distinct? (list baker cooper)))
      (require (not (= cooper 1)))
      (let ((fletcher (amb 1 2 3 4 5)))
	(require
	 (distinct? (list baker cooper fletcher)))
	(require (not (= fletcher 5)))
	(require (not (= fletcher 1)))
	(require (not (= (abs (- fletcher cooper)) 1)))
	(let ((miller (amb 1 2 3 4 5)))
	  (require
	   (distinct? (list baker cooper fletcher miller)))
	  (require (> miller cooper))
	  (let ((smith (amb 1 2 3 4 5)))
	    (require
	     (distinct? (list baker cooper fletcher miller smith)))
	    (require (not (= (abs (- smith fletcher)) 1)))
	    (list (list 'baker baker)
		  (list 'cooper cooper)
		  (list 'fletcher fletcher)
		  (list 'miller miller)
		  (list 'smith smith))))))))

なんか微妙。