Привет, Хабр! ??

Меня зовут Олег Булыгин, я data scientist, аналитик, автор и спикер IT-курсов.

Я готовлю разный полезный контент, туториалы и руководства по Python, которыми бы хотел делиться с вами :)

Когда вы впервые учитесь программировать, вы ищете (или, возможно, вам поручают) проекты, которые нужны для закрепления базовых концепций языка. Но как часто вы, набравшись чуть-чуть больше знаний и опыта, пересматриваете такие проекты самых для начинающих?

В этой статье мы сделаем именно это. Вернёмся к стандартному проекту для начинающих — реализации игры «Камень, ножницы, бумага» на Python, посмотрев, как её можно «улучшить».

Правила игры «Камень-ножницы-бумага»

Прежде чем углубиться в код, давайте вспомним правила игры. Каждый из двух игроков выбирает один из трёх предметов: камень, бумагу или ножницы. Игроки одновременно сообщают друг другу о своём выборе, и победитель определяется по следующим правилам:

1. Камень бьёт ножницы.

2. Ножницы бьют бумагу.

3. Бумага бьёт камень.

При помощи этой игры можно решать очень многие "крайне важные" жизненные вопросы и споры :)

Требования

Давайте изложим некоторые требования к реализации. Вместо того, чтобы создавать полноценную игру, сосредоточимся на написании функции play(), которая принимает два строковых аргумента — выбор «камня», «бумаги» или «ножниц» каждым игроком — и возвращает строку, указывающую победителя (например, «бумага выигрывает») или, если игра заканчивается вничью, строку «ничья».

Вот несколько примеров того, как вызывается функция play() и что она возвращает:

play("камень", "бумага") 
# побеждает бумага
play("ножницы", "бумага")
# побеждают ножницы
play("бумага", "бумага")
# ничья

Если один или оба аргумента некорректны, то есть не являются "камень", "бумага" или "ножницы", функция play() должна вызвать какое-то исключение.

play() также должна быть коммутативной. Иными словами, вызов play("камень", "бумага") должна возвращать то же самое, что и play("бумага", "камень").

Решение для «начинающих»

В качестве базы для сравнения рассмотрим, как новичок мог бы реализовать функцию play(). Он, скорее всего, начал бы записывать целую кучу if:

def play(player1_choice, player2_choice):
    if player1_choice == "камень":
        if player2_choice == "камень":
            return "ничья"
        elif player2_choice == "бумага":
            return "побеждает бумага"
        elif player2_choice == "ножницы":
            return "побеждает камень"
        else:
            raise ValueError(f"Invalid choice: {player2_choice}")
    elif player1_choice == "бумага":
        if player2_choice == "камень":
            return "побеждает бумага"
        elif player2_choice == "бумага":
            return "ничья"
        elif player2_choice == "ножницы":
            return "побеждает камень"
        else:
            raise ValueError(f"Invalid choice: {player2_choice}")
    elif player1_choice == "ножницы":
        if player2_choice == "камень":
            return "побеждает камень"
        elif player2_choice == "бумага":
            return "побеждают ножницы"
        elif player2_choice == "ножницы":
            return "ничья"
        else:
            raise ValueError(f"Неверный выбор: {player2_choice}")
    else:
        raise ValueError(f"Неверный выбор: {player1_choice}")

Строго говоря, в этом коде нет ничего плохого. Он работает без ошибок и соответствует всем требованиям. Кроме того, он похож на ряд высоко ранжированных реализаций в поисковике по запросу "rock paper scissors python".

Однако чуть более опытные программисты сразу почувствуют запах неоптимальности, в таком решении очень много повторяющихся строк.

Продвинутое решение №1

Один из способов реализовать «Камень-ножницы-бумага» с чуть более продвинутой точки зрения подразумевает использование словарей. Словарь может сопоставлять предметы с теми, которые они обыгрывают в соответствии с правилами игры.

Давайте назовем этот словарь loses_to:

loses_to = {"камень": "ножницы", 
            "бумага": "камень", 
            "ножницы": "бумага" }

loses_to предоставляет простой интерфейс для определения того, какой элемент проигрывает другому:

