19.06 Условие проигрыша

Решение БУ

from functools import lru_cache


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

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

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

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

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

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


# Олаф - первый игрок
# Свен - второй игрок
for S in range(1, 49 + 1):  # Перебор значений S
    # Чтобы Свен выиграл первым ходом при неудачном ходе Олафа нужно
    # сделать все возможные первые ходы Олафа вручную и
    # запустить функцию игры с уже изменённой кучей.
    # Тогда Свен для функции станет первым игроком и нужно будет искать значение 1.
    # Это работает, так как среди всех сделанных ходов Олафа можно будет отыскать неудачный
    if game(S + 1) == 1 or game(S + 2) == 1 or game(S + 3) == 1 or game(S * 3) == 1:
        print(S)
                                                                                                     
                                                                                                     
        break  # Первое выведенное значение и будет минимальным

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif any(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(1, 50):
    if game(s) == ’LOSE1’:
        print(s)
        break