#advent_of_code_2024

Day 8
https://adventofcode.com/2024/day/8
Part 1
Проходимо по матриці та збираємо координати всіх різних антен.
Проходимось по координатам антен однієї групи попарно: для кожної пари антен виявляємо антиноду базовим геометричним обчисленням, беремо тільки ті антиноди, які знаходяться в межах матриці (оскільки пара буде проходитись двічі в такому циклі, то можемо за раз оброблювати тільки 1 антиноду).
Маємо масив антинод на кожну групу антен: збираємо їх до купи, фільтруємо унікальні і рахуємо кількість.
Part 2
Тепер кожна антинода спавниться на лінії будь-яких двох антен. Це означає, що треба проходитись по матриці і виявляти, чи є точка на такій лінії. Для кожної з пари антент однієї групи зробимо функцію-рівняння прямої (по 2 точкам можна визначити пряму), результат якої буде 0, якщо точка лежить на прямій.

(y1 - y2) * x + (x2 - x1) * y + (x2 * y1 - x1 * y2) = 0

Для кожної точки в матриці перевіряємо в окремо створеній матриці для антинод, чи є вона там (тобто кешуємо) і обраховуємо цей результат, опісля рахуємо кількість антинод.

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

#advent_of_code_2024

Day 9
https://adventofcode.com/2024/day/9
Part 1
Наївним солюшном буде переставлення крайнього правого чесла на перший індекс точки, але в великому інпуті 240к символів і такий солюшн виповнюється дуже довго.
Далі, я переробив солюшн: замість того, щоб процессити строку з точками, я зразу шукаю на ній суму: маючи один поінтер спочатку, який проходиться по масиву і сумує елементи і поінтер с кінця, який видає першому поінтеру поточне число замість точки.
Відповідь не сходилась, виявилось, що при генерації строки з точкою я в тупу додав в строку айді поточного файлу, що не працювало на двухзначних числах.
Після фікса відповідь виявилась правильною і обраховувалась за декілька мс.
Part 2
Повертаємося до наївного солюшна з 1 частини, але дещо змінимо. Замість того, щоб колупатися в готовій строці з точками, будемо міняти основну строку, а точніше її репрезентацію: представимо її у вигляді масиву, в якому чергуються елементи айдішок та пустого простору. Будемо манюпулювати цими елементами: для кожного елемента айдішки справа знаходимо підходящий простий простір і переносимо елемент туди: при цьому треба врахувати, що якщо різниця кількостей елементів не нульова (тобто пустий простір більше за айдішку), то треба залишити залишок пустого простору, а також не забути поміняти тип айдішки справа на пустий простір.

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

))

#advent_of_code_2024

Day 10
https://adventofcode.com/2024/day/10
Part 1
Класична dfs задачка.
Парсимо матрицю. Знаходимо нулі, для них стартуєм dfs функцію: додаємо в робочий масив координати з метаданими координат початку і для кожних суміжних клітинок перевіряємо, чи можна туди "зайти", таким чином, додаємо нові дані в цей робочий масив. Коли можемо перейти в 9: записуємо дані в мапу.
Після проходження dfs, читаємо дані з мапи, знаходимо унікальні пари гешмапи 0-9 та видаємо це за відповідь.
Part 2
Як бачимо, дизайн першої частини підходить під другу. Замість того, щоб зберегати унікальні пари, тепер будемо накопичувати кількість таких пар: якщо з точки А в точку Б можна пройти 3 способами, то зберігаємо число 3, таким чином, сумуємо всі такі способи і отримуємо результат.

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

#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

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