 # 'Bulls and cows' solver

a guest
Nov 11th, 2012
1,203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python3
2.
3. import re
4. from math import log
5. from copy import copy
6. from random import shuffle, randrange, seed
7.
8.
9. seed(42)
10.
11. NUM_DIGITS = 4
12.
13.
14. def is_allowed_number(number):
15.     return len(str(number)) == NUM_DIGITS and len(set(str(number))) == NUM_DIGITS
16.
17.
18. ALL_NUMBERS = [number for number in range(1000, 10000) if is_allowed_number(number)]
19. 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)]
20. # this order should accelerate the execution of question_entropy()
21.
22.
23. def count_bulls_and_cows(number, question):
24.     number = str(number)
25.     question = str(question)
26.     bulls = 0
27.     cows = 0
28.     for i in range(NUM_DIGITS):
29.         for j in range(NUM_DIGITS):
30.             if number[i] == question[j]:
31.                 if i == j:
32.                     bulls += 1
33.                 else:
34.                     cows += 1
35.     return (bulls, cows)
36.
37.
39.     return count_bulls_and_cows(number, question) == answer
40.
41.
42. def count_possible_numbers(history, allowed_numbers):
43.     count = 0
44.     for number in allowed_numbers:
46.             count += 1
47.     return count
48.
49.
50. def get_unique_possible_number(history):
51.     for number in ALL_NUMBERS:
53.             return number
54.
55.
56. def question_entropy_by_history(history, allowed_numbers):
57.     current_min_entropy = 10 ** 9
58.     def question_entropy(question):
59.         nonlocal current_min_entropy
60.         result = 0
62.             count = count_possible_numbers([(question, answer)], allowed_numbers)
63.             if count > 0:
64.                 result += - log(1 / count) * count
65.                 if result > current_min_entropy:
66.                     return result
67.         current_min_entropy = result
68.         return result
69.     return question_entropy
70.
71.
72. def get_best_question(step, history, current_allowed_numbers):
73.     if step > 1:
74.         for number in list(current_allowed_numbers):
75.             if not number_is_consistent_with_qa(number, *history[-1]):
76.                 current_allowed_numbers.remove(number)
77.
78.     sample = list(current_allowed_numbers)
79.     shuffle(sample)
80.     sample = sample[:10 ** (step - 1)]
81.     return min(sample, key=question_entropy_by_history(history, current_allowed_numbers))
82.
83.
84. class Game:
85.     def __init__(self):
86.         self.history = []
87.         self.i = 0
88.         self.current_allowed_numbers = set(ALL_NUMBERS)
89.
90.     def is_finished(self):
91.         return count_possible_numbers(self.history, ALL_NUMBERS) <= 1
92.
93.     def get_question(self):
94.         assert not self.is_finished()
95.         self.i += 1
96.         self.last_question = get_best_question(self.i, self.history, self.current_allowed_numbers)
97.         return self.last_question
98.
102.
103.     def get_step(self):
104.         if self.is_finished():
105.             return self.i if self.history[-1] == 4 else self.i + 1
106.         else:
107.             return self.i
108.
109.     def is_correct(self):
110.         return count_possible_numbers(self.history, ALL_NUMBERS) > 0
111.
112.     def guessed_number(self):
113.         return get_unique_possible_number(self.history)
114.
115.
116. def interactive_game():
117.     print("""This is 'Bulls and cows' solver
118. Author: Vitaly Pavlenko, http://vk.com/vitalypavlenko
119. Date: Nov 11 2012
120.
121. Think of some number of four digits.  All digits should be different.
123. Example: if your secret number is 1234 and my question is 1453, you should answer '1 2'.
124. """)
125.     game = Game()
126.     while not game.is_finished():
127.         question = game.get_question()
128.         print('Question #{0}: {1}'.format(game.get_step(), question))
129.         answer = tuple([int(i) for i in re.findall(r'[0-9]+', input())])  # should be a tuple of two numbers
133.     if game.is_correct():
134.         print("Your number is {0}.  It took me {1} steps to guess it.".format(game.guessed_number(), game.get_step()))
135.     else:
136.         print("It seems that you've made a mistake somewhere.")
137.
138.
139. def test_all_numbers():
140.     worst_number_of_steps = 0
141.     for number in ALL_NUMBERS:
142.         print('Testing number {0}'.format(number))
143.         game = Game()
144.         while not game.is_finished():
145.             question = game.get_question()
146.             print('  Question #{0}: {1}'.format(game.get_step(), question))
150.         assert game.is_correct()
151.         if game.get_step() > worst_number_of_steps:
152.             worst_number_of_steps = game.get_step()
153.         print('  Total number of steps:', game.get_step())
154.         print('  The worst one was:    ', worst_number_of_steps)
155.
156.
157. if __name__ == "__main__":
158.     interactive_game()
159.     # test_all_numbers()