#advent_of_code_2024

Day 11
https://adventofcode.com/2024/day/11
Part 1
Дуже багато тексту, а насправді легка задачка.
Фактично, все що треба написати, так це функцію трансформації одного масиву каменів в інший.
Так і робимо: для кожного каменя в масиві пишемо іфи для перевірки на нуль, перевірки на парність кількості цифр в камені (приводимо його в строку) та останню операцію множення і проводимо таких ітерацій 25 штук (як сказано в задачі), отримуємо результат.
Part 2
Цікава друга частина, умова та ж сама, але кліпаємо очима тепер 75 раз, а не 25 і звичайно часу на обчислення було дуже багато, треба перероблювати наївний алгоритм.
Очевидно, що тут треба заюзати динамічне програмування і кешувати проміжні результати, але яким чином ітеруватися по камінням?
Дуже просто: будемо рахувати кількість каменів для кожного значення рекурсивно, враховуючи кількість кліпань.
Нехай у нас є масив каменів: для кожного з них сумуємо їх кількості каменів (але вже понижуючи кількість кліпань на 1): кожного разу, коли обчислили скільки у каменю є кількість каменів після трансформації, записуємо це в кеш разом з кількістю кліпань. Зрозуміло ж, що для каменя 0 з кліпанням 1 буде кількість каменів 1 (бо масив - [1]), але для такого ж самого каменю 0 з кліпанням 10 буде кількість каменів 39.
Оскільки для кожного каменю ми будемо брати кеш або рекурсивно дізнаватись кількість каменів у трансформованих: будемо мати високу швидкість, в мене вийшло десь 64мс, замість використання 1 частини, де процес проходить більше за 1 хвилину.

солюшн тут: https://github.com/Pyroarsonist/advent-of-code-2024

За це я плачу за інтернет

https://youtu.be/eKKFuyiUrFo
це офігенно

#coolstory
По ту сторону моралі

#advent_of_code_2024

Day 12
https://adventofcode.com/2024/day/12
Part 1
Задача на розфарбування графа.
Запускаємо функцію, яка розфарбовує матрицю по суміжним клітинкам.
Помітимо, що периметр можна знайти за кількістю вершин та їх сусідів в розфарбованому графі (периметр = 4 * кількість - кількість сусідів).
Легко рахуємо суму цін, яка є множенням периметра на площу (кількість вершин).
Part 2
Тепер замість периметру треба враховувати кількість сторін многокутника.
Для цього будемо акумулювати не сусідів вершини, а кількість вертикальних і горизонтальних сторін.
Розпочнемо для горизонтальних: будемо проходити масив зліва-направо зверху-вниз.
Для кожної вершини матриці будемо перевіряти її верхню та нижню грань, для них будемо записувати теперішній колір грані. Наприклад, якщо колір грані не міняється, то це означає, що нам не треба додавати ще одну сторону, бо вона продовжується. Але якщо колір грані помінявся, то це означає, що між двома вершинами була поставлена грань (тобто огорожа по задачі). Також варто враховувати, чи співпадає колір двох вершин - якщо так, то грані між ними немає: це внутрішня частина многокутника.
Робимо те ж саме відповідно для лівої та правої грані вершини матриці, по неї будемо проходитись зверху-вниз зліва-направо.
Сумуємо кількості сторін, маємо ціну і маємо результат.

солюшн тут: https://github.com/Pyroarsonist/advent-of-code-2024