Программа

Руками мы разобрали игру с порогом 21. На экзамене порог в сотни камней, а куч бывает две — там нужна программа. Как объяснить Python правила игры?

Правила записывают двумя функциями: moves — какие позиции получаются одним ходом, finished — кончилась ли игра. Для нашей игры +1 или ×2 до 21:

def moves(s):    return [s + 1, s * 2]  def finished(s):    return s >= 21  print(moves(10), finished(20), finished(21))

Всё, что зависит от условия, живёт в этих двух функциях. Остальная программа одна на все игры темы: для новой задачи переписывают только moves и finished.

Как записать «есть хотя бы один ход» и «все ходы»?

any — верна ли хотя бы одна проверка, all — верны ли все. Из 11 можно получить 12 и 22. Кончает ли игру хоть один ход? А все?

nxt = moves(11)print(nxt)print(any(finished(q) for q in nxt))print(all(finished(q) for q in nxt))

Внутри скобок — генераторное выражение: для каждой позиции q из nxt проверить finished(q). Это и есть два правила подтемы 1: на своём ходе хватает одного удачного — any, на ходе соперника нужны все — all.

Как найти группу позиции программой?

Функция g(s) проверяет четыре определения в том же порядке, что и разбор от конца, и возвращает число: 1 — В1, −1 — П1, 2 — В2, −2 — П2, 0 — до победы больше двух ходов. Знак — кто выигрывает: плюс — тот, кто ходит, минус — его соперник. Число — каким по счёту ходом всё решится, как цифра в названии группы.

def moves(s):    return [s + 1, s * 2]  def finished(s):    return s >= 21  def g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  print(g(9))

Разберём строки по очереди:

• any(finished(q) for q in nxt) — есть ход, который кончает игру: В1.
• r = [g(q) for q in nxt] — группы всех позиций, которые получит соперник. Здесь функция вызывает саму себя. В этих позициях ходит уже соперник, поэтому 1 в списке r — это его В1, а не наша.
• all(x == 1 for x in r) — все ходы ведут в В1: П1.
• -1 in r — в списке есть −1, то есть ход, после которого соперник в П1: В2.
• all(x > 0 for x in r) — все ходы ведут в В1 или В2: П2. Положительные числа только у этих двух групп.

Порядок проверок важен. До строки В2 доходят, только если позиция не В1 и не П1, — ровно как в определении. Пройди вызовы g(9) по шагам:

Отдельного базового случая у функции нет: его роль играет строка В1. Каждый вызов идёт к позициям с большим числом камней, а из большой кучи какой-то ход кончает игру — функция сразу возвращает 1 и дальше не спрашивает. На этом рекурсия и останавливается.

Зачем над функцией пишут @cache?

В одну позицию можно прийти разными путями, и без запоминания g считает её заново каждый раз. В 10 приходят и из 9, и из 5, а с двумя кучами путей к одной позиции десятки.

В задаче темы с двумя кучами функция без запоминания делает почти 90 миллионов вызовов и считает около 40 секунд. С @cache — меньше двух тысяч вызовов, и ответ появляется сразу. Запоминание — две строки:

from functools import cache  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0

Формула функции не меняется: @cache только запоминает ответ для каждой позиции и при повторном вызове берёт его готовым.

Как получить ответы на задания 19, 20 и 21?

Перебрать все начальные S и отобрать нужную группу: задание 20 — g(s) == 2, задание 21 — g(s) == -2. Задание 19 в форме «при любом ходе Пети» — это g(s) == -1. А для неудачного хода Пети нужна своя проверка: есть ход Пети, после которого Ваня выигрывает сразу.

from functools import cache  def moves(s):    return [s + 1, s * 2]  def finished(s):    return s >= 21  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  def mistake(s):    # Петя ходит так, что Ваня выигрывает сразу    return any(not finished(q) and g(q) == 1               for q in moves(s))  starts = range(1, 21)print(min(s for s in starts if mistake(s)))print([s for s in starts if g(s) == -1])print([s for s in starts if g(s) == 2])print([s for s in starts if g(s) == -2])

Это те же числа, что в ручном разборе: 6 для неудачного хода, 10 — П1, 5 и 9 — В2, 8 — П2. Так программу и проверяют: сначала на маленькой игре, где ответ известен, потом меняют правила.

В mistake стоит not finished(q): если ход Пети кончил игру, Петя выиграл — это не ошибка. Диапазон range(1, 21) — все S из условия, от 1 до 20: правая граница в range не входит.

Программа нашла список значений. Что записать в ответ?

Ровно то, что спрашивает условие: из одного списка берут разные части. Пусть подходящие S собраны в found = [s for s in starts if g(s) == 2]:

все значения

print(*found)через пробел по возрастанию

наименьшее

min(found)одно число

наибольшее

max(found)одно число

два наименьших

found[:2]первые два — список уже по возрастанию

наименьшее и наибольшее

min(found), max(found)в порядке условия

количество

len(found)сколько значений

Если в ответе два числа, их пишут через пробел в том порядке, что назван в условии: для задания 20 нашей игры — 5 9.

• Правилаmoves и finished — дословно по условию
• anyхотя бы один ход — свой ход
• allвсе ходы — ход соперника
• g(s)1, −1, 2, −2 — В1, П1, В2, П2; 0 — дальше
• @cacheкаждую позицию считаем один раз
• Задания19 — mistake или −1, 20 — 2, 21 — −2
• Проверкаигра +1, ×2 до 21: 6, [10], [5, 9], [8]