今回はアナグラムのお話。
リンクはCodeKata: Kata Six: Anagrams。
今週は実用的な実装をやめて、クロスワードを解いてみよう。
イギリスでは、よく新聞のクロスワードをやって何時間も無駄にしていた。クロスワード好きはイギリスの暗号クロスワードをアメリカのクロスワードとはかなり違うように感じる。多くのキーワードは、だじゃれや言葉遊びだが、その中でもアナグラムが数多くある。例えば、Guardianクロスワードだと
Down:
..
21. Most unusual form of arrest (6)ヒントは"form of"というフレーズで、アナグラムを探せっていう誘導だ。"arrest"は6文字なのは分かるんだけど、その6文字を入れ替えると"rarest"っていう「珍しい」って意味の単語に変わるんだ。（他にも、raster, raters, Sartre, starerとかもある。）
話を少し戻すと、Rubyのメーリングリストにアナグラムを見つけることについてのスレッドがあった。その話を載せる。問題はとてもシンプルで、1行に1単語が書かれているファイルに対し単語のアナグラムの組み合わせを出力するということだ。出力の各行には、アナグラムで作成した全ての単語が含まれている。例えば、以下のような出力になる。
kinship pinkish enlist inlets listen silent boaster boaters borates fresher refresh sinks skins knits stink rots sort
もしwordlist.txtの単語に対して、上のアナグラムのコードを動かしたら、アナグラムは2530組全部で（5680単語ある）見つかるだろう。大きい辞書（234k単語）を利用してOSXで計算させたら、15048組のアナグラムを見つけた（actaeonidae/donatiaceaeとか変なのも含める）。
プログラミングに関して更に負荷をかけると、アナグラムの中で最長の単語を見つけてみよう。そして、一番多くのアナグラムを含む単語を見つけてみよう。（例えば、"parsley players replays sparely"は4単語しかアナグラムがないので、これではないだろう。）
Kataの目的
単語で遊ぶのもいいけど、このKataではアルゴリズムについて考えるべきなんだ。アナグラムの組を全て見つけるための一番シンプルなアルゴリズムは、多分計算に時間が無限にかかるようなものだろう。そこで、代替案として計算時間のオーダーを下げるようなものを見つけるべきだ。比較するベンチマークみたいなものとして、私は25行のRubyでコードを書いた。そして先程の単語数に対し1.5GHzのマシンで1.5秒で終了した。では、もう一つ面白いテストとして、辞書の全単語を使ってっも上手く行くかユニットテストを書いてみよう。かけるかな？
追記：wordlist.txtのリンクが切れているから、前回のKataで紹介されていた"/usr/share/dict/words"の単語リストを利用したほうがよいだろう。
