2018年4月30日月曜日

操車場アルゴリズムの実装例[Python]

1. 概要

コンパイラを書いてみたいと思いつつも,構文解析すらわからない.
その手の本を開くと操車場アルゴリズムというものが書いてあったのでWikipediaをもとに実装してみた.
ついでに逆ポーランド記法の処理系と変数及び代入を実装し,対話形式で計算ができるようにした.


一応確認した限りではちゃんと動作しているのが,クリティカルなミスはない(と信じたい).

2. ソースコード

200行ちょいと,ブログに貼るのは少し長くなったのでGitHub Gistにあげた.


3. 感想とか

動作したところはこんなかんじ.
操車場アルゴリズムのWikipediaが割と詳しく書いてあったので良かった.実装時にそれ以外のリファレンスは特に見ていない.
このサイトにあるコードを写経したときはこんなに面倒なのかと思ったけど,これなら僕にも実装できそうだ(というかできた)のでよかった.

そういえば今年に入ってPython3に移行した.
WindowsでのPython2の開発環境の構築が無限に面倒だったので,またインストールするの嫌だなぁと渋っていたのですが,やってみたらすぐ終わってしまった.
とくにpipでnumpyとかが入るのはすごい.Python2だとまだ入らないのでは.
mapの返り値がイテレータなのはビビったけどなんとか使えそう.

2018年4月28日土曜日

パズル「美術館」を解くプログラムを書いたお話[Rust]

新しい言語としてRustを始めたのですが,まだ使い慣れていない状態です.
練習がてらなにかプログラムを書きたいと思っていたところ,友人が,プログラミングの課題で「美術館」というパズルを解くプログラムを書かされたという話を聞いた.
面白そうなので書いてみたところ,思ったよりも辛い問題で,躓いた点があったのでメモします.

1.概要

「美術館」というパズルゲームはニコリという出版社が生み出したパズルゲームで,Nクイーン問題みたいなパズル.
ルールやサンプル問題などは以下を参照.

公式サイトはFlashのバージョンの問題からか,ChromeやFirefoxからはスッと試すことができなかったので,一度手でやってみたいという方は4番目のニコリパズル道場!という趣味で自作のパズルをあげてるサイトを見ると良いと思います.

2.解法

単純に深さ優先探索とかで書くと,探索空間が2^(WH)で増えていくので解くことはできない.
ただ,一度自分の手で解いてみるとわかりますが,とりあえず置いてみておかしいところが無いか確認する探索よりも,よく知られている経験則によって置く場所が決まることが多いです.
そういった人間でいう「解くためのコツ」を如何に高速に実装できるかがキモでした.
ただ問題によってはある経験則を消したほうが早くなる場合もあってこうしたら絶対に良くなると言い切るのは難しいです.

私の実装では置ける場所・明るくなった場所をbool型の2次元配列でもっておき,以下の制約を実装しました(1-2はルールの言い換え).
  1. 数字マスの周りに置かれた照明の数が,数字マスの数字と一致した場合,その数字マスの周囲にはもう照明は置けない.
  2. 明るくなったマスには照明は置けない.
  3. 数字マスの数字が,置ける空白マスの数と一致している場合は,全ての置ける空白マスに照明をおける.(e.g. 数字4のマスの周りは全て置ける)
  4. 数字マスの周囲に,数字マスに書かれた数だけ照明を置く事ができない場合は条件を満たすことができないので探索を終える.
  5. 置くことができる暗いマスで,その縦列・横列に置ける場所がない場合はそのマスに照明を置ける.
  6. 置くことができない暗いマスで,その縦列・横列に置ける場所がない場合は条件を満たすことができないので探索を終える.
上記のルールに基づいていけば結構なマスを埋めることができます.
ただ,5はない方が早いこともあるしあったほうが早くなることもあるが,6番目の条件は,これがないとマトモに解けない問題もあります.

この条件でマスを埋めることができなくなった場合は
  1. 照明を置ける場所にとりあえず置いてみて条件が満たせないか確認し,もとに戻す.条件を満たせなかったらそのマスは置けないマスとなる.(e.g.数字3のマスの斜め方向には置けないなどの制約になる→Wikipediaの解法を参照)
  2. 数字の周りから先に探索する
という方針で探索領域を狭めながら探索を進めたところ,当方の環境でニコリのお試し問題すべてを4秒以内に解けるようになりました.
ただ公開するにあたって修正したのですが,修正する前のコードは半分ぐらいの時間で計算しているので実装の仕方次第でもう少し早くなるはずです.

3.ソースコード

サンプル入力・出力とともにGithub Gistにあげました.
サンプル入力はニコリのお試し問題からの引用です.
見た目を良くしたつもりなのですが500行を超えてます.
しかも整形しただけで計算時間が2倍になった理由がわからない…….

4.追記

書いた後に調べたところ,もっと良い経験則があるとのこと.


爆速になるらしいので機会があったら実装したいです(多分しない)

2018年1月7日日曜日

2018年最初の投稿

また年が変わりましたね.あけましておめでとうございます.

昨年は全然ブログ更新とかしてなかったのですが,毎年ブログで目標を立てて生きているので,今年も昨年を振り返りつつ目標をたてて1年頑張りたいと思います(去年の投稿はここ).

1.昨年を振り返って

今思うと激動の1年だったと思います.
ざっくりいうとCPUと動物に興味を広げたという一年だった.

1月……
ペットボトルロケット飛ばしてた(この記事とかこの記事).
何かと雑だったけどそれなりの開傘アルゴリズムだと自負してる.この手法でハイブリッドロケットも回収できたのでよかった.

2月……
ハフマン符号化の実装をしてたみたい.このツイートが数回RTされたところで既出ネタだったことが発覚.まぁみんな考えるよね.


3月……
後述するが昨年の目標として本を読むことをあげていたので春休み中は何かと本を読んでいた.
『数値計算の常識』とか読んでいたのでLU分解の実装をしてたらしい.あとはim920とか使って遊んでた.

4月……
基本情報技術者試験を受けた.11月に受けた応用情報技術社試験も含めて合格したけど,これ読解力の試験だなぁという感想が強い.ストラテジ・マネジメントの問題は全然覚えてなかったけど日本語読めばこれは違うだろうというのが明らかだったので消去法で言ったら結果的にそっちの方が点数が良かった気がする.午後問も同様に答えが文章中にあるタイプの問題でこれはちょっと……ってなった.
その勉強をしている際にアセンブラとかに興味が湧いたので『Hacking: 美しき策謀』を少し読んでう~~~ん???と唸ることになった.

5月……
『CPUの創りかた』を読んだ.目からうろこだったのでLogisimでTD4作ったりして遊んだ.今見るとひどい回路だけどこれは大きな知見が得られた.
同時期に春休みぐらいからちまちま写経してた離散数学の教科書に目を通しきった.
更には『コンピュータの構成と設計 第2版 上』も5月中によんでたらしい.

6月……
BrainfuckCPUを作ったりしながら結構本を読んでいたらしい.
友人が仮想通貨で一儲けしたらしく,少し興味を持ったので『暗号が通貨になる「ビットコイン」のからくり』『ブロックチェーン入門』を読んだ.ここでBTCを買っとけば…….
他に『自然言語処理 (放送大学教材)』を読んだりしたが,この月に読んだ本で一番大きな衝撃を与えたのはP.J.B. スレーター 著『動物行動学入門』だった.けものフレンズを見てすこし読んでみるかーと手に取った,私にとっては異色の本だったがこれがドハマリした.この本を最初に読んだのは正解だったと今おもうと感じる.動物行動学という動物の行動に着目する学問があるということを初めて知った.この学問が血縁淘汰説を支持することになることを知るのはしばらく後である.
さらに『世界哺乳類図鑑 (ネイチャー・ハンドブック)』を読んで哺乳類がウマ目・ウシ目・ネコ目などという幾つかの大きなくくりが存在することを知った.大学には学研の図鑑のようなとっつきやすい本が無いのが非常に残念だったが僕の興味を広げるにはこの本は十分だった.

7月~12月……
この後はずっと月に1度ほどの頻度で動物園に行きつつ,動物関係の本を読み漁ることしかしていない.
『利己的な遺伝子』を読んだのは非常に印象に残っている.これは非常に良書だった.長い本だったがその分充実感は大きかった.血縁淘汰説をとても面白く感じたのを覚えている.
カール・ジンマー 著の『進化の教科書』は僕が知りたかったことを抽出して書いてくれて非常に良かった.利己的な遺伝子では少々回りくどく,浅い理解だったところを程よくおさらいできた.
技術的な方だと『ゼロから作るDeep Learning』を読んで実装した.結構いろんな知見が得られた.後は現代制御の勉強の結果を使って倒立振子のシミュレーション・制御をしたりRustを初めたりした.Rustは結構良い.

2.去年できるようになったこと

昨年の投稿に倣って書いてみると

  • 基礎的なRustのコードが書けるようになった
  • logisimでCPUを作れるようになった
  • 現代制御で初歩的な制御対象を制御できるようになった
  • CAD(授業にて)

結構少ない…….動物関係にリソースを割きすぎてしまった気はする.

3.去年の目標達成率

・数学の能力を上げる……25点
離散数学の本は読んだけど結局記号に慣れただけという印象が強い.もう少し頑張りたかった.

・関数型言語の勉強……50点
Rustは関数型言語……というのは誤りであることがわかったので50点ですかね(そういう書き方もできるだろうが).そもそも関数型言語ってなんやねんという感じが強い.再帰つかったりfoldとかmapとか使うのはまぁできるけどうーん.純粋な関数型言語は触れなかったなぁ…….

・大会やニコ動にアウトプットしてく……0点
だめですね(だめなのです).去年も駄目だったんですよね.うーん性ではない気はする.

・本を読む……80点
これは意識的に行った.100冊ぐらい読みたかったが児童書含めて60冊だった.友人で3年で1000冊の本を読んだ男が居るが到底かなわない.
ただあまりにもインプットに徹しすぎたというか,冊数を稼ぐゲームになっていたのでこれは良くないと感じた.趣向を変えるべきだと思う.

4.今年の目標

入学直後に先生が言った「学部時代に勉強しなかった科目は一生学ぶことがない」という発言が頭をよぎる.
昨年は動物の本にリソースを割きすぎた.動物は具体的で,読みやすい本が多いが深くまで切り込んだ本が少ないと感じた.
今年はもう少しうまくリソースを配分し,より深く,抽象的な理論を学ぶことをしたい.

・英語の多読をする……
 TOEICに対してプログラムのドキュメンテーションを読むだけではダメだというのがわかったので.院試が終わったらやめる.

・数学の勉強をする……
 院試用の試験勉強+論理を追う力をつけたい.論理学を良書の情報を聞きつけたのでそれを読む予定.

・Lispの勉強をする……
 『Land of Lisp』を入手したので読む.関数型言語のキモはここで学ぶ.

・CPUのより詳細な内容(割り込みとか)/コンパイラ/OSについて学ぶ……
 「学部時代に勉強しなかった科目は一生学ぶことがない」という発言が頭をよぎる.

・本を読む……
 冊数にこだわるのではなく内容を重視していきたい.新書よりも専門書,なるべく手を動かしていきたい.ただ月に1度ぐらいのペースで軽めの本も読むつもり.

・ブログを更新する……
 アウトプットはここで.ハードルも低い.なんかコンペみたいなのに出したりするのはハードル高いし性に合わないことがわかった.ただ人に見せられるようなプロダクトの形をした物を作ってみたいなとは思う.

・新しいことに挑戦する……
 雑な目標だが僕は保守的な人間であるということを感じて非常に時代遅れになっているのを感じるのでなれないことになるべく手を出していきたい.


研究室に配属し,さらには院試もあるが頑張っていきたい.