SQL HowTo: поиск пути и дихотомия (Advent of Code 2024, Day 18: RAM Run)

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

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

Сегодня напишем для решения простую реализацию алгоритма Ли и дихотомии.

• Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)

• Решение Day 2: Red-Nosed Reports (логические агрегаты)

• Решение Day 3: Mull It Over ("чистые" регулярки)

• Решение Day 4: Ceres Search (работа с массивами)

• Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка "пузырьком")

• Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)

• Решение Day 7: Bridge Repair ("экспоненциальная" рекурсия)

• Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)

• Решение Day 9: Disk Fragmenter (оптимизируем рекурсию)

• Решение Day 10: Hoof It (поиск "в ширину" внутри цикла)

• Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)

• Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)

• Решение Day 13: Claw Contraption (пошагово решаем СЛУ)

• Решение Day 14: Restroom Redoubt (находим "елочку" с помощью центра масс)

• Решение Day 15: Warehouse Woes (играем в сокобан с помощью json-карты и типа point)

• Решение Day 16: Reindeer Maze (укрощаем рекурсию в лабиринте)

• Решение Day 17: Chronospatial Computer (подбираем значение ветвлением)

• Решение Day 18: RAM Run (поиск пути и дихотомия)

---

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

Advent of Code 2024, Day 18: RAM Run

--- День 18: Пробег RAM ---

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

Как раз когда вы собираетесь осмотреть окрестности, к вам подбегает программа. «Эта область памяти небезопасна! Пользователь неправильно понял, что такое pushdown-автомат, и его алгоритм выталкивает на нас целые байты! Бегите!»

Алгоритм быстр - он будет заставлять байт попадать в ваше пространство памяти раз в наносекунду! К счастью, вы быстрее, и, быстро сканируя алгоритм, вы создаете список байтов, в том порядке, в котором они попадут в ваше пространство памяти (ваши входные данные для головоломки).

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

5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0

Каждая позиция байта задается в виде координат X,Y, где X- расстояние от левого края области памяти, а Y - расстояние от верхнего края области памяти.

Вы и Историки в настоящее время находитесь в верхнем левом углу пространства памяти (в 0,0) и должны достичь выхода в нижнем правом углу (70,70 в вашем пространстве памяти, но 6,6 в этом примере). Вам нужно будет смоделировать падающие байты, чтобы спланировать, где будет безопасно бежать; для начала смоделируйте только первые несколько байтов, падающих в ваше пространство памяти.

Когда байты попадают в ваше пространство памяти, они делают эту координату поврежденной. Поврежденные координаты памяти не могут быть введены вами или Историками, поэтому вам нужно будет тщательно спланировать свой маршрут. Вы также не можете покинуть границы пространства памяти; ваша единственная надежда - добраться до выхода.

В приведенном выше примере, если бы вы изобразили пространство памяти после того, как первые 12 байтов попали (используя . для безопасных и # для поврежденных), это выглядело бы так:

...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....

Вы можете делать шаги вверх, вниз, влево или вправо. После того, как всего 12 байтов испортили ячейки в вашем пространстве памяти, кратчайший путь от верхнего левого угла до выхода будет содержать 22 шага. Вот один из таких путей (отмечен O):

OO.#OOO
.O#OO#O
.OOO#OO
...#OO#
..#OO#.
.#.O#..
#.#OOOO

Имитируйте первый килобайт (1024 байт), падающий на ваше пространство памяти. После этого, какое минимальное количество шагов необходимо, чтобы достичь выхода?

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

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

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

В приведенном выше примере после того, как байт падает в 1,1, все еще остается путь к выходу:

O..#OOO
O##OO#O
O#OO#OO
OOO#OO#
###OO##
.##O###
#.#OOOO

Однако после добавления следующего байта (в точке 6,1) пути к выходу больше нет:

...#...
.##..##
.#..#..
...#..#
###..##
.##.###
#.#....

Итак, в этом примере координаты первого байта, который делает выход недоступным, равны 6,1.

Смоделируйте больше байтов, которые вот-вот испортят ваше пространство памяти. Каковы координаты первого байта, который сделает выход недоступным из вашей начальной позиции? (Укажите ответ в виде двух целых чисел, разделенных запятой, без других символов.)

Часть 1

Итак, для решения нам требуется найти кратчайший путь между начальной и конечной клетками на карте с препятствиями. Для этого есть классическое решение - волновой алгоритм Ли. Очень похожую реализацию я использовал ранее для генерации лабиринтов.

Сначала определим координаты угловых стартовой и финальной точек и "арену":

WITH RECURSIVE src AS (
  SELECT
    '(0,0)' s
  , '(6,6)' e
)
, arena AS (
  SELECT
    box(
      s::point
    , e::point
    ) -- прямоугольник с углами (0,0) и (N,N)
  FROM
    src
)

Соберем все "выпадающие" байты в массив с тестовыми представлениями координат клеток:

, bytes AS (
  SELECT
    array_agg(point(line[1]::integer, line[2]::integer)::text) corrupted -- массив координат "текстом"
  FROM
    regexp_matches($$
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0
$$
  , '(\d+),(\d+)'
  , 'g') line
)

corrupted
{"(5,4)","(4,2)","(4,5)","(3,0)","(2,1)"
,"(6,3)","(2,4)","(1,5)","(0,6)","(3,3)"
,"(2,6)","(5,1)","(1,2)","(5,5)","(2,5)"
,"(6,5)","(1,4)","(0,4)","(6,4)","(1,1)"
,"(6,1)","(1,0)","(0,5)","(1,6)","(2,0)"}

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

В качестве представления координат каждой из клеток будем использовать тип point и его текстовое представление:

, r AS (
  SELECT
    0 i
  , ARRAY[s::text] fill -- уже "залитые" клетки
  , ARRAY[s::text] wave -- "фронт" волны
  FROM
    src
UNION ALL
  SELECT
    i + 1
  , ARRAY(
      SELECT DISTINCT
        unnest
      FROM
        unnest(r.fill || T.wave)
    ) -- объединяем с уникализацией множества ранее и сейчас достигнутых клеток
  , T.wave
  FROM
    r
  , src
  , arena
  , bytes
  , LATERAL (
      SELECT
        array_agg(DISTINCT np::text) wave -- уникализируем текстовые представления "точек"
      FROM
        unnest(r.wave) cell -- "разворачиваем" массив координат клеток "волны"
      , point(cell) p       -- преобразуем каждую пару координат в геометрическую точку
      , LATERAL (           -- определяем доступные ячейки из текущей
          VALUES
            (p + '(1,0)'::point)  -- справа
          , (p + '(0,1)'::point)  -- снизу
          , (p + '(-1,0)'::point) -- слева
          , (p + '(0,-1)'::point) -- сверху
        ) n(np)
      WHERE
        np <@ box AND                       -- новая клетка должна лежать в границах арены
        np::text <> ALL(corrupted[:12]) AND -- не принадлежать нужному набору "поврежденных"
        np::text <> ALL(r.fill)             -- и не входить в список уже достигнутых ранее
    ) T
  WHERE
    e <> ALL(r.wave) -- "гоним волну", пока конечная точка не окажется среди достигнутых
)

Если изобразить номер шага на карте из примера "после 12 байтов", получится примерно так:

012#89A
12#67#B
2345#DC
345#FE#
45#HG#.
5#JI#M.
#.#JKLM

Для решения задачи нам осталось лишь найти максимальный номер шага:

WITH RECURSIVE src AS (
  SELECT
    '(0,0)' s
  , '(6,6)' e
)
, arena AS (
  SELECT
    box(
      s::point
    , e::point
    ) -- прямоугольник с углами (0,0) и (N,N)
  FROM
    src
)
, bytes AS (
  SELECT
    array_agg(point(line[1]::integer, line[2]::integer)::text) corrupted -- массив координат "текстом"
  FROM
    regexp_matches($$
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0
$$
  , '(\d+),(\d+)'
  , 'g') line
)
, r AS (
  SELECT
    0 i
  , ARRAY[s::text] fill -- уже "залитые" клетки
  , ARRAY[s::text] wave -- "фронт" волны
  FROM
    src
UNION ALL
  SELECT
    i + 1
  , ARRAY(
      SELECT DISTINCT
        unnest
      FROM
        unnest(r.fill || T.wave)
    ) -- объединяем с уникализацией множества ранее и сейчас достигнутых клеток
  , T.wave
  FROM
    r
  , src
  , arena
  , bytes
  , LATERAL (
      SELECT
        array_agg(DISTINCT np::text) wave -- уникализируем текстовые представления "точек"
      FROM
        unnest(r.wave) cell -- "разворачиваем" массив координат клеток "волны"
      , point(cell) p       -- преобразуем каждую пару координат в геометрическую точку
      , LATERAL (           -- определяем доступные ячейки из текущей
          VALUES
            (p + '(1,0)'::point)  -- справа
          , (p + '(0,1)'::point)  -- снизу
          , (p + '(-1,0)'::point) -- слева
          , (p + '(0,-1)'::point) -- сверху
        ) n(np)
      WHERE
        np <@ box AND                       -- новая клетка должна лежать в границах арены
        np::text <> ALL(corrupted[:12]) AND -- не принадлежать нужному набору "поврежденных"
        np::text <> ALL(r.fill)             -- и не входить в список уже достигнутых ранее
    ) T
  WHERE
    e <> ALL(r.wave) -- "гоним волну", пока конечная точка не окажется среди достигнутых
)
SELECT
  max(i)
FROM
  r;

На реальных данных (карта 70x70 и 1024 первых байта) решение занимает чуть меньше 3 секунд:

Часть 2

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

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

В этом случае нам потребуется проверить не более log2(N) вариантов - то есть, грубо можно оценить для входного набора как 12 * 3 = 36 секунд.

Сделаем внешний рекурсивный "цикл", реализующий дихотомию:

, ro AS (
  SELECT
    0 step
  , 0 lr
  , array_length(corrupted, 1) rr
  FROM
    bytes
UNION ALL
  SELECT
    step + 1
  , CASE WHEN cond THEN (lr + rr) >> 1 ELSE lr END
  , CASE WHEN cond THEN rr ELSE ((lr + rr) >> 1) END
  FROM
    ro
  , LATERAL (
      WITH RECURSIVE r AS (
        ...
              np::text <> ALL(corrupted[:((lr + rr) >> 1)]) AND -- нужное количество первых байт
        ...
      )
      SELECT
        e = ANY(wave) cond -- достигли ли мы конечной точки на последнем шаге рекурсии?
      FROM
        r
      , src
      ORDER BY
        i DESC
      LIMIT 1
    ) T
  WHERE
    lr < rr - 1 -- пока левая и правая границы не стали соседями
)

step | lr | rr
   0 |  0 | 25 -- ( 0 + 25) >> 1 = 12 - выход доступен, идем вправо
   1 | 12 | 25 -- (12 + 25) >> 1 = 18 - выход доступен, идем вправо
   2 | 18 | 25 -- (18 + 25) >> 1 = 21 - выход недоступен, идем влево
   3 | 18 | 21 -- (18 + 21) >> 1 = 19 - выход доступен, идем вправо
   4 | 19 | 21 -- (19 + 21) >> 1 = 20 - выход доступен, идем вправо
   5 | 20 | 21 -- зажато - при 20 выход доступен, при 21 - уже нет

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

SELECT
  regexp_replace(
    corrupted[(
      SELECT
        rr
      FROM
        ro
      ORDER BY
        step DESC
      LIMIT 1
    )]
  , '[\(\)]' -- убираем лишние скобки
  , ''
  , 'g')
FROM
  bytes;

Полный вариант запроса:

WITH RECURSIVE src AS (
  SELECT
    '(0,0)' s
  , '(6,6)' e
)
, arena AS (
  SELECT
    box(
      s::point
    , e::point
    ) -- прямоугольник с углами (0,0) и (N,N)
  FROM
    src
)
, bytes AS (
  SELECT
    array_agg(point(line[1]::integer, line[2]::integer)::text) corrupted -- массив координат "текстом"
  FROM
    regexp_matches($$
5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0
$$
  , '(\d+),(\d+)'
  , 'g') line
)
, ro AS (
  SELECT
    0 step
  , 0 lr
  , array_length(corrupted, 1) rr
  FROM
    bytes
UNION ALL
  SELECT
    step + 1
  , CASE WHEN cond THEN (lr + rr) >> 1 ELSE lr END
  , CASE WHEN cond THEN rr ELSE ((lr + rr) >> 1) END
  FROM
    ro
  , LATERAL (
      WITH RECURSIVE r AS (
        SELECT
          0 i
        , ARRAY[s::text] fill -- уже "залитые" клетки
        , ARRAY[s::text] wave -- "фронт" волны
        FROM
          src
      UNION ALL
        SELECT
          i + 1
        , ARRAY(
            SELECT DISTINCT
              unnest
            FROM
              unnest(r.fill || T.wave)
          ) -- объединяем с уникализацией множества ранее и сейчас достигнутых клеток
        , T.wave
        FROM
          r
        , src
        , arena
        , bytes
        , LATERAL (
            SELECT
              array_agg(DISTINCT np::text) wave -- уникализируем текстовые представления "точек"
            FROM
              unnest(r.wave) cell -- "разворачиваем" массив координат клеток "волны"
            , point(cell) p       -- преобразуем каждую пару координат в геометрическую точку
            , LATERAL (           -- определяем доступные ячейки из текущей
                VALUES
                  (p + '(1,0)'::point)  -- справа
                , (p + '(0,1)'::point)  -- снизу
                , (p + '(-1,0)'::point) -- слева
                , (p + '(0,-1)'::point) -- сверху
              ) n(np)
            WHERE
              np <@ box AND                       -- новая клетка должна лежать в границах арены
              np::text <> ALL(corrupted[:((lr + rr) >> 1)]) AND -- нужное количество первых байт
              np::text <> ALL(r.fill)             -- и не входить в список уже достигнутых ранее
          ) T
        WHERE
          e <> ALL(r.wave) -- "гоним волну", пока конечная точка не окажется среди достигнутых
      )
      SELECT
        e = ANY(wave) cond -- достигли ли мы конечной точки на последнем шаге рекурсии?
      FROM
        r
      , src
      ORDER BY
        i DESC
      LIMIT 1
    ) T
  WHERE
    lr < rr - 1 -- пока левая и правая границы не стали соседями
)
SELECT
  regexp_replace(
    corrupted[(
      SELECT
        rr
      FROM
        ro
      ORDER BY
        step DESC
      LIMIT 1
    )]
  , '[\(\)]' -- убираем лишние скобки
  , ''
  , 'g')
FROM
  bytes;

Вместо предельных 36 секунд реальное решение заняло даже меньше 8 секунд: