Advent of Code 2022
Jan. 16th, 2024 02:20 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frЯ уже давно, ещё после бессонной ночи у catpad (ничего личного, просто jetlag) хотел побаловаться с python. До какого-то начального уровня прокачал (достаточно, чтобы детям помогать с домашним заданием из школы — они там тоже python учат), но двигаться дальше уже сложно, нужны какие-то конкретные примеры, вместе с мотивацией ими заниматься. После поста avva записал себе идею пройти Advent of Code, а тут как раз удачно порвал связки на лыжах, и у меня оказались под рукой насколько свободных дней, компьютер и интернет. Запустил python (Spyder — когда-то давно поставил себе Anaconda, что-то там надо было разобрать с матрицами, не пригодилось, но и не снёс), открыл первый попавшийся справочник по python, открыл ChatGPT (avva не рекомендовал, но мне эта часть как раз показалась самой интересной) — и понеслась!
Чтобы иметь возможность «соревноваться» с упомянутым в посте Питером Норвигом (я не знаю, кто это, Википедию только что прочитал), занялся прошлогодним календарём. Задачки все, в принципе, не сложные, если ты когда-то занимался около-олимпиадным программированием. У меня к ChatGPT были в основном вопросы о структурах данных — примерно описываешь, что ты хочешь сделать, и спрашиваешь, как называется соответствующий тип данных, а потом читаешь документацию о том, как на самом деле работают все эти tuple / set / list / dictionnary. Решил задачу — смотришь на решение Норвига, понимаешь, насколько проще можно было написать, запоминаешь идеи впрок, в следующих задачах пытаешься их использовать.
Разобрался попутно с GitHub. В прошлый раз, когда я на питоне пытался сделать Splendor (а точнее даже платформу для произвольных настольных игр, что-то вроде Tabletopia — была у меня мечта устроить соревнование разных самообучающихся алгоритмов, чтобы находить какие-то новые стратегии в игрушках, но это быстро переросло объём времени, который я согласен выделять на хобби) я уже сделал себе репозиторий, в этот раз разобрался и с клиентом.
Попытался разобраться с jupyter, но что-то пошло не так. Если у кого-то из друзей найдётся время, чтобы провести меня за руку по всему процессу от начала до первого hello world, буду признателен. Хотя, наверное, это как раз самое то, что нужно спрашивать у ChatGPT.
Задачи очень хорошо сделаны. Во-первых, всегда есть какое-то бредовое введение. Танцующие слоны, летающие обезьяны, не работающий передатчик, который ты должен срочно починить. Во-вторых, каждая задача из нескольких частей. Сначала простой пример, на котором тебе объясняют правила. Я сначала про себя ругался: кому они так разжёвывают условия? Пока не наткнулся на задачу (№ 23), в которой я сам не понял условия, и только перечитав 5 раз пример, понял, что я неправильно интерпретировал одно слово в задании. Короче, не надо бояться казаться слишком подробным.
Так вот, на этом примере ты пишешь свой код, отлаживаешь его, убеждаешься в работоспособности, а потом только включаешь данные настоящей задачи. У меня всегда настоящая задача сразу же работала правильно. Один раз (задача № 7) система выдала, что я неправ. Я потерял несколько часов, написав сначала другое решение (ответ тот же). Потом сделав Excel-файл, в котором решил эту же задачу чуть ли не ручками — всё равно ответ тот же. После чего система приняла его — а я понял, что никогда не надо вбивать правильный ответ руками, всегда нужно копировать. Видимо, в первый раз я просто опечатался — а сайт просто говорит, что ты ошибся, не показывая твой вариант ответа (хозяйке на заметку: это очень плохой дизайн).
Так вот, а после этого тебе выдают вторую часть той же задачи. После которого ты обычно говоришь себе, что да, данные можно было бы организовать и по-другому. И то, что годилось для первой части, займёт несколько дней расчёта для второй, если только всё не переписать заново. И ты переписываешь всё заново. Офигенное упражнение — пытаться сразу видеть будущие осложнения в задаче!
Какие задачки запомнились.
Задача № 16. Единственная, у которой я не сделал вторую часть. Там у тебя есть граф, каждое ребро графа занимает сколько-то времени, чтобы пройти из одного узла в другой. В каждом узле графа есть механизм, который можно включить (на это тоже нужна единица времени), и который будет производить какой-то результат с определённой скоростью (по легенде мы там чинили вентиляцию внутри вулкана). У тебя есть ограниченное количество времени — нужно максимизировать суммарный результат.
В лоб задача не решается, потому что время полного перебора дерева вариантов слишком долгое. Но если выкинуть из графа все узлы без мотора (а их много), после чего связать каждый узел с каждым (сделав вид, что ты не проходишь через другие узлы, а идёшь напрямую за суммарную стоимость соответствующих рёбер), то решается.
А во второй части тебе в помощь прислали слона, и вы можете ходить по лабиринту одновременно. И тут я запутался. Потому что обход в одиночку делается просто: если мне нужно 10 шагов, чтобы дойти до определённого узла, то я в симуляции просто ставлю «время -= 10» и перемещаю себя в пункт назначения. А если мы вдвоём, то управление временем становится чуть сложнее — через пару часов я окончательно запутался и забил.
Проверил, как эту же задачу решил Норвиг — он схалявил. Предположим, говорит, я всё так же хожу по маршруту, который был оптимальным в одиночку, а слона отправлю по тем узлам, куда я не собираюсь заходить. Скорее всего, это будет близко к оптимальному решению, проверим. А если не угадали — постараемся подвигать туда-сюда, может ещё что выгадаем. Он попробовал — и у него сразу получилось. Я такой чит даже пробовать не стал, мне интересно общее решение!
Задача № 17. У тебя есть практически тетрис, только стакан потенциально бесконечный, ну и полные строки не убираются. Впрочем, они и не формируются, потому что играешь не ты: тебе дают список падающих фигур и список нажатий на клавиши. Эти нажатия никак не соответствуют логике тетриса, поэтому фигуры в основном тупо падают одна на другую. Вопрос в задаче: когда упадёт 2024 фигуры, какой высоты достигнет самая верхняя фигура в стакане?
Задача решается просто, но второй уровень говорит: ваша модель (по легенде это было моделирование падающих на нас камней, чтобы убедить слонов в безопасности перехода) наверняка работает, но слонам всё равно страшно, они хотят тот же самый результат для 100000000000 фигур. Понятно, что ты не будешь моделировать 1012. Но ты можешь найти цикл (список фигур конечный и зацикленный, список нажатий на клавиши тоже конечный и зацикленный). Я только потом додумался, что можно было найти длину этого цикла чисто аналитически :-) Вместо этого я проследил за какими-то ключевыми событиями (фигура застывает так, что трогает левый или правый борт стакана — подразумевая, что после этих двух событий ни одна фигура не сможет больше упасть ниже этих двух фигур), вывел их время на график и чисто глазами увидел этот цикл.
Норвиг тоже увидел возможность найти цикл. Но он пытался найти цикл, который возвращает в исходное положение (не произвольная поверхность, запрещающая фигурам падать ниже её, а ровная линия наверху), а это, понятное дело, не всегда возможно (циклический процесс может иметь нециклическую часть в начале).
Задача № 18. Тебе дают координаты 3D кубиков, составляющих некое тело, и ты должен понять, какой объём у его внутренних пустот. Простая задача, но в голове нужно держать на одно измерение больше привычного — приятно, когда это получается.
Задача № 18. У тебя есть робот, который производит единицу первого ресурса в единицу времени. И у тебя есть прайслист: сколько стоит построить ещё одного такого робота, какие ещё есть роботы, какие ещё есть ресурсы. У тебя есть финальный ресурс, количество которого ты должен максимизировать за заранее выданное тебе время. Тоже задача, которая не решается в лоб, вопрос в том, как ты сможешь оптимзировать перебор.
Я очень долго оптимизировал, и дошёл до пары минут на сценарий. Норвиг оптимизировал до доль секунд на сценарий — монстр!
Задача № 22. У тебя есть лабиринт со стенками и инструкция в духе «10 шагов вперёд, поверни налево, 15 шагов вперёд, поверни направо». Наткнулся на стенку — оставшиеся шаги пропали. В какой клеточке ты будешь в конце? Решается достаточно просто.
Зато вторая часть — фантастика. Оказывается, это был не просто лабиринт странной формы, это была выкройка куба. И ты можешь переходить с одной грани куба на другую, не поворачивая. Понятно, что на уровне 2D-выкройки это соответствует телепортации по определённым правилам, да ещё и с поворотом. Моделировать это в 3D — тоже сомнительное удовольствие. Эту задачу я решал уже в последний день, когда мы сдали ключи от дома, все поехали кататься, а я сидел в булочной, присосавшись к их розетке. Первая задача, для которой мне пришлось достать ручку и бумагу. Решил через одно место (каждую выкройку нужно конфигурировать ручками), но всё-таки решил!
А последняя задача расстроила. Она всего из одного уровня, а чтобы получить вторую звёздочку, нужно собрать 49 звёздочек, то есть решить все предыдущие задачи. А я не доделал вторую часть № 16 :-(
Наверняка буду решать и другие года календаря. Осталось только ещё раз ногу сломать :-)
catpad (ничего личного, просто jetlag) хотел побаловаться с python. До какого-то начального уровня прокачал (достаточно, чтобы детям помогать с домашним заданием из школы — они там тоже python учат), но двигаться дальше уже сложно, нужны какие-то конкретные примеры, вместе с мотивацией ими заниматься. После поста avva записал себе идею пройти Advent of Code, а тут как раз удачно порвал связки на лыжах, и у меня оказались под рукой насколько свободных дней, компьютер и интернет. Запустил python (Spyder — когда-то давно поставил себе Anaconda, что-то там надо было разобрать с матрицами, не пригодилось, но и не снёс), открыл первый попавшийся справочник по python, открыл ChatGPT (avva не рекомендовал, но мне эта часть как раз показалась самой интересной) — и понеслась!Чтобы иметь возможность «соревноваться» с упомянутым в посте Питером Норвигом (я не знаю, кто это, Википедию только что прочитал), занялся прошлогодним календарём. Задачки все, в принципе, не сложные, если ты когда-то занимался около-олимпиадным программированием. У меня к ChatGPT были в основном вопросы о структурах данных — примерно описываешь, что ты хочешь сделать, и спрашиваешь, как называется соответствующий тип данных, а потом читаешь документацию о том, как на самом деле работают все эти tuple / set / list / dictionnary. Решил задачу — смотришь на решение Норвига, понимаешь, насколько проще можно было написать, запоминаешь идеи впрок, в следующих задачах пытаешься их использовать.
Разобрался попутно с GitHub. В прошлый раз, когда я на питоне пытался сделать Splendor (а точнее даже платформу для произвольных настольных игр, что-то вроде Tabletopia — была у меня мечта устроить соревнование разных самообучающихся алгоритмов, чтобы находить какие-то новые стратегии в игрушках, но это быстро переросло объём времени, который я согласен выделять на хобби) я уже сделал себе репозиторий, в этот раз разобрался и с клиентом.
Попытался разобраться с jupyter, но что-то пошло не так. Если у кого-то из друзей найдётся время, чтобы провести меня за руку по всему процессу от начала до первого hello world, буду признателен. Хотя, наверное, это как раз самое то, что нужно спрашивать у ChatGPT.
Задачи очень хорошо сделаны. Во-первых, всегда есть какое-то бредовое введение. Танцующие слоны, летающие обезьяны, не работающий передатчик, который ты должен срочно починить. Во-вторых, каждая задача из нескольких частей. Сначала простой пример, на котором тебе объясняют правила. Я сначала про себя ругался: кому они так разжёвывают условия? Пока не наткнулся на задачу (№ 23), в которой я сам не понял условия, и только перечитав 5 раз пример, понял, что я неправильно интерпретировал одно слово в задании. Короче, не надо бояться казаться слишком подробным.
Так вот, на этом примере ты пишешь свой код, отлаживаешь его, убеждаешься в работоспособности, а потом только включаешь данные настоящей задачи. У меня всегда настоящая задача сразу же работала правильно. Один раз (задача № 7) система выдала, что я неправ. Я потерял несколько часов, написав сначала другое решение (ответ тот же). Потом сделав Excel-файл, в котором решил эту же задачу чуть ли не ручками — всё равно ответ тот же. После чего система приняла его — а я понял, что никогда не надо вбивать правильный ответ руками, всегда нужно копировать. Видимо, в первый раз я просто опечатался — а сайт просто говорит, что ты ошибся, не показывая твой вариант ответа (хозяйке на заметку: это очень плохой дизайн).
Так вот, а после этого тебе выдают вторую часть той же задачи. После которого ты обычно говоришь себе, что да, данные можно было бы организовать и по-другому. И то, что годилось для первой части, займёт несколько дней расчёта для второй, если только всё не переписать заново. И ты переписываешь всё заново. Офигенное упражнение — пытаться сразу видеть будущие осложнения в задаче!
Какие задачки запомнились.
Задача № 16. Единственная, у которой я не сделал вторую часть. Там у тебя есть граф, каждое ребро графа занимает сколько-то времени, чтобы пройти из одного узла в другой. В каждом узле графа есть механизм, который можно включить (на это тоже нужна единица времени), и который будет производить какой-то результат с определённой скоростью (по легенде мы там чинили вентиляцию внутри вулкана). У тебя есть ограниченное количество времени — нужно максимизировать суммарный результат.
В лоб задача не решается, потому что время полного перебора дерева вариантов слишком долгое. Но если выкинуть из графа все узлы без мотора (а их много), после чего связать каждый узел с каждым (сделав вид, что ты не проходишь через другие узлы, а идёшь напрямую за суммарную стоимость соответствующих рёбер), то решается.
А во второй части тебе в помощь прислали слона, и вы можете ходить по лабиринту одновременно. И тут я запутался. Потому что обход в одиночку делается просто: если мне нужно 10 шагов, чтобы дойти до определённого узла, то я в симуляции просто ставлю «время -= 10» и перемещаю себя в пункт назначения. А если мы вдвоём, то управление временем становится чуть сложнее — через пару часов я окончательно запутался и забил.
Проверил, как эту же задачу решил Норвиг — он схалявил. Предположим, говорит, я всё так же хожу по маршруту, который был оптимальным в одиночку, а слона отправлю по тем узлам, куда я не собираюсь заходить. Скорее всего, это будет близко к оптимальному решению, проверим. А если не угадали — постараемся подвигать туда-сюда, может ещё что выгадаем. Он попробовал — и у него сразу получилось. Я такой чит даже пробовать не стал, мне интересно общее решение!
Задача № 17. У тебя есть практически тетрис, только стакан потенциально бесконечный, ну и полные строки не убираются. Впрочем, они и не формируются, потому что играешь не ты: тебе дают список падающих фигур и список нажатий на клавиши. Эти нажатия никак не соответствуют логике тетриса, поэтому фигуры в основном тупо падают одна на другую. Вопрос в задаче: когда упадёт 2024 фигуры, какой высоты достигнет самая верхняя фигура в стакане?
Задача решается просто, но второй уровень говорит: ваша модель (по легенде это было моделирование падающих на нас камней, чтобы убедить слонов в безопасности перехода) наверняка работает, но слонам всё равно страшно, они хотят тот же самый результат для 100000000000 фигур. Понятно, что ты не будешь моделировать 1012. Но ты можешь найти цикл (список фигур конечный и зацикленный, список нажатий на клавиши тоже конечный и зацикленный). Я только потом додумался, что можно было найти длину этого цикла чисто аналитически :-) Вместо этого я проследил за какими-то ключевыми событиями (фигура застывает так, что трогает левый или правый борт стакана — подразумевая, что после этих двух событий ни одна фигура не сможет больше упасть ниже этих двух фигур), вывел их время на график и чисто глазами увидел этот цикл.
Норвиг тоже увидел возможность найти цикл. Но он пытался найти цикл, который возвращает в исходное положение (не произвольная поверхность, запрещающая фигурам падать ниже её, а ровная линия наверху), а это, понятное дело, не всегда возможно (циклический процесс может иметь нециклическую часть в начале).
Задача № 18. Тебе дают координаты 3D кубиков, составляющих некое тело, и ты должен понять, какой объём у его внутренних пустот. Простая задача, но в голове нужно держать на одно измерение больше привычного — приятно, когда это получается.
Задача № 18. У тебя есть робот, который производит единицу первого ресурса в единицу времени. И у тебя есть прайслист: сколько стоит построить ещё одного такого робота, какие ещё есть роботы, какие ещё есть ресурсы. У тебя есть финальный ресурс, количество которого ты должен максимизировать за заранее выданное тебе время. Тоже задача, которая не решается в лоб, вопрос в том, как ты сможешь оптимзировать перебор.
Я очень долго оптимизировал, и дошёл до пары минут на сценарий. Норвиг оптимизировал до доль секунд на сценарий — монстр!
Задача № 22. У тебя есть лабиринт со стенками и инструкция в духе «10 шагов вперёд, поверни налево, 15 шагов вперёд, поверни направо». Наткнулся на стенку — оставшиеся шаги пропали. В какой клеточке ты будешь в конце? Решается достаточно просто.Зато вторая часть — фантастика. Оказывается, это был не просто лабиринт странной формы, это была выкройка куба. И ты можешь переходить с одной грани куба на другую, не поворачивая. Понятно, что на уровне 2D-выкройки это соответствует телепортации по определённым правилам, да ещё и с поворотом. Моделировать это в 3D — тоже сомнительное удовольствие. Эту задачу я решал уже в последний день, когда мы сдали ключи от дома, все поехали кататься, а я сидел в булочной, присосавшись к их розетке. Первая задача, для которой мне пришлось достать ручку и бумагу. Решил через одно место (каждую выкройку нужно конфигурировать ручками), но всё-таки решил!
А последняя задача расстроила. Она всего из одного уровня, а чтобы получить вторую звёздочку, нужно собрать 49 звёздочек, то есть решить все предыдущие задачи. А я не доделал вторую часть № 16 :-(
Наверняка буду решать и другие года календаря. Осталось только ещё раз ногу сломать :-)
