Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.
В этой челлендж-серии статей, начатой с прошлогоднего эвента, попробуем использовать 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.