Guest User

'Bulls and cows' solver

a guest
Nov 11th, 2012
1,046
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.  
  38. def number_is_consistent_with_qa(number, question, answer):
  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:
  45.         if all(number_is_consistent_with_qa(number, question, answer) for question, answer in history):
  46.             count += 1
  47.     return count
  48.  
  49.  
  50. def get_unique_possible_number(history):
  51.     for number in ALL_NUMBERS:
  52.         if all(number_is_consistent_with_qa(number, question, answer) for question, answer in history):
  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
  61.         for answer in POTENTIAL_ANSWERS:
  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.  
  99.     def put_answer(self, answer):
  100.         assert len(answer) == 2
  101.         self.history.append((self.last_question, answer))
  102.  
  103.     def get_step(self):
  104.         if self.is_finished():
  105.             return self.i if self.history[-1][1][0] == 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.
  122. For every question please answer two numbers: bulls and cows.
  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
  130.         if len(answer) != 2:
  131.             raise ValueError('your answer should contain exactly two numbers')
  132.         game.put_answer(answer)
  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))
  147.             answer = count_bulls_and_cows(number, question)
  148.             print('  Answer: {0}'.format(answer))
  149.             game.put_answer(answer)
  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()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×