Как стать автором
Поиск
Написать публикацию
Обновить
167.91
Рейтинг
Тензор
Разработчик системы Saby

SQL HowTo: кратчайший путь «туда и обратно» и его самосоединение (Advent of Code 2024, Day 20: Race Condition)

Уровень сложностиПростой
Время на прочтение9 мин
Количество просмотров1.2K
Блог компании ТензорPostgreSQL*SQL*Алгоритмы*Занимательные задачки
Кейс

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

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

Дважды применяем волновой алгоритм для нахождения единственного кратчайшего пути и самосоединение для поиска "читов".

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

Advent of Code 2024, Day 20: Race Condition

--- День 20: Состояние гонки ---

Историки снова довольно пикселизированы. На этот раз над вами возвышается массивное черное здание — вы прямо за пределами ЦП!

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

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

Они дают вам карту ипподрома (ваш пазл). Например:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Карта состоит из пути (.), включая начальную (S) и конечную (E) позиции (обе они также считаются путем), и стен (#).

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

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

Правила для чита очень строгие. Только один раз за гонку программа может отключить столкновение на срок до 2 пикосекунд. Это позволяет программе проходить сквозь стены, как если бы это была обычная трасса. В конце чита программа должна вернуться на обычную трассу; в противном случае она получит ошибку сегментации и будет дисквалифицирована.

Таким образом, программа может пройти дистанцию ​​за 72 пикосекунды (сэкономив 12 пикосекунд), сжульничав для двух ходов, отмеченных 1 и 2:

###############
#...#...12....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Или программа может пройти дистанцию ​​за 64 пикосекунды (сэкономив 20 пикосекунд), сжульничав для двух ходов, отмеченных 1 и 2:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...12..#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Этот чит экономит 38 пикосекунд:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.####1##.###
#...###.2.#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Этот чит экономит 64 пикосекунды и приводит программу прямо в конец:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..21...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

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

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

  • Существует 14 приемов, которые экономят 2 пикосекунды.

  • Существует 14 приемов, которые экономят 4 пикосекунды.

  • Есть 2 способа сэкономить 6 пикосекунд.

  • Есть 4 способа сэкономить 8 пикосекунд.

  • Есть 2 способа сэкономить 10 пикосекунд.

  • Есть 3 способа сэкономить 12 пикосекунд.

  • Есть один чит, который экономит 20 пикосекунд.

  • Есть один чит, который экономит 36 пикосекунд.

  • Есть один чит, который экономит 38 пикосекунд.

  • Есть один чит, который экономит 40 пикосекунд.

  • Есть один чит, который экономит 64 пикосекунды.

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

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

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

Теперь, в дополнение ко всем читам, которые были возможны всего за две пикосекунды, возможны еще многие читы. Этот чит за шесть пикосекунд экономит 76 пикосекунд:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#1#####.#.#.###
#2#####.#.#...#
#3#####.#.###.#
#456.E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

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

###############
#...#...#.....#
#.#.#.#.#.###.#
#S12..#.#.#...#
###3###.#.#.###
###4###.#.#...#
###5###.#.###.#
###6.E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Читы не обязательно должны использовать все 20 пикосекунд; читы могут длиться любое количество времени вплоть до 20 пикосекунд (но все равно могут закончиться только тогда, когда программа находится в нормальном режиме). Любое неиспользованное время чита теряется; его нельзя сохранить для другого чита позже.

Вам все еще понадобится список лучших читов, но теперь есть еще больше вариантов для выбора. Вот количество читов в этом примере, которые экономят 50 пикосекунд или больше:

  • Существует 32 способа сэкономить 50 пикосекунд.

  • Существует 31 способ сэкономить 52 пикосекунды.

  • Существует 29 способов сэкономить 54 пикосекунды.

  • Существует 39 способов сэкономить 56 пикосекунд.

  • Существует 25 способов сэкономить 58 пикосекунд.

  • Существует 23 способа сэкономить 60 пикосекунд.

  • Существует 20 приемов, которые экономят 62 пикосекунды.

  • Существует 19 приемов, которые экономят 64 пикосекунды.

  • Существует 12 приемов, которые экономят 66 пикосекунд.

  • Существует 14 приемов, которые экономят 68 пикосекунд.

  • Существует 12 приемов, которые экономят 70 пикосекунд.

  • Существует 22 способа сэкономить 72 пикосекунды.

  • Есть 4 способа сэкономить 74 пикосекунды.

  • Есть 3 способа сэкономить 76 пикосекунд.

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

Часть 1

В задаче нас просят найти количество "читов" длины 2, связывающих точки пути, отстоящие не менее чем на 100 шагов.

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

WITH RECURSIVE matrix AS MATERIALIZED (
  SELECT
    array_agg(regexp_split_to_array(line[1], '')) m
  FROM
    regexp_matches(
      $$
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
$$
    , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
)

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

, init AS MATERIALIZED ( -- начальная/конечная точки
  SELECT
    point(
      min(x) FILTER(WHERE m[y][x] = 'S')
    , min(y) FILTER(WHERE m[y][x] = 'S')
    )::text s
  , point(
      min(x) FILTER(WHERE m[y][x] = 'E')
    , min(y) FILTER(WHERE m[y][x] = 'E')
    )::text e
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  WHERE
    m[y][x] <> '.'
)
, rs AS ( -- волна от начала к концу
  SELECT
    0 i
  , e
  , ARRAY[s] fill
  , ARRAY[s] wave
  FROM
    init
UNION ALL
  SELECT
    i + 1
  , e
  , fill || T.wave
  , T.wave
  FROM
    rs
  , matrix
  , LATERAL (
      SELECT
        array_agg(DISTINCT (d.x, d.y)::text) wave
      FROM
        (
          SELECT
            p[0]::integer x
          , p[1]::integer y
          FROM
            unnest(wave::point[]) p
        ) s
      , LATERAL (
          VALUES
            (s.x - 1, s.y)
          , (s.x + 1, s.y)
          , (s.x, s.y - 1)
          , (s.x, s.y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] <> '#' AND
        (d.x, d.y)::text <> ALL(fill)
    ) T
  WHERE
    e <> ALL(rs.wave)
)
, re AS ( -- волна от конца к началу
  SELECT
    (SELECT max(i) FROM rs) i
  , s
  , ARRAY[e] fill
  , ARRAY[e] wave
  FROM
    init
UNION ALL
  SELECT
    i - 1
  , s
  , fill || T.wave
  , T.wave
  FROM
    re
  , matrix
  , LATERAL (
      SELECT
        array_agg(DISTINCT (d.x, d.y)::text) wave
      FROM
        (
          SELECT
            p[0]::integer x
          , p[1]::integer y
          FROM
            unnest(wave::point[]) p
        ) s
      , LATERAL (
          VALUES
            (s.x - 1, s.y)
          , (s.x + 1, s.y)
          , (s.x, s.y - 1)
          , (s.x, s.y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] <> '#' AND
        (d.x, d.y)::text <> ALL(fill)
    ) T
  WHERE
    s <> ALL(re.wave)
)

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

, path AS (
  SELECT
    i
 , (ARRAY( -- пересечение множеств - единственная точка пути на i-м шаге
      SELECT unnest(rs.wave)
    INTERSECT ALL
      SELECT unnest(re.wave)
    ))[1]::point cell
  FROM
    rs
  JOIN
    re
      USING(i)
)

Осталось лишь вычислить количество "читов".

Длина чита (2) - это сумма расстояний "по X и "по Y", а сэкономленное расстояние пути - разница между номерами начального/конечного шагов чита за вычетом длины чита:

SELECT
  count(*) FILTER(
    WHERE
      (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer = 2 AND
      p2.i - p1.i - (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer >= 100
  )
FROM
  path p1
JOIN
  path p2
    ON p2.i > p1.i;

Собственно, весь запрос выглядит так:

WITH RECURSIVE matrix AS MATERIALIZED (
  SELECT
    array_agg(regexp_split_to_array(line[1], '')) m
  FROM
    regexp_matches(
      $$
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
$$
    , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
)
, init AS MATERIALIZED ( -- начальная/конечная точки
  SELECT
    point(
      min(x) FILTER(WHERE m[y][x] = 'S')
    , min(y) FILTER(WHERE m[y][x] = 'S')
    )::text s
  , point(
      min(x) FILTER(WHERE m[y][x] = 'E')
    , min(y) FILTER(WHERE m[y][x] = 'E')
    )::text e
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  WHERE
    m[y][x] <> '.'
)
, rs AS ( -- волна от начала к концу
  SELECT
    0 i
  , e
  , ARRAY[s] fill
  , ARRAY[s] wave
  FROM
    init
UNION ALL
  SELECT
    i + 1
  , e
  , fill || T.wave
  , T.wave
  FROM
    rs
  , matrix
  , LATERAL (
      SELECT
        array_agg(DISTINCT (d.x, d.y)::text) wave
      FROM
        (
          SELECT
            p[0]::integer x
          , p[1]::integer y
          FROM
            unnest(wave::point[]) p
        ) s
      , LATERAL (
          VALUES
            (s.x - 1, s.y)
          , (s.x + 1, s.y)
          , (s.x, s.y - 1)
          , (s.x, s.y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] <> '#' AND
        (d.x, d.y)::text <> ALL(fill)
    ) T
  WHERE
    e <> ALL(rs.wave)
)
, re AS ( -- волна от конца к началу
  SELECT
    (SELECT max(i) FROM rs) i
  , s
  , ARRAY[e] fill
  , ARRAY[e] wave
  FROM
    init
UNION ALL
  SELECT
    i - 1
  , s
  , fill || T.wave
  , T.wave
  FROM
    re
  , matrix
  , LATERAL (
      SELECT
        array_agg(DISTINCT (d.x, d.y)::text) wave
      FROM
        (
          SELECT
            p[0]::integer x
          , p[1]::integer y
          FROM
            unnest(wave::point[]) p
        ) s
      , LATERAL (
          VALUES
            (s.x - 1, s.y)
          , (s.x + 1, s.y)
          , (s.x, s.y - 1)
          , (s.x, s.y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] <> '#' AND
        (d.x, d.y)::text <> ALL(fill)
    ) T
  WHERE
    s <> ALL(re.wave)
)
, path AS (
  SELECT
    i
  , (ARRAY( -- пересечение множеств - единственная точка пути на i-м шаге
      SELECT unnest(rs.wave)
    INTERSECT ALL
      SELECT unnest(re.wave)
    ))[1]::point cell
  FROM
    rs
  JOIN
    re
      USING(i)
)
SELECT
  count(*) FILTER(
    WHERE
      (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer = 2 AND
      p2.i - p1.i - (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer >= 100
  )
FROM
  path p1
JOIN
  path p2
    ON p2.i > p1.i;

Для вычисления ответа требуется чуть больше 37 секунд, из которых почти половина уходит на перебор всех пар точек пути:

Часть 2

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

  count(*) FILTER(
    WHERE
      (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer <= 20 AND
      p2.i - p1.i - (abs(p1.cell[0] - p2.cell[0]) + abs(p1.cell[1] - p2.cell[1]))::integer >= 100
  )

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

Теги:
Хабы:
+13
Комментарии0
Тензор
Разработчик системы Saby
Сайт
204
Карма
63
Рейтинг
Боровиков Кирилл @Kilor

Архитектура ИС: PostgreSQL, Node.js и highload

Отправить сообщение
СайтСайт

Публикации

Информация

Сайт
saby.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr