2012-09-08

ゲームなら　語彙力付くかと　思ったよ

どうもー。PCKで変数名間違えて30分無駄にしたきゃたつぱーです。きゃっとあっぱーです。
いやー　PCKは　たいへんやったわー。
そんなことはともかく、前回wordheroのsolverを作りましたよね。
PCK終わった後お通夜してたんで、冷えてたんで、ノリを戻すべくwordhero日本語版つくりました。
https://gist.github.com/3672833
ほれリンクじゃ。
中身はでかい。
２つのファイルが入っておるじゃろ。
その２つを同じディレクトリにおいて、jap.pyをpythonで実行すれば動く。
注意するべきはpygameモジュールが入ってないと動かないぞよ。
あとフォントを設定せんといかん。
jap.pyの最初に２つの変数があるじゃろFO
NORMAL_FONTとNUMBER_FONT
その二つには日本語があつかえるフォントファイル（.ttfとか.ttc）のパスを入力しな。
さもないと動かないぞよ。

みんな遊ぶがいいー

2012-09-06

ゲームして　気がつきゃ２時間　たっている

どうも最近word heroにはまっているきゃらっぱーです。きゃっとあっぱーです。
word heroとはなんぞや。
アンドロイドOS向けのゲームでして、jubeatのようなマス状の文字で単語を作っていくだけの単純なゲームなのですが。きづけば２時間たっているくらいの悪魔のゲームです。もうdiamondです。宿題考査の点数が悪くなったのもこれのせい。

話は変わりますが、私プログラミングという趣味がございまして、このようなルールのかっちりした単純なゲームを発見するとsolverを作りたくなる次第でございます。とりわけ今回のゲームは目標が「より多くの、より長い単語を見つける」というわかりやすいものでしたこともあり、また16文字しかない、という非常に計算速度面からみても実現可能っぽかったので一晩で組むことに成功しました。

コード解説

中身は簡単で

辞書データを読み込む
ソートする
マス目データを読み込む
全探索+枝刈り
存在した単語を文字数でソートする
出力

一見に如かずということでソースコード上げます。

ソースコード自体は簡単ですが問題は辞書データです。
wordheroは複数形、過去形、現在進行形、過去分子など辞書ではひとつにまとめられているものも別に扱ってくれます。
ということはちゃんと全部のってる辞書データーが必要です。
UNIXの人は/usr/share/dict/wordsに英単語辞書がございますのでご利用ください。
辞書の形式は一行に一単語書いてあるものであれば順番は何でもいいです
その他いくつかウェブから拾ってきたりすると使えたりします。
私も方々から辞書データを集めているのですが、サイズがそこそこ大きいことと、一部権利がどうのこうのと面倒くさいところがあったのでうｐしないです。
ほしかったら言ってください。

ちなみにこれを使って無双仕様と思ったのですが、ボードのアルファベットを入力して出力待って目で見ながら手で入力とかやってると、時間が足りなくてたいしてポイントとれません。そのかわり超長い単語があったりすると楽しくなります。

2012-08-30

謎木速いけど微妙にバｇ・・・バグらないだと！？

どうもJOI夏季セミナー2012に行ってきたきゃっぱーです。きゃっとあっぱーです。
こわいひとにたくさんあえて楽しかったです（小学生並みの感想）。
遺伝的プログラミングの本を読みたかったのですが、じゃんけんでことごとく負けて

Introduction to Algorithms (MIT Press)

作者:Cormen, Thomas H.,Leiserson, Charles E.,Rivest, Ronald L.,Stein, Clifford
The MIT Press

Amazon

この本を読みました。蟻本++っていうのが的確な表現だと思いますー。
好きなテーマで本を読解して発表するというものなのですが、まず本が英語で詰んでました。
まぁ技術書なんでそこまで英語は難しくなかったのでなんとかなりますたー。
セミナー中にCodeForcesがありまして、ネット環境がなかったのでjubeat板で問題を読んで、コードはPCで組んで、Bluetoothでjubeat板に送ってsubmitしようと思ったのですがBluetooth接続で失敗して無理ですた。残念
なにより朝飯が3完でした。しかも逃したのが発表当日の最終日ということで、朝飯を抜いて午前最後の発表をするという高難易度のミッションでしたー。こんどからは目覚まし持ちあるこう。

