Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/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()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement