Log of Alprog

Advent of Code 2022 Done!
#code

Ну вот и закончился Advent of Code.
Расскажу про задачки, которые хоть чем-то запомнились:

8. Treetop Tree House.
Сама задача не особо примечательная, но я уже после основного решения выпендрился оптимизацией, сделав поиск однопроходным и заюзав intrinsic functions (get_trailing_zeros).

11. Monkey in the Middle.
Первая задача, в которой надо было минимально подумать, заглянув в инпут и проанализировав его. Про наименьшее общее кратное. Хотелось бы больше такого.

13. Distress Signal.
Мудацкая задача со списками, которая легко решается в какой-нибудь динамике типа python или lua, чуть ли не простым eval(), но на крестах задолбёшься только структуры заводить.

16. Proboscidea Volcanium.
Пожалуй, самая интересная задача. Нужно было сначала упростить граф + запилить кэширование стейтов тем или иным способом. Плюс во второй части нужно было придумать, как "распараллелить" дерево возможностей. Жалко, что оптимальное решение у слона и человека не пересекается. Можно было ещё усложнить немного. Тем не менее, понравилось больше всего. Классная.

17. Pyroclastic Flow.
Неплохая задача про тетрис. Выпендрился тем, что уложил многоэтажные фигуры тетриса целиком в один uint64_t и двигал их влево-вправо простым шифтом. Ну и в стакан зашивал битовыми операциями соответственно.

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

19. Not Enough Minerals.
На эту задачу бомбил больше всего. На первый взгляд похожа на 16, но честно закэшировать стейты не получается. В итоге решается эвристиками отсечения, которые на самом деле не гарантируют правильного ответа. Причём самое подлое, что тестовые данные подобраны хитрые, на которых простые эвристики не работают, но которые вполне подходят для самого паззла. То есть в выигрыше были те, кто раньше забили на тестовый пример и сразу попробовали свои эвристики на основном инпуте.

22. Monkey Map.
Максимально душная задача. По началу ничего особенно сложного, но во второй части появляется условие, которое хрен запишешь сколько-нибудь красиво. Получается соревнование на то, кто быстрее сможет это захардкодить под конкретный инпут и при этом не запутается. Я всё равно проспал, поэтому решил решать честно и универсально, на что угрохал весь день. Но под конец уже так преисполнился, что даже объяснение алгоритма на реддит запостил.

***

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

Участвовать в таком конкурсе на крестах, это, конечно, «‎здоровья погибшим», как говорится; но ни о чём не жалею. Насчёт следующего года не уверен, но может быть поучаствую на питоне, чтобы подучить его наконец-то.

И да: всех с Рождеством!

www.tgoop.com/logofalprog/210

1.68K viewsedited  Dec 25, 2022 at 07:43

Advent of Code 2022 Done!
#code

Ну вот и закончился Advent of Code.
Расскажу про задачки, которые хоть чем-то запомнились:

8. Treetop Tree House.
Сама задача не особо примечательная, но я уже после основного решения выпендрился оптимизацией, сделав поиск однопроходным и заюзав intrinsic functions (get_trailing_zeros).

11. Monkey in the Middle.
Первая задача, в которой надо было минимально подумать, заглянув в инпут и проанализировав его. Про наименьшее общее кратное. Хотелось бы больше такого.

13. Distress Signal.
Мудацкая задача со списками, которая легко решается в какой-нибудь динамике типа python или lua, чуть ли не простым eval(), но на крестах задолбёшься только структуры заводить.

16. Proboscidea Volcanium.
Пожалуй, самая интересная задача. Нужно было сначала упростить граф + запилить кэширование стейтов тем или иным способом. Плюс во второй части нужно было придумать, как "распараллелить" дерево возможностей. Жалко, что оптимальное решение у слона и человека не пересекается. Можно было ещё усложнить немного. Тем не менее, понравилось больше всего. Классная.

17. Pyroclastic Flow.
Неплохая задача про тетрис. Выпендрился тем, что уложил многоэтажные фигуры тетриса целиком в один uint64_t и двигал их влево-вправо простым шифтом. Ну и в стакан зашивал битовыми операциями соответственно.

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

19. Not Enough Minerals.
На эту задачу бомбил больше всего. На первый взгляд похожа на 16, но честно закэшировать стейты не получается. В итоге решается эвристиками отсечения, которые на самом деле не гарантируют правильного ответа. Причём самое подлое, что тестовые данные подобраны хитрые, на которых простые эвристики не работают, но которые вполне подходят для самого паззла. То есть в выигрыше были те, кто раньше забили на тестовый пример и сразу попробовали свои эвристики на основном инпуте.

22. Monkey Map.
Максимально душная задача. По началу ничего особенно сложного, но во второй части появляется условие, которое хрен запишешь сколько-нибудь красиво. Получается соревнование на то, кто быстрее сможет это захардкодить под конкретный инпут и при этом не запутается. Я всё равно проспал, поэтому решил решать честно и универсально, на что угрохал весь день. Но под конец уже так преисполнился, что даже объяснение алгоритма на реддит запостил.

***

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

Участвовать в таком конкурсе на крестах, это, конечно, «‎здоровья погибшим», как говорится; но ни о чём не жалею. Насчёт следующего года не уверен, но может быть поучаствую на питоне, чтобы подучить его наконец-то.

И да: всех с Рождеством!

BY Log of Alprog