POC Bagel Solver
После недавней встречи с Bagel Game моей целью было выяснить, как создать решатель, который мог бы помочь кому-то сделать умные догадки о том, каким может быть выбранное число. Чтобы создать решатель, нужно знать правила игры. Они заключаются в следующем:
- Есть секретный хранитель (или "выбор номера") и игрок (или "догадчик номера").
- Секретный хранитель (SK) и игрок (P) по очереди взаимодействуют друг с другом.
- SK создает число, используя цифры 0 - 9.
- Ни одна из цифр в номере не может появляться более одного раза.
- В результате построенное число должно содержать от 1 до 10 цифр.
- Как только SK выбрал число, P пытается угадать, что это за число.
- SK возвращает абсолютно правдивую информацию в P на основе каждого предположения.
- Игра заканчивается, когда Р угадывает секрет или слишком много раз угадывает.
Когда SK отвечает на предположение P, ответ всегда имеет вид следующего:
- "Рогалики" говорят один раз, если догадка не имеет ничего общего с секретом.
- "Ферми" произносится один раз для каждой цифры, которая соответствует положению в догадке и секрете.
- "Пико" произносится один раз для каждой цифры, которую догадка имеет общее с секретом, но не с позицией.
- П не получает никакой дополнительной информации из порядка слов в ответе от СК.
Учитывая вышеизложенные правила, была разработана следующая программа для проверки концепции:
#! /usr/bin/env python3
import itertools
import random
import sys
def main():
digits = get_digits()
all_possible = list(itertools.permutations(range(10), digits))
while True:
print('There are', len(all_possible), 'candidates.')
if not all_possible:
print('Someone must be confused ...')
sys.exit()
candidate = random.choice(all_possible)
print('Try the number', ''.join(map(str, candidate)))
pico, fermi, bagels = get_answer(digits)
if bagels:
for index, number in reversed(tuple(enumerate(all_possible))):
if any(a == b for a, b in itertools.product(number, candidate)):
del all_possible[index]
else:
for index, number in reversed(tuple(enumerate(all_possible))):
pico_test, fermi_test = test_number(number, candidate)
if pico_test != pico or fermi_test != fermi:
del all_possible[index]
assert candidate not in all_possible
def get_digits():
while True:
try:
answer = int(input('How many digits are there in the number? '))
except (EOFError, KeyboardInterrupt):
sys.exit()
except ValueError:
print('Please enter a number.')
else:
if 1 <= answer <= 10:
return answer
print('Please enter a number between 1 and 10.')
def get_answer(digits):
while True:
try:
answer = input('What answer was given? ')
except (EOFError, KeyboardInterrupt):
sys.exit()
else:
if not answer:
print('Please tell me what was said.')
continue
pico = fermi = bagels = 0
for word in answer.lower().split():
if 'pico'.startswith(word):
pico += 1
elif 'fermi'.startswith(word):
fermi += 1
elif 'bagels'.startswith(word):
bagels += 1
else:
print(f'Did not understand {word!r}')
break
else:
# input was accepted; now validate
if pico + fermi + bagels == 0:
print('Please tell me what was said.')
continue
if bagels > 0:
if bagels > 1:
print('There cannot be more than one bagel.')
continue
if pico or fermi:
print('Bagels cannot appear with pico or fermi.')
continue
return pico, fermi, bagels
if fermi + pico > digits:
print('Pico and fermi cannot be more than digits.')
continue
if fermi == digits:
print('Congratulations! We have won.')
sys.exit()
return pico, fermi, bagels
def test_number(number, candidate):
pico = fermi = 0
for a, b in zip(number, candidate):
if a == b:
fermi += 1
elif b in number:
pico += 1
return pico, fermi
if __name__ == '__main__':
main()
Как эту программу нужно изменить, чтобы включить поиск мин / макс в свой алгоритм?