08.12.2025 06:10
Kilor 0 2100 Источник

Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

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

Advent of Code 2025, Day 4: Printing Department

--- День 4: Отдел печати ---

Вы спускаетесь на эскалаторе в отдел печати. ​​Там явно готовятся к Рождеству: повсюду куча больших рулонов бумаги, а в углу даже стоит огромный принтер (для печати действительно больших объёмов).

Украсить здесь будет легко: они смогут сделать украшения сами. Что вам действительно нужно, так это найти способ добраться дальше вглубь базы на Северном полюсе, пока лифты не работают.

«Вообще-то, возможно, мы можем помочь», — отвечает один из эльфов, когда вы просите о помощи. «Мы почти уверены, что за стеной есть кафетерий. Если бы мы смогли пробить стену, вы бы смогли двигаться дальше. Жаль, что все наши погрузчики так заняты перемещением этих огромных рулонов бумаги».

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

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

Например:

..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.

Погрузчики смогут получить доступ к рулону бумаги только в том случае, если в восьми соседних позициях находится меньше четырёх рулонов. Если вы сможете определить, к каким рулонам бумаги погрузчики смогут получить доступ, они потратят меньше времени на поиски и больше на разрушение стены кафетерия.

В этом примере показаны 13рулонов бумаги, к которым можно получить доступ с помощью вилочного погрузчика (отмечены x):

..xx.xx@x.
x@@.@.@.@@
@@@@@.x.@@
@.@@@@..@.
x@.@@@@.@x
.@@@@@@@.@
.@.@.@.@@@
x.@@@.@@@@
.@@@@@@@@.
x.x.@@@.x.

Рассмотрите полную схему расположения рулонов бумаги. Сколько рулонов бумаги доступно погрузчику?

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

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

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

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

Начальное состояние:
..##.##@#.
#@@.@.@.@@
@@@@@.#.@@
@.@@@@..@.
#@.@@@@.@#
.@@@@@@@.@
.@.@.@.@@@
#.@@@.@@@@
.@@@@@@@@.
#.#.@@@.#.

Убрали 13 рулонов:
..xx.xx#x.
x@@.#.#.@#
#@@@@.x.@@
#.@@@@..#.
x@.@@@@.#x
.#@@@@@@.#
.#.@.@.@@@
x.@@@.@@@@
.#@@@@@@@.
x.x.@@@.x.

Убрали 12 рулонов:
.......x..
.#@.x.x.#x
x@@@@...##
x.@@@@..x.
.#.@@@@.x.
.x@@@@@@.x
.x.@.@.@@#
..@@@.@@@@
.x#@@@@@@.
....@@@...

Убрали 7 рулонов:
..........
.x#.....x.
.#@@@...xx
..@@@@....
.x.@@@@...
..#@@@@@..
...@.@.@@x
..#@@.@@@#
..x@@@@@@.
....@@@...

Убрали 5 рулонов:
..........
..x.......
.x#@@.....
..@@@@....
...@@@@...
..x@@@@@..
...@.@.@@.
..x@@.@@@x
...@@@@@#.
....@@@...

Убрали 2 рулона:
..........
..........
..x@@.....
..#@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@x.
....@@@...

Убрали 1 рулон:
..........
..........
...#@.....
..x@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

Убрали 1 рулон:
..........
..........
...x#.....
...@@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

Убрали 1 рулон:
..........
..........
....x.....
...#@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

Убрали 1 рулон:
..........
..........
..........
...x@@....
...@@@@...
...@@@@@..
...@.@.@@.
...@@.@@@.
...@@@@@..
....@@@...

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

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

Часть 1

Начнем решение с очевидного - превращения исходной схемы в записи о наличии рулона в клетке с конкретными координатами:

WITH matrix AS(
  SELECT
    x
  , y
  FROM
    regexp_matches($$
..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
    $$, '(?:\.|@)+', 'g')
      WITH ORDINALITY y(line, y) -- номер строки - координата по Y
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(ch, x)   -- номер символа - координата по X
  WHERE
    ch = '@' -- рулон есть в этой позиции
)

На исходной схеме 71 такая позиция:

 x | y
 3 | 1
 4 | 1
 6 | 1
 7 | 1
 8 | 1
 9 | 1
 1 | 2
 2 | 2
 3 | 2
 5 | 2
 7 | 2
 9 | 2
10 | 2
...

Теперь подсчитаем, сколько рулонов находится на расстоянии не больше 1 от каждой клетки. Для этого каждый рулон "учтем" в каждую соседнюю с ним клетку, включая и ту, где находится он сам (dx = dy = 0):

, near AS (
  SELECT
    x + dx x
  , y + dy y
  , count(*)
  FROM
    matrix
  , generate_series(-1, 1) dx -- цикл [-1, 0, +1] по X
  , generate_series(-1, 1) dy -- цикл [-1, 0, +1] по Y
  GROUP BY
    1, 2
)

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

WITH matrix AS(
  SELECT
    x
  , y
  FROM
    regexp_matches($$
..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
    $$, '(?:\.|@)+', 'g')
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(ch, x)
  WHERE
    ch = '@'
)
, near AS (
  SELECT
    x + dx x
  , y + dy y
  , count(*)
  FROM
    matrix
  , generate_series(-1, 1) dx
  , generate_series(-1, 1) dy
  GROUP BY
    1, 2
)
SELECT
  count(*) FILTER(WHERE count <= 4) -- рулон (1) + 8 его соседей (< 4)
FROM
  matrix
NATURAL JOIN -- соединение даст только занятые рулонами клетки
  near;

Часть 2

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

Чтобы иметь возможность использовать группировку внутри рекурсивного шага, "запечем" состояние рекурсивной части выборки r в промежуточную CTE T, а дальше - все просто:

  • оставляем на каждом шаге только рулоны, где наш счетчик показывает 5 и больше (то есть сам рулон + минимум 4 соседа)

  • делаем шаги, пока количество остающихся рулонов уменьшается

, r AS (
  SELECT
    0 i
  , *
  FROM
    matrix
UNION ALL
  (
    WITH T AS (
      TABLE r
    )
    , stay AS (
      SELECT
        T.*
      FROM
        (
          SELECT
            i + 1
          , x + dx x
          , y + dy y
          FROM
            T
          , generate_series(-1, 1) dx
          , generate_series(-1, 1) dy
          GROUP BY
            1, 2, 3 -- добавилась группировака по номеру шага i
          HAVING
            count(*) > 4 -- соседей минимум 4
        ) T
      NATURAL JOIN -- соединение оставит только клетки, исходно содержащие рулоны
        matrix
    )
    SELECT
      *
    FROM
      stay
    WHERE
      (SELECT count(*) FROM stay) < (SELECT count(*) FROM T) -- хоть что-то убрали
  )
)

Подсчитаем, сколько рулонов оставалось после каждого шага:

, step AS (
  SELECT
    i
  , count(*) remain
  FROM
    r
  GROUP BY
    1
)

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

SELECT
  (
    SELECT
      remain
    FROM
      step
    ORDER BY
      i
    LIMIT 1
  ) - (
    SELECT
      remain
    FROM
      step
    ORDER BY
      i DESC
    LIMIT 1
  );

Итоговый запрос:

WITH RECURSIVE matrix AS(
  SELECT
    x
  , y
  FROM
    regexp_matches($$
..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.
    $$, '(?:\.|@)+', 'g')
      WITH ORDINALITY y(line, y)
  , regexp_split_to_table(line[1], '')
      WITH ORDINALITY x(ch, x)
  WHERE
    ch = '@'
)
, r AS (
  SELECT
    0 i
  , *
  FROM
    matrix
UNION ALL
  (
    WITH T AS (
      TABLE r
    )
    , stay AS (
      SELECT
        T.*
      FROM
        (
          SELECT
            i + 1
          , x + dx x
          , y + dy y
          FROM
            T
          , generate_series(-1, 1) dx
          , generate_series(-1, 1) dy
          GROUP BY
            1, 2, 3 -- добавилась группировака по номеру шага i
          HAVING
            count(*) > 4 -- соседей минимум 4
        ) T
      NATURAL JOIN -- соединение оставит только клетки, исходно содержащие рулоны
        matrix
    )
    SELECT
      *
    FROM
      stay
    WHERE
      (SELECT count(*) FROM stay) < (SELECT count(*) FROM T)
  )
)
, step AS (
  SELECT
    i
  , count(*) remain
  FROM
    r
  GROUP BY
    1
)
SELECT
  (
    SELECT
      remain
    FROM
      step
    ORDER BY
      i
    LIMIT 1
  ) - (
    SELECT
      remain
    FROM
      step
    ORDER BY
      i DESC
    LIMIT 1
  );

Комментарии (0)