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

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

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

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

Advent of Code 2024, Day 12: Garden Groups

--- День 12: Садовые группы ---

Почему бы не поискать Главного историка рядом с садовником и его огромной фермой? Там много еды, поэтому историки берут что-нибудь поесть, пока ищут.

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

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

AAAA
BBCD
BBCC
EEEC

Эта композиция 4x4 включает в себя садовые участки, на которых произрастают пять различных видов растений (обозначенных A, B, C, D, и E), каждый из которых сгруппирован в своем собственном регионе.

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

Площадь региона — это просто количество садовых участков, которые содержит регион. Карта выше содержит регионы растений типов A, B, и C площадью 4. Растения типа E находятся в регионе площадью 3; растения типа D - в регионе площадью 1.

Каждый садовый участок представляет собой квадрат и поэтому имеет четыре стороны. Периметр региона — это количество сторон садовых участков в регионе, которые не касаются другого садового участка в том же регионе. Растения типов Aи C находятся в регионах с периметром 10. Тип Bи E - в регионах с периметром 8. Отдельный участок D образует свой собственный регион с периметром 4.

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

+-+-+-+-+
|A A A A|
+-+-+-+-+     +-+
              |D|
+-+-+   +-+   +-+
|B B|   |C|
+   +   + +-+
|B B|   |C C|
+-+-+   +-+ +
          |C|
+-+-+-+   +-+
|E E E|
+-+-+-+

Растения одного и того же типа могут появляться в нескольких отдельных регионах, а регионы могут даже появляться в других регионах. Например:

OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

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

Каждая из четырех Xобластей имеет площадь 1и периметр 4. Область, содержащая 21 растение O, более сложная; в дополнение к ее внешнему краю, дающему периметр 20, ее граница с каждой Xобластью дает дополнительно +4 к ее периметру, что дает общий периметр 36.

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

В первом примере у региона Aесть цена 4 * 10 = 40, у региона Bесть цена 4 * 8 = 32, у региона Cесть цена 4 * 10 = 40, у региона Dесть цена 1 * 4 = 4, и у региона Eесть цена 3 * 8 = 24. Таким образом, общая цена для первого примера составляет 140.

Во втором примере регион со всеми Oучастками имеет цену 21 * 36 = 756, а каждый из четырех маленьких Xрегионов имеет цену 1 * 4 = 4, то есть общая цена составляет 772( 756 + 4 + 4 + 4 + 4).

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

RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE

Он содержит:

Регион Rрастений с ценой 12 * 18 = 216.
Регион Iрастений с ценой 4 * 8 = 32.
Регион Cрастений с ценой 14 * 28 = 392.
Регион Fрастений с ценой 10 * 18 = 180.
Регион Vрастений с ценой 13 * 20 = 260.
Регион Jрастений с ценой 11 * 20 = 220.
Регион Cрастений с ценой 1 * 4 = 4.
Регион Eрастений с ценой 13 * 18 = 234.
Регион Iрастений с ценой 14 * 22 = 308.
Регион Mрастений с ценой 5 * 12 = 60.
Регион Sрастений с ценой 3 * 8 = 24.

Итак, его общая стоимость составляет 1930.

Какова общая стоимость ограждения всех регионов на вашей карте?

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

К счастью, эльфы стараются заказать так много заборов, что могут рассчитывать на оптовую скидку!

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

Рассмотрим этот пример еще раз:

AAAA
BBCD
BBCC
EEEC

Область, содержащая растения типа A, имеет 4стороны, как и каждая из областей, содержащих растения типа B, Dи E. Однако более сложная область, содержащая растения типа C, имеет 8сторон!

Используя новый метод расчета цены для каждого региона путем умножения площади региона на количество его сторон, регионы Aпо Eимеют цены 16, 16, 32, 4и 12, соответственно, что в сумме составляет 80.

Во втором примере выше (с набором Xи Oрастений) общая стоимость составит 436.

Вот карта, на которой изображен регион в форме буквы E, полный типовых Eрастений:

EEEEE
EXXXX
EEEEE
EXXXX
EEEEE

Область в форме E имеет площадь 17и 12сторон по цене 204. Включая две области, полные типовых растений X, эта карта имеет общую цену 236.