ではでは、セミナーでやった話を具体的に。

蟻本++の中で私はvan Emde Boas treeという木構造についていろいろやりました。
この本の目次の中で唯一タイトルを見ても見当がとんとつかないものだったのでやってみました。
この木はあらゆる操作がO(log log　u)でできる集合でして、すごい強者なのですが実装が重いです。
詳細についてはslideshareに上げてるスライドがあるので参照よろしくおねがいします。

スライドでも述べたとおりオペレーションと値の持ち方が非直感的でややこしいので順を追って説明していきます。
なお説明の中でuとnが出てきますが、uは集合が持ちうる値の種類の数でnは集合が実際に持つ値の数です。

要素の持ち方

van Emde Boas tree(以下謎木）は集合ですので、ある要素が有るか無いかという情報を持ちます。
まずこの集合が要素として持ちうる値の種類の数だけのメモリを確保します。
たとえばint型の謎木ならば32bit分のメモリを、char型の謎木ならば8bit分のメモリを確保します。
これらのメモリはフラグとして使用し、値が有るなら1、無いなら0を格納するという感じで情報を保持します。
スライドでも出てきた平衡二分探索木はこれらを葉とするような平衡二分木を作って二分木的に操作をしています。
謎木も同じようにこれらを葉とする木なのですが、深さをlog log uにするために
サイズUの親がサイズ√Uの謎木を√U個持つ
という形をとっています。
ここで重要になってくるのは葉以外のノードがどのような情報を持つかということです。

各ノードのもつ情報

平衡二分探索木では葉以外のノードはただ一つの値を持ち、自分の子孫である葉に一つでも1があれば1,そうでなければ0という値を持ちます。
このようにするとオペレーションで再帰的に木を降りていくときに値の有無が判断でき、効率の良い枝刈りによりO(log u)ですべてのオペレーションを実現しています。
謎木でも同じように自分の子孫の葉に1が少なくとも一つあるか無いかという情報（Summary）を各ノードに持たせています。
この持ち方が実に巧妙で、平衡二分探索木ではそのノードの子孫のSummaryを持っていましたが、謎木はその子達のSummaryを持っています。
サイズUの親は√U個の子を持つので、持つSummaryの情報量は√Uになります。
ここで重要になるのが、Summaryも0,1で情報を表すビット列だという事です。
そしてサイズUの子のサイズが√Uということ。
これはつまり、各ノードのSummaryは子と同じ構造で扱うことができるという事です。
よって各親は√U + 1個のサイズ√Uの子(およびSummary）を持つことになります。
そして謎木の性質上　最も重要な情報として、そのノードの子孫の最大値と最小値を持ちます。
どうしてこれが重要なのかは後で説明しましょう。

最大値、最小値、有無のオペレーション

これは簡単です。
最大値、最小値は各ノードが持っていますのでもちろん根も持っています。それを参照するだけなのでO(1)です。
有無は、その値と対応する場所まで降りて0か1かを確認するだけなので、再帰回数は深さ分。つまりO（log log U）です。

追加

値を追加するのは情報の書き換えがあるのでややこしいです。
なによりもっとも厄介なのがこの木の情報の持ち方です。
ノードは最大値と最小値をもっているので、これを使ってその子孫の要素数が0個,1個,2個以上のどれであるかを判断できます。
最大値も最小値も無ければ0個
最大値と最小値が等しかったら1個
それいがいならば2個
です。
この木では要素を追加するとき0個から1個に増えるノードに関してはそこで再帰をやめます。なんとSummaryの更新もしません。
そして値を追加するとき、もちろん途中で通るノードのもつ最小値の情報も書き換えていくのですが、普通に更新するのではありません。
再帰の途中で最小値より小さくなったら、最小値と追加する値を交換します。それに対して最大値は交換せずに更新するだけです。いみわからん。
このような追加の仕方をすることによって謎木がどのような状態になるのかというと。
各要素はいずれかのノードの最小値である。そしてその親のSummaryはそれの有無については扱わない。またその子もその値について扱わない。
このような非対称的なやっかいな状態になります。

削除

値の削除はなお厄介です。
もっとも大変なのはSummaryの更新で、平衡二分探索木では子が2個なので再帰の帰りにSummaryを更新する時に兄弟のSummaryを見ればO(1)で0に戻すべきかそうでないかが判断できました。
しかし謎木は個の数が多いのでO(1)でSummaryを0にするべきかわかりません。
ここで役に立つのが最大値、最小値です。
Summaryを0にするのは要素数が1から0に変わるときだけです。
最大値が最小値と同じかどうかで、要素数を1かどうか判断できることができますので、O(1)でSummaryの変更の判断が可能です。
実は他にもうひとつ問題があり、最小値の削除です。
先述の通り最小値についてはそのノードの子孫はあつかっておりませんが、それ以外は扱ってますので、新しく最小値になる値をその子孫から消さないといけません。
またその親のSummaryも扱っていますからそこからも消さないといけません。
すると二回消す動作を行うので再帰呼び出し数が二個になってO(log U)になってしまうように思えます。
実はSummaryを更新するという事はそこに対応する子は値を一つしか持ってなかったことになります。つまりそちらの再帰の深さは1です。よって呼び出しを二回しても、片方はO(1)でおわるので結果的に処理数は深さ分になります。
O(log log u)
です。

Successor

これは与えられた値より大きい要素の中で最小のものを返す関数です。
最大値最小値は各ノードが持ってますのでこれをうまく使えば単純な操作だけで実現できそうです。
具体的には普通にその値に対応する葉の方向に降りて行って、とちゅうでその値が最小値よりも小さくなったらその最小値が返すべき値です。
もしも最大値よりも大きくなってしまったら、その親の「次の兄弟」の最小値が返すべき値です。「次の兄弟」というのはSummaryにおいてSuccessorを使うことによって得ることができるので結果的に処理数は深さ分になります。
O(log log u)
です。

Predecessor

こちらはSuccessorの逆で与えられた値より小さい要素の中で最大のものを返す関数で、次ソスはSuccessorの逆なので割愛します。

空間計算量

さて、データー構造は速けりゃいいってもんじゃない。メモリを沢山食っては動きません。
この謎木は普通に考えると葉の数だけメモリが必要ですので空間計算量O(u)になりそうです。long long int型ならば2**64のメモリが必要ですが、さすがに扱えません。
しかしInsertの動きをよくみてみると、各要素はいずれかのノードの最小値になっています。そして最小値はそのノード以外で扱わないので、結果的に情報を持つノードは要素数を超えません。よって、子を動的に確保していけば空間計算量は要素数分　つまりO(n)までおさえることができます。

よってヒープと同じ空間計算量でオペレーションはO(log log u)でできる謎な木が出来上がりましたー。　やったぜー。

実装

まぁ実装が重いです。　C++で組めるもんなら組んでみれば良い。
私はpythonで組みました。

URL:https://gist.github.com/3505897
こんど機会があったらC++で実装してみたいと思います。

2012-07-24

【python描画シリーズ】PIL

どうも最近pythonで描画する欲求を持つきゃたぱです。きゃっとあっぱーです。
今回はPILの紹介でもしようかと。
PILとはなんぞや
Python Imaging Libraryのことです。
画像編集全般のモジュールです。easy_installでインストールできます。

sudo easy_install PIL

このブログでドラゴン曲線の画像をのっけたりしてますがPILで描画したものです。
また随分前に作った苺ましまろの画像でhelloworldする謎言語もこれで画像処理してます。
公式ドキュメントのPDFが目次がなくて非常に読みにくいです。html版はありますのでそっちを読むべき。
たぶん画像処理ではこれが一番のモジュールだと思われ
ちょいな編集（反転、しきい値で選択）などのモジュールの品揃えがいいんで高度な編集にも使えます。
だが、あいにく編集する画像を持ち合わせていないので、ロジステック写像の有名なカオスなグラフでも書いて見ることにする。

logi.bmpという画像データが出来上がってプロットされた図があるはずです。
まぁこんなかんじです。

もともとグラフ書くためのものじゃないので座標軸書いたり、数字書いたりしないといけないのですが直線などの幾何学図形の描画ツールもそろっているので問題なく書けます。だけどやっぱりめんどうくさいです。