Advent of Code 2023

· 2 min read

В этом году получилось так, что это мне удалось затянуть @webholt в соревнование по Advent of Code. Вообще, план был такой, чтобы на работе попробовали 10-15 человек и дошли 2-3, но не сошлось. Правда, больше людей узнали об этом сайте, так что всё не зря. Подробнее о разных сайтах для решения задачки мы рассказывали в подкасте Два Ивана.

Начнём с того, что прошлый год не прошлом даром и опыт накапливается. Это видно по минимальным местам и медиане.

Места

Да, до призовых 100 мест ещё далеко, но и цели нет туда попадать. Большинство людей пропускают лор и шутки, имеют библиотеку заготовленных алгоритмов или знают типы загадок автора. И вот это про типы загадок мы поговорим отдельно.

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

СЛАУ

Если хочешь конкретику про математику
  • Были задачи на квадратные уравнение или скорее их нахождение во входных данных
  • Shoelace formula для вычисления точек внутри контура
  • Система линейных алгебраических уравнение в трёхмерном пространстве

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

  • cycle detection, то есть нам дают посчитать 1_000_000_000 итераций, но там на 1000-1500 начинаются повторения
  • в этом году брутфорс, брутфорс который работает, но нужно не сломаться на правильном обработке шага
  • краевые кейсы сразу с первой задачи (привет, eightwo!), на которых народ горел

В этом году был дан коммит решить 5 первых задач на Rust, потому что давно хотелось попробовать язык. В серьёзных проблемах приходится бороться с borrowing. На удивление решено на Rust было 16 дней из 25. И по нескольким дням прям видно, как менялся стиль с императивного на функциональный, который в этом языке более удобный.

Изменение стиля

Так же удобно было, что можно прям в том же файле писать тесты и считывать файл в память на этапе компиляции через макрос. А ещё случилось волшебное и один из дней, когда уже перекатился на python так как пошли сложные задачи, вернулся в Rust и забрутфорсил решением тем же алгоритмом.

Rust goes brr…

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

  1. Типа Conway’s game of life на 21 день
  2. Поиск точек в замкнутом контуре на 10 день
  3. Пересечь все 3d линии с остальными на 24 день