昨日のつづき id:smeghead:20070613:maze

今の自分にとっては、非常に難しい問題でした。小さいFunctionを繋げていくように作っていったんですが、意外と終盤の作業が非常にスピーディーに運びました。On Lispに書かれているボトムアップで進めるという意味が解った気がします。

例えばjavaで書こうとすると、まず何をクラスにするかを考えます。perlでも同じ感じです。

• javaとかの場合
  • クラス抽出
    • 問題になりそうな部分を解決できるにはどうするか
    • 全体がシンプルに収まるようするにはどうするか
  • クラス実装
    • 重複が無いように
    • 適切なクラスに適切な処理が書かれるように

lispの場合は、違う視点で見るようになっている気がしました。

• lispの場合
  • データ構造
    • 入力をどう表すか
    • 出力をどう表すか
  • 実装
    • 入力データをどのように変換して出力すればよいか

でも、これは、lispに対して無知だからということと、取り組んでいる問題が他の言語で取り組んでいる問題より小さい(自分にとっての難易度ではなく)からというだけかもしれないです。もうちょっと自由に書けるようになったら、もっと沢山のことを考えるようになるでしょうけど。

迷路の問題はなんとか解けました。

;問題 a. 迷路を表すStructure
(defstruct maze size data)
;問題 b. ファイルからmazeを作るFunction
(defun load-maze (file)
(with-open-file (stream file :direction :input)
(let (num data str)
(setq num (read stream))
(loop
(if (eq (setq str (read stream nil 'eof)) 'eof)
(return (make-maze :size num
:data (make-array (list num num)
:initial-contents (reverse data))))
(push str data))))))
;問題 c. 迷路を表示するFunction
(defun print-maze (maze)
(let ((c 0))
(loop
(let (x y (conv #'(lambda (n) (case n (0 "　") (1 "■") (2 "＊")))))
(if (= c (* (maze-size maze) (maze-size maze))) (return))
(multiple-value-setq (y x) (truncate c (maze-size maze)))
(if (< x (maze-size maze))
(format t "~a" (funcall conv (aref (maze-data maze) y x))))
(if (= x (1- (maze-size maze)))
(terpri))
(incf c)))
(terpri)))
;位置を表すStructuer
(defstruct point (x 0) (y 0))
;指定したpointから移動可能な方向をリストで取得するFunction
(defun can-move-to (p m)
(let ((data (maze-data m)) directions)
(if (point-is-space (point-x p) (1- (point-y p)) m)
(push (make-point :x (point-x p) :y (1- (point-y p))) directions))
(if (point-is-space (point-x p) (1+ (point-y p)) m)
(push (make-point :x (point-x p) :y (1+ (point-y p))) directions))
(if (point-is-space (1- (point-x p)) (point-y p) m)
(push (make-point :x (1- (point-x p)) :y (point-y p)) directions))
(if (point-is-space (1+ (point-x p)) (point-y p) m)
(push (make-point :x (1+ (point-x p)) :y (point-y p)) directions))
directions))
;指定したx y の場所がスペースかどうかを判定するFunction
(defun point-is-space (x y m)
(and
(> x -1) (< x (maze-size m))
(> y -1) (< y (maze-size m))
(zerop (aref (maze-data m) y x))))
;pointが等しいかどうかを判定するFunction
(defun point= (p1 p2)
(and (= (point-x p1) (point-x p2))
(= (point-y p1) (point-y p2))))
;移動可能なpointを取得するFunction
(defun get-directions (route m)
(let ((directions (can-move-to (car (last route)) m)))
(remove-if
#'(lambda (elm)
(find-if
#'(lambda (e)
(point= e elm))
route))
directions)))
;ゴールまでのルートを全て取得するFunction
(defun get-routes (route m goal reached)
(cond ((point= (car (last route)) goal)
(progn
(cons route reached))) ;ゴールまで到達したrouteを返す
(t
(let ((directions (get-directions route m)) (i -1))
(loop
(incf i)
(if (null (nth i directions))
(return reached)) ;選択肢が無くなったので上に戻る。
(setf reached (get-routes (append route (list (nth i directions))) m goal reached)))))))
;最短のルートを表示するFunction
(defun output-answer (m reached)
(let ((data (maze-data m))
(answer (car (sort reached #'(lambda (a b) (< (length a) (length b)))))))
(let ((i 0))
(loop
(if (= i (length answer))
(return)
(let ((x (point-x (nth i answer)))
(y (point-y (nth i answer))))
(setf (aref data y x) 2)))
(incf i)))
(print-maze m)))
;問題 d. ファイル名を引数にとり、迷路を解いて表示する。 
(defun solv-maze (file)
(let ((m (load-maze file)))
(output-answer m
(get-routes `(,(make-point :x 7 :y 0)) m (make-point :x 1 :y 8) nil))
(format t "Solved!~%")))
(solv-maze "m9.txt")

実行結果

■■■■■■■＊■
■　　＊＊＊＊＊■
■　■＊■■■　■
■　■＊＊＊■　■
■　■■■＊■　■
■　■＊＊＊■　■
■■■＊■■■　■
■＊＊＊■　　　■
■＊■■■■■■■
Solved!

昨日からスパムTBが激しい。自業自得かorz.

明かに関係ないトラックバックは消させていただきますm(_ _)m