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

SICP scheme

脳が相当に疲弊。ひるね中にリストを数え上げる夢を見てしまう位です。週のアタマから頭がパンパンで何も考えられない状態。週末は休まないと駄目だなぁ。
ちなみに単純な数え上げはなんとかなったようですが、guile では stack overflow だそうです。gauche って凄いな。で、でっち上げたナニですが

(flatmap 
 (lambda (i) 
   (map (lambda (j) (append (list j) i)) '(1 2 3 4 5)))
 (flatmap 
  (lambda (i) 
    (map (lambda (j) (append (list j) i)) '(1 2 3 4 5)))
  (flatmap 
   (lambda (i) 
     (map (lambda (j) (append (list j) i)) '(1 2 3 4 5)))
   (flatmap (lambda (i) (map (lambda (j) (list i j)) '(1 2 3 4 5)))
	    '(1 2 3 4 5)))))

とか

(define (test-enum l)
 (let f ((l (cddr l)) (rslt (flatmap 
			     (lambda (i) (map (lambda (j) (list i j))
					      (car l)))
			     (cadr l))))
   (cond ((null? l) rslt)
         (else
          (f (cdr l) (flatmap 
		      (lambda (i) (map (lambda (j) (append (list j) i))
				       (car l)))
		      rslt))))))

みたいな感じ。下の方は繰返しにすれば良いのか、とゆー事ででっち上げたんですが、accumulate が再帰になっているので駄目。繰返しな accumulate を作れば良いのでしょうが、そんなリキは (以下略
# てか、可能かどうかも微妙
とりあえず数え上げはできてる模様なのでこれをフィルタしてやれば良いはず。それは良いとして、面倒だけど手動でヤる事に何かの意味があると見て真面目にやってみる。

問題 4.38

てコトで地味に取り組んでみます。

(require (not (= (abs (- smith fletcher)) 1)))

な制限が無くなると以下のパターンがダウト認定でなくなる。

  • fletcher が 2F、cooper が 4F
  • fletcher が 2F、cooper が 5F
  • fletcher が 3F、cooper が 5F
  • cooper が 2F、fletcher が 4F

ちなみに制限が無くならない場合、

  • 一番上は 5F に smith を置かざるを得なくて (> miller cooper) な条件が満たせない
  • 二番目は (> miller cooper) な条件が満たせない (これは制限が無くなってもダウト認定)
  • 三番目も (> miller cooper) な条件が満たせない
  • 四番目はパス (例示されてる解答はこのパターン)

となります。てコトは最後のソレで手当たり次第なソレを試せば良いとゆー事ッスか。以下に手動でヒリ出したリストを。

(1 2 4 3 5)
(1 2 4 5 3)
(3 2 4 1 5)
(3 2 4 5 1)
(5 2 4 1 3)
(5 2 4 3 1)

ええと、miller は cooper より上に居なきゃいけないから、3 番目と 5 番目はダウト。あと baker 5 階はダウトだから 6 番目もダウト。なので

((baker 1) (cooper 2) (fletcher 4) (miller 3) (smith 5))
((baker 1) (cooper 2) (fletcher 4) (miller 5) (smith 3))
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))

が解なのかなぁ。別途 4.41 のナニで確認予定。