Если вы не знаете, что такое Advent of Code, обязательно ознакомьтесь с моими предыдущими сообщениями, где я объясняю, что это за событие, и мой опыт. (https://github.com/JPYamamoto/advent_of_code/#my-experience-solving-the-aoc)

Мое решение сегодняшних проблем:https://github.com/JPYamamoto/advent_of_code/blob/master/lib/advent_of_code_2018/day_09.ex

Репозиторий, в котором я размещаю все свои решения для Advent of Code 2018:https://github.com/JPYamamoto/advent_of_code/

Я уже несколько дней с нетерпением жду возможности опубликовать эту статью, потому что многому научился на девятом дне появления кода. 🤓

Задача была не очень сложной, но это была отличная возможность узнать о функциональных структурах данных.

Прежде всего, позвольте мне рассказать вам, что такое структура данных. Структура данных — это способ хранения информации в памяти. Некоторые структуры данных, с которыми вы, возможно, уже знакомы, — это списки (или массивы, в зависимости от используемого вами языка) и карты (также известные как словари, ассоциативные массивы). Хотя они оба могут содержать одинаковую или подобную информацию, они по-разному сохраняют ее в памяти компьютера. 🧠

Для простоты давайте проанализируем, как работают списки. Внутри список будет иметь набор элементов. Каждый элемент будет хранить часть данных (соответствующую определенному индексу в списке) и указатель на следующий элемент. Этот указатель укажет компьютеру, какой адрес в памяти посетить следующим, чтобы перейти к следующему элементу в списке.

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

Чтобы решить эту проблему, нам нужно использовать двусвязный список. Таким образом, чтобы посетить элемент n-1, нам нужно только следовать указателю, хранящемуся в элементе n.

Еще одна вещь, которую следует учитывать, это то, что в языках с изменяемыми типами становится довольно легко добавлять и удалять элементы из списка, независимо от их индекса. Но с такими языками, как Elixir, где типы неизменяемы, это может быть проблемой, так как вам нужно будет создать клон списка и отфильтровать элемент, который вы хотите удалить, или добавить элемент, который вы хотите вставить, при дублировании. Это. Таким образом, это становится довольно дорогостоящей задачей по мере увеличения списка. 😓

На этом небольшом фоне позвольте мне познакомить вас с сегодняшним испытанием, и давайте посмотрим, как мы можем справиться с ним в Эликсире.

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

Как только все ваши шарики будут размещены в круге (количество шариков указано во входных данных), побеждает игрок с наибольшим количеством очков. 😃

Как видно из описания игры, мы будем постоянно двигаться вперед и назад по списку. Если мы используем обычный список, возможно, у нас не будет проблемы, когда количество шариков невелико, но по мере роста числа наша программа может очень медленно решать задачу. Мы могли бы действительно извлечь выгоду из двусвязного списка, но как мы можем смоделировать такую ​​структуру данных?

Мы можем использовать молнию! 😮 Zipper — это структура данных, в которой у нас есть список, содержащий элементы до нашей текущей позиции, и другой список с нашим текущим элементом и элементами после него.

Я не буду вдаваться в подробности реализации, так как она может варьироваться от языка к языку, но если вы хотите глубже погрузиться в подход Erlang/Elixir, обязательно ознакомьтесь с Еще одна статья о Zippers, в Erlang от Фреда Хеберта.

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

После того, как вы внедрили собственную структуру данных Zipper, решить эту задачу становится очень просто. Вы можете просто повторять несколько раз (в зависимости от количества шариков), добавляя номер шарика в список Zipper и увеличивая счет только тогда, когда шарик кратен 23.

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

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

Задача 2 позволит вам узнать, насколько хорошо ваше решение. Если он недостаточно хорош (может быть, вы используете обычный список), скорее всего, вычисление решения займет очень много времени или может произойти сбой. Если вы использовали хороший подход, то все должно быть в порядке. 👊

Надеюсь, вы нашли этот пост интересным. Если да, не забудьте поставить лайк 👏 (или тридцать) и поделиться, чтобы охватить больше людей.

Если у вас есть какие-либо вопросы или вы просто хотите поболтать 💬, вы можете написать мне в личку, вот мой твиттер (JPYamamoto9).

Кроме того, если вам интересно узнать больше о Advent of Code, я предлагаю вам подписаться на меня, так как я буду ежедневно публиковать сообщения о проблемах этого года.