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

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

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

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

Advent of Code 2024, Day 6: Guard Gallivant

--- День 6: Бродящий охранник ---

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

Вам все еще нужно быть осторожным с временными парадоксами, поэтому будет важно избегать кого-либо из 1518, пока Историки ищут Шефа. К сожалению, эту часть лаборатории патрулирует один охранник.

Может быть, вы сможете заранее решить, куда пойдет охрана, чтобы Историки могли безопасно провести поиск?

Вы начинаете с создания карты (вход вашего пазла) ситуации. Например:

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

На карте показано текущее положение охранника ^(чтобы указать, что охранник в данный момент смотрит вверх с точки зрения карты). Любые препятствия — ящики, столы, алхимические реакторы и т. д. — показаны как #.

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

  • Если прямо перед вами что-то находится, повернитесь направо на 90 градусов.

  • В противном случае сделайте шаг вперед.

Следуя вышеописанному протоколу, охранник несколько раз поднимается, пока не достигнет препятствия (в данном случае — кучи неисправных прототипов костюмов):

....#.....
....^....#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...

Поскольку перед охранником теперь возникло препятствие, он поворачивает направо, прежде чем продолжить движение прямо в новом направлении:

....#.....
........>#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#...

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

....#.....
.........#
..........
..#.......
.......#..
..........
.#......v.
........#.
#.........
......#...

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

....#.....
.........#
..........
..#.......
.......#..
..........
.#........
........#.
#.........
......#v..

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

....#.....
....XXXXX#
....X...X.
..#.X...X.
..XXXXX#X.
..X.X.X.X.
.#XXXXXXX.
.XXXXXXX#.
#XXXXXXX..
......#X..

В этом примере охранник посетит 41различную точку на вашей карте.

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

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

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

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

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

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

В приведенном выше примере есть только 6разных положений, в которых новое препятствие заставит охранника застрять в петле. Диаграммы этих шести ситуаций используют Oдля обозначения нового препятствия, |для показа положения, в котором охранник движется вверх/вниз, -для показа положения, в котором охранник движется влево/вправо, и +для показа положения, в котором охранник движется как вверх/вниз, так и влево/вправо.

Вариант первый, поставить печатный станок рядом со стартовой позицией охранника:

....#.....
....+---+#
....|...|.
..#.|...|.
....|..#|.
....|...|.
.#.O^---+.
........#.
#.........
......#...

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

....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
......O.#.
#.........
......#...

Третий вариант: поставьте ящик с прототипом ткани, пропитанной дымоходным газом, рядом со столом, за которым можно сидеть стоя, в правом нижнем квадранте:

....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
.+----+O#.
#+----+...
......#...

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

....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
..|...|.#.
#O+---+...
......#...

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

....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
....|.|.#.
#..O+-+...
......#...

Вариант шестой, поставить бачок с клеем «Суверен» прямо рядом с бачком с универсальным растворителем:

....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
.+----++#.
#+----++..
......#O..

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

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

Часть 1

  1. Сначала преобразуем нашу карту в двумерный массив, ровно как делали это в Day 4.

  2. Сформируем набор массивов, описывающих направления движений вверх/вниз/влево/вправо.

  3. Найдем исходную позицию охранника на карте (x, y) и зададим направление движения "вверх" du.

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

  5. Остается лишь подсчитать количество уникальных позиций, которые мы прошли: count(DISTINCT (x, y)).

WITH RECURSIVE matrix AS ( -- карту - в матрицу (двумерный массив)
  SELECT
    array_agg(regexp_split_to_array(line, '')) m
  FROM
    regexp_split_to_table($$
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
, dir AS ( -- набор "направлений"
  SELECT
    ARRAY[0, -1] du -- вверх
  , ARRAY[0, +1] dd -- вниз
  , ARRAY[-1, 0] dl -- влево
  , ARRAY[+1, 0] dr -- вправо
)
, r AS ( -- моделируем "обход"
  SELECT
    x
  , y
  , du d  -- исходное направление движения "вверх"
  FROM
    matrix
  , generate_subscripts(m, 1) y -- перебираем все ячейки матрицы
  , generate_subscripts(m, 2) x
  , dir
  WHERE
    m[y][x] = '^' -- стартовая позиция охранника в матрице
UNION ALL
  SELECT
    -- если можем ходить - принимаем новую позицию и сохраняем направление
    -- если не можем - сохраняем позицию и принимаем новое направление
    CASE WHEN cond THEN nx ELSE x  END
  , CASE WHEN cond THEN ny ELSE y  END
  , CASE WHEN cond THEN d  ELSE nd END
  FROM
    matrix
  , r
  , LATERAL ( -- предрасчитываем плановые значения для следующего шага
      SELECT
        x + d[1] nx
      , y + d[2] ny
      , CASE d
          WHEN dl THEN du -- влево -> вверх
          WHEN du THEN dr -- вверх -> вправо
          WHEN dr THEN dd -- вправо -> вниз
          WHEN dd THEN dl -- вниз -> ввлево
        END nd
      FROM
        dir
    ) n
  , LATERAL (
      SELECT
        coalesce(m[ny][nx], '') <> '#' cond -- можно ли сходить, куда хотим?
    ) T
  WHERE
    m[ny][nx] IS NOT NULL -- шагаем, пока не вышли за границы
)
SELECT
  count(DISTINCT (x, y)) -- подсчитываем количество уникальных клеток на нашем пути
FROM
  r;

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

Часть 2

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

  1. Точно так же находим весь путь, только по дороге еще и подчитываем номер текущего шага i.

  2. Отбираем из него только уникальные посещенные позиции (поскольку мы могли пройти одну позицию несколько раз в разных направлениях), и для каждой находим с помощью DISTINCT ON и оконной функции lag(?) OVER(ORDER i) предыдущее состояние (px, py, pd) - то есть где находился и куда двигался охранник, прежде чем попасть в текущую позицию.

  3. Для каждой из них эмулируем постановку препятствия в эту позицию, расширением условия (nx, ny) <> (T.x, T.y) внутри точно той же рекурсии повторного построения пути из "предыдущей" позиции. Очевидно, что повторять заново построение всего пути раньше нее не имеет смысла - мы и так там ни во что новое упереться не могли.

  4. На вложенную генерацию пути накладываем "защиту от зацикливания" CYCLE x, y, d SET is_cycle USING path - то есть проверяем, что уже проходили ту же позицию, двигаясь в том же направлении.

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

  6. Суммируем количество этих позиций.

WITH RECURSIVE matrix AS (
  SELECT
    array_agg(regexp_split_to_array(line, '')) m
  FROM
    regexp_split_to_table($$
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
, dir AS (
  SELECT
    ARRAY[0, -1] du
  , ARRAY[0, +1] dd
  , ARRAY[-1, 0] dl
  , ARRAY[+1, 0] dr
)
, src AS ( -- поиск стартовой позиции
  SELECT
    x
  , y
  , du d
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  , dir
  WHERE
    m[y][x] = '^'
)
, r AS ( -- поиск первичного пути с подсчетом шагов
  SELECT
    0 i
  , *
  FROM
    src
UNION ALL
  SELECT
    i + 1
  , CASE WHEN cond THEN nx ELSE x  END
  , CASE WHEN cond THEN ny ELSE y  END
  , CASE WHEN cond THEN d  ELSE nd END
  FROM
    matrix
  , r
  , LATERAL (
      SELECT
        x + d[1] nx
      , y + d[2] ny
      , CASE d
          WHEN dl THEN du
          WHEN du THEN dr
          WHEN dr THEN dd
          WHEN dd THEN dl
        END nd
      FROM
        dir
    ) n
  , LATERAL (
      SELECT
        coalesce(m[ny][nx], '') <> '#' cond
    ) T
  WHERE
    m[ny][nx] IS NOT NULL
)
SELECT
  count(*) FILTER(WHERE is_cycle) -- количество позиций, приводящих к зацикливанию
FROM
  (
     SELECT DISTINCT ON(x, y) -- список всех посещенных позиций, куда будем ставить препятствие
       x
     , y
       -- состояние на предыдущем шаге
     , lag(x) OVER(ORDER BY i) px
     , lag(y) OVER(ORDER BY i) py
     , lag(d) OVER(ORDER BY i) pd
     FROM
       r
     ORDER BY
       x, y, i
    ) T
, LATERAL (
    WITH RECURSIVE r AS ( -- построение пути с препятствием в текущей позиции
      SELECT
        T.px x -- стартуем с предыдущей позиции
      , T.py y
      , T.pd d
      WHERE
        (T.x, T.y) <> (SELECT x, y FROM src)
    UNION ALL
      SELECT
        CASE WHEN cond THEN nx ELSE x  END
      , CASE WHEN cond THEN ny ELSE y  END
      , CASE WHEN cond THEN d  ELSE nd END
      FROM
        matrix
      , r
      , LATERAL (
          SELECT
            x + d[1] nx
          , y + d[2] ny
          , CASE d
              WHEN dl THEN du
              WHEN du THEN dr
              WHEN dr THEN dd
              WHEN dd THEN dl
            END nd
          FROM
            dir
        ) n
      , LATERAL (
          SELECT
            coalesce(m[ny][nx], '') <> '#' AND -- не было блока, куда хотим сходить
            (nx, ny) <> (T.x, T.y) cond        -- и мы его сейчас туда не ставили
        ) T
      WHERE
        m[ny][nx] IS NOT NULL
    ) CYCLE x, y, d SET is_cycle USING path -- защита от зацикливания
    SELECT
      bool_or(is_cycle) is_cycle -- цикл в какой-то момент все-таки возник
    FROM
      r
  ) chk;

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

Основная причина тут, конечно, в необходимости временно сохранять на диске для проверки зацикливания полный путь path на каждой итерации общим объемом до 171GB.

Несмотря на это, PostgreSQL успешно справился и с такой нетипичной задачей!