loses_to["камень"] 
# ножницы
loses_to["ножницы"]
# бумага

С учётом этого, функцию play() можно было бы определить так:

def play(player1_choice, player2_choice): 
    if player2_choice == loses_to[player1_choice]: 
        return f"побеждает {player1_choice}"
    if player1_choice == loses_to[player2_choice]: 
        return f"побеждает {player2_choice}" 
    if player1_choice == player2_choice: 
        return "ничья"

В этой версии play() использует встроенную ошибку KeyError, вызванную словарём loses_to при попытке получить доступ к несуществующему ключу. Это позволяет легко обработать некорректный ввод. Таким образом, если какой-либо игрок выбирает несуществующий предмет — что-то вроде «ящерицы» или 1234 — play() вызывает KeyError:

play("ящерица", "бумага") 

Traceback (most recent call last): 
  File "<stdin>", line 1, in <module> 
  File "<stdin>", line 2, in play 
KeyError: "ящерица"

Хотя исключение KeyError не так информативно, как ValueError с точки зрения описания проблемы, но оно всё равно решает проблему.

Новая функция play() намного проще, чем изначальная. Вместо того чтобы обрабатывать кучу конкретных случаев, нужно обработать только три:

1. player2_choice проигрывает player1_choice

2. player1_choice проигрывает player2_choice

3. player1_choice и player2_choice одинаковые.

Однако есть четвёртый скрытый случай, на который стоит обратить внимание. Этот случай возникает, когда ни один из трёх других случаев не является истинным, и в этом случае функция play() возвращает значение None.

Но... может ли этот случай действительно произойти? На самом деле нет, не может. Согласно правилам игры, если игрок 1 не проигрывает игроку 2 и игрок 2 не проигрывает игроку 1, то оба игрока должны были выбрать один и тот же элемент.

Другими словами, мы можем удалить последний блок if из play() и просто написать return "ничья", если ни один из двух других блоков if не выполняется:

def play(player1_choice, player2_choice):
    if player2_choice == loses_to[player1_choice]:
        return f"побеждает {player1_choice}"
    if player1_choice == loses_to[player2_choice]:
        return f"побеждает {player2_choice}"
    return "ничья"

Мы пошли на компромисс. Мы пожертвовали понятностью кода — для понимания того, как работает вышеупомянутая функция play(), требуется бОльшая когнитивная нагрузка по сравнению с первой версией для начинающих, — чтобы сократить функцию.

Стоил ли этот компромисс того? It depends. Побеждает ли краткость эффективность?

Продвинутое решение №2

Предыдущее решение отлично работает. Оно в целом читабельно и намного короче, чем решение для «начинающих». Но оно не очень гибкое. То есть оно не может обрабатывать различные вариации игры без необходимости переписывать части реализации.

Например, есть вариация под названием «Камень, ножницы, бумага, ящерица, Спок» с более сложным набором правил:

1. Камень бьёт ножницы и ящерицу.

2. Бумага бьёт камень и Спока.

3. Ножницы бьют бумагу и ящерицу.

4. Ящерица бьёт Спока и бумагу.

5. Спок бьёт ножницы и камень.

Как можно адаптировать код, чтобы так расширить правила?

Сначала заменим строковые значения в словаре loses_to множествами. Каждое множество содержит все элементы, которые проигрывают соответствующему ключу. Вот как выглядит эта версия loses_to, использующая оригинальные правила "Камень-ножницы-бумага":

loses_to = {
    "камень": {"ножницы"},
    "бумага": {"камень"},
    "ножницы": {"бумага"},
}

Почему именно множества? Потому что нам важно только то, какие элементы проигрывают данному ключу. Нас не волнует порядок этих элемнтов.

Чтобы адаптировать play() для обработки нового словаря loses_to, всё, что нам нужно сделать, это заменить == на in, чтобы использовать проверку принадлежности вместо проверки равенства:

def play(player1_choice, player2_choice):
    #                 замена == на in
    if player2_choice in loses_to[player1_choice]:
        return f"побеждает {player1_choice}"
    #                 замена == на in
    if player1_choice in loses_to[player2_choice]:
        return f"побеждает {player2_choice}"
    return "ничья"

