Если вы не знаете, что такое 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_07.ex

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

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

Решение проблем — это навык, которым должны овладеть все разработчики программного обеспечения. Однако иногда мы недостаточно обучаем его, возможно, потому, что мы только передаем данные из веб-фреймворка в базу данных, или потому, что мы используем слишком простые API, которые делают всю тяжелую работу за нас.

К счастью для нас, появился код, который может помочь нам натренировать наши умственные способности для решения проблем. 💪

Задача Day 07 напомнила мне о том, как я впервые столкнулся с функциональным программированием. Я прошел курс Erlang, посвященный рекурсивному преобразованию данных с использованием списков и вызовов хвостовой рекурсии.

На сегодняшний день я толком не знаю, что включает в себя стандартная библиотека Erlang, но мне удалось создать свои собственные функции более высокого порядка, анализируя данные и выполняя сложные преобразования списков.

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

Не поймите меня неправильно. Я использовал ряд инструментов, предоставляемых стандартной библиотекой, но «основные» функции, выполняющие итерации и определяющие, какие действия выполнять, были набраны мной. ⌨

Итак, первая часть задачи была относительно легкой. Вам предоставляется ваш ввод, содержащий ряд шагов и их соответствующих зависимостей. Например, если шаг A требует, чтобы вы сначала решили шаг B, вы вернете строку "BA".

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

Не так уж и сложно, если честно. 🙂 Я использовал функцию Эликсира, называемую хвостовыми рекурсивными вызовами. Это означает, что вы можете использовать рекурсивные функции для преобразования данных (обычно итерации по списку) столько раз, сколько хотите, без проблем с переполнением стека. При таком типе рекурсивной операции вы не храните в памяти данные, которые использовали каждый раз, когда рекурсивно вызываете функцию. Вместо этого вы передаете данные, которые хотите использовать в следующей итерации, в качестве аргумента, а все остальное удаляется из памяти, и ваша программа возвращается к началу функции.

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

Теперь вторая часть испытания была намного сложнее. Чтобы выполнить его, вам нужно было организовать те же шаги, что и для предыдущего задания. Но на этот раз вы можете запускать более одной задачи одновременно. 😓

Учитывая количество рабочих, нужно было организовать задачи так, чтобы они выполнялись за минимальное количество времени. Время, которое занимает каждая задача, определяется их индексом в алфавите (так, задача A занимает 1 секунду, задача B занимает 2 и т. д.) плюс задержка в заданное количество секунд.

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

Итак, как я решил задачу? Ну, это может сбивать с толку, но если у вас есть какие-либо сомнения, обязательно оставьте комментарий 👇, отправьте мне твит 💬 или проверьте код.

  • Прежде всего, мы должны разобрать данные. В этом случае я использовал структуру данных ключ-значение. Ключом является каждый шаг и список его зависимостей в качестве значения. Зависимости — это шаги, которые должны быть выполнены, прежде чем можно будет выполнить шаг.
  • Затем сделайте так, чтобы шаги, не имеющие зависимостей, выполнялись первыми.
  • Если шагов, которые можно выполнить, больше, чем рабочих, поместите их в список ожидания.
  • Всякий раз, когда вы ставите задачу на выполнение или в список ожидания, удалите их из набора шагов.
  • Затем передайте все данные рекурсивной функции. Каждый вызов этой функции будет имитировать секунду.
  • В каждой итерации добавляйте одну секунду к выполняемым задачам.
  • Как только количество секунд, необходимое для каждой задачи, будет достигнуто, удалите ее из текущего набора.
  • Удалите завершенные задачи из зависимостей, которые есть у каждого шага.
  • Если есть задачи, готовые к запуску, добавьте их в список ожидания.
  • Если запущенных задач меньше, чем рабочих, добавьте задачи для запуска из списка ожидания.
  • Продолжайте итерацию… не забывайте следить за количеством итераций, которое будет равно количеству секунд.
  • Помните, что у вас должен быть базовый случай. Для этой проблемы, когда нет ни запущенных задач, ни задач в списке ожидания, ни пропущенных шагов, вы можете вернуть количество секунд.

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

Что ж, это был хороший вызов! Много рекурсии, но именно так это делается с Эликсиром. 😀

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

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

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