Bulls and Cows (Incinerator) - 隠された4桁の数字を当てろ

いやー、初めてギブアップしようかと思った問題。
数時間考えて、絶対に無理だと思ったが、なんとかクリアできた。

どんな問題？

Bulls and Cows
http://www.checkio.org/mission/bulls-and-cows/

隠された4桁の数字を当てるゲームで勝利せよ。
こちらが4桁の数字を推測して伝えると、相手は、

数字も位置も合っている個数（Bulls）

数字は合っているが位置が間違っている個数（Cows）

というBullsとCowsを調べて結果を返す。
これを繰り返し、8ターン以内に正解を見つけることができれば勝利。
なお、4桁の数字は重複しない。

引数は、相手とのやりとりをリスト形式で受け取る。
["1234 0B2C", "6512 2B2C"] であれば、
1回目のこちらの推測した数字は 1234、その結果が 0B2C
2回目のこちらの推測した数字は 6512、その結果が 2B2C
となる。
結果が 0B2C なら、Bullsが0、Cowsが2を意味する。（結果が 4B0C、つまりBullsが4になれば勝利。）

どうやって解く？

またも、どこから手を付けて良いのやら、さっぱりわからぬ・・・。
まず、数字の位置はおいといて、とりあえず4つの数字を当てるゲームとして考えてみる。

試行錯誤、その１

まず、Bulls＋Cowsの数が、正解の数字の数だから、
"1234 0B2C"
からは、{1,2,3,4} に正解が2個あることがわかる。
"6512 2B2C"
からは、{6,5,1,2} に正解が4個、つまり、4つの数字は6,5,1,2で確定している。

例えば、
['0123 0B3C', '4567 0B1C', '8901 0B1C']
であれば、

{0,1,2,3}に3個
{4,5,6,7}に1個
{8,9,0,1}に1個

ということがわかる。さらに、

{0,1,2,3,4,5,6,7,8,9}に4個

という条件もある。

以上の条件から、

{0～9}(4個) - {0,1,2,3}(3個) - {4,5,6,7}(1個) から、{8,9}に0個とわかる。
{8,9,0,1}(1個) - {8,9}(0個) から、{0,1}に1個とわかる。
{0,1,2,3}(3個) - {0,1}(1個) から{2,3}に2個とわかる。

この時点で、8,9はどちらも×、2,3はどちらも○だと確定した。
未確定は0,1,4,5,6,7だから、ここで、次の推測を'0145'として…

うーん、なんかこんがらがってきた。この方法で解ける気がしない。

試行錯誤、その２

最初の3ターンは、毎回同じように推測、例えば、'0123','2345','4567'と決めて、この結果から絞っていく方法はどうだろう。

例えば、

{0,1,2,3}に3個
{2,3,4,5}に3個
{4,5,6,7}に1個

であれば、
{0,1},{1,2},{2,3},{3,0}のいずれも、1～2個
{2,3},{3,4},{4,5},{5,2}のいずれも、1～2個
{4,5},{5,6},{6,7},{7,4}のいずれも、0～1個
となる。
{4,5}は、0～1個かつ 1～2個だから、1個だと確定する。{4,5}に1個がわかれば、

{4,5,6,7}に1個から、{6,7}に0個と確定する。
{2,3,4,5}に3個から、{2,3}に2個と確定する。

{2,3}に2個がわかれば、{0,1,2,3}に3個から、{0,1}に1個だと確定する。
また、{0,1,2,3}に3個、{4,5,6,7}に1個だから、{8,9}に0個だと確定。
で、次に{0,1}と{4,5}を確定できるような数字、例えば'0423'と'0523'を聞けば、4つの数字がすべて確定する。

ここまでで5ターン使っているので、後3ターン以内で位置を確定する必要があるが・・・。

いや、そもそも最初の分布がもっと違っていたら、数字を確定できない場合もあるだろう。
例えば、

{0,1,2,3}に2個
{2,3,4,5}に2個
{4,5,6,7}に1個

の場合だと、何一つ確定できない。

この方針もちょっと無理そうだ。

ちょっと諦めてみる

ダメだ、まったく解ける気がしない。ただ、ここまで全ての問題を順番にクリアしてきたので、ギブアップはしたくない。ちょっと汚い方法でもいいから解けないものか。

Restrict Prime（素数の判定問題）では、あらかじめ10000以下の素数を全部計算してコード中に書いている人がいた。こういうパターンならできるかも。
4桁の数字（重複無し）ってことは、10x9x8x7だから、えーと5040通り。これくらいなら、あらかじめ計算しておくのも可能だろう。
5040通りの全ての数字について、推測した数が'0123'のとき、Bulls&Cowsはどうなるかの分布を計算してみた。

import itertools

def get_bulls_and_cows(guess, secret):
    bulls = cows = 0
    for u, g in zip(guess, secret):
        if u == g:
            bulls += 1
        elif u in secret:
            cows += 1
    return "{0}B{1}C".format(bulls, cows)

def test():
    numbers = [''.join(p) for p in itertools.permutations('0123456789', r=4)]  # 5040 numbers

    guess = '0123'
    dic = dict()
    for secret in numbers:
        bc = get_bulls_and_cows(guess, secret)
        if bc in dic:
            dic[bc] += 1
        else:
            dic[bc] = 1
    for k in sorted(dic):
        print('|{}|{}|'.format(k, dic[k]))

結果はこちら。

0B0C	360
0B1C	1440
0B2C	1260
0B3C	264
0B4C	9
1B0C	480
1B1C	720
1B2C	216
1B3C	8
2B0C	180
2B1C	72
2B2C	6
3B0C	24
4B0C	1

つまり、'0123'と推測して、その結果が'0B0C'なら、答えは360個に絞れるということになる。結果が'4B0C'のときは、答えは1個、つまり推測がズバリ正解だったというわけだ。一番多い場合でも1440個。これを繰り返せば、徐々に答えが絞れていくから、8ターン繰り返せば確定できそうだな。

問題は、結果が'0B0C'だった場合に、次はどう推測すべきだろう？ランダムに推測を8ターン繰り返しても、答えが確定できるとは思えない。
そうか、正解が360個に絞れたら、次はその360個のうちの一つを返せばいい。そうすれば、少なくとも 1/360 で正解に当たるはずだ。当たらなくても、次の答えの分布を見て、さらに候補を絞ることができる。

あれ、これをそのまま書けばいいんじゃないか？
5040個の数字リストのなかから、結果（Bulls&Cows）が一致する数字だけを残していく。残った数字候補から1つ選んで戻り値にする。

まとめ

import itertools

def get_bulls_and_cows(guess, secret):
    bulls = cows = 0
    for u, g in zip(guess, secret):
        if u == g:
            bulls += 1
        elif u in secret:
            cows += 1
    return "{0}B{1}C".format(bulls, cows)

def checkio(data):
    if len(data) == 0:
        return '0123'  # 最初は0123

    numbers = [''.join(p) for p in itertools.permutations('0123456789', r=4)]  # 5040 numbers
    for s in data:
        guess, bull_cow = s.split(' ')
        # 5040個の数字の中から、BullsCowsが一致するものだけを残す
        numbers = [n for n in numbers if get_bulls_and_cows(guess, n) == bull_cow]
    # 残った数字から1つ選んで返す
    return numbers[0]

あれれ、すごく短く書けてしまった。

とりあえず、Run & Check...

なんとクリアしてしまった！
あんなに考えてもわからなかったのに、こんなあっさりと。

失敗ケースを分析

テストはクリアしたものの、すべての数字(5040個)で本当に8ターン以内に解けるのかテストしてみた。

for n in [''.join(p) for p in itertools.permutations('0123456789', r=4)]:
    check_solution(checkio, n)

かなり時間がかかるが、なんとか全部チェックが終わった。
正解までに必要なターン数(step)の分布も調べてみたが、次の通り。

step数	個数
1	1
2	13
3	108
4	596
5	1668
6	1768
7	752
8	129
9	5

残念ながら、8ターンでは解けず、9ターンまでかかる数字が5つあった。
5293, 9204, 9214, 9241, 9431

失敗例を分析してみると、例えば、5293の場合、8ターンでの引数(data)と、残った候補(numbers)はこうなっていた。
data = ['0123 1B1C', '0245 1B1C', '0356 0B2C', '1543 1B1C', '1625 0B2C', '4263 2B0C', '5273 3B0C']
numbers = ['5283', '5293']
残り2つにまで絞れているが、numbers[0]の'5283'を返したため、Failとなったのだ。

9204の場合
data = ['0123 0B2C', '1045 0B2C', '2354 1B1C', '2406 1B2C', '2560 0B2C', '3604 2B0C', '7204 3B0C']
numbers = ['8204', '9204']
こちらも同じように8ターンで2つの候補が残っている。

ターン数を減らすには、単純にnumbers[0]を返すのではなく、候補の中から、より答えに近いものを探す工夫が必要なのだろう。

他の人の答えを見るのは後日にして、とりあえず今日はこのくらいにしておく。
厳密にはクリアしたとは言えないが、自力でここまでできたので、よしとしよう。

（っていうか、8ターンっていう縛りは厳しすぎるよなぁ。10ターン以内でクリア、余裕のある人は7ターンを目指す、というようにしてほしい。）

summer_tree_home

Check iOでPython3をマスターするぜっ