Общая стоимость этой карты составляет 368:

AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA

Она включает в себя два региона растений B(каждый с 4сторонами) и один регион растений A (с 4сторонами снаружи и 8 сторонами внутри, всего 12сторон). Будьте особенно внимательны при подсчете забора вокруг регионов, таких как тот, что полон растений A; в частности, каждая секция забора имеет внутреннюю и внешнюю стороны, поэтому забор не соединяется посередине региона (где два Bрегиона соприкасаются по диагонали). (Эльфы использовали бы вместо этого компанию Möbius Fencing Company, но условия их контракта были слишком односторонними.)

Более крупный пример из предыдущего раздела теперь имеет следующие обновленные цены:

Регион Rрастений с ценой 12 * 10 = 120.
Регион Iрастений с ценой 4 * 4 = 16.
Регион Cрастений с ценой 14 * 22 = 308.
Регион Fрастений с ценой 10 * 12 = 120.
Регион Vрастений с ценой 13 * 10 = 130.
Регион Jрастений с ценой 11 * 12 = 132.
Регион Cрастений с ценой 1 * 4 = 4.
Регион Eрастений с ценой 13 * 8 = 104.
Регион Iрастений с ценой 14 * 16 = 224.
Регион Mрастений с ценой 5 * 6 = 30.
Регион Sрастений с ценой 3 * 6 = 18.

Сложение этих значений дает новую общую цену 1206.

Какова новая общая стоимость ограждения всех регионов на вашей карте?

Часть 1

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

