2005年12月28日
mpuz の思い出＆裏話
mpuz を覚えているだろうか。陰郎の３作目の Palmware である。これ、リリース直後に重複解問題が発生してあわててバージョンアップしたのだが、当時の記録がこの日記に書いていないことを思い出した。そろそろ今年も押し詰まってきたし、１年の反省モードに入りつつあるのでここらでちょっと書いておこう。mixi に５月頃書いていた内容からかき集めてきたものを体裁を整えて加筆修正をしてみた。
そもそも mpuz の問題生成方法は、ランダムに生成した数式を英文字でマスクして設問とするという手法をとっている。そのため、別解が存在してもそれは正解として扱うことができない。正直なところ別解のことは最初の時点では考えていなかった。言い訳がましいが、気づいていなかったわけではない．．．と記憶している。しかし、リリース初日でいきなり重複解の指摘を受けたため、なんとかしようと。そう思って調査したわけだ。
調査の結果、設問になりうる 45,237 問のうち、841 問で別解が存在することが判明。重複解の総合計は 2,199 問。重複解を持つ設問が表示される可能性はかなり低いとはいえ、実際にリリース初日に発生し、それに気づいたユーザーがいたのだ。これはなんとかせないかん。
この調査のなかで、かなり多くの重複解をもつ設問があることもわかった。次の問題を見て欲しい。
ＡＢＢ
ｘ ＣＣ
─────
ＡＤＣＥ
ＡＤＣＥ
──────
ＡＢＤＦＥ
これ、答が１２通りもあるのだ。
122 x 99 = 12,078
144 x 99 = 14,256
177 x 99 = 17,523
233 x 99 = 23,067
244 x 99 = 24,156
344 x 99 = 34,056
388 x 99 = 38,412
488 x 99 = 48,312
566 x 99 = 56,034
577 x 99 = 57,123
677 x 99 = 67,023
788 x 99 = 78,012
調査の結果、これが最多重複解問題である。これを発見したときは正直絶句した．．．このような現状に対し、どのように対処すべきか。最初は、「 単一解問題のみを出題する 」 という措置はとりたくなかった。しかし、考えれば考えるほど複数解問題のサポートは面倒だという話になってくる。ユーザーの解き方にも関わってくる問題だ。基本的には１文字ずつあてていくという解き方を想定しているが、全ての文字について答えを考えた後に答えを入れていく人には複数解問題のサポートは返って迷惑だろう。結果として、単一解問題のみを出題することに決定したのだ。
方針は決まった。では、どうやって実装するか．．．ランダムに設問を生成する部分は変更したくない。生成した設問が 「 出題してはならない 2,199 問 」 に含まれるかどうかを調べる方が速いだろう。このチェックは一瞬で終了する必要がある。運悪く複数解問題を生成してしまったら、もう一度設問の生成からやらなければならないのだから。
いろいろと考えた結果、静的な配列を用意し、禁止される 2,199 問をソート済みの状態で格納しておくことになった。生成した問題をこの配列に対してバイナリサーチ （ ２分木検索 ） をかけるのだ。検索に成功してしまったらそれは重複解問題である。2,199 といえば２の11乗より大きく、２の12乗より小さい。つまりバイナリサーチなら12回のアタックで済むのだ。静的な配列ならアプリ起動時の初期化もない （ はずだ ） から体感速度はほとんどまったく変わらない。配列のポインタ演算だから定数時間。これしかないだろうと結論した。
当然、生成した問題がこの配列に「含まれない」ことを確認するわけだから、必ず12回の比較が発生する。しかし時間のコストはそれだけ。では空間のコストは？ mpuz.prc が９ＫＢ肥った。これを大きいと見るか小さいと見るか．．．難しいところだ。しかし、実現しようとする内容と比べればまぁ許容範囲内だろう。
．．．というわけで、現在の mpuz に至っている。基本的に自分の選択と決断は間違っていなかったと信じている。以上、思い出話終了。
投稿者 kagelow : 2005年12月28日 12:55
トラックバック
このエントリーのトラックバックURL:
http://www.project-enigma.jp/members/kagelow/locus/mt-tb.cgi/149
このリストは、次のエントリーを参照しています: mpuz の思い出＆裏話:
» mpuz 1.01.001 from Good News Forever@はてな
陰郎さんがmpuz((http://www.project-enigma.jp/products/mpuz/))の1.01についての解説((http://www... [続きを読む]
トラックバック時刻: 2005年12月28日 21:27