Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Bulls and Cows by Sim0000
# This code is guaranteed to solve all problems within 8 steps.
from itertools import permutations
def calc(x, y):
hit = sum(x[i] == y[i] for i in range(4))
blow = sum(x[i] in y for i in range(4))
return (hit, blow - hit)
def maketable(hints):
table = []
for p in permutations('1234567890', 4):
if p in hints: continue
for h in hints:
if calc(p, h) != hints[h]: break
else:
table.append(p)
return table
def checkio(data):
if len(data) == 0: return '1234'
# compile hint
hints = {}
for h in data:
a, b, c = h[:4], int(h[5]), int(h[7])
hints[tuple(a)] = (b, c)
# make all possible list and return decision
table = maketable(hints)
return ''.join(table[len(table) // 2])
#
# This code solve all problem within 8 steps.
# Distribution of steps is summerized below.
#
# steps count
# 1 1
# 2 13
# 3 108
# 4 604
# 5 1783
# 6 1891
# 7 604
# 8 36
#
# Average steps is 27544/5040 = 5.465079365079365
#
# Of course, This is not minimum.
# In 1996, Japanese researcher Tetsuro Tanaka proves 5.22 is the minimum
# by computer exaustive search [1].
# [1] Tetsuro Tanaka, "An Optimal MOO Strategy", Game Programming Workshop, Japan, 1996
# http://www.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/papers/gpw96.pdf
# Caution!! This paper written in Japanese.
#
# The worst case are listed below (we needs 8 step to solve it).
# 2168 2197 2359 2305 2468 2560 2570 2598 2731 2870
# 2097 3147 3462 3560 3642 3697 3075 3078 4172 4695
# 4721 4798 4790 4860 4078 4087 5128 5370 6349 6821
# 7143 7213 8126 8193 8510 9710
#
if __name__ == '__main__':
#This part is using only for self-checking and not necessary for auto-testing
def check_solution(func, goal):
recent = []
for step in range(7):
user_result = func(recent)
bulls = cows = 0
for u, g in zip(user_result, goal):
if u == g:
bulls += 1
elif u in goal:
cows += 1
recent.append("{0} {1}B{2}C".format(user_result, bulls, cows))
if bulls == 4:
print("{0} Win with {1} steps.".format(goal, step + 1))
return True
print("{0} Fail.".format(goal))
return False
assert check_solution(checkio, "1234"), "1234"
assert check_solution(checkio, "6130"), "6130"
assert check_solution(checkio, "0317"), "0317"
assert check_solution(checkio, "9876"), "9876"
Feb. 25, 2014
