SET YOUR NUMBER
1
4
7
9
ウィーキーとガルフがヒット＆ブローを覚えたようです。最悪でも７回、平均で約５．８回のトライで求まります。
このアルゴリズムはGreedyに求めたものですが、多分これが一番早いと思います。
くだらない茶番を気にする必要はありません。
あなたが最初に４桁の数字を設定します。ウィーキー(左下)にはその数字がわかりません。
しかし何故かガルフ(右下)には分かっています。
ウィーキーはその数字を当てようとします。順番も合っていなければなりません。
ウィーキーが数字を宣言(トライ)すると、ガルフはそれに対してヒントを与えます。
そのヒントを頼りに何度もトライを行い、何回で当てられるかを競います。
位置は違うけれども数字が合っていればブロー(Ｂ)、位置も数字も合っていればヒット(Ｈ)といいます。
ガルフはウィーキーの宣言した数字に対してヒットとブローの個数を答えてあげます。例えば、
答えが１３５７のときに「０１２３」と宣言すると「０Ｈ２Ｂ」、
答えが０３４５のときに「０１２３」と宣言すると「１Ｈ１Ｂ」、
答えが００４５のときに「０１２３」と宣言すると「１Ｈ０Ｂ」、
答えが３４５０のときに「００１２」と宣言すると「０Ｈ１Ｂ」となります。
つまり一か所の数字は一回しか数えません。
結局トライするときに宣言する数は００００〜９９９９の１００００通りしかありません。
したがって、これらすべての数を「評価」し、最も良いものを選べばよいのです。
トライすると答えが返ってきます。その答えによって、あと何通りの数が残るかが決まります。
「最悪の場合で何通りの数が残るか」によって評価をします。
例えば、最初に「０１２３」と宣言すると「０Ｈ０Ｂ」では１２９６通り、「ＯＨ１Ｂ」では３０４８通り、…
の答えが残り、最も多いのが「０Ｈ１Ｂ」の時の３０４８通りです。従って「０１２３」の評価値は３０４８となります。
これを００００から９９９９まで全て評価し、最も評価値の小さかったものを採用します。
以上でアルゴリズムにはなっているのですが、最初にトライする数を００００〜９９９９まで全て考える必要はありません。
最初にトライする数は、対称性を考えると００００、０００１、００１１、００１２、０１２３のみ考えればよいことになります。
これらの中で最も評価値が小さかったのはやはり０１２３でした。
いちいち最善手を求めていると遅いので、あらかじめ全ての答えの出方に対する最善手を求めてあります。
それがこれです。ウィーキーはこれを見てるだけなので、時間計算量はＯ(１)となります。