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

• Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)

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

AAAA
BBCD
BBCC
EEEC

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

OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE

AAAA
BBCD
BBCC
EEEC

EEEEE
EXXXX
EEEEE
EXXXX
EEEEE

AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA

Часть 1

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

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 ( -- 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;

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