SQL HowTo: поиск «в ширину» внутри цикла (Advent of Code 2024, Day 10: Hoof It)

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

---

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

Advent of Code 2024, Day 10: Hoof It

--- День 10: Пешая прогулка ---

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

Олень держит книгу под названием «Путеводитель по острову Лава». Однако, когда вы открываете книгу, вы обнаруживаете, что большая ее часть, похоже, обожжена лавой! Когда вы собираетесь спросить, чем можете помочь, олень приносит вам пустую топографическую карту окрестностей (ваш пазл) и взволнованно смотрит на вас.

Возможно, вы можете помочь заполнить недостающие пешеходные маршруты?

Топографическая карта показывает высоту в каждой точке с использованием шкалы от 0(самой низкой) до 9(самой высокой). Например:

0123
1234
8765
9876

На основе необожженных обрывков книги вы определяете, что хороший пешеходный маршрут должен быть максимально длинным и иметь ровный, постепенный подъем. Для всех практических целей это означает, что пешеходный маршрут — это любой путь, который начинается на высоте 0, заканчивается на высоте 9и всегда увеличивается на высоту ровно на 1 на каждом шаге. Пешие маршруты никогда не включают диагональные шаги — только вверх, вниз, влево или вправо (с точки зрения карты).

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

Начало тропы - это любая позиция, которая начинает один или несколько пешеходных маршрутов - здесь эти позиции всегда будут иметь высоту 0. Собирая больше фрагментов страниц, вы устанавливаете, что оценка начала тропы - это количество позиций 9-высоты, достижимых от этого начала по пешеходной тропе. В приведенном выше примере единственное начало тропы в верхнем левом углу имеет оценку 1, поскольку из него можно достичь единственной 9 (той, что в нижнем левом углу).

Этот маршрут имеет оценку 2:

...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9

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

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

..90..9
...1.98
...2..7
6543456
765.987
876....
987....

На этой топографической карте указаны два начала тропы; начало тропы вверху имеет оценку 1, а начало тропы внизу имеет оценку 2:

10..9..
2...8..
3...7..
4567654
...8..3
...9..2
.....01

Вот более крупный пример:

89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732

В этом большем примере 9 точек начала тропы. Рассматривая точки начала тропы в порядке чтения, они имеют оценки 5, 6, 5, 3, 1, 3, 5, 3 и 5. Складывая эти оценки вместе, сумма оценок всех точек начала тропы составляет 36.

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

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

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

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

.....0.
..4321.
..5..2.
..6543.
..7..4.
..8765.
..9....

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

.....0.   .....0.   .....0.
..4321.   .....1.   .....1.
..5....   .....2.   .....2.
..6....   ..6543.   .....3.
..7....   ..7....   .....4.
..8....   ..8....   ..8765.
..9....   ..9....   ..9....

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

..90..9
...1.98
...2..7
6543456
765.987
876....
987....

На этой карте указана одна начальная точка тропы с рейтингом 227(поскольку существует 121отдельная пешеходная тропа, ведущая к 9на правом краю и 106 - к на 9нижнем краю):

012345
123456
234567
345678
4.6789
56789.

Вот более крупный пример из предыдущего примера:

89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732

Рассматривая начальные точки в порядке чтения, они имеют рейтинги 20, 24, 10, 4, 1, 4, 5, 8 и 5. Сумма всех рейтингов начальных точек на этой большой топографической карте составляет 81.

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

Часть 1

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

1. Переводим текстовую матрицу в двухмерный массив высот.

2. Находим все стартовые точки высоты 0.

3. Для каждой запускаем рекурсивный поиск "в ширину".

4. Считаем, сколько разных точек высоты 9 мы смогли достичь.

WITH matrix AS MATERIALIZED ( -- переводим матрицу в массив
  SELECT
    array_agg(regexp_split_to_array(line, ''))::integer[] m
  FROM
    regexp_split_to_table($$
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
SELECT
  sum(score)
FROM
  matrix
, LATERAL ( -- находим все стартовые точки высоты 0
    SELECT
      x
    , y
    FROM
      generate_subscripts(m, 2) x
    , generate_subscripts(m, 1) y
    WHERE
      m[y][x] = 0
  ) T
, LATERAL ( -- для каждой рекурсивно перебираем все возможные маршруты "вширину"
    WITH RECURSIVE r AS (
      SELECT
        T.x
      , T.y
      , 0 h
    UNION ALL
      SELECT
        d.x
      , d.y
      , h + 1
      FROM
        r
      , LATERAL ( -- 4 возможных направления следующего шага
          VALUES
            (x - 1, y)
          , (x + 1, y)
          , (x, y - 1)
          , (x, y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] = h + 1 -- проверка условия возрастания высоты ровно на 1
    )
    SELECT
      count(DISTINCT (x, y)) FILTER(WHERE h = 9) score -- кол-во достигнутых уникальных точек высоты 9
    FROM
      r
  ) S;

Для получения результата понадобилось всего лишь порядка 30мс:

Часть 2

Во второй части нас просят подсчитать количество всех путей, которыми мы могли проходить от 0 до 9. Для этого нам достаточно изменить всего одну строку с вычислением оценки: count(*) FILTER(WHERE h = 9).

Остальной запрос никак не меняется, а потому не меняется и его план:

--explain (analyze, costs off)
WITH matrix AS MATERIALIZED ( -- переводим матрицу в массив
  SELECT
    array_agg(regexp_split_to_array(line, ''))::integer[] m
  FROM
    regexp_split_to_table($$
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
SELECT
  sum(score)
FROM
  matrix
, LATERAL ( -- находим все стартовые точки высоты 0
    SELECT
      x
    , y
    FROM
      generate_subscripts(m, 2) x
    , generate_subscripts(m, 1) y
    WHERE
      m[y][x] = 0
  ) T
, LATERAL ( -- для каждой рекурсивно перебираем все возможные маршруты "вширину"
    WITH RECURSIVE r AS (
      SELECT
        T.x
      , T.y
      , 0 h
    UNION ALL
      SELECT
        d.x
      , d.y
      , h + 1
      FROM
        r
      , LATERAL ( -- 4 возможных направления следующего шага
          VALUES
            (x - 1, y)
          , (x + 1, y)
          , (x, y - 1)
          , (x, y + 1)
        ) d(x, y)
      WHERE
        m[d.y][d.x] = h + 1 -- проверка условия возрастания высоты ровно на 1
    )
    SELECT
      count(*) FILTER(WHERE h = 9) score -- кол-во путей, достигнувших высоты 9
    FROM
      r
  ) S;