13.01.2025 09:00
Kilor 0 242 Источник

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части воспользуемся возможностями линейной генерации и подсчета уникальных значений.

Оригинальная постановка задачи и ее перевод:

Advent of Code 2024, Day 8: Resonant Collinearity

--- День 8: Резонансная коллинеарность ---

Вы оказываетесь на крыше сверхсекретной инсталляции «Пасхальный кролик».

Пока Историки занимаются своим делом, вы смотрите на знакомую огромную антенну. К вашему большому удивлению, она, похоже, была перенастроена для излучения сигнала, который повышает вероятность того, что люди купят шоколад марки Easter Bunny Imitation Mediocre в качестве рождественского подарка на 0,1%! Немыслимо!

Просканировав город, вы обнаруживаете, что таких антенн на самом деле много. Каждая антенна настроена на определенную частоту, обозначенную одной строчной буквой, заглавной буквой или цифрой. Вы создаете карту (ваш вход для головоломки) этих антенн. Например:

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

Сигнал применяет свое пагубное воздействие только в определенных пучностях, основанных на резонансных частотах антенн. В частности, пучность возникает в любой точке, которая идеально совпадает с двумя антеннами той же частоты, но только когда одна из антенн находится в два раза дальше другой. Это означает, что для любой пары антенн с той же частотой существуют две пучности, по одной с каждой стороны от них.

Итак, для этих двух антенн с частотой a, они создают две пучности, отмеченные #:

..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........

Добавление третьей антенны с той же частотой создает еще несколько пучностей. В идеале это добавило бы четыре пучности, но две находятся за пределами правой стороны карты, поэтому вместо этого добавляется только две:

..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......#...
..........
..........

Антенны с разными частотами не создают пучностей; Aи aсчитаются разными частотами. Однако пучности могут возникать в местах, где есть антенны. На этой диаграмме одиночная антенна с частотой заглавной Aне создает пучностей, но имеет a-частотную пучность в своем местоположении:

..........
...#......
#.........
....a.....
........a.
.....a....
..#.......
......A...
..........
..........

В первом примере используются антенны с двумя разными частотами, поэтому создаваемые ими пучности выглядят следующим образом, плюс пучность, перекрывающая самую верхнюю Aантенну 4-й частоты:

......#....#
...#....0...
....#0....#.
..#....0....
....0....#..
.#....A.....
...#........
#......#....
........A...
.........A..
..........#.
..........#.

Поскольку самая верхняя антенна A -частоты перекрывается с пучностью 0-частоты, в пределах карты cуществуют 14 уникальных местоположений, содержащие пучность.

Рассчитайте воздействие сигнала. Сколько уникальных мест в пределах карты содержат пучность?

--- Часть вторая ---

Наблюдая за вашей работой через плечо, один из Историков спрашивает, учитывали ли вы в своих расчетах эффекты резонансных гармоник.

Упс!

После обновления вашей модели выясняется, что пучность возникает в любой позиции сетки, которая находится точно на одной линии с по крайней мере двумя антеннами той же частоты, независимо от расстояния. Это означает, что некоторые из новых пучностей возникнут в позиции каждой антенны (если только эта антенна не является единственной на своей частоте).

Итак, эти трехчастотные T-антенны теперь создают множество пучностей:

T....#....
...T......
.T....#...
.........#
..#.......
..........
...#......
..........
....#.....
..........

На самом деле, все три Tантенны частоты находятся точно на одной линии с двумя антеннами, поэтому они все также являются пучностями! Это доводит общее число пучностей в приведенном выше примере до 9.

В исходном примере теперь есть 34пучности, включая пучности, которые появляются на каждой антенне:

##....#....#
.#.#....0...
..#.#0....#.
..##...0....
....0....#..
.#...#A....#
...#..#.....
#....#.#....
..#.....A...
....#....A..
.#........#.
...#......##

Рассчитайте воздействие сигнала, используя эту обновленную модель. Сколько уникальных мест в пределах карты содержат пучность?

Часть 1

  1. Традиционно, сначала превратим исходную текстовую "матрицу" в двухмерный массив ячеек с помощью regexp_split_to_table и regexp_split_to_array.

  2. Мы не знаем "габаритов" полученной матрицы, поэтому воспользуемся generate_subscripts для перебора всех индексов каждой из размерностей.

  3. Остается лишь перебрать JOIN'ом все пары антенн совпадающей частоты, чтобы вычислить координаты (tx, ty) точек, где возникают пучности - а это ровно те точки, где выполняется условие tx - x1 = 2 * (tx - x2) для каждой из координат. Или немного иначе: tx = 2 * x2 - x1.

  4. Не забываем проверить, что в исходной матрице нашим координатам хоть что-то соответствовало (m[ty][tx] IS NOT NULL) - то есть мы все еще находимся в рамках поля.

  5. Используя count(DISTINCT (tx, ty)) считаем количество уникальных координат.

WITH matrix AS ( -- превращаем текстовую матрицу в двухмерный массив
  SELECT
    array_agg(regexp_split_to_array(line, '')) m -- превращаем строку в массив символов
  FROM
    regexp_split_to_table($$
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
$$, '[\r\n]+') line -- разбиение по строкам
  WHERE
    btrim(line) <> '' -- отбрасываем пустые строки
)
, freq AS ( -- только антенны
  SELECT
    m[y][x] f
  , x
  , y
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  WHERE
    m[y][x] <> '.' -- нумеруем ячейки и оставляем только содержащие антенны
)
SELECT
  count(DISTINCT (tx, ty))
FROM
  (
    SELECT
      2 * f2.x - f1.x tx -- тут "расстояние до одной в 2 раза больше, чем до другой"
    , 2 * f2.y - f1.y ty
    FROM
      freq f1
    JOIN
      freq f2
        ON f2.f = f1.f AND           -- одинаковая частота
        (f2.x, f2.y) <> (f1.x, f1.y) -- но разные точки
  ) T
, matrix
WHERE
  m[ty][tx] IS NOT NULL; -- отсекаем точки за пределами исходной матрицы

Реальные данные содержат всего 50 строк, поэтому результат мы получаем почти мгновенно - за 16мс:

Причем самой долгой операцией, на 3/4 всего времени, оказывается стартовый поиск в матрице точек с антеннами.

Часть 2

  1. Во второй части нас спрашивают про все точки на "кратном" расстоянии, а не только 2x - поэтому вычисление координаты tx приведем к виду x2 - i * (x1 - x2)., где i будем перебирать от 0 до максимального (greatest) "габарита" нашей матрицы.

explain (analyze)
WITH matrix AS (
  SELECT
    array_agg(regexp_split_to_array(line, '')) m
  FROM
    regexp_split_to_table($$
............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
, freq AS (
  SELECT
    m[y][x] f
  , x
  , y
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  WHERE
    m[y][x] <> '.'
)
SELECT
  count(DISTINCT (tx, ty))
FROM
  matrix
, greatest(
    array_length(m, 1)
  , array_length(m, 2)
  ) lim -- предельный "габарит" матрицы
, LATERAL (
    SELECT
      *
    , f2.x - i * (f1.x - f2.x) tx -- "кратные" координаты
    , f2.y - i * (f1.y - f2.y) ty
    FROM
      freq f1
    JOIN
      freq f2
        ON f2.f = f1.f AND
        (f2.x, f2.y) <> (f1.x, f1.y)
    , generate_series(0, lim) i -- перебор всех потенциальных "кратностей"
  ) T
WHERE
  m[ty][tx] IS NOT NULL;

В этом случае генерация целевых точек занимает побольше времени, но все равно все решение укладывается в 30мс:

Комментарии (0)