#!/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()