Задача 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. Условие задачи
В обновлённой модели антиноды возникают не только в особых симметричных точках, но на всех узлах, достижимых по вектору, соединяющему две антенны одинаковой частоты.
Так например, T-частотные антенны на следующем рисунке образуют антиноды, помеченные знаком # (кроме того антиноды также образуются и в локациях с антеннами).
T....#....
...T......
.T....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........
Задача: определить общее количество уникальных антинод, лежащих внутри границ карты.
💡 Идея
Для каждой пары антенн с одинаковой частотой определяем вектор направления (dr, dc) и, начиная от каждой из антенн, распространяемся по этому вектору вперёд и назад, пока остаёмся в пределах карты. Каждую достигнутую точку заносим в хеш-сет.
🛠 Детали подхода
- Структура
AntiNodes хранит размеры карты и HashSet для уникальных позиций.
checked_add гарантирует, что добавляемая точка не выходит за границы.- Для перебора всех пар антенн одной частоты используем
itertools::tuple_combinations()
- В
solve_hard в цикле перебираем узлы сетки в обе стороны от каждой пары антенн.
📈 Асимптотика
Введём обозначения
n — количество различных частот (не более 62),k² — среднеквадратичное число антенн на одну частоту,m — линейный размер карты (rows ≈ cols ≈ m).
Тогда:
-
solve_simple:
- Временная сложность:
O(n·k²) — перебор всех пар антенн одной частоты.
- Память:
O(m²) — в худшем случае почти вся карта может быть покрыта антинодами.
-
solve_hard:
- Временная сложность:
O(n·k²·m) — каждая пара антенн порождает максимум m шагов вдоль прямой (в обе стороны), всего O(k²·m) на частоту.
- Память:
O(m²) — аналогично solve_simple.
🧾 Исходный код
use super::TaskData;
use std::collections::HashSet;
use itertools::Itertools;
pub struct Solution;
struct AntiNodes {
rows: i32,
cols: i32,
positions: HashSet<(i32, i32)>,
}
impl Solution {
// Part I: antinode occurs only when one antenna is twice as far as the other on a line
pub fn solve_simple(data: &TaskData) -> i32 {
let mut antinodes = AntiNodes::new(data.rows, data.cols);
for (_, positions) in &data.antenna_lists {
for (&(r0, c0), &(r1, c1)) in positions.iter().tuple_combinations() {
// Compute symmetric antinode positions
antinodes.checked_add(2 * r0 - r1, 2 * c0 - c1);
antinodes.checked_add(2 * r1 - r0, 2 * c1 - c0);
}
}
antinodes.count() as _
}
// Part II: antinode occurs along the entire line through any two same-frequency antennas
pub fn solve_hard(data: &TaskData) -> i32 {
let mut antinodes = AntiNodes::new(data.rows, data.cols);
for (_, positions) in &data.antenna_lists {
for (&(r0, c0), &(r1, c1)) in positions.iter().tuple_combinations() {
let (dr, dc) = (r1 - r0, c1 - c0);
// Extend line forward from (r1, c1)
let (mut r, mut c) = (r1, c1);
while antinodes.checked_add(r, c) {
r += dr;
c += dc;
}
// Extend line backward from (r0, c0)
let (mut r, mut c) = (r0, c0);
while antinodes.checked_add(r, c) {
r -= dr;
c -= dc;
}
}
}
antinodes.count() as _
}
}
impl AntiNodes {
fn new(rows: i32, cols: i32) -> Self {
Self {
rows,
cols,
positions: HashSet::new(),
}
}
// Adds position if it's within map bounds
fn checked_add(&mut self, r: i32, c: i32) -> bool {
if (0..self.rows).contains(&r) && (0..self.cols).contains(&c) {
self.positions.insert((r, c));
true
} else {
false
}
}
fn count(&self) -> usize {
self.positions.len()
}
}
Tags: #rust #algorithms #adventofcode #hashset