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

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

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

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

Advent of Code 2025, Day 9: Movie Theater

--- День 9: Кинотеатр ---

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

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

Например:

7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3

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

..............
.......#...#..
..............
..#....#......
..............
..#......#....
..............
.........#.#..
..............

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

Например, можно создать прямоугольник (обозначенный как O) с площадью 24от 2,5до 9,7:

..............
.......#...#..
..............
..#....#......
..............
..OOOOOOOO....
..OOOOOOOO....
..OOOOOOOO.#..
..............

Или же можно создать прямоугольник с площадью 35между 7,1и 11,7:

..............
.......OOOOO..
.......OOOOO..
..#....OOOOO..
.......OOOOO..
..#....OOOOO..
.......OOOOO..
.......OOOOO..
..............

Можно даже сделать тонкий прямоугольник с площадью всего лишь 6между 7,3и 2,3:

..............
.......#...#..
..............
..OOOOOO......
..............
..#......#....
..............
.........#.#..
..............

В конечном итоге, наибольший прямоугольник, который можно построить в этом примере, имеет площадь 50. Один из способов сделать это — расположить прямоугольник между 2,5и 11,1:

..............
..OOOOOOOOOO..
..OOOOOOOOOO..
..OOOOOOOOOO..
..OOOOOOOOOO..
..OOOOOOOOOO..
..............
.........#.#..
..............

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

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

Эльфы только что вспомнили: они могут заменять только красные или зеленые плитки . Поэтому ваш прямоугольник может содержать только красные или зеленые плитки.

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

Используя тот же пример, что и раньше, отмеченные плитки Xбудут зелеными:

..............
.......#XXX#..
.......X...X..
..#XXXX#...X..
..X........X..
..#XXXXXX#.X..
.........X.X..
.........#X#..
..............

Кроме того, все плитки внутри этого контура из красных и зеленых плиток также зеленые. Таким образом, в этом примере это все — зеленые плитки:

..............
.......#XXX#..
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

Остальные плитки никогда не бывают красными или зелеными.

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

Например, вы можете составить прямоугольник из красных и зеленых плиток с площадью 15от 7,3до 11,1:

..............
.......OOOOO..
.......OOOOO..
..#XXXXOOOOO..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

Или же можно сделать тонкий прямоугольник с площадью 3от 9,7до 9,5:

..............
.......#XXX#..
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXXOXX..
.........OXX..
.........OX#..
..............

Наибольший прямоугольник, который можно построить в этом примере, используя только красные и зеленые плитки, имеет площадь 24. Один из способов сделать это — расположить его между 9,5и 2,3:

..............
.......#XXX#..
.......XXXXX..
..OOOOOOOOXX..
..OOOOOOOOXX..
..OOOOOOOOXX..
.........XXX..
.........#X#..
..............

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

Часть 1

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

Единственная сложность в решении - не забыть, что сторона прямоугольника между плитками с координатами x1 и x2 будет на 1 больше модуля их разности:

WITH tile AS(
  SELECT
    line[1]::bigint x
  , line[2]::bigint y
  FROM
    regexp_matches($$
7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3
    $$, '(\d+),(\d+)', 'g') line
)
SELECT
  max(
    (abs(T1.x - T2.x) + 1) * -- длина стороны по X
    (abs(T1.y - T2.y) + 1)   -- длина стороны по Y
  )
FROM
  tile T1
, tile T2;

Часть 2

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

Такое расширение задачи лишь кажется существенным усложнением, поскольку возможности PostgreSQL по работе с геометрическими типами данных позволяют добавить к предыдущему запросу всего лишь два действия: построение многоугольника-контура с помощью функции polygon и проверки вложенности прямоугольника в многоугольник-контур оператором <@:

WITH tile AS(
  SELECT
    line[1]::bigint x
  , line[2]::bigint y
  FROM
    regexp_matches($$
7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3
    $$, '(\d+),(\d+)', 'g') line
)
SELECT
  max(
    (abs(T1.x - T2.x) + 1) *
    (abs(T1.y - T2.y) + 1)
  )
FROM
  (
    SELECT
      polygon('(' || string_agg(point(x, y)::text, ',') || ')') -- многоугольник-контур
    FROM
      tile
  ) p
, tile T1
, tile T2
WHERE
  polygon(              -- многоугольник по 4 сторонам прямоугольника
    box(                -- прямоугольник по противоположным углам
      point(T1.x, T1.y)
    , point(T2.x, T2.y)
    )
  ) <@ polygon;         -- проверка вложенности

Здесь вместо перечисления всех 4 углов проверяемого прямоугольника мы воспользовались возможностью передать в polygon тип box - прямоугольник, построенный на точках противоположных углов.

А для определения многоугольника-контура мы формируем его текстовое представление из списка координат "угловых" точек функцией string_agg.