GDDJ 2010のしりとり問題をScalaで解く（ための支援を行う）

論文を読む必要があるらしいので、しりとりゲームの数理的解析を読んでみた。

いくつか簡略化する方法があるようだが、そのなかでも「逆向きの有向辺の相殺」のみを、

プログラミングしてみた。

準備：しりとりで使用する語彙リストをinput.txtというファイルで用意しておく。

次のScalaソースを実行するとGraphvizのdot記述が出力されるので、それを元に手動で解く。

結果：Graphvizを使って眺めればいいのだが、Ajax/Graphvizを使うとお手軽に眺められるみたい。

object Shiritori extends Application {

 val words = scala.io.Source.fromFile("input.txt").getLines.toList

 val graph = words.map(word => word.head -> word.last)

 println("digraph {")

 graph.filterNot(edge => graph.contains(edge.swap)).foreach(edge => println(edge._1 + " -> " + edge._2 + ";"))

 println("}");

# その後、しりとりの論文を探すと「最長しりとり問題の解法」を発見！

# そういえば、昔ここで勉強してたんだよな→自分。

# 思い出した。トリビアの泉ネタだったな、これ。