Bulls and Cows - Computer Simulation Code

bullsncows.py

# 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)