elisp-maze, python-maze

Table of Contents

クロスワードパズル

早速やってみた。 

クロスワードパズルを作成してください。
題材は、歴史上の有名な日本人とします。
縦の列で9名。横でも9名を収納してください。
列は、A,B ... 。行は、1,2 ... とします。
ヒントは、縦の始点2,A 医学者 のようにして下さい。
文字が入る所は、'_' の様な伏せ字。該当しない所は、
'#' にしてください。

以下は、歴史上の有名な日本人に関するクロスワードパズルです。縦の列で9人、横でも9人を収納しています。各セルには、ヒントとして縦の始点、列、およびその人物の説明が含まれています。 

  1 2 3 4 5 6 7 8 9
A 医学者         #
B #   #   #   #   #
C #   #   #   #   #
D #   #   #   #   #
E #   #   #   #   #
F #   #   #   #   #
G #   #   #   #   #
H #   #   #   #   #
I #   #   #   #   #

1. 縦の始点2, A: 医学者
3. 縦の始点4, B: 戦国武将
5. 縦の始点6, D: 小説家
7. 縦の始点8, E: 政治家
9. 横の始点1, A: 日本画家
2. 横の始点3, C: 皇后
4. 横の始点5, D: 科学者
6. 横の始点7, F: 陸軍軍人
8. 横の始点9, G: 映画監督

このクロスワードパズルをお楽しみいただければ幸いです。答えは以下の通りです： 

1. 医学者: 中村恵
2. 皇后: 恵美押し
3. 戦国武将: 織田信長
4. 科学者: 高橋是清
5. 小説家: 村上春樹
6. 陸軍軍人: 本庄繁
7. 映画監督: 黒澤明
8. 政治家: 鳩山由紀夫
9. 日本画家: 与謝野晶子

すっきりしないな。人物像が、そもそも間違っているし。

クロスワードパズル 先人がおられた。皆、考える事は一緒だね。 この方のChatGPTとのやりとりが面白いなあ。

debug maze

前回のバックトレースを簡単に再現できる様に、簡単なコードを作成。 そもそも、こんな事に手を出したのは、迷路の作成と探索結果の表示を、途中 にファイルを経由する事なく実施したかったから。それで、地雷を踏んだ訳。 あちこちに、地雷が埋設してあるな。まあ、そのおかげで、こうして記事に出 来るんだけど。

まずはデフォ で、let* を使って、変数を関数内に閉じ込めていたけど、後で検証が容易 な様に、グローバルにしてみた。 

(defvar maze nil)
(defvar res nil)
(defvar rmaze nil)

(defun testme ()
  (setq maze (new-maze 2 3))
  (dig-maze maze 1 1)
  (setq res (solve-maze maze)) )

これをrepl上で、ロードして、(testme)を実行すると 