WITH RECURSIVE matrix AS ( -- переводим матрицу в массив
  SELECT
    array_agg(regexp_split_to_array(line, '')) m
  FROM
    regexp_split_to_table($$
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
, ro AS ( -- внешняя рекурсия
  SELECT
    NULL::text kind     -- тип (буква) региона
  , '{}'::text[] filled -- все уже закрашенные клетки карты
  , '{}'::text[] region -- клетки региона, закрашенного на этом шаге
UNION ALL
  (
    WITH RECURSIVE ri AS ( -- внутренняя рекурсия
    (
      SELECT
        filled
      , m[y][x] kind
      , '{}'::text[] || (x, y)::text wave      -- все клетки региона
      , '{}'::text[] || (x, y)::text wavefront -- текущий фронт "волны"
      FROM
        ro
      , matrix
      , generate_subscripts(m, 2) x
      , generate_subscripts(m, 1) y
      WHERE
        m[y][x] IS NOT NULL AND
        (x, y)::text <> ALL(filled) -- в качестве стартовой для региона берем первую незакрашенную
      LIMIT 1
    )
    UNION ALL
      SELECT
        filled
      , kind
      , wave || d.wavefront
      , d.wavefront
      FROM
        ri
      , matrix
      , LATERAL (
          SELECT
            array_agg(DISTINCT (d.x, d.y)::text) wavefront -- только уникальные клетки
          FROM
            (
              SELECT
                p[0]::integer x
              , p[1]::integer y
              FROM
                unnest(wave::point[]) p
            ) s
          , LATERAL ( -- 4 возможные соседние клетки
              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] = kind AND        -- клетка-сосед того же типа ...
            (d.x, d.y)::text <> ALL(wave) -- ... и еще не принадлежит волне-региону
        ) d
      WHERE
        d.wavefront IS NOT NULL -- пока фронт не кончился
    )
    SELECT
      kind
    , filled || wave::text[]
    , wave::text[]
    FROM
      ri
    ORDER BY
      array_length(wave, 1) DESC -- берем состояние "заливки" региона с последнего шага
    LIMIT 1
  )
)
SELECT
  sum(array_length(region, 1) * l) -- размер массива - это площадь региона
FROM
  ro
, matrix
, LATERAL (
    SELECT
      sum(                      -- вычисляем количество сегментов забора ...
        (m[p[1] - 1][p[0]] IS DISTINCT FROM kind)::integer +
        (m[p[1] + 1][p[0]] IS DISTINCT FROM kind)::integer +
        (m[p[1]][p[0] - 1] IS DISTINCT FROM kind)::integer +
        (m[p[1]][p[0] + 1] IS DISTINCT FROM kind)::integer
      ) l
    FROM
      unnest(region::point[]) p -- ... для каждой клетки региона
  ) T
WHERE
  kind IS NOT NULL;

Общее время вычисления на реальных данных - чуть больше 17 минут, из которых "заливка" регионов заняла примерно 99.5%:

Часть 2

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

Количество сторон забора равно количеству его углов - внешних и внутренних

Внешний угол возникает, если оба соседа "через стенку" - другого вида. Внутренний - если оба соседа того же вида, а вот по диагонали между ними - другого:

WITH RECURSIVE matrix AS(
  SELECT
    array_agg(regexp_split_to_array(line, '')) m
  FROM
    regexp_split_to_table($$
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
$$, '[\r\n]+') line
  WHERE
    btrim(line) <> ''
)
, ro AS (
  SELECT
    NULL::text kind
  , '{}'::text[] filled
  , '{}'::text[] region
UNION ALL
  (
    WITH RECURSIVE ri AS (
    (
      SELECT
        filled
      , m[y][x] kind
      , '{}'::text[] || (x, y)::text wave
      , '{}'::text[] || (x, y)::text wavefront
      FROM
        ro
      , matrix
      , generate_subscripts(m, 2) x
      , generate_subscripts(m, 1) y
      WHERE
        m[y][x] IS NOT NULL AND
        (x, y)::text <> ALL(filled)
      LIMIT 1
    )
    UNION ALL
      SELECT
        filled
      , kind
      , wave || d.wavefront
      , d.wavefront
      FROM
        ri
      , matrix
      , LATERAL (
          SELECT
            array_agg(DISTINCT (d.x, d.y)::text) wavefront
          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] = kind AND
            (d.x, d.y)::text <> ALL(wave)
        ) d
      WHERE
        d.wavefront IS NOT NULL
    )
    SELECT
      kind
    , filled || wave::text[]
    , wave::text[]
    FROM
      ri
    ORDER BY
      array_length(wave, 1) DESC
    LIMIT 1
  )
)
SELECT
  sum(array_length(region, 1) * c)
FROM
  ro
, matrix
, LATERAL (
    SELECT
      sum( -- общее количество углов
        olu::integer +
        old::integer +
        oru::integer +
        ord::integer +
        ilu::integer +
        ild::integer +
        iru::integer +
        ird::integer
      ) c
    FROM
      unnest(region::point[]) p -- для каждой клетки региона ...
    , LATERAL (                 -- ... определяем типы каждой из клеток-соседей
        SELECT
          m[p[1] - 1][p[0] - 1] lu
        , m[p[1] - 1][p[0]] u
        , m[p[1] - 1][p[0] + 1] ru
        , m[p[1]][p[0] - 1] l
        , m[p[1]][p[0] + 1] r
        , m[p[1] + 1][p[0] - 1] ld
        , m[p[1] + 1][p[0]] d
        , m[p[1] + 1][p[0] + 1] rd
      ) X
    , LATERAL (                 -- ... и, как следствие, наличия углов забора
        SELECT
          -- внешние углы
          (l IS DISTINCT FROM kind AND u IS DISTINCT FROM kind) olu
        , (l IS DISTINCT FROM kind AND d IS DISTINCT FROM kind) old
        , (r IS DISTINCT FROM kind AND u IS DISTINCT FROM kind) oru
        , (r IS DISTINCT FROM kind AND d IS DISTINCT FROM kind) ord
          -- внутренние углы
        , (l IS NOT DISTINCT FROM kind AND u IS NOT DISTINCT FROM kind AND lu IS DISTINCT FROM kind) ilu
        , (l IS NOT DISTINCT FROM kind AND d IS NOT DISTINCT FROM kind AND ld IS DISTINCT FROM kind) ild
        , (r IS NOT DISTINCT FROM kind AND u IS NOT DISTINCT FROM kind AND ru IS DISTINCT FROM kind) iru
        , (r IS NOT DISTINCT FROM kind AND d IS NOT DISTINCT FROM kind AND rd IS DISTINCT FROM kind) ird
      ) Y
  ) T
WHERE
  kind IS NOT NULL;

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

SQL HowTo: волновой алгоритм и подсчет границ (Advent of Code 2024, Day 12: Garden Groups)