Twitter上でメッセージをReplyで送ると、それを表示するBrainf*ckスクリプトを生成するbotを作ってみました。
このbot(@NeoRabbit)で使っているBrainfuckジェネレータを、Haskellで書き直してみました。
（元はこれとほぼ同じことをperlでやってます。Haskell環境のないサーバで動いてるので。）
コードはcodepadにて。
細かいことを考えるのが面倒だったので、割と力づく(brute force)です。大まかな流れは、以下のような感じです。
- コマンドライン引数に与えられた文字列（もしくは"a"）を、1文字ずつ処理していく。(processString)
- メモリ上に文字を作る。
- メモリ上で一番近い文字からスタート。
- メモリ上の値と次の文字コードの差を素因数分解し、因数の組み合わせから最も短いコードを吐けるものを総当たりで探す。 (makeFpairs)
- たとえば18を素因数分解すると2,3,3。
- + を18個並べるよりも、因数を適当に組み合わせて 6×3 : ++++++ [>+++<-] >. とした方が短くなる。
- 小さな因数の方が+が減ってコードも短いが、一方で組み合わせる因数の数が少ないほどループが減って短くなる。
- さらに、例えば 19 (素数)は 18 を上記のように作って 1 を足した方が短いので、前後の適当な区間も同様にして探してみる。(bestFpair)
- 以上を繰り返して、指定された文字列を一通り調べ終わったら、BFコードの文字列を生成してひとまず終了(generateBF')。
- 簡単な文字列の場合は以上で良いが、複数の文字を一括して初期化した方が短くなる場合がある。
- 例えば、"n2"という文字列(ASCIIコードは110, 50)は、10×11 → 10×5 等と一文字ずつ作るよりも 10×(11 → 5) のように纏めて作った方が短く済む。
10×11 → 10×5 : ++++++++++[>+++++++++++<-]>.>++++++++++[>+++++<-]>. 10×(11 → 5) : ++++++++++[>+++++++++++>+++++<<-]>.>.
-
- クラスタリングの手法（最短距離法の変形）を使って、指定された文字列のうち、近い文字は纏め、適度に離れた文字集合を得る (cluster)
- クラスタリングした文字集合を、適当に前後にずらしつつ、大きな公倍数が得られる組み合わせを探す。 (bestCluster)
- [72,101,44] → [72,104,48] (公倍数8) →8×[9, 13, 6]
- クラスタリングした結果でメモリを初期化しておき、あとは最初のステップと同じ方法で一文字ずつ処理していく (generateBF2)
- BFコードを出力する時は、まず初期化文字列を生成(convertCluster)してから、generateBF' を呼び出す
- 出力する前に、無意味な移動(><とか)をカットしたり(optimizeBF1,3)、使ってないメモリを飛ばしたり(optimizeBF2)といった最適化をかける。
- クラスタリングしたらかえって長くなった！という場合もあるので、クラスタリングしたものとしなかったものを比較して、短い方を最終結果として出力する。(main)
数学的かと思いきや、とにかくブルートフォース＋止まらなくならないようにヒューリスティックという感じなので、もっと良いアルゴリズムもあるよなーって気がします。