mod(nil 3)
(* (mod r (progn (or (progn (and (memq (type-of maze) cl-struct-maze-tags) t)) (signal 'wrong-type-argument (list 'maze maz$
(+ (* (mod r (progn (or (progn (and (memq ... cl-struct-maze-tags) t)) (signal 'wrong-type-argument (list 'maze maze))) (ar$
(aref (progn (or (progn (and (memq (type-of maze) cl-struct-maze-tags) t)) (signal 'wrong-type-argument (list 'maze maze)))$
(let ((cell (aref (progn (or (progn (and ... t)) (signal 'wrong-type-argument (list ... maze))) (aref maze 3)) (+ (* (mod r$
maze-set(#s(maze :rows 3 :cols 4 :data [(visited wall) (visited ceiling) (visited ceiling) (visited wall ceiling) (visited $
(while (not (equal pt exit)) (maze-set maze (car pt) (cdr pt) 'visited) (let ((exits (drop-visited maze (find-exits maze (c$
(let (solution (exit (cons (- (progn (or (progn ...) (signal ... ...)) (aref maze 1)) 2) (- (progn (or (progn ...) (signal $
solve-maze(#s(maze :rows 3 :cols 4 :data [(visited wall) (visited ceiling) (visited ceiling) (visited wall ceiling) (visite$
(setq res (solve-maze maze))
testme()

このエラーの内容横に長い為、途中で切れてしまっている。よって、バッファー の内容をファイルに落として、最初のS式を整形してみた。

簡単にファイルに落とすって書いたけど、実際は少し面倒。back-traceのバッ ファーに移動して、C-x C-w btlog する。別端末で、cp btlog BTLOG する。 だって、emacs上ではbtlogがロックされてるみたいで、編集出来ないからね。 それに、emacsを終了すると、btlogが消滅してしまうんだ。だから、shellを 使ってバックアップしたのさ。多分、ちゃんとした解決方法が有るだろうけど、 クイック・ハックって事で許して下さい。 

(*
 (mod r
      (progn (or
              (progn (and (memq (type-of maze) cl-struct-maze-tags) t))
              (signal 'wrong-type-argument (list 'maze maze)))
             (aref maze 1)))
 (progn (or
         (progn (and (memq (type-of maze) cl-struct-maze-tags) t))
         (signal 'wrong-type-argument (list 'maze maze)))
        (aref maze 2)))

展開したコードと突き合わせてみると、r に相当する部分がnilになってる。 次のprognの部分が、構造体からのデータを引き出してくる部分だろう。

macro and defstruct

emacs macro で検索をかけると、キーボードマクロばかりヒットする。世の中 なんて、そんな物なのか。打鍵の省エネに絶大な効果有り。楽して儲けたいと 言う資本主義が骨の髄まで染み込んでいるな。オイラーが望むのは、そんなん じゃなくて、ビューティフル・コードに絶大な威力を発揮する方よ。

12. マクロ 

ELISP> (defmacro maze-pt (w r c)
  `(+ (* (mod ,r (maze-rows ,w)) (maze-cols ,w))
      (mod ,c (maze-cols ,w))))
ELISP> (macroexpand '(maze-pt w r c))
(+
 (*
  (mod r
       (maze-rows w))
  (maze-cols w))
 (mod c
      (maze-cols w)))

ちゃんとプリティプリントしてくれてる。 

ELISP> (defmacro maze-ref (w r c)
  `(aref (maze-data ,w) (maze-pt ,w ,r ,c)))
maze-ref
ELISP> (macroexpand '(maze-ref w r c))
(aref
 (maze-data w)
 (maze-pt w r c))

徹底的に展開したいなら、macroexpand-all とかを使うんだな。 

ELISP> (aref "abcdef" 2)
99 (#o143, #x63, ?c)

arefの使い方ね。引数の配置が、schemeとかとは、異なるなあ。混乱の元にな りそうです。

ついでに、elispに首をつっこんできた、 cl-libもちょいち見ておく。さしあ たって、 11 Structures このあたりかな。

ちょっと心配なので、ANSI Common Lispなんて言うポール・グレアム著な本を 参照。2002年の購入ってメモが残っていた。あの頃はCLに熱をあげてたんか。

構造体の説明を読むと、defstractすると、暗黙のうちに、便利な関数が定義 されるそうだ。突然に関数が湧いてきて、右往左往しないように。 

(cl-defstruct maze rows cols data)

なら、make-maze,maze-p,copy-maze,maze-rows,maze-cols,maze-dataが出現す るようだ。そのままelispに通用するかは、知らないけど。

debug next

余りを求めるmodの引数になんでnilが紛れ込む？ バックトレースのログを遡っ てみると。 

maze-set(#s(maze :rows 3 :cols 4 :data [(visited wall) .. (visited wall ceiling)]) nil nil visited)

(while (not (equal pt exit)) (maze-set maze (car pt) (cdr pt) 'visited) ...

maze-set の第一、第二引数が、nil になってる。これでmodを計算しようとし て、落ちてしまっているんだな。 

(defun testr ()
  (setq rmaze (read-maze "LOG"))
  (setq res (solve-maze rmaze)) )

今度は、こんなコードを作成。LOGは、上で実行した時に出来たmazeを print-maze したもの。 

ELISP> res
((1 . 2)
 (0 . 2)
 (0 . 1)
 (1 . 1)
 (1 . 0)
 (0 . 0))

ELISP> (print-maze rmaze res)
+   +---+---+
| * | *   * |
+   +   +   +
| *   * | * |
+---+---+   +
ELISP> rmaze
#s(maze :rows 3 :cols 4 :data
0,0*         [(visited wall)
0,1*         (visited wall ceiling)
0,2*         (visited ceiling)
0,3          (visited wall ceiling)
1,0*          (visited wall)
1,1*         (visited)
1,2*         (wall)
1,3          (visited wall ceiling)
2,0          (visited wall ceiling)
2,1          (visited wall ceiling)
2,2          (visited wall)
2,3          (visited wall ceiling)])

勿論、mazeとrmazeは同一だった。0,0* とかはメモ。

using edebug

ついでなので、ソースレベルのdebuggerに手を出してみる。

前準備として、 関数定義の名前の所で C-u C-M-x して、目当ての関数でedebugが起動出来る様に する。解除は、C-M-x 。 

SPC   ステップ実行
n     S式を評価して停止(これが便利)
g     次のブレークポイントまで実行
c     ブレークポイントを表示しながら最後まで実行(C-g で止めるとその位置から再開できる)
t     S式を1秒おきに、トレースする
h     カーソル位置まで実行
i     直後の関数に入る
b     ブレークポイントを張る
u     ブレークポイントを削除
q     edebug を抜ける
e     式を評価する(実行中の値が使える)
C-h v 変数の値を表示する(実行中の値が見れる)
?     ヘルプ

debuggerに突入したら、n していく。これで、S式を評価して結果を mini-bufferに表示して停止する。<SPC>でのstep実行よりスピィーディーに事 を進められるぞ。何故なら、関数に出会っても潜っていかないから。

t を使うとトレースしてくれる。nして1秒停止。またnして1秒停止を自動実行 してくれるイメージだ。中止したい場合は、任意のコマンドを入力すれば良い。

まるで、dr-schemeだかにあった、step実行を彷彿させるな。最初、その機能 に遭遇した時は、感動したものだけど、edebugのこみ機能は、当たり前のよう に思っちゃう。贅沢病に罹患しているのだろうか？ 

    (while (not (equal pt exit))
=>    (maze-set maze (car pt) (cdr pt) 'visited)

こんな風に、矢印とカーソル位置で、停止してる所が表示される。もう普通の gdbを使っているのと大差ない。

trace

lispと言えば、もう一つ便利な機能がある。そう、トレースね。関数に突入す る時、その引数を表示。関数を脱出する時、その結果を表示。これはgdbでや ろうとしても、なかなか面倒だ。 

ELISP> (setq edebug-trace t)
t
;; C-u C-M-x maze-set on source-buffer
ELISP> (solve-maze maze)

(defun maze-set (maze r c v)
=>(let ((cell (maze-ref maze r c)))
    (when (not (member v cell))

cして、どんどん継続 

{ maze-set args: (#s(maze 3 4 [(visited wall) .. (visited wall ceiling)]) 0 0 visited)
} maze-set result: nil
{ maze-set args: (#s(maze 3 4 [(visited wall) .. (visited wall ceiling)]) nil nil visited)

trace-bufferの結果。冒頭に付加されている { は、関数への突入時、} は、 脱出時の状況を表現している。

一方、ログファイルをreadして、それを使うと 

{ maze-set args: (#s(maze 3 4 [(wall) (ceiling) .. (visited wall ceiling)]) 0 0 visited)
} maze-set result: (visited wall)
{ maze-set args: (#s(maze 3 4 [(visited wall) (ceiling) .. (visited wall ceiling)]) 0 1 visited)
} maze-set result: (visited ceiling)
{ maze-set args: (#s(maze 3 4 [(visited wall) (visited ceiling) .. (visited wall ceiling)]) 0 2 visited)
} maze-set result: (visited ceiling)
{ maze-set args: (#s(maze 3 4 [(visited wall) .. (visited wall ceiling)]) 0 1 visited)
} maze-set result: nil
{ maze-set args: (#s(maze 3 4 [(visited wall) .. (visited wall ceiling)]) 1 1 visited)
} maze-set result: (visited wall)

この様になった。すなわち、最初の実行では、間違ったデータmazeを与えてた。 後の実行では、rmazeを与えていた。 

ELISP> maze
#s(maze :rows 3 :cols 4 :data
         [(visited wall)
          (visited ceiling)
          (visited ceiling)
          (visited wall ceiling)
          (visited wall)
          (visited wall ceiling)
          (visited)
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall)
          (visited wall ceiling)])
ELISP> rmaze
#s(maze :rows 3 :cols 4 :data
         [(wall)
          (ceiling)
          (ceiling)
          (visited wall ceiling)
          (wall)
          (wall ceiling)
          nil
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall)
          (visited wall ceiling)])

mazeの方は、これを作成する為に全部のcellを訪問してる(visited)。一方、 rmazeは、これを元に再創成したものだけど、不要なvisitedは削除されている。 この違いが、スキャンに影響を与えてるって事だ。

なお、一度迷路解決してしまうと、visitedが付与されてしまう。 

ELISP> (testr)
((1 . 2)
 (0 . 2)
 (0 . 1)
 (0 . 0))

ELISP> rmaze
#s(maze :rows 3 :cols 4 :data
         [(visited wall)
          (visited ceiling)
          (visited ceiling)
          (visited wall ceiling)
          (wall)
          (wall ceiling)
          nil
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall ceiling)
          (visited wall)
          (visited wall ceiling)])

trace-function-xx

上のedebugに内包されてるtraceを使うより、もっとカジュアルなトレース方 法が有る。

M-x trace-function-xx して、どちらかを指定。backgroundを選ぶと、裏に bufferが作成されて、結果はそちらに行く。 

trace-function (trace-function-foreground)
trace-function-background
trace-function-foreground

maze-setをトレースした、一例。こちらの方が判り易いな。 

======================================================================
1 -> (maze-set #s(maze 3 4 [(wall ceiling) .. (wall ceiling)]) 0 3 visited)
1 <- maze-set: (visited wall ceiling)
======================================================================
1 -> (maze-set #s(maze 3 4 [(wall ceiling) .. (wall ceiling)]) 1 3 visited)
1 <- maze-set: (visited wall ceiling)
======================================================================
 :

トレースの解除をするには、どちらかを選択する。 

untrace-all
untrace-function

haskell vs emacs

上のnilを知らずに別関数に渡してしまって、とんでもない所で、それが表面 化するってのは、日常ありふれている。そもそもの問題は、 

ELISP> (car '())
nil
ELISP> (cdr '())
nil

こんな風に、空リストに対しての、car,cdrが、その場でエラーにならない事。 

[sakae@deb ~]$ sbcl
This is SBCL 2.1.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

 * (car '())
NIL

念のため、lisp-2族の雄である奴でも確認してみた。 

gosh$ (car '())
 *** ERROR: pair required, but got ()
Stack Trace:
_______________________________________
  0  (car '())
        at "(input string port)":1
  1  (eval expr env)
        at "/usr/local/share/gauche-0.98/0.9.12/lib/gauche/interactive.scm":336

たまには、gaucheって事で。ちゃんとエラーになった。 

[sakae@deb ~]$ scheme
Chez Scheme Version 9.5.6
Copyright 1984-2021 Cisco Systems, Inc.

> (car '())

Exception in car: () is not a pair
Type (debug) to enter the debugger.

もう一発。別なschemeでは？ やはりエラー検出。ひょっとしてRnRSで規定さ れてるの？ 

ghci> head []
 *** Exception: Prelude.head: empty list
ghci> tail []
 *** Exception: Prelude.tail: empty list

car,cdrなんて、時代がかった関数名とすっかり縁を切ったhaskellでも確認。

どうやら、lisp-2族は、昔のままの仕様を引きずった、恐竜みたいなもんだな。 いや、恐竜の生き残りの鳥さんも、美味しく頂けたり、眼をうるおわせてくれ る存在だったりするから、無碍に毛嫌いするなよ。

でも car,cdrは、こんな風に組み合わせる時に、便利。 

gosh$ (caddr '(1 2 3 4 5 6 7))
3

haskell風にやると、こんな事になる。感じが出ないと嘆くオイラーは、恐竜 時代の生き残り？ 

ghci> (_:_:y:_) = "1234567"
ghci> y
'3'

無限cxr 好きな人は、こんな事をやっている。語源の由来は、こちら CARとCDR

profile, benchmark

後はプロファイルかな、とか思っていたら、ピッタリな案内を見付けた。

Emacsのプロファイリング機能の紹介

素晴しい、後で試してみよう。

by python

pythonの例が分かり易かったので、 make_maze(w = 5, h = 2) を pdb して、 主要な配列をdumpしてみた。 

(Pdb) pp vis
[[0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1]]
(Pdb) pp ver
[['|  ', '|  ', '|  ', '|  ', '|  ', '|'],
 ['|  ', '|  ', '|  ', '|  ', '|  ', '|'],
 []]
(Pdb) pp hor
[['+--', '+--', '+--', '+--', '+--', '+'],
 ['+--', '+--', '+--', '+--', '+--', '+'],
 ['+--', '+--', '+--', '+--', '+--', '+']]
(Pdb) n ### ここまでが初期化。次からは、実行後の配列
> /tmp/pmaze.py(19)make_maze()
(Pdb) pp vis
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
(Pdb) pp ver
[['|  ', '   ', '   ', '|  ', '   ', '|'],
 ['|  ', '   ', '|  ', '   ', '   ', '|'],
 []]
(Pdb) pp hor
[['+--', '+--', '+--', '+--', '+--', '+'],
 ['+  ', '+--', '+  ', '+  ', '+--', '+'],
 ['+--', '+--', '+--', '+--', '+--', '+']]
(Pdb) c ### 最終的な表示結果
+--+--+--+--+--+
|        |     |
+  +--+  +  +--+
|     |        |
+--+--+--+--+--+

素直に配列を用意してる。visは、訪問したかの記憶。verは、隣合う壁(左の 壁と考えるのが妥当かな)が貫通 しているかの表現。horは、上下の壁と言うか天井に穴が開いているかの表現。

emacs tips menu-bar access

emacsをputtyから使っていても、たまにメニューに触れたい事がある。 

M-x menu-bar-mode  でメニューを出し
ESC `              本当のESCキーに続いて、バッククォートで、選択しる。
M-x menu-bar-open  で、メニューがドロップ・ダウンする。後は矢印キーで
                   誘導。サブメニューは、そこでReturnキーを叩く

emacs info

emacs info に掲載の資料をWeb上でも。

An Introduction to Programming in Emacs Lisp

GNU Emacs Lisp Reference Manual

The GNU Emacs FAQ

Emacs Lisp Cookbook

GNU Emacs Manual (jp)

EmacsをVSCode風にする 番外編だけど、面白い!

This year's Index

Home