спірітус маргіналіс

#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

GitHub

GitHub - Pyroarsonist/advent-of-code-2024: https://adventofcode.com/2024

https://adventofcode.com/2024. Contribute to Pyroarsonist/advent-of-code-2024 development by creating an account on GitHub.

www.group-telegram.com/sg/Pyroborea.com/16668

99 viewsDanylo The Great 🔥, Dec 13, 2024 at 23:57

#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

BY спірітус маргіналіс