21.01 Теория игр

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во таблеток в куче стало более 112
    if heap > 112:
        # Возвращаем 1,
        # которая преобразуется в победу Тринити первым ходом из-за "плохого" хода Нео
        return 1

    # Если кол-во таблеток в куче стало не менее 45
    if heap >= 45:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 2), game(heap * 3)]

    # Находим значения, через которые может победить Нео
    neo_win = [i for i in moves if i <= 0]

    if neo_win:  # Если такие значения нашлись и список не пуст
        return -max(neo_win) + 1
    else:  # Иначе побеждает Тринити максимальным ходом
        return -max(moves)


# Нео - первый игрок
# Тринити - второй игрок
for S in range(1, 44 + 1):
    # Если в данной позиции Тринити гарантированно выигрывает своим вторым ходом
    if game(S) == -2:
        print(S)  # В ответ берём последнее выведенное значение

Решение АР

from functools import lru_cache

def moves(heap):
    return heap + 2, heap * 3

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(44, 0, -1):
    if game(s) == ’LOSE2’:
        print(s)
        break