Можете проверить и убедиться, что всё работает корректно.

Теперь заменим loses_to словарём, реализующим правила для «Камень, ножницы, бумага, ящерица, Спок». Вот как это выглядит:

loses_to = {
    "камень": {"ножницы", "ящерица"},
    "бумага": {"камень", "Спок"},
    "ножницы": {"бумага", "ящерица"},
    "ящерица": {"Спок", "бумага"},
    "Спок": {"ножницы", "камень"},
}

Новая функция play() отлично работает и с новыми правилами:

play("камень", "бумага")
# побеждает бумага

play("Спок", "ящерица")
# побеждает ящерица

play("Спок", "Спок")
# ничья

Это отличный пример того, как важно выбрать правильную структуру данных. Используя множества для хранения всех нужных элементов, которые проигрывают ключу в словаре loses_to, и заменив == на in, мы создали более универсальное решение без необходимости добавлять строки кода.

Продвинутое решение №3

Давайте сделаем шаг назад и воспользуемся немного другим подходом. Вместо того чтобы искать элементы в словаре, чтобы определить победителя, мы составим таблицу всех возможных входных данных и их результатов.

Нам все ещё нужно что-то, чтобы представлять правила игры, поэтому давайте начнём с loses_to, как в предыдущем решении:

loses_to = {
    "камень": {"ножницы"},
    "бумага": {"камень"},
    "ножницы": {"бумага"},
}

Затем напишем функцию build_results_table(), которая принимает словарь правил, например loses_to, и возвращает новый словарь, который сопоставляет состояния с их результатами. Например, вот что build_results_table() должен возвращать при вызове с loses_to в качестве аргумента:

>>> build_results_table(loses_to)

{
    {"камень", "ножницы"}: "побеждает камень",
    {"бумага", "камень"}: "побеждает бумага",
    {"ножницы", "paper"}: "побеждают ножницы",
    {"камень", "камень"}: "ничья",
    {"бумага", "бумага"}: "ничья",
    {"ножницы", "ножницы"}: "ничья",
}

Если вы думаете, что тут что-то не так, вы правы. В этом словаре есть две ошибки:

1. Множества типа {"камень", "камень"} не могут существовать. Множества не могут содержать повторяющихся элементов. По факту это множество имело бы вид {"камень"}. На самом деле для нас это не проблема, это никак не повлияет на результат.

2. Нельзя использовать множества в качестве ключей словаря. Но мы хотим использовать множества, потому что они автоматически обеспечивают коммутативность. То есть {"камень", "бумага"} и {"бумага", "камень"} будут равны и, следовательно, должны возвращать один и тот же результат.

При помощи типа frozenset можно решить проблему с неизменяемостью, сравнением и использованием в качестве ключей словаря. Как и в случае с типом set, операции проверки принадлежности элемента проходят быстро. В отличие от типа set, экземпляры типа frozenset неизменяемы. Из-за этого они могут быть использованы в качестве ключей словаря.

Чтобы реализовать build_results_table(), вы могли бы перебирать каждый из ключей в словаре loses_to и создавать экземпляр frozenset для каждого из значений строк в наборе, соответствующих ключу:

def build_results_table(rules):
     results = {}
     for key, values in rules.items():
         for value in values:
             state = frozenset((key, value))
             result = f"побеждает {key}"
             results[state] = result
     return results

Благодаря такому подходу мы окажемся примерно на половине пути к цели:

build_results_table(loses_to)

# {frozenset({'камень', 'ножницы'}): 'побеждает камень',
# frozenset({'бумага', 'камень'}): 'побеждает бумага',
# frozenset({'бумага', 'ножницы'}): 'побеждают ножницы'}

Однако состояния, которые приводят к ничьей, не рассматриваются. Чтобы добавить их, вам нужно создать frozenset для каждого ключа в словаре правил, которые сопоставляются со строкой "ничья":

def build_results_table(rules):
     results = {}
     for key, values in rules.items():
         # Добавления состояния "ничья"
         results[frozenset((key,))] = "ничья"  # <— Новое
         # Добавление выигрышных состояний
         for value in values:
             state = frozenset((key, value))
             result = f"побеждает {key}"
             results[state] = result
     return results

Теперь значение, возвращаемое build_results_table(), выглядит правильно:

build_results_table(loses_to)

# {frozenset({'камень'}): 'ничья',
# frozenset({'камень', 'ножницы'}): 'побеждает камень',
# frozenset({'бумага'}): 'ничья',
# frozenset({'бумага', 'камень'}): 'побеждает бумага',
# frozenset({'ножницы'}): 'ничья',
# frozenset({'бумага', 'ножницы'}): 'побеждают ножницы'}

Зачем так заморачиваться? В конце концов, build_results_table() выглядит сложнее, чем функция play() из предыдущего решения.

Это так, но такой шаблон может быть весьма полезным. Если в программе может существовать конечное число состояний, иногда можно значительно увеличить скорость, предварительно рассчитав результаты для всех этих состояний. Это может быть излишеством для чего-то столь простого, как «Камень-ножницы-бумага», но может иметь огромное значение в ситуациях, когда существуют сотни тысяч или даже миллионы состояний.

Одним из реальных сценариев, в которых такой подход имеет смысл, является алгоритм Q-learning, используемый в приложениях для обучения с подкреплением. В этом алгоритме поддерживается таблица состояний — Q-таблица, которая сопоставляет каждое состояние с набором вероятностей для некоторых заранее определённых действий. Как только агент обучен, он может выбрать действие, основанное на вероятностях наблюдаемого состояния, а затем его выполнить.

Часто таблицу, подобную той, что генерируется build_results_table(), создают и затем сохраняют в файле. Когда программа запускается, предварительно вычисленная таблица загружается в память и затем используется приложением.

Итак, теперь, когда у вас есть функция, которая может создавать таблицу результатов, создадим переменную outcomes с её результатами:

outcomes = build_results_table(loses_to)

Теперь можно написать функцию play(), которая ищет состояние в таблице результатов на основе переданных аргументов, а затем возвращает результат:

def play(player1_choice, player2_choice):
    state = frozenset((player1_choice, player2_choice))
    return outcomes[state]

Эта версия play() невероятно проста. Всего две строки кода! Можно даже и одной написать:

def play(player1_choice, player2_choice):
    return outcomes[frozenset((player1_choice, player2_choice))]

Новая функция play() полностью соответствует правилам и является коммутативной:

play("камень", "бумага")
# побеждает бумага

play("бумага", "камень")
# побеждает бумага

play() даже вызывает KeyError, если она вызывается с некорректным аргументом, но текст ошибки теперь менее явный из-за того, что ключи являются frozenset:

play("ящерица", "бумага")

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 21, in play
    return outcomes[state]
KeyError: frozenset({'ящерица', 'бумага'})

Но это не будет серьёзной проблемой. Сейчас мы реализуем только play(). В реальной реализации мы, скорее всего, приняли бы ввод пользователя и проверили его перед передачей в качестве аргумента в функцию.

Итак, насколько быстрее эта реализация по сравнению с предыдущими? Вот результаты замера времени для сравнения производительности различных вариантов с использованием магической функции %timeit. play1() — это версия play() из раздела "Продвинутое решение №2", а play2() — текущая версия:

%timeit play1("камень", "бумага")
141 ns ± 0.0828 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%timeit play2("камень", "бумага")
188 ns ± 0.0944 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

В этом случае решение, использующее таблицу результатов, на самом деле работает медленнее, чем предыдущая реализация. Виновником здесь является строка, которая преобразует аргументы функции в frozenset. Таким образом, хотя поиск по словарю выполняется быстро, а построение таблицы, сопоставляющей состояния с результатами, потенциально может повысить производительность, нужно быть осторожным, чтобы избежать дорогостоящих операций, которые могут в конечном итоге свести на нет все выгоды, которые можно получить.

Заключение

Пересмотр своих старых проектов может быть очень полезным, это позволяет оценить свой прогресс в программировании и найти неочевидные способы улучшения кода. Как бы отличались реализации ваших самых первых проектов с высоты текущего опыта?

?Если тебе интересны и другие полезные материалы по Python и IT, то подписывайся на мой канал в tg: PythonTalk ?