solver.py

#!/usr/bin/env python3

import re
from math import log
from copy import copy
from random import shuffle, randrange, seed


seed(42)

NUM_DIGITS = 4


def is_allowed_number(number):
    return len(str(number)) == NUM_DIGITS and len(set(str(number))) == NUM_DIGITS


ALL_NUMBERS = [number for number in range(1000, 10000) if is_allowed_number(number)]
POTENTIAL_ANSWERS = [(0, 1), (0, 2), (1, 1), (1, 0), (0, 0), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0), (0, 4), (1, 3), (2, 2), (4, 0)]
# this order should accelerate the execution of question_entropy() 


def count_bulls_and_cows(number, question):
    number = str(number)
    question = str(question)
    bulls = 0
    cows = 0
    for i in range(NUM_DIGITS):
        for j in range(NUM_DIGITS):
            if number[i] == question[j]:
                if i == j:
                    bulls += 1
                else:
                    cows += 1
    return (bulls, cows)


def number_is_consistent_with_qa(number, question, answer):
    return count_bulls_and_cows(number, question) == answer


def count_possible_numbers(history, allowed_numbers):
    count = 0
    for number in allowed_numbers:
        if all(number_is_consistent_with_qa(number, question, answer) for question, answer in history):
            count += 1
    return count


def get_unique_possible_number(history):
    for number in ALL_NUMBERS:
        if all(number_is_consistent_with_qa(number, question, answer) for question, answer in history):
            return number


def question_entropy_by_history(history, allowed_numbers):
    current_min_entropy = 10 ** 9
    def question_entropy(question):
        nonlocal current_min_entropy
        result = 0
        for answer in POTENTIAL_ANSWERS:
            count = count_possible_numbers([(question, answer)], allowed_numbers)
            if count > 0:
                result += - log(1 / count) * count
                if result > current_min_entropy:
                    return result
        current_min_entropy = result
        return result
    return question_entropy


def get_best_question(step, history, current_allowed_numbers):
    if step > 1:
        for number in list(current_allowed_numbers):
            if not number_is_consistent_with_qa(number, *history[-1]):
                current_allowed_numbers.remove(number)

    sample = list(current_allowed_numbers)
    shuffle(sample)
    sample = sample[:10 ** (step - 1)]
    return min(sample, key=question_entropy_by_history(history, current_allowed_numbers))


class Game:
    def __init__(self):
        self.history = []
        self.i = 0
        self.current_allowed_numbers = set(ALL_NUMBERS)

    def is_finished(self):
        return count_possible_numbers(self.history, ALL_NUMBERS) <= 1

    def get_question(self):
        assert not self.is_finished()
        self.i += 1
        self.last_question = get_best_question(self.i, self.history, self.current_allowed_numbers)
        return self.last_question

    def put_answer(self, answer):
        assert len(answer) == 2
        self.history.append((self.last_question, answer))

    def get_step(self):
        if self.is_finished():
            return self.i if self.history[-1][1][0] == 4 else self.i + 1
        else:
            return self.i

    def is_correct(self):
        return count_possible_numbers(self.history, ALL_NUMBERS) > 0

    def guessed_number(self):
        return get_unique_possible_number(self.history)


def interactive_game():
    print("""This is 'Bulls and cows' solver
Author: Vitaly Pavlenko, http://vk.com/vitalypavlenko
Date: Nov 11 2012

Think of some number of four digits.  All digits should be different.
For every question please answer two numbers: bulls and cows.
Example: if your secret number is 1234 and my question is 1453, you should answer '1 2'.
""")
    game = Game()
    while not game.is_finished():
        question = game.get_question()
        print('Question #{0}: {1}'.format(game.get_step(), question))
        answer = tuple([int(i) for i in re.findall(r'[0-9]+', input())])  # should be a tuple of two numbers
        if len(answer) != 2:
            raise ValueError('your answer should contain exactly two numbers')
        game.put_answer(answer)
    if game.is_correct():
        print("Your number is {0}.  It took me {1} steps to guess it.".format(game.guessed_number(), game.get_step()))
    else:
        print("It seems that you've made a mistake somewhere.")


def test_all_numbers():
    worst_number_of_steps = 0
    for number in ALL_NUMBERS:
        print('Testing number {0}'.format(number))
        game = Game()
        while not game.is_finished():
            question = game.get_question()
            print('  Question #{0}: {1}'.format(game.get_step(), question))
            answer = count_bulls_and_cows(number, question)
            print('  Answer: {0}'.format(answer))
            game.put_answer(answer)
        assert game.is_correct()
        if game.get_step() > worst_number_of_steps:
            worst_number_of_steps = game.get_step()
        print('  Total number of steps:', game.get_step())
        print('  The worst one was:    ', worst_number_of_steps)


if __name__ == "__main__":
    interactive_game()
    # test_all_numbers()