一昨日・昨日と続いている「情報共有と電話の回数」（ http://www.hyuki.com/diary/200501#i20050110133233 ）の続き。
http://www.hyuki.com/diary/200501#i20050113223350 → http://www.sampou.org/cgi-bin/haskell.cgi?comment%3aEveryday%3a2005-01-12&l=jp
によると、4人以上なら、人数の倍引く4回が必要最小限だと証明されているらしい。
という情報を読む前に、最小手数を探索するプログラムを決定的に高速化する方法を思いついた。
せっかくなので、すでに探索する意味はないが、実装してみた。
そしたらなんと。
以前は5時間かかっていた9人の場合の計算が、20秒で終わるようになった。ブラボー！……もう意味はないけど。
以前のバージョンでは数日は要すると思われた 10人の場合も 7分足らずで完了。YARV を入れたらさらに半分の時間になりそうだが、面倒なのでパス。
今回の高速化は：
秘密a を知らない人が Na人いると、少なくともあと Na 回電話が必要。「今までに行った電話の数」+Na が既知の最小手数以上なら探索不要。
というもの。
それと。
こういうプログラムを書く時は、インラインコールバックが非常に便利だといつも感じる。きっと、haskell や ocaml にも似たような機能はあるんだろうけれども。
