一泊二日コード漬け - Pixel Pedals of Tomakomai

terapyonさんの主催している開発合宿に参加させてもらいました。

初めてこういうのに参加しましたが、はかどり方が半端じゃないです。一人で家で開発作業をやってると、30分〜1時間くらい開発した辺りで飽きが来て遊びに出たりしてまうことが多いのですが、周囲で作業をやってる人がいるとそうもいかなくなります。仕事でやってるんじゃなく、みんな好きで集まってやってるってのがうまく前向きな雰囲気を作っていて、相乗効果で自分もやる気になりました。こんなに開発に没頭したのは久々。

今回はオートマトンの本で得た知識を使って、pythonでDFAによる正規表現エンジンを作るつもりでした。しかし、NFAからDFAを構築するとこで挫折。数学的な証明で利用するDFAの構築方法では、NFAの状態集合のベキ集合をDFAの状態集合とします。例えば状態が20個のNFAに対して真面目にDFAを構築すると、1,048,576個の状態を持つDFAになるんですよね・・・実装しようとするまで気がつかなかったorz 初期状態と遷移関数を睨めっこして、必要な状態だけでDFAを構成する方法を考えたんですが、スマートな方法が思いつかず*1、結局NFAのまま評価しました。動いたからまあよしとしますか。

反省

テーマが難しくて余裕がなかったせいもあり、あんま他の人と情報交換できなかった
コード書くのが遅い*2。素振りが足りないことを実感。

5/27 追記

CodeReposに作った物を晒しときました。このままじゃあまりにひどいんで作り込む予定です。

試し方

>>> import dfareg
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "pythonperl")
True
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "rubyphp")
True
>>> dfareg.strict_match("(p(ython|erl|hp)|ruby)*", "java")
False