プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(22)

読み飛ばしていい愚痴

自分はスキルを身につけて転職したいのですが、
それなのに何故Common Lispとかいう仕事にならなさそうな
言語を勉強しているのか時々悩みがちです。
なぜLispを学んでいるのかというと、以前SICPという本を読んだ時に
数ページ読んだ時点で「Schemeめっちゃ楽しいじゃん!」となり、
調べてみたらSchemeよりCommon Lispの方が色々便利(要出典)な気がして
それで今に至るわけです。

こんな意味不明な感じで勉強しているので全く転職というゴールに
たどり着ける気がせず悩んでしまうのですが、それはそれ。

今日も今日とて「Land of Lisp」を進めます。
昨日はGraphvizを使ってグラフを生成しました。
今回は複雑なノードを使うゲームを作るみたいです。
というわけでまたGraphvizのお世話になります。
そしてもはや恥も外聞もなく写経していきます。

ゲーム内容

途方もなく入り組んだ街で主人公は人を探しています。
1ブロックか2ブロックぐらいに近づければ痕跡が見つかるはずです。
また、この街にはヤバイ奴らがいて、もし出会ったら
酷い目に遭います(ゲーム的には別の場所に移動させられる)。
また、通ったらゲームオーバーになる道もあります。
ゲームオーバーにならずに探し人がいるノードを特定できれば
ゲームクリアです。外したりダメな道を通ればゲームオーバーです。

大体こんなゲームのはずです。ストーリー設定は割愛します。
ストーリーは「こんなヤバいプログラム、教科書に載っていいのか!」と
挿絵で煽られています。
気になる方はぜひ「Land of Lisp」をお買い求めください。
(お世話になっているので宣伝)

エッジの定義

まず昨日作った、グラフを作るためのlispを読み込みます。

CL-USER> (load "graph-util")
;; Loading file /Users/user/Desktop/lisp/graph-util.lisp ...
;; Loaded file /Users/user/Desktop/lisp/graph-util.lisp
T
CL-USER>

読み込めてそうです。
それではダイナミック変数でマップの定義を宣言していきます。

CL-USER> (defparameter *congestion-city-nodes* nil)
*CONGESTION-CITY-NODES*
CL-USER> (defparameter *congestion-city-edges* nil)
*CONGESTION-CITY-EDGES*
CL-USER> (defparameter *visited-nodes* nil)
*VISITED-NODES*
CL-USER> (defparameter *node-num* 30)
*NODE-NUM*
CL-USER> (defparameter *edge-num* 45)
*EDGE-NUM*
CL-USER> (defparameter *worm-num* 3)
*WORM-NUM*
CL-USER> (defparameter *cop-odds* 15)
*COP-ODDS*
CL-USER>

*congestion-city-nodes*にはそこに標的がいるか、
やばいやつがいるか、等々の情報が格納される予定。
*congestion-city-edges*にはそこがゲームオーバーになる
道かどうかの情報が入ります。
*node-num*にはノード数、*edge-num*にはエッジ数、
*worm-num*にはヤバイ奴らがいる場所の数、
*cop-odds*には通っちゃいけない道の数です。
*visited-nodes*は…行ったことある場所が入るんでしょうか。
とりあえず定義は終わりです。

ランダムなエッジの生成

ランダムなエッジのリストを作る関数を書きます。

CL-USER> (defun random-node ()
           (1+ (random *node-num*)))
RANDOM-NODE
CL-USER> (defun edge-pair (a b)
           (unless (eql a b)
             (list (cons a b) (cons b a))))
EDGE-PAIR
CL-USER> (defun make-edge-list ()
           (apply #'append (loop repeat *edge-num*
                                collect (edge-pair (random-node) (random-node)))))
MAKE-EDGE-LIST
CL-USER>

よし、わかる気がします。
random-nodeは、1以上 *random-node*以下の数をランダム生成。
edge-pairは引数に受け取った2つが等しくなければ
その2つをドットリストにします。しかも2パターン作ります。
make-edge-listは、*edge-num*の数だけ繰り返し、
random-nodeで生成した数同士をedge-pairでリストにしています。
appendはいくつかのリストを繋げて一つのリストにするのでした。
applyはネストしたリストの各要素に引数として渡した関数を
適用するものでした。
とはいえ、loopの動作については以前ちらっと推測しただけなので
よくわかっていません。
ちょうど解説があるので見てみます。

loopコマンド

そのうち詳しく扱うのでサラッと紹介してくれるそうです。
使い方の一つは、数値のリストを作ること。

CL-USER> (loop repeat 10
              collect 3)
(3 3 3 3 3 3 3 3 3 3)
CL-USER>

10個の3からなるリストを作ってくれ、て感じですね。
あとは、ある数からある数まで増えるリストです。

CL-USER> (loop for n from 1 to 10
              collect n)
(1 2 3 4 5 6 7 8 9 10)
CL-USER> (loop for n from 0 to 9
              collect (* n n))
(0 1 4 9 16 25 36 49 64 81)
CL-USER>

ふむ、さっきのがC言語で言うwhileみたいなもんで、
こっちがforって感じですね。

で、これを踏まえてさっきの処理を考えると、

(loop repeat *edge-num*
      collect (edge-pair (random-node) (random-node)))

の部分で、一番内側にedge-pairで作られたリストができ、
collectの力によって更に2つのドットリストをまとめたリストができ、
その大量のドットリストをまとめたリストのリストができる感じかな。
それをapplyによってappendでドットリストのリストにすると。
あ〜自分でも何いってんだかわからなくなってきました。

CL-USER> (make-edge-list)
((28 . 13) (13 . 28) (12 . 11) (11 . 12) (25 . 20) (20 . 25) (9 . 2) (2 . 9)
 (5 . 16) (16 . 5) (2 . 19) (19 . 2) (20 . 5) (5 . 20) (1 . 3) (3 . 1)
 (17 . 16) (16 . 17) (8 . 18) (18 . 8) (9 . 27) (27 . 9) (6 . 19) (19 . 6)
 (22 . 29) (29 . 22) (17 . 13) (13 . 17) (27 . 8) (8 . 27) (2 . 1) (1 . 2)
 (12 . 19) (19 . 12) (30 . 27) (27 . 30) (23 . 28) (28 . 23) (15 . 28)
 (28 . 15) (4 . 28) (28 . 4) (24 . 25) (25 . 24) (5 . 12) (12 . 5) (7 . 4)
 (4 . 7) (30 . 8) (8 . 30) (6 . 10) (10 . 6) (7 . 15) (15 . 7) (27 . 11)
 (11 . 27) (15 . 19) (19 . 15) (15 . 30) (30 . 15) (3 . 15) (15 . 3) (9 . 6)
 (6 . 9) (10 . 4) (4 . 10) (20 . 26) (26 . 20) (22 . 6) (6 . 22) (7 . 18)
 (18 . 7) (26 . 2) (2 . 26) (24 . 7) (7 . 24) (28 . 4) (4 . 28) (28 . 8)
 (8 . 28) (18 . 11) (11 . 18) (30 . 7) (7 . 30) (11 . 18) (18 . 11))
CL-USER>

ドットリストのリストたちを集めて一つのドットリストのリストにする!
という感じです。

どこにも繋がっていないノード

先程の関数はランダムなノードの組み合わせのリストを
一瞬で作ってくれる優れものですが、あまりにランダムなので
どこにも繋がっていないノードができてしまいそうです。
そんなことがないように、接続されていないノードを探し
それを他のノードとつなげる関数を作ります。

CL-USER> (defun direct-edges (node edge-list)
           (remove-if-not (lambda (x)
                            (eql (car x) node))
                          edge-list))
DIRECT-EDGES
CL-USER> (defun get-connected (node edge-list)
           (let ((visited nil))
             (labels ((traverse (node)
                        (unless (member node visited)
                          (push node visited)
                          (mapc (lambda (edge)
                                  (traverse (cdr edge)))
                                (direct-edges node edge-list)))))
               (traverse node))
             visited))
GET-CONNECTED
CL-USER>

まだまだですが、一旦整理したいのでここで切ります。
direct-edgesはedge-listから、引数として渡された
nodeをcar部分に含むものだけを返してくる関数ですね。
get-connectedは、まずvisitedにnilを設定。
traverse関数を定義。traverseは、nodeを引数にとり、
もしnodeがvisitedに含まれなければ、nodeをvisitedに追加。
無名関数部分では…deirect-edgeにnodeとedge-listを渡して、
返ってきたリスト、つまりそのノードを起点にしている
エッジのリストの要素に対して更にtraverseを適用していきます。
そして最終的にvisitedの評価が戻り値になるわけですが、
その時visitedには最初に渡したnode、及び
そのノードから辿ることのできた全てのノードが入っているはずです。
ぐぐぐ…結構理解するのに時間がかかりました。続けます。

CL-USER> (defun find-islands (nodes edge-list)
           (let ((island nil))
             (labels ((find-island (node)
                        (let* ((connected (get-connected (car nodes) edge-list))
                              (unconnected (set-difference nodes connected)))
                        (push connected island)
                        (when unconnected
                          (find-island unconnected)))))
               (find-island nodes))
             island))
FIND-ISLANDS
CL-USER> 

またストップです。ちょくちょく理解のために止まってしまいます。
find-islandsは…islandを定義して、find-islandを定義。
find-islandの中ではconnectedとunconnectedを定義しています。
let*は確か、labelsの変数バージョンみたいなもので、
あとで定義する変数の定義にそのスコープ内で定義した変数が使えるのです。
connectedは、nodesのcar部分とedge-listでget-connectedをした結果、
つまり(car nodes)から行ける全ノードのリストですね。
unconnectedは…set-difference?知らないやつですね。

set-differenceは二つのリストを引数とし、最初のリストにあって
2番目のリストに含まれない要素をリストにしてくれるそうです。
つまりここでは、nodesのリストの中からconnectedに含まれない
ノードのリストがunconnectedになるのですね。
そしてconnectedをislandsに加えます。むむむ。
そしてunconnectedがあるのなら、find-islandを呼んで
unconnectedを渡します。最終的にislandsが評価されるわけですが
なにが入ってるのでしょう。

CL-USER> (defparameter *test-nodes* 
           (loop for n from 1 to 30
                collect n))
*TEST-NODES*
CL-USER> *test-nodes*
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
 30)
CL-USER> (defparameter *test-edges* (make-edge-list))
*TEST-EDGES*
CL-USER> *test-edges*
((27 . 12) (12 . 27) (14 . 17) (17 . 14) (28 . 23) (23 . 28) (13 . 3) (3 . 13)
 (28 . 1) (1 . 28) (13 . 27) (27 . 13) (9 . 6) (6 . 9) (28 . 30) (30 . 28)
 (20 . 6) (6 . 20) (3 . 4) (4 . 3) (4 . 23) (23 . 4) (6 . 10) (10 . 6) (3 . 22)
 (22 . 3) (17 . 20) (20 . 17) (18 . 23) (23 . 18) (18 . 28) (28 . 18) (8 . 27)
 (27 . 8) (2 . 25) (25 . 2) (24 . 5) (5 . 24) (4 . 1) (1 . 4) (11 . 26)
 (26 . 11) (21 . 13) (13 . 21) (2 . 4) (4 . 2) (28 . 25) (25 . 28) (3 . 13)
 (13 . 3) (14 . 24) (24 . 14) (6 . 11) (11 . 6) (21 . 20) (20 . 21) (30 . 13)
 (13 . 30) (27 . 1) (1 . 27) (24 . 21) (21 . 24) (19 . 15) (15 . 19) (28 . 24)
 (24 . 28) (4 . 6) (6 . 4) (1 . 6) (6 . 1) (21 . 26) (26 . 21) (19 . 8)
 (8 . 19) (25 . 10) (10 . 25) (26 . 25) (25 . 26) (28 . 20) (20 . 28) (28 . 17)
 (17 . 28) (22 . 5) (5 . 22) (12 . 17) (17 . 12))
CL-USER> (find-islands '(1) *test-edges*)
((18 30 15 19 8 11 26 2 25 10 9 6 20 21 22 5 24 14 17 12 27 13 3 4 23 28 1))
CL-USER>

うーん、やっぱり探索済みというか、たどり着けるノードが返ってきますよね。

CL-USER> (set-difference *test-nodes* (car (find-islands '(1 2 3) *test-edges*)))
(7 16 29)
CL-USER>

上記の数がislandに入っていないようです。
つまりこれらは*test-edges*に入っていないようです。
islandって名前からして、接続されていないノードが入ると
思ったのですが逆のようです。
なんか思い違いをしているのかな。

CL-USER> (length (car (find-islands '(1) *test-edges*)))
27
CL-USER>

う〜ん、ノードが30に満たないのは別にいいのでしょうか。
色々もやもやしていますが時間を凄い使っちゃったので先に行きます。

CL-USER> (defun connect-with-bridges (islands)
           (when (cdr islands)
             (append (edge-pair (caar islands) (caadr islands))
                     (connect-with-bridges (cdr islands)))))
CONNECT-WITH-BRIDGES
CL-USER> (defun connect-all-islands (nodes edge-list)
           (append (connect-with-bridges (find-islands nodes edge-list)) edge-list))
CONNECT-ALL-ISLANDS
CL-USER>

またまた考えます。
connect-with-bridgesは(cdr islands)があれば
islandsの(caar islands)と(caadr islands)をペアに、
つまりその二つのノード間に橋をかけているわけですね。
islandsの要素が一つになるまでひたすら続けて、
できたペアを全てappendで一つのリストにしています。
最後のconnect-all-islandsは…これまでの処理のまとめ、
既存のedge-listに孤島同士をつないだリストを足す、
みたいな処理ですね。

これはまだ後々引数を別の関数で作るのかな。
そこで今の所エッジのリストに入っていないノードのリストを
渡して処理してもらえば全ての島が繋がることになりますもんね。
多分そういうことでしょう。

苦戦に次ぐ苦戦でした。今日は疲れたのでまた明日、と
いつもならしているところですが、まだまだやります。
でも長いので一旦切ります。