Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
7 or fewer solution in Clear category for Bulls and Cows by nickie
from itertools import permutations
from collections import Counter
# Evaluate an attempt w.r.t. to the secret correct key
def evaluate(correct, attempt):
bulls = sum(1 for x, y in zip(attempt, correct) if x == y)
cows = sum(1 for x in attempt if x in correct) - bulls
return "{}B{}C".format(bulls, cows)
# All the 5040 == 3.38**7 permutations
everything = ["".join(r) for r in permutations("0123456789", 4)]
# Shuffling speeds things up considerably and (unfortunately) is required
# for correctness. But I'm using a fixed seed: my algorithm is not randomized.
from random import shuffle, seed
seed(42)
shuffle(everything)
# Solve
def checkio(data):
round = len(data)
if round == 0: return everything[0]
def is_consistent(guess):
return all(evaluate(guess, fact[0:4]) == fact[5:9] for fact in data)
consistent = frozenset(guess for guess in everything if is_consistent(guess))
tried = tuple(fact[0:4] for fact in data)
def safest(attempt):
return Counter(evaluate(guess, attempt)
for guess in consistent).most_common(1)[0][1]
remaining = len(consistent)
if remaining == 1: return min(consistent)
best = remaining + 1
good_enough = remaining / 3.38
solution = None
for guess in everything:
if guess not in tried:
this = safest(guess)
if this < best:
best, solution = this, guess
if this < good_enough and (round < 3 or guess in consistent):
break
return solution
Feb. 16, 2014
Comments:
