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()

Как эту программу нужно изменить, чтобы включить поиск мин / макс в свой алгоритм?

0 ответов

Другие вопросы по тегам