2011年3月29日火曜日

Emacs Lisp で Lake Counting

深さ優先探索アルゴリズム(depth-first search, DFS)の基本的な例題として、"Lake Counting"(湖あるいは水たまり数え上げ問題?)と呼ばれる問題がある。問題の内容は他の文献に書いてあるので、ここでは Emacs Lisp で解いた例を記録しておく。

コード

vector型(いわゆる配列)は使わない方針。つまり、配列にデータを読み込んで添字でアクセスするのではなく、Emacsのバッファに記述されている文字列をそのまま処理する。したがって、"point"関連の組み込み関数を多用している。また、8近傍の要素を表す一時的なデータも、配列ではなくリストにしている。

(defun lake-count (b e)
  "入力となるリージョンを選択した状態で M-x lake-count を実行すると、答えをミニバッファに出力する。"
  (interactive "r")
  (save-excursion
    (let ((cnt 0)
          (first-line (line-number-at-pos b)) ;リージョンの先頭行番号を記録しておく
          (last-line (line-number-at-pos e))) ;リージョンの最終行番号を 〃
      (loop for p from b to e do
            (goto-char p)
            (sit-for 0.1) ;カーソルの動きを観察するため一瞬停止
            (when (eq ?W (char-after p))
              (dfs)
              (incf cnt) ))
      (message "%d" cnt))))             ;結果出力

(defun dfs ()
  "補助関数。現在のポイントを文字.に置換する。8近傍に文字Wがあれば再帰的に適用する。"
  (let* ((cline (line-number-at-pos))
         (ccol (current-column))
         (poslist `((,(1- cline) ,(1- ccol)) ;8近傍を表す(行,列)のリスト
                    (,(1- cline) ,ccol)
                    (,(1- cline) ,(1+ ccol))
                    (,cline ,(1- ccol))
                    (,cline ,(1+ ccol))
                    (,(1+ cline) ,(1- ccol))
                    (,(1+ cline) ,ccol)
                    (,(1+ cline) ,(1+ ccol)) )))
    (delete-char 1) ; この2行で W を . に置換
    (insert ?.)     ; 〃
    (setf poslist
          (remove-if  ;リージョンの外に出る要素をリストから消す
           (lambda (pos)
             (or (< (first pos) first-line);上にはみ出す場合
                 (> (first pos) last-line) ;下にはみ出す場合
                 (< (second pos) 0)))      ;左にはみ出す場合
           poslist))
    (mapcar (lambda (pos) ;8近傍の各要素に対してラムダ式を適用
              (goto-line(first pos))
              (move-to-column (second pos)) ;近傍にポイントを移動
              (sit-for 0.1)  ;カーソルの動きを観察するため一瞬停止
              (if (eq ?W (char-after))  ;Wなら再帰的に呼び出す
                  (dfs)))
            poslist)))

使用している組み込み関数/マクロ

詳細はEmacs上でdescribe-functionを行えば出てくるので、列挙だけしておく。

  • let
  • let*
  • loop
  • when
  • incf
  • eq
  • sit-for
  • insert
  • delete-char
  • mapcar
  • remove-if
  • char-after
  • goto-line
  • move-to-column
  • mapcar
  • save-excursion
  • goto-char
  • first
  • second

よいか悪いかは別として、C言語などで書く場合と比べると、たくさんの語彙を駆使したプログラムになってしまう(バッククォートとか、カンマまで使っている…)。

実行&結果

  1. *scratch*バッファなどで、"W"と"."を使った水たまりのASCIIアートを描く。
  2. 先頭の行をC-SPCでマークして、カーソルを最後の行まで移動。全体を選択状態にする。
  3. M-x lake-count を実行する。
  4. 最終的にすべての"W"が"."に置換され、ミニバッファに水たまりの数が表示される。
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
上記の入力の場合、正解は 3。動画も作ってみたが、全画面表示にしないと見えない。
video

0 件のコメント:

コメントを投稿