116 lines
3.9 KiB
Python
116 lines
3.9 KiB
Python
"""
|
|
Naive cows and bulls brute force implementation.
|
|
Generates all possible numbers in a pool
|
|
"""
|
|
import random
|
|
|
|
|
|
def number_has_repeating_or_zero(number):
|
|
"""
|
|
Check the digits in the number and if any is repeating or 0, return True, False otherwise
|
|
"""
|
|
str_number = str(number)
|
|
used_numbers = []
|
|
for digit in str_number:
|
|
if digit == '0' or digit in used_numbers:
|
|
return True
|
|
used_numbers += [digit]
|
|
return False
|
|
|
|
|
|
def count_cows(number, guess):
|
|
"""
|
|
cows are how many digits in the guess are in the number but *NOT* correct position
|
|
"""
|
|
cows = 0
|
|
for pos, digit in enumerate(number):
|
|
if digit in guess and digit != guess[pos]:
|
|
cows += 1
|
|
return cows
|
|
|
|
|
|
def count_bulls(number, guess):
|
|
"""
|
|
bulls are how many digits in the guess are the same and in the correct position
|
|
"""
|
|
bulls = 0
|
|
for pos, digit in enumerate(number):
|
|
if digit == guess[pos]:
|
|
bulls += 1
|
|
return bulls
|
|
|
|
|
|
def is_number_guess_cb_match(number, guess, cows, bulls):
|
|
"""
|
|
The crux of the algo - the number and guess combo must match
|
|
the number of cows and bulls
|
|
"""
|
|
guess_cows = count_cows(number, guess)
|
|
guess_bulls = count_bulls(number, guess)
|
|
return guess_cows == cows and guess_bulls == bulls
|
|
|
|
|
|
def main():
|
|
"""
|
|
Generate all non-digit-repeating possible numbers between 1111 and 9999 excluding 0
|
|
that means that the first possible is 1234 and last is 9876.
|
|
Then chose a random number from the pool as the first guess, wait for input for cows and bulls,
|
|
prune the pool from impossible matches and repeat until 4 bulls
|
|
"""
|
|
number_pool = [i for i in range(1234, 9877) if not number_has_repeating_or_zero(i)]
|
|
assert len(number_pool) == 3024 # 9*8*7*6 = 3024
|
|
|
|
# input loop
|
|
done = False
|
|
print("Write cows and bulls as two digits separated by blank space, e.g. 2 0")
|
|
while not done:
|
|
print("There are {} options left. Press c to see them".format(len(number_pool)))
|
|
guess = random.choice(number_pool)
|
|
# input verification loop
|
|
while True:
|
|
guess_result = input("{} ?".format(guess))
|
|
guess_result = guess_result.strip().strip()
|
|
if guess_result in ['c', 'C']:
|
|
print(number_pool)
|
|
continue
|
|
# input verification - must be 2 digits between 0 and 4
|
|
splitted_guess = guess_result.split()
|
|
if len(splitted_guess) != 2:
|
|
print("wrong input")
|
|
continue
|
|
cows, bulls = splitted_guess
|
|
if not cows.isdigit() or not bulls.isdigit() or \
|
|
not 0 <= int(cows) <= 4 or not 0 <= int(bulls) <= 4:
|
|
print("wrong input")
|
|
continue
|
|
cows, bulls = int(cows), int(bulls)
|
|
if bulls == 4:
|
|
print("Done! Your number is {}".format(guess))
|
|
done = True
|
|
break
|
|
# generate new pool - all that don't match can't possibly be the number so eliminate them
|
|
number_pool = [x for x in number_pool if is_number_guess_cb_match(str(x), str(guess), cows, bulls)]
|
|
# do a new guess
|
|
break
|
|
|
|
def test():
|
|
assert number_has_repeating_or_zero(1234) is False
|
|
assert number_has_repeating_or_zero(1123) is True
|
|
assert number_has_repeating_or_zero(1322) is True
|
|
assert number_has_repeating_or_zero(1233) is True
|
|
assert number_has_repeating_or_zero(1230) is True
|
|
|
|
assert count_cows("1234", "4321") == 4
|
|
assert count_cows("1234", "5678") == 0
|
|
assert count_cows("1234", "1258") == 0 # but 2 bulls
|
|
assert count_cows("1234", "6581") == 1
|
|
assert count_bulls("1234", "1234") == 4
|
|
assert count_bulls("1234", "1258") == 2
|
|
assert count_bulls("1234", "4321") == 0
|
|
assert count_bulls("1234", "4132") == 1
|
|
|
|
|
|
if __name__ == '__main__':
|
|
test()
|
|
main()
|