子供に、国の名前でしりとりをしようと言われ、国名なんか少ないからすぐ行き詰まるだろうと思いながらやってみると、意外にも20ヶ国くらい繋がった。
それで、最長パターンはどれくらいなのだろう、と思って調べてみた。
■プログラム
shiritori_solver.py
■結果
最長しりとり (44ヶ国):
モルディブ → ブルンジ → ジンバブエ → エスワティニ → ニウエ → エジプト → トルコ → コモロ → ロシア → アルジェリア → アルバニア → アルメニア → アイルランド → ドイツ → ツバル → ルーマニア → アイスランド → ドミニカ → カーボヴェルデ → デンマーク → クウェート → トンガ → ガイアナ → ナミビア → アメリカ → カタール → ルクセンブルク → クック諸島 → ウクライナ → ナイジェリア → アラブ首長国連邦 → ウルグアイ → イスラエル → ルワンダ → 大韓民国 → クロアチア → アンドラ → ラオス → スイス → スリランカ → カンボジア → アンゴラ → ラトビア → アルゼンチン
プログラムはほぼGemini Code Assistに作らせた。
国名のリストはこのファイルからGeminiに抽出させた後、先頭や末尾が漢字のものはカタカナを付けるなど、手で整形した。
100ヶ国分の全探索はすぐに終わったが、120ヶ国分にすると数分待っても終わらなくなったので、大まかな進捗率を表示させるようにした上、次のような最低限の探索量削減の工夫をした。
(1)「アルメニア」「アルバニア」など先頭と末尾が同じ文字の複数の国名の順列は1つに固定
(2)「アイルランド」「アイスランド」など先頭と末尾の組が同じ国名は同じ深さで1つしか検索しない
他に1通りしかない部分列は事前にまとめておく、PythonでなくC言語でやるなどを考えたが、指数オーダーの削減効果は無いだろうと考えたのと、上の対策で194ヶ国分で丸1日はかからなさそうになったので省略した。
結局、Apple M1のMacBook Airで約11時間で完了した。
コメント