Advent of Code 2022

С подачи webholt решил поучаствовать в Advent of Code. О мероприятие знал последние 2-3 года, но не доходил порешать задачи в момент проведения. При этом загадки можно решать и постфактум, что не так интересно как в момент проведения соревнований. Это не первые головомки, в которые меня затягивало, в 2017 году мы с Владом уже игрались в CodeWars. А где-то под конец 2020 меня увлекли задачи с leetcode.

TL;DR: хорошее отвлечение мозгов от задачек на перекладывание json’ов.

Начнём с приватного дашборда, так как в общем зачёте у нас по нулям:

Advent of code выделяется среди них следующими пунктами:

1. Исходя из названия, используется структура advent календаря. Задачка появляется каждый день утром.
2. Для задачек есть одна сквозная история, как оказалось с пасхалками.
3. Все задачки деляться на две части, где вторая часть является усложнением первой.
4. Для задачек даётся один тестовый пример для отладки и одни входные данные, которые необходимо решить.
5. В качестве результата получается число. Ни программа, ни её оптимальности никого не интересует.
6. Для соревнований используется время: первые 100 получают от 1 до 100 баллов в общем зачёте. Но можно участвовать и в приватных соревнованиях, так как уровень олимпиадников в общем зачёте удручает вдохновляет.

Пункты 4 и 5 и отделяет advent of code от остальных площадок. Тебе не нужно задумываться о том, чтобы программа работала всегда. Нужно только чтобы работала на твоих данных. Минимум один раз в этом году, большинство (судя по реддиту) участников прибегли к очень большому хардкоду.

Не знаю, было ли так задумано автором головоломок, но общий тренд от задачек такой:

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

Все задачки для меня упали в следующие категории:

1. задачки на “пописать код”: никаких дополнительных знаний не нужно.
2. задачки на поиск граф: волновой алгоритм, Дейкстра, A*.
3. задачки на симуляцию: пописать код, но с поиском краевых кейсов и ошибок на 1 из-за нулевых индексов.
4. задачки на математику: просто пописать не получится, надо понять какие кейсы заранее не валидны.
5. задачки на поиск решений, как комбинация трёх предыдущих задач, надо построить граф по симуляции или симуляция по графу и понять как по нему оптимально бегать.

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

Так как все шли с разным темпам, переписка тоже превратилась в новогоднюю ёлку:

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

Перед собой ставил задачу в этом году завершить 18 задач, так как посмотрел 20+ задачки из прошлых годов. Остался доволен, что получилось пройти всё. Большое спасибо скажем нарастающей сложности задач. Причём самые сложными оказались совсем не последние задачи.

Собственный рейтинг наиболее сложных задач:

1. Симуляция пути на кубике в 22 дне
2. Симуляция ресурсов а ля RTS в 19 дне
3. Симуляция двух коммивояжеров на графе в 16 дне

Поставил себе на начало следующего года ещё немного порешать на leetcode задачи на графы, так как увидел свои пробелы. А так же, что граф решений - это все ещё граф. (: