屑俺日記

☆ 川渡り問題

本で少し触れられていた。
まだ実は解けてないが、その途中くらいまで。

初期状態の定義。

(setq all '((人 . 北) (狼 . 北)
            (羊 . 北) (菜 . 北)))
((人 . 北) (狼 . 北) (羊 . 北) (菜 . 北))

どれかを渡した場合。

(defun flipflop (alists)
  (cond
   ((eq (cdr alists) '北)
    (cons (car alists) '南))
   (t
    (cons (car alists) '北))))
 
(defun alistsflipcons (alists num)
  (cond
   ((> num 3) 'too_large)
   ((< num 0) 'too_small)
   ((null alists) 'no_alists)
   ((zerop num)
    (cons
     (flipflop (car alists)) (cdr alists)))
   (t
    (cons
     (car alists)
     (alistsflipcons (cdr alists) (- num 1))))))
 
(setq all (alistsflipcons all 2))
((人 . 北) (狼 . 北) (羊 . 南) (菜 . 北))

まだ渡りきってない一例。
この場合は、大丈夫なはずである。狼は菜を食べないし、 同じ側に人が(戻って)いる。

もう少しましな関数が浮かんだ気がしたが、 いまひとつ形にならないうちに何かが尽きた。

☆ 川渡り続く

どれかが、どちらにいるかを返す関数を書いてみた。

(setq all (alistsflipcons all 2))
((人 . 北) (狼 . 北) (羊 . 南) (菜 . 北))
 
(defun ano_cdr (alists item)
  (cond
   ((null alists) nil)
   ((eq	item (car (car alists))) 
    (cdr (car alists)))
   (t
    (ano_cdr (cdr alists) item))))
 
(ano_cdr all '羊)
南

もう少し。

☆ 川渡り、もう少し

で、今度は、 人がいない状況(人と羊が別の位置)で、 羊と狼、もしくは 羊と菜の 組み合わせかどうかチェック。

(defun errcheck (alists)
  (cond
   ((and
     (not
      (eq (ano_cdr alists '人)
          (ano_cdr alists '羊)))
     (or (eq (ano_cdr alists '羊)
             (ano_cdr alists '狼))
         (eq (ano_cdr alists '羊)
             (ano_cdr alists '菜))))
    'nil)
   (t
    t)))
 
(errcheck '((人 . 南) (狼 . 北) (羊 . 南) (菜 . 北)))
t
(errcheck '((人 . 北) (狼 . 南) (羊 . 南) (菜 . 北)))
nil

渡り方は、もう少し考えてからにするか。