Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Bulls and Cows - Computer Simulation Code
# Bulls and Cows - simulation code
# For more info refer to: http://buzypi.in/2005/12/18/bulls-and-cows-computer-simulation-results/
# (c) Gautham Pai
# http://buzypi.in/
# This code is released under GPL: http://www.gnu.org/licenses/gpl.html
import random
import sys
class System:
def __init__(self, secret_no=None):
if secret_no == None:
self.secret_no = self.create_secret()
else:
self.secret_no = self.get_padded_no(secret_no)
def create_secret(self):
secret_no = 'xxxx'
return ''.join([str(random.random())[-1] for item in secret_no])
def get_bulls_and_cows(self, guessed_no):
guessed_no = self.get_padded_no(guessed_no)
bulls = 0
cows = 0
cows_set = set()
for index in range(len(self.secret_no)):
if self.secret_no[index] == guessed_no[index]:
bulls = bulls + 1
guessed_no = guessed_no[:index] + 'x' + guessed_no[index+1:]
else:
cows_set.add(self.secret_no[index])
for digit in cows_set:
if digit in guessed_no:
cows = cows + 1
return bulls, cows
def get_padded_no(self, number):
return '0'*(4-len(number)) + number if len(number) != 4 else number
# 1. To play the game, uncomment these lines
#system = System()
#tried_upto = 0
#while True:
# guessed_no = raw_input(">")
# bulls, cows = system.get_bulls_and_cows(guessed_no)
# if bulls == 4:
# print "You got it!"
# sys.exit(0)
# print "Bulls: %s, Cows: %s" % (bulls, cows)
# 2. To try out a simulation of 2 players, uncomment these lines
def get_padded_no(number):
return '0'*(4-len(number)) + number if len(number) != 4 else number
def get_next_best_guess(bc_map, possible_numbers):
# Look for the next possible number
numbers_to_remove = set()
for possible_number in possible_numbers:
# If possible_number was the number, would it have generated the same
# number of bulls and cows (matched all the solutions in the map)?
temp_system = System(str(possible_number))
for number, (bulls_in_old_try, cows_in_old_try) in bc_map.items():
bulls, cows = temp_system.get_bulls_and_cows(str(number))
if bulls == bulls_in_old_try and cows == cows_in_old_try:
continue
else:
numbers_to_remove.add(possible_number)
break
for number in numbers_to_remove:
possible_numbers.remove(number)
# Possible numbers contains the list of possible numbers now - the rest
# have been removed
# Let's now compute the digit weights - which is the sum of all the times
# the digit occurs in all possible numbers
digit_weight_map = {}
for possible_number in possible_numbers:
digit_set = set()
for digit in get_padded_no(str(possible_number)):
digit_set.add(digit)
for digit in digit_set:
digit_weight_map[digit] = digit_weight_map[digit] + 1 if digit in digit_weight_map else 1
# With the given digit weights, which number is most probable - the one with
# most weight
max_weight = 0
max_weight_possibility = -1
for possible_number in possible_numbers:
total_weight = 0
digit_set = set()
for digit in get_padded_no(str(possible_number)):
digit_set.add(digit)
for digit in digit_set:
total_weight = total_weight + digit_weight_map[digit]
if total_weight > max_weight:
max_weight = total_weight
max_weight_possibility = possible_number
return max_weight_possibility, possible_numbers
def run_simulation(system):
guess = 1234
bc_map = {}
possible_numbers = set()
for i in range(10000):
possible_numbers.add(i)
while True:
# Could guess be the number?
bulls, cows = system.get_bulls_and_cows(str(guess))
if bulls == 4:
print "%s, %s" % (guess, len(bc_map) + 1)
return
# No, it was not, so we add it to the map
bc_map[guess] = (bulls, cows)
possible_numbers.remove(guess)
# If we don't have all the digits yet, try the next combination
if guess == 1234 and (bulls + cows < 4):
guess = 5678
continue
guess, possible_numbers = get_next_best_guess(bc_map, possible_numbers)
# Try for all numbers from 0 to 9999
for i in range(10000):
system = System(str(i))
run_simulation(system)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment