Я ожидаю, что если вы выбрали эту статью для чтения, вы, вероятно, уже знаете, что такое Advent of Code (AoC) … но если вы этого не знаете, это серия из 25 задач по кодированию, которые Эрик Вастл решает каждый раз. Декабрь.
Каждая из них представляет собой проблему, которую вы теоретически могли бы решить самостоятельно, если бы у вас было сорок две тысячи лет… но, конечно же, у вас ее нет, поэтому вместо этого вы пишете компьютерную программу для ее решения. Обычно они относятся к какой-либо математической или компьютерной концепции, такой как двоичные числа, клеточные автоматы или деревья (нет, не тот вид или такой тип, а ТАТОЙ вид).
В этом году я решил впервые попробовать челлендж:
- Я писал свои программы на Ruby (нечетные дни) и JavaScript (четные дни).
- Только с использованием стандартных библиотек этих языков
- Без поиска решений в Интернете (поиск общих понятий, таких как «как преобразовать двоичное число в десятичное», вполне допустим)
- Попытка следовать лучшим практикам программирования (DRY, написание функций, которые делают только одну вещь и т. д.), вместо того, чтобы просто пытаться написать как можно более компактный код.
Моя первоначальная цель состояла в том, чтобы выполнить все задание до написания этого поста, но, увы, некоторые из последних дней оказались настолько сложными, что я думаю, что лучше взять перерыв и вернуться к ним со свежим взглядом.
ВНИМАНИЕ: ВПЕРЕД СПОЙЛЕРЫ. ВЫ МОЖЕТЕ СЛЕДИТЬ ЗА МОИМИ РЕШЕНИЯМИ ЗДЕСЬ
Что я извлек из этого?
- Освойте регулярные выражения. В Advent of Code входные данные для ваших задач не приходят в аккуратном формате, готовом к использованию в программе, например JSON. Он поставляется в виде текстового файла, и разбор его содержимого — полдела. Таким образом, задействовано много символов /\s\d+/ (нет, если вам интересно, это не смайлик, он соответствует пустому пространству, за которым следует одна или несколько цифр.)
- Осознайте важность порядка роста. Когда вы впервые слышите об O-значениях и Θ-значениях при обучении кодированию, легко подумать: "Это хорошо, но для меня все это греческое". (я имею в виду, Θ буквально!),но ваша типичная элементарная задача кодирования обычно решается за долю секунды, независимо от насколько эффективно вы ее решаете. Но были дни, когда порядок роста действительно имел большое значение (например, см. День 15 ниже).
- Осознайте важность размышлений перед написанием кода. Перед каждым испытанием я имел привычку записывать шаги своего алгоритма словами или псевдокодом, просто чтобы знать, что я делаю, прежде чем писать код. (Вы можете увидеть это в комментариях над каждым файлом в моем репозитории). Иногда я оказывался в затруднительном положении и нуждался в прогулке на улице, и тогда мне приходило возможное решение. Но нет смысла писать код, пока вы не знаете, что пишете.
- Научитесь не переусердствовать. Иногда я тратил много времени на написание общей функции с большим количеством аргументов, которые могли бы подойти для множества различных сценариев, но это занимало у меня пару часов, когда мне действительно нужно было решить только одну проблему. под рукой. Иногда (см. День 25 ниже) самым быстрым решением является грубая сила.
Но без лишних слов, вот как дела шли день за днем:
"1 день"
Алгоритм сегодняшнего дня фактически находится в другом файле, потому что я использовал его для практики наследования в Ruby. Это один из дней, когда я немного увлекся и попытался написать функцию, которая позволила бы мне определить, составляют ли четыре, пять или шесть чисел в списке желаемую сумму с помощью рекурсии. то есть, чтобы найти три числа, которые в сумме дают 2020, просто переберите список и для каждого числа X найдите два других числа в остальной части списка, которые в сумме дают 2020-X.
Довольно просто, если вы правильно проанализируете входной файл. Правила довольно произвольны, но именно в этот день я понял, что нет смысла пытаться написать универсальную программу, которая может обрабатывать другие типы правил: мне нужно применить эти правила только один раз.
Это было самое простое испытание для меня, мне понадобилось всего около 15 минут, чтобы закончить обе части. Как только я заметил, что во входном файле места были пронумерованы в двоичном формате (где «F» и «L» представляют «0», а «B» и «R» представляют «1»), to_i(2 ) достаточно для решения проблемы.
Почти уверен, что есть более эффективные способы обхода дерева, но я только что написал метод, чтобы определить, может ли мешок цвета A содержаться в мешке цвета B, и применил его рекурсивно.
Я начал с попытки повторно использовать метод, который написал в первый день, чтобы найти N чисел, которые в сумме составляют сумму. Но, потратив впустую много времени, я поймал себя на мысли: «Ну, довольно глупо пытаться найти 6 чисел во всем списке, которые в сумме составляют 3 базиллиона, когда мне нужно найти только 6 чисел в строке это дополняет это!»
Сначала это было сложно, но после того, как я написал несколько примеров карандашом и бумагой, я понял, что его можно решить с помощью последовательности, подобной Фибоначчи, за исключением того, что вам нужно добавить три предыдущих числа, чтобы получить следующее число последовательности. (Я уверен, что какой-то математик дал ей имя, вероятно, она называется последовательностью Шварцкопфа или что-то в этом роде, верно?)
Первая из нескольких задач на клеточный автомат, в которой большое количество пространств переключается между состояниями «включено» и «выключено» в зависимости от состояний их соседей. Я пытался придумать способ, как не писать отдельный код для управления тем, как места будут переключаться между занятыми и незанятыми во всех восьми направлениях, но не хотел тратить на это время, поэтому код доходит почти до 200. линии.
Часть 2 Дня 13 была одним из первых серьезных испытаний. Я действительно не хотел использовать грубую силу. Пытаясь свести к минимуму количество операций в алгоритме, я решил начать с выбора двух самых больших номеров автобусов (449 и 733) и найти время, при котором эти два автобуса прибывают вовремя. Это требует повторения от 0 до LCM 449 и 733, чтобы найти единственное число N, которое соответствовало бы критериям.
Теперь вы знаете, что решением по модулю (449 * 733) будет N. Итак, вы можете перебирать список, пока, наконец, не найдете единственное число между 0 и НОК всех номеров автобусов, которое соответствует необходимым критериям — что, кстати, оказывается более чем на 700 триллионов минут отсюда. Иначе известно как «количество времени, которое потребуется, чтобы решить эту проблему с помощью карандаша и бумаги»;)
Как и многие младшие программисты, я никогда не задумывался, почему && и || являются синтаксисом для операторов и и или во многих распространенных языках. Оказывается, & и | зарезервированы для выполнения побитовых операций и и или, как будто вы в основном применяете логический вентиль к одной паре нулей или единиц, как вы видите на первом курсе математики.
Проблема не слишком сложная, но я столкнулся с ограничениями JavaScript (побитовые операции работают только с 32-битными целыми числами, а способ обработки знаковых битов не идеален для этой задачи). Поскольку мы работаем с 36-битными целыми числами, в итоге я переписал программу на Ruby (который действительно правильно выполняет побитовые операции над bigint).
Сначала мне не удавалось решить задачу за разумное время, потому что я просил компьютер на каждом этапе игры выполнять итерацию в обратном направлении и находить самый последний раз, когда это число было произнесено. Таким образом, рост был квадратичным — увеличение количества шагов в 2 раза увеличило бы в 4 раза количество операций, которые код мог бы выполнить.
После того, как я вместо этого решил отслеживать в отдельном хэше (пары ключ-значение) самое последнее время произнесения каждого числа, программа теперь имела линейный рост O (N) и могла быть решена за 10 секунд времени выполнения, даже с Относительно медленный интерпретатор Ruby.
Это невероятно расстроило. Я обманул и импортировал пакет Node для деревьев интервалов, но за то время, которое у меня ушло на чтение документации и изучение его использования, я, вероятно, мог бы реализовать его сам.
Я долго не мог понять, как решить задачу, требующую декодирования текста, написанного на таинственном языке, поэтому я заставил программу записать вывод с середины задачи в файл, где я мог посмотри. Затем я понимаю, что есть один атрибут (тип), который вы можете определить сразу, а затем вы можете рекурсивно пройтись по остальным атрибутам и выяснить, какая часть билета является каким атрибутом, методом исключения.
Здесь я решил остальную часть проблемы вручную, используя выходной файл, вместо того, чтобы писать код для этого. (Однако аналогичная проблема возникает на 21-й день, и на этот раз я узнал решение и написал для него метод)
Проблема с клеточным автоматом №2. Я потратил массу времени на планирование этого, но в конце концов решил, что проще всего использовать один массив с ключами типа «202020» для обозначения местоположения в трехмерном пространстве вместо «20, 20, 20» и использовать трехмерный массив. . Но ключ был в том, чтобы написать несколько вспомогательных методов, решающих одну часть проблемы, сделать их модульными.
После решения части 1, часть 2 просто нуждалась во мне, чтобы добавить четвертое измерение. Это было довольно быстро, так как мне просто нужно было изменить один или два метода, а остальные продолжали работать. Ура!
Не буду врать, я думал о ядерном варианте: посмотреть, могу ли я просто переопределить, что «+» или «x» стоит первым в порядке операций в JavaScript, временно изменив основные библиотеки языка. Черт, это могло бы быть даже выполнимо в Ruby, с таким количеством обезьяньих исправлений… но проблема на самом деле была не так уж серьезна. На самом деле это дало мне гораздо больше признательности разработчикам, которые пишут стандартные математические библиотеки (или тем, кто выясняет, как воспроизвести математическую функцию C, скажем, в Python).
Дни 19 и 20
В первый день я не смог выполнить задание. Мой код не дает правильного результата, и, вероятно, есть лучший способ, который я могу использовать, который позволяет мне комбинировать регулярные выражения, но я пока не нашел решения.
Это вызвало у меня массу разочарований. Видите ли, игра с крабом гарантированно разрешается только при четном количестве карт. При нечетном количестве карт игра может зацикливаться в определенных ситуациях:
Player 1: 5, 1 Player 2: 2, 4, 3
Эта игра никогда не закончится, потому что «5» и «4» никогда не встретятся и, таким образом, бесконечно останутся в руках противоположных игроков. Вход головоломки состоит из 50 карт, поэтому ее можно решить.
Однако, когда я читаю содержимое входного файла, я разделяю его на новую строку, чтобы создать массив с числами в нем. Однако входной файл имеет новую строку в конце, а JS преобразовал пустую строку в конце в число «0», потому что я забыл обрезать! Таким образом, у меня на самом деле был лишний 0 в руке Игрока 2, что означало, что я моделировал игру с 51 картой, которая никогда не закончится. Я провел два часа, ожидая завершения программы (к тому времени она достигла 10-миллиардной итерации!), что удобно было как раз для 21-го дня.
Но после обнаружения ошибки я смог перейти ко второй части… где Эрик услужливо упомянул, что иногда игра может не закончиться, если есть нечетное количество карт, поэтому он добавил то, что шахматисты называют правилом «повторения позиции». . (Игрок 1 автоматически побеждает) Эй, спасибо, Эрик, было бы неплохо узнать об этом два часа назад!!
(Просто шучу.)
День 23 — наполовину готово
Я потратил некоторое время на размышления об этом, пытаясь придумать алгоритм. Но, не справившись с этим, я сделал часть 1, просто выполнив 100 итераций. Часть 2, требующая миллионов итераций с миллионами чашек, мне, вероятно, понадобится какой-то другой метод для решения, иначе мне придется ждать дольше, чтобы увидеть решение, чем для моей вакцины против COVID-19.*
\* Будучи здоровым молодым человеком, я, вероятно, окажусь в конце очереди.
Проблема с клеточным автоматом №3! К этому моменту я уже привык к ним, но здесь есть одна особенность: ячейки расположены на шестиугольной сетке, как на доске Settlers of Catan, а не в красивых рядах и столбцах, как пронумерованные улицы в Долина Фрейзер!
В своем решении я решил, что самым простым способом было бы определить одну из диагональных осей как ось Y, поэтому мне просто нужно было определить (1,1) и (-1,-1), но НЕ (1, -1) и (-1, 1) как соседние ячейки с (0,0).
Как только вы разобрались с сеткой, все становится довольно просто.
Был канун Рождества, поэтому очень не хотелось тратить время на выяснение того, как решить проблему. К счастью, Эрик, кажется, согласен — так что проблема может быть решена грубой силой за 15 минут.
"Просто найдите количество солей от 1 до 10 000, которые работают. Нет? Хорошо, попробуйте до 100 000 сейчас. Теперь попробуй миллион. Теперь попробуйте до 10 миллионов. АГА! Вот решение!»
Заключительные мысли
Мне определенно нужно освежить свои знания о структурах данных… это может помочь мне найти правильное решение раньше.
Спасибо Эрику за отличный набор головоломок! Это превратило процесс обучения кодированию и написанию алгоритмов в игру, и мы с нетерпением ждем следующего года!
