Advent of Code
#code
В этом году впервые играю в Advent of Code. Это движуха, когда весь декабрь (с первого числа и до рождества) каждый день появляется новая задачка для программистов. Первые дни разминочные, но потом, говорят, будет интересно. Решать можно на любом языке. Всё делается у вас на компьютере локально, а на сайт нужно лишь загрузить ответ.
Я решаю на С++20. Следить за моими решениями можно на гитхабе.
У меня до этого никогда не было адвент-календарей, но на самом деле что-то в этом есть. Каждый день просыпаешься, а тебя ждёт новая задачка — и впрямь появляется ощущение приближающего праздника. Вливайтесь! Пока прошло только два дня, так что можно легко нагнать.
А если хотите дополнительного фана в виде небольшого соревновательного элемента, то добавляйтесь в мою приватную лидерборду: 2341807-220d9fc6. Там не самая лучшая система рейтинга: дополнительные очки даются тем, кто решил задачу раньше других, но без учёта часовых поясов. Задачки появляются каждый день в полночь по UTC-5. Это 6 утра по моему времени или 8 утра по Москве. Так что все оказываются в разных условиях и очки не очень справедливые, но всё равно интересно смотреть за прогрессом друг друга.
#code
В этом году впервые играю в Advent of Code. Это движуха, когда весь декабрь (с первого числа и до рождества) каждый день появляется новая задачка для программистов. Первые дни разминочные, но потом, говорят, будет интересно. Решать можно на любом языке. Всё делается у вас на компьютере локально, а на сайт нужно лишь загрузить ответ.
Я решаю на С++20. Следить за моими решениями можно на гитхабе.
У меня до этого никогда не было адвент-календарей, но на самом деле что-то в этом есть. Каждый день просыпаешься, а тебя ждёт новая задачка — и впрямь появляется ощущение приближающего праздника. Вливайтесь! Пока прошло только два дня, так что можно легко нагнать.
А если хотите дополнительного фана в виде небольшого соревновательного элемента, то добавляйтесь в мою приватную лидерборду: 2341807-220d9fc6. Там не самая лучшая система рейтинга: дополнительные очки даются тем, кто решил задачу раньше других, но без учёта часовых поясов. Задачки появляются каждый день в полночь по UTC-5. Это 6 утра по моему времени или 8 утра по Москве. Так что все оказываются в разных условиях и очки не очень справедливые, но всё равно интересно смотреть за прогрессом друг друга.
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.
Максимально душная задача. По началу ничего особенно сложного, но во второй части появляется условие, которое хрен запишешь сколько-нибудь красиво. Получается соревнование на то, кто быстрее сможет это захардкодить под конкретный инпут и при этом не запутается. Я всё равно проспал, поэтому решил решать честно и универсально, на что угрохал весь день. Но под конец уже так преисполнился, что даже объяснение алгоритма на реддит запостил.
***
В целом был интересный опыт. Но под конец уже знатно задолбали задачи про регулярные квадратные сетки и ту или иную вариацию поиска на ней. На последней собирался уже в шашлык стрелять, если снова будет сетка. Хотелось бы больше чего-то, где надо именно догадаться, как решать, а не просто аккуратно надолбить условия и поиск в ширину.
Участвовать в таком конкурсе на крестах, это, конечно, «здоровья погибшим», как говорится; но ни о чём не жалею. Насчёт следующего года не уверен, но может быть поучаствую на питоне, чтобы подучить его наконец-то.
И да: всех с Рождеством!
#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.
Максимально душная задача. По началу ничего особенно сложного, но во второй части появляется условие, которое хрен запишешь сколько-нибудь красиво. Получается соревнование на то, кто быстрее сможет это захардкодить под конкретный инпут и при этом не запутается. Я всё равно проспал, поэтому решил решать честно и универсально, на что угрохал весь день. Но под конец уже так преисполнился, что даже объяснение алгоритма на реддит запостил.
***
В целом был интересный опыт. Но под конец уже знатно задолбали задачи про регулярные квадратные сетки и ту или иную вариацию поиска на ней. На последней собирался уже в шашлык стрелять, если снова будет сетка. Хотелось бы больше чего-то, где надо именно догадаться, как решать, а не просто аккуратно надолбить условия и поиск в ширину.
Участвовать в таком конкурсе на крестах, это, конечно, «здоровья погибшим», как говорится; но ни о чём не жалею. Насчёт следующего года не уверен, но может быть поучаствую на питоне, чтобы подучить его наконец-то.
И да: всех с Рождеством!