Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

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

Advent of Code 2025, Day 7: Laboratories

--- День 7: Лаборатории ---

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

Судя по большой вывеске с надписью «телепортационный центр», похо��е, они изучают телепортацию; невольно захочешь попробовать это сам и ступить на большую желтую телепортационную площадку.

Внезапно вы оказываетесь в незнакомой комнате! В комнате нет дверей; единственный выход - телепорт. К сожалению, телепорт, похоже, испускает магический дым.

Поскольку это лаборатория телепортации, здесь валяется множество запасных частей, руководств и диагностического оборудования. После подключения одного из диагностических инструментов он любезно отображает код ошибки 0H-N0, что, по-видимому, означает проблему с одним из тахионных коллекторов.

Вы быстро находите схему тахионного многообразия (ваш вход для головоломки). Тахионный луч входит в многообразие в точке, отмеченной S; тахионные лучи всегда движутся вниз. Тахионные лучи свободно проходят через пустое пространство (.). Однако, если тахионный луч сталкивается с разделителем (^), луч останавливается; вместо этого новый тахионный луч продолжает движение непосредственно слева и непосредственно справа от разделителя.

Например:

.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

В этом примере входящий тахионный луч (|) простирается вниз от Sдо тех пор, пока не достигнет первого разветвителя:

.......S.......
.......|.......
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

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

.......S.......
.......|.......
......|^|......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

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

.......S.......
.......|.......
......|^|......
......|.|......
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

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

.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

Этот процесс продолжается до тех пор, пока все тахионные лучи не достигнут разветвителя или не выйдут из коллектора:

.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
.....|.|.|.....
....|^|^|^|....
....|.|.|.|....
...|^|^|||^|...
...|.|.|||.|...
..|^|^|||^|^|..
..|.|.|||.|.|..
.|^|||^||.||^|.
.|.|||.||.||.|.
|^|^|^|^|^|||^|
|.|.|.|.|.|||.|

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

Проанализируйте свою диаграмму многообразия. Сколько раз луч разделится?

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

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

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

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

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

В приведенном выше примере представлено множество временных шкал. Например, есть временная шкала, где частица всегда двигалась влево:

.......S.......
.......|.......
......|^.......
......|........
.....|^.^......
.....|.........
....|^.^.^.....
....|..........
...|^.^...^....
...|...........
..|^.^...^.^...
..|............
.|^...^.....^..
.|.............
|^.^.^.^.^...^.
|..............

Или же существует временная шкала, где частица поочередно двигалась влево и вправо на каждом разветвителе:

.......S.......
.......|.......
......|^.......
......|........
......^|^......
.......|.......
.....^|^.^.....
......|........
....^.^|..^....
.......|.......
...^.^.|.^.^...
.......|.......
..^...^|....^..
.......|.......
.^.^.^|^.^...^.
......|........

Или же существует временная шкала, где частица оказывается в той же точке, что и на альтернативной време��ной шкале, но движется к ней совершенно другим путем:

.......S.......
.......|.......
......|^.......
......|........
.....|^.^......
.....|.........
....|^.^.^.....
....|..........
....^|^...^....
.....|.........
...^.^|..^.^...
......|........
..^..|^.....^..
.....|.........
.^.^.^|^.^...^.
......|........

В этом примере частица в итоге оказывается на 40разных временных линиях.

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

Часть 1

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

WITH RECURSIVE matrix AS(
  SELECT
    x
  , y
  , c
  FROM
    regexp_matches($$
.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
    $$, '(?:\.|\^|S)+', 'g')
      WITH ORDINALITY y(line, y)       -- разбиение по строкам
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(c, x)          -- разбиение по столбцам (символам)
)

В данном случае нам важно сохранить и факт наличия "пустых" (.) точек на карте, чтобы в последующем легко определять, находимся ли мы мы все еще в пределах карты или уже вышли за границы.

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

  • стартовая позиция луча находится в клетке с символом S

  • на каждом шаге y-координата луча всегда увеличивается на 1

  • при этом луч может или остаться в той же x-координате, или разделится на x-1 и x+1 - для этого воспользуемся возможностью "размножить" строки конструкцией unnest(ARRAY[...])

  • поскольку нам требуется анализировать только уникальные позиции луча, используем для шага рекурсии оператор UNION вместо UNION ALL

  • координаты каждой новой клетки "пересечем" с клетками исходной карты - вышедшие за границы автоматически отсеются, в том числе и когда y-координата уйдет за пределы - в этот момент рекурсия и остановится, поскольку прекратится генерация новых записей

, r AS (
  SELECT
    x
  , y
  FROM
    matrix
  WHERE
    c = 'S' -- стартовая позиция
UNION -- уникализация путей
  SELECT
    unnest( -- "размножение" строк в зависимости от условия
      CASE c
        WHEN '^' THEN ARRAY[r.x - 1, r.x + 1]
        ELSE ARRAY[r.x]
      END
    )
  , r.y + 1 -- луч идет всегда вниз
  FROM
    r
  NATURAL JOIN -- пересекаем с клетками исходной карты
    matrix m
)

Для исходного примера это будет выглядеть примерно так:

 x | y
 8 | 1 -- точка S, луч #1
 8 | 2 -- #1, просто падает вниз
 8 | 3 -- #1
 7 | 4 -- #2, разделение #1 в точке (8;3) на #2 и #3
 9 | 4 -- #3
 7 | 5 -- #2
 9 | 5 -- #3
 6 | 6 -- #4, разделение #2 в точке (7;5) на #4 и #5
 8 | 6 -- #5, слияние разделившихся выше #2 и #3
10 | 6 -- #6, разделение #3 в точке (9;5) на #5 и #6
 6 | 7 -- #4
 8 | 7 -- #5
10 | 7 -- #6
...

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

WITH RECURSIVE matrix AS(
  SELECT
    x
  , y
  , c
  FROM
    regexp_matches($$
.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
    $$, '(?:\.|\^|S)+', 'g')
      WITH ORDINALITY y(line, y)       -- разбиение по строкам
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(c, x)          -- разбиение по столбцам (символам)
)
, r AS (
  SELECT
    x
  , y
  FROM
    matrix
  WHERE
    c = 'S' -- стартовая позиция
UNION -- уникализация путей
  SELECT
    unnest( -- "размножение" строк в зависимости от условия
      CASE c
        WHEN '^' THEN ARRAY[r.x - 1, r.x + 1]
        ELSE ARRAY[r.x]
      END
    )
  , r.y + 1 -- луч идет всегда вниз
  FROM
    r
  NATURAL JOIN -- пересекаем с клетками исходной карты
    matrix m
)
SELECT
  count(*) FILTER(WHERE c = '^') -- сколько пройденных клеток содержат разделители
FROM
  r
NATURAL JOIN
   matrix;

Часть 2

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

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

.......S....... -- стартовая точка
.......1.......
......1^1...... -- до каждой новой позиции столько же путей, как до разделителя
......1.1......
.....1^2^1..... -- при слиянии пути просуммировались
.....1.2.1.....
....1^3^3^1....
....1.3.3.1....
...1^4^331^1...
...1.4.331.1...
..1^5^434^2^1.. -- слияние 3 путей луча, который "просто прошел" + 1 от "разделившегося"
..1.5.434.2.1..
.1^154^74.21^1.
.1.154.74.21.1.
1^2^A^B^B^211^1
1.2.A.B.B.211.1 -- 1 + 2 + 10 + 11 + 11 + 2 + 1 + 1 + 1 = 40

По этой причине шаг рекурсии несколько усложнится:

  • добавляем отслеживание количества путей в каждой достигнутой клетке

  • уникализацию клетки вместе с суммированием путей вносим под шаг рекурсии - для этого рекурсивный шаг придется обернуть в "лишние" скобки и добавить вспомогательную CTE, чтобы обращаться к r лишь единожды

, r AS (
  SELECT
    x
  , y
  , 1::numeric pathes -- исходная клетка достижима единственным способом
  FROM
    matrix
  WHERE
    c = 'S'
UNION ALL
  (
    WITH T AS ( -- вспомогательная CTE
      SELECT
        unnest(
          CASE c
            WHEN '^' THEN ARRAY[r.x - 1, r.x + 1]
            ELSE ARRAY[r.x]
          END
        ) x
      , r.y + 1 y
      , pathes -- сохраняем количество путей
      FROM
        r
      NATURAL JOIN
        matrix m
    )
    SELECT DISTINCT ON(x, y)              -- уникализируем клетки
      x
    , y
    , sum(pathes) OVER(PARTITION BY x, y) -- суммируем количество путей в каждой
    FROM
      T
  )
)

Остается лишь просуммировать количество путей, достигнутое во всех клетках с максимальной y-координатой:

WITH RECURSIVE matrix AS(
  SELECT
    x
  , y
  , c
  FROM
    regexp_matches($$
.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
    $$, '(?:\.|\^|S)+', 'g')
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(c, x)
)
, r AS (
  SELECT
    x
  , y
  , 1::numeric pathes -- исходная клетка достижима единственным способом
  FROM
    matrix
  WHERE
    c = 'S'
UNION ALL
  (
    WITH T AS ( -- вспомогательная CTE
      SELECT
        unnest(
          CASE c
            WHEN '^' THEN ARRAY[r.x - 1, r.x + 1]
            ELSE ARRAY[r.x]
          END
        ) x
      , r.y + 1 y
      , pathes -- сохраняем количество путей
      FROM
        r
      NATURAL JOIN
        matrix m
    )
    SELECT DISTINCT ON(x, y)              -- уникализируем клетки
      x
    , y
    , sum(pathes) OVER(PARTITION BY x, y) -- суммируем количество путей в каждой
    FROM
      T
  )
)
SELECT
  sum(pathes)
FROM
  r
WHERE
  y = (SELECT max(y) FROM r); -- максимальная достигнутая y-координата

Замечу, что если бы CTE r была у нас настолько больших размеров, что повторное обращение к ней (сначала нашли максимум, потом отобрали все записи с ним) было бы неэффективно, мы могли бы переписать этот блок, отобрав с помощью FETCH ... WITH TIES сразу все записи с максимальным значением ключа сортировки:

SELECT
  sum(pathes)
FROM
  (
    SELECT
      *
    FROM
      r
    ORDER BY
      y DESC           -- ключ сортировки (y)
    FETCH FIRST 1 ROWS -- нам нужна хотя бы одна запись
      WITH TIES        -- получаем все записи с совпадающим значением ключа сортировки
  ) T;