Я прошел все 8 «Пришествий кода» за один раз: вот уроки, которые я усвоил.

Контекст

В декабре прошлого года я завершил свое первое Пришествие кода: 2022. До этого у меня было в общей сложности около шести звезд за последние семь лет. Но в этом году мы создали приватную таблицу лидеров в Docker, и это мотивировало меня идти как можно дальше.

Для тех, кто не знаком с Advent Of Code, одно короткое слово: это адвент-календарь головоломок по программированию. Каждый год, начиная с 2015 года, Эрик Вастл выпускает в декабре новую головоломку каждый день до 25-го дня. Как правило, головоломки со временем усложняются.

Поскольку в декабре прошлого года, в начале 2023 года, мне было так весело, я решил бросить себе вызов: попытаться завершить все предыдущие годы и получить все возможные звезды. После написания 34 281 строк кода (без учета тестов) мне захотелось написать пост с описанием всех уроков, которые я усвоил в ходе этого поистине удивительного опыта 🚀.

ПРИМЕЧАНИЕ.Я закончил Advents Of Code в основном на Go и немного на Rust, но я буду держать этот пост как можно более независимым от языка.

Графики, графики и графики

Мне никогда не приходилось использовать причудливые структуры данных для завершения Advent Of Code. Тем не менее, нам нужно знать самые распространенные из них: массивы, связанные списки, стеки, очереди, кучи, деревья и… графы.

На мой взгляд, умение работать с графами абсолютно необходимо: как представить граф и наиболее распространенные алгоритмы. Для меня два алгоритма, которые я использовал чаще всего, были:

Поиск в ширину (BFS): позволяет вычислить кратчайший путь в невзвешенном графе.
Топологическая сортировка: позволяет сортировать вершины

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

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

A, B, C, D

Почему этот алгоритм важен? Возьмем в качестве примера 2019 день 14. Нам дан список химических реакций:

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

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

В целом, прохождение Advents Of Code позволило мне более комфортно работать с графами, и я открыл для себя неизвестные мне алгоритмы (например, использование Флойда–Уоршалла для вычисления длины кратчайших путей между всеми парами графов). вершины, которые я использовал для 2022 день 16 здесь). Advent Of Code — отличный способ изучить и попрактиковаться в алгоритмике.

Кодирование! = Разработка программного обеспечения

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

Тем не менее, написание кода для Advent Of Code или подобных задач — это совершенно другой контекст. Нам все равно, ремонтопригодно ли наше решение: мы единственные, кто работает над ним, и как только мы получаем две звезды, мы переходим к чему-то другому. Мы можем столкнуться со многими проблемами, которые не обязательно совпадают с теми, что возникают в нашей повседневной работе.

В (отличной) книге Разработка программного обеспечения в Google есть одна цитата, которая идеально резюмирует мою точку зрения:

«Инженерия программного обеспечения — это программирование, интегрированное во времени».

«Пришествие кода» снова заставило меня осознать, насколько иногда кодирование может отличаться от работы инженера-программиста. Как разработчики программного обеспечения, мы сталкиваемся с временным измерением, которое оказывает огромное влияние на нашу деятельность. Иногда к лучшему, иногда к худшему.

Если результат случайный, это отличный путь для следования

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

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

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

Как полагаться на инварианты алгоритма

Независимо от языка, который мы используем, у всех нас есть способы проверить утверждения; иначе говоря, проверяя предикаты в коде, которые всегда должны быть истинными. Я обнаружил, что иногда использование утверждений в моем коде было особенно полезным.

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

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

ПРИМЕЧАНИЕ. В Go мы можем, например, использоватьpanicдля семантического выражения: «это не ошибка как таковая; это фактическая ошибка, и такого случая быть не должно».

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

За пределами большого О

Обозначение Big O — отличный способ моделировать масштабирование алгоритма. Тем не менее, это далеко не единственная часть, которую следует учитывать. Например, мы можем разработать решение с квадратичной сложностью:O(n²). Однако при каком значении n наше решение станет слишком медленным для выполнения?

Это заставило меня осознать, что я далек от точного понимания того, сколько инструкций можно выполнить за приличное количество времени. Например, и вопрос в Go, но порядок или величина, вероятно, аналогичны для большинства языков программирования: сколько времени потребуется, чтобы получить 100 миллионов случайных записей из карты, содержащей тысячу значений (I намеренно разработали эксперимент не для использования кэшей ЦП)?

1 миллисекунда?
1 секунда?
10 секунд?
1 минута?
10 минут?

Ответ примерно одна секунда. Таким образом, для извлечения 100 миллионов случайных записей из карты длиной в тысячу значений требуется одна секунда.

Как только вы начнете понимать, что выполнимо за приличный промежуток времени, вы также сможете сопоставить свой большой О-анализ с вашим возможным решением. Конечно, в 2017 день 15 нам нужно было повторить операцию 40 миллионов раз, но моё решение выполняется менее чем за 20 миллисекунд.

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

ПРИМЕЧАНИЕ.Прекрасным дополнением к этому вопросу является страница, созданная Джулией Эванс и Камалем Мархуби: Знаете ли вы, сколько ваш компьютер может сделать за секунду? В нем приводится список примеров, показывающих, что программа может решить за секунду.

Изменчивость может быть источником ошибок

В течение 22 дня 2018 года нам дали способ сгенерировать карту (сама карта не является входными данными), и нам нужно было найти кратчайший путь из одной точки (M ) к другому (T). Одной из проблем было также то, что карта не была ограничена, и, возможно, кратчайший путь проходил через ряды ниже фактической цели (X обозначают кратчайший путь):

M=.|=.|.|=.|=|=.
XXXXX|||..|.=...
.==|X...||=..|==
=.|.X..|.==.|==.
=|..X=...=.|==..
=||.X.=||=|=..|=
|.=.X==|||..=..|
|..=X||=.|==|===
.=..XX=..=|.|||.
.====X=|||=|=.|=
.===|X|===T===||
=|||.XX|==X.|=.|
=.=|=.XXXXX||==| <-- Passing through this row
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||

В своем решении я обновил две переменные параметра, добавив дополнительную длину:

func toCave(depth, targetCol, targetRow int) *Cave {
   const (
      extraRow = 100
      extraCol = 100
   )

   targetCol += extraCol // Mutate parameter variable
   targetRow += extraRow // Mutate parameter variable
   // ...
}

Этот код действителен на 100%: переменные в Go изменяемы. Тем не менее, мне было очень больно понять, почему мое решение не проходит. Действительно, в этой функции я использовал targetCol и targetRow двумя разными способами:

Чтобы представить максимальный размер 2D-массива
Но и указать координаты цели

В обоих случаях это было глупо. Для первого это была семантическая проблема; Я использовал переменную с именем targetXXX для чего-то, что на самом деле не было целью. И для последнего это была чистая ошибка, потому что цель, которую я искал (T), больше не была фактической целью из-за этой дополнительной дельты, которую я добавлял.

В моем случае я должен был создать две новые переменные:

func toCave(depth, targetCol, targetRow int) *Cave {
   const (
      deltaRow = 100
      deltaCol = 100
   )

   totalCol := targetCol+ deltaCol // New variable
   totalRow := targetRow + deltaRow // New variable
   // ...
}

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

Что, если решение решает пример, но не решает задачу

Я почти уверен, что это случается со всеми нами. Мы внедряем решение, запускаем его на небольшом примере, приведенном в дневном описании, и тест проходит. Затем мы запускаем наше решение против нашего ввода головоломки и уверенно нажимаем «Отправить», но мы получаем это:

Первое, что я делаю в этом случае (помимо подозрения на ошибку в решениях Advent Of Code, что никогда так не бывает), запускаю успешный тест, используя функцию покрытия кода моей IDE:

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

Когда вы застряли на 1/3: попробуйте визуализировать свои данные

Если вы застряли на проблеме, один из возможных подходов — попытаться визуализировать ваши данные.

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

pos=<-34870395,34498817,-2843154>, r=96244937
pos=<-52741579,9875242,37136273>, r=89509114
pos=<23303891,41664349,2510522>, r=63042453
pos=<10573027,54782809,49932958>, r=97928881
pos=<30268215,-1711562,83940876>, r=91888282
...

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

Благодаря этому я придумал алгоритм, который:

Делит все координаты на миллион, выбирает наиболее интересную область и копается в ней.
Затем делит координаты на 100 тысяч, выбирает наиболее интересную область и копается в ней.
И т. д.

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

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

Когда вы застряли на 2/3: попробуйте другой подход

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

Например, 2015, день 19, часть 2 (задача с некоторыми преобразованиями строк) я потратил слишком много времени, пытаясь решить задачу от начала до цели, тогда как мне потребовалось всего несколько минут, чтобы решить ее другим способом. вокруг, от цели до старта.

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

Когда вы застряли на 3/3: идите займитесь чем-нибудь другим или идите немного поспите!

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

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

ПРИМЕЧАНИЕ.У меня возникли трудности с выполнением этого совета. В некоторых случаях я работал до умственного истощения. Иногда легко дать совет, которому сам не следуешь!

Появление кода заставило меня снова полюбить алгоритмы и структуры данных

Не знаю, как вам, но лично мне чаще всего приходится использовать структуры данных (я имею в виду вне просто массивы и карты), когда я готовлюсь к собеседованиям по программированию. И из-за этого контекста я склонен ассоциировать эти темы с чем-то сдерживающим: я делаю это не потому, что мне это нравится; Я делаю это, потому что должен.

Благодаря Advent Of Code я снова полюбил работать над алгоритмикой. Я начал читать Расширенные алгоритмы и структуры данных Марчелло Ла Рокка, потому что хочу расширить свои знания за пределы базовых структур данных, которые мы должны знать во время собеседований по кодированию, таких как деревья K-d, кластеризация, кучи d-way, градиентный спуск и т. д. , В этой области есть чему поучиться. Это действительно увлекательно.

Заключение

Огромное спасибо Eric Wastl и всем людям, работавшим над Advent Of Code ❤️. Я не могу нахвалиться, насколько замечательным был мой опыт, и если вы не знакомы с Advent Of Code или немного сопротивляетесь, вам обязательно стоит попробовать!

А пока вот мой репозиторий на GitHub:

GitHub — teivah/advent-of-code: 🎄 Мои решения для появления кода с 2015 по 2022 год.
github.com

Бонус

Нормально ли так сильно бороться за реализацию двусвязного списка в Rust? Поскольку такой веб-сайт существует, мне кажется, что да.
3D это сложно! По крайней мере для меня. Я никогда не умел визуализировать данные в трехмерном пространстве. Я очень боролся с такими днями, как 2021 день 21 или 2022 день 22 часть 2 (нет, не 3D-куб! 😱).
Люди, соревнующиеся за глобальную таблицу лидеров, действительно великолепны. Среди них действительно выделяется бетаверос. Этот парень почти постоянно входит в топ-10 каждый день. Наличие таких людей заставляет вас оставаться скромным.
Если вы хотите начать Advent Of Code, я бы порекомендовал вам либо начать создавать собственную библиотеку, либо повторно использовать существующую. Например, активность по анализу входных данных головоломки должна быть максимально быстрой. Даже если вы не боретесь за место в таблице лидеров, важно сосредоточиться на реальной проблеме. Следовательно, важно полагаться на библиотеку общих утилит. Если вы используете Go, вы можете взглянуть на тот, который я построил здесь. Я также сделал небольшой скрипт для создания нового проекта и автоматического импорта ввода головоломки.