SavePearlHarbor

SQL HowTo: рекурсивные циклы и их контроль (Advent of Code 2024, Day 6: Guard Gallivant)

—

от автора

admin

В этой челлендж-серии статей попробуем использовать 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 успешно справился и с такой нетипичной задачей!


ссылка на оригинал статьи https://habr.com/ru/articles/869982/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *