Задача 6-го дня Advent of Code — Guard Gallivant.
📘 Часть I. Описание задачи
Нам требуется смоделировать движение охранника по лаборатории, представленной в виде сетки.
- Охранник начинает в определённой клетке, смотрит в одном из четырёх направлений и следует следующим правилам:
- Если перед ним препятствие (
#), он поворачивает направо на 90°.
- Иначе делает шаг вперёд.
Задача — определить количество уникальных клеток, которые охранник посетит, прежде чем покинет карту.
💡 Идея
Необходимо симулировать движение охранника, учитывая его текущую позицию и направление. Для отслеживания посещённых клеток используется двумерный массив, где каждая клетка хранит информацию о направлениях, с которых она была посещена. Если охранник возвращается в ту же клетку с тем же направлением, это означает начало цикла.
📘 Часть II. Описание задачи
Во второй части задачи требуется определить количество позиций, где добавление одного нового препятствия приведёт к тому, что охранник зациклится и никогда не покинет карту. Очевидно, что нельзя размещать препятствие в начальной позиции охранника.
💡 Идея
Читать дальше →
ответить
Задача 8-го дня Advent of Code — Resonant Collinearity.
🧩 Часть I. Условие задачи
В городе расставлены антенны, каждая из которых настроена на определённую частоту, обозначенную символом (a–z,A–Z,0–9). Если две антенны одной частоты расположены на прямой, и одна из них находится ровно в два раза дальше от точки, чем другая, то в этой точке возникает антинод.
Нужно найти количество уникальных позиций на карте, в которых возникает антинод. Позиции должны лежать в пределах карты. Антенны с разными частотами не создают антиноду.
💡 Идея
Для каждой частоты рассматриваем все пары антенн, стоящих на одной частоте. Каждая пара порождает ровно два симметричных антинода, расположенных по формуле:
(2*r0 - r1, 2*c0 - c1) и (2*r1 - r0, 2*c1 - c0)
Затем добавляем эти позиции в хеш-сет, если они находятся в пределах границ карты.
🧩 Часть II. Условие задачи
Читать дальше →
ответить
Задача пятого дня Advent of Code - Print Queue.
📘 Часть I. Условие задачи
- Набор страниц необходимо печатать в определённом порядке.
- Каждое правило задаётся в виде
X | Y, что означает: если обе страницы X и Y присутствуют в обновлении, то X должна появиться раньше Y.
- Дан список правил и набор последовательностей страниц.
- Требуется найти те, которые уже соответствуют правилам, и для каждой взять среднюю (центральную) страницу.
- Сумма этих страниц и является ответом.
💡 Идея
Для проверки корректности можно обходить последовательность и накапливать множество страниц, которые должны были уже встретиться раньше.
Если мы наткнемся на одну из них позже зависимой страницы, это нарушение!
📘 Часть II. Условие задачи
Теперь рассмотрим некорректные последовательности страниц.
Их нужно перестроить согласно правилам и взять сумму центральных страниц из корректных порядков.
💡 Идея
Это задача на топологическую сортировку.
- Правила определяют DAG (граф без циклов).
Читать дальше →
ответить
Задача 4-го дня Advent of Code — Ceres Search.
📌 Часть I. Условие задачи
Нам дано поле из символов. Нужно найти все вхождения слова "XMAS".
Слово может быть записано:
- по горизонтали,
- по вертикали,
- по диагонали,
- в обратном порядке,
- поверх других слов (т.е. вхождения могут перекрываться).
💡 Идея
Для поиска всех таких слов:
- Перебираем каждую ячейку как потенциальную стартовую.
- Из неё идём во все
8 направлений (вверх, вниз, вправо, влево, и 4 диагонали).
- Читаем
4 символа в этом направлении.
- Сравниваем полученное слово с
"XMAS".
📌 Часть II. Условие задачи
Теперь требуется найти не само слово XMAS, а X-образное расположение двух слов "MAS" вокруг символа "A".
Пример расположения:
M . S
Читать дальше →
ответить
Задача третьего дня Advent of Code — Mull It Over.
📘 Часть I. Описание задачи
- В дампе памяти содержатся команды вида
mul(X,Y), где X и Y — это числа от 1 до 999.
- Такие команды представляют собой простое умножение двух чисел.
- Однако память повреждена, и в тексте могут встречаться невалидные команды
(например: "mul(4*," "mul ( 2 , 3 )" и т.п.).
Необходимо выделить все корректные mul(X,Y) и подсчитать сумму произведений.
💡 Идея
Парсим только строки, точно соответствующие регулярному выражению "mul(\d{1,3},\d{1,3})", остальные пропускаем. После чего результат каждого умножения суммируем.
📘 Часть II. Описание задачи
Кроме mul, в дампе встречаются do() и don't():
do() включает обработку muldon't() отключает
По умолчанию mul разрешён. Надо подсчитать только те mul, которые активны в момент встречи.
💡 Идея
Читать дальше →
ответить
Задача второго дня Advent of Code — Red-Nosed Reports.
📘 Часть I. Описание задачи
Имеется множество отчётов, каждый из которых представляет собой последовательность целых чисел — уровней. Отчёт считается безопасным, если:
- Все уровни строго возрастают или строго убывают.
- Разность между любыми двумя соседними уровнями по модулю составляет от 1 до 3 включительно.
Пример безопасных отчётов:
Пример небезопасных отчётов:
1 2 5 9 # шаг больше 35 4 4 1 # не строго убывает
💡 Идея
Необходимо пройтись по каждой последовательности и проверить, являются ли все пары элементов:
- либо строго возрастающими (
a < b)
- либо строго убывающими (
a > b)
- и при этом |a - b| <= 3
Если хотя бы одна из этих проверок не выполняется — отчёт считается небезопасным.
Читать дальше →
ответить
100 задач с LeetCode мы уже обозрели. Пора переходить к более тяжёлым наркотикам.
Дальше будем смотреть на задачи из последнего Advent of Code.
Задача первого дня — Historian Hysteria несложная и затравочная 😻.
📘 Условие части I
Даны два списка целых чисел одинаковой длины. Необходимо оценить, насколько они различаются.
Для этого:
- Сопоставим наименьшее число из левого списка с наименьшим числом из правого.
- Затем второе по величине — со вторым по величине, и так далее.
- Для каждой пары чисел вычисляется расстояние между ними — это модуль разности.
- Все такие расстояния суммируются, и результат отражает общее расхождение между списками.
Пример:
- Левый список:
3 4 2 1 3 3
- Правый список:
4 3 5 3 9 3
После сопоставления по возрастанию:
- Пары:
(1, 3), (2, 3), (3, 3), (3, 4), (3, 5), (4, 9)
- Расстояния:
2, 1, 0, 1, 2, 5
- Сумма расстояний:
2 + 1 + 0 + 1 + 2 + 5 = 11
Читать дальше →
ответить
