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