В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части мы научимся вычислять состояния клеточного автомата без прямого моделирования и узнаем, как можно среди них найти интересное.
Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)
Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка "пузырьком")
Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)
Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)
Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)
Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)
Решение Day 14: Restroom Redoubt (находим "елочку" с помощью центра масс)
Оригинальная постановка задачи и ее перевод:
Advent of Code 2024, Day 14: Restroom Redoubt
--- День 14: Туалетный редут ---
Одному из Историков нужно в туалет; к счастью, вы знаете, что рядом с не посещенным местом в их списке есть туалет, и поэтому вас всех быстро телепортируют прямо в вестибюль штаб-квартиры Пасхального Кролика.
К сожалению, EBHQ, похоже, снова "улучшил" безопасность туалета после вашего последнего визита. Территория за пределами ванной кишит роботами!
Чтобы Историку безопасно добраться до ванной, вам понадобится способ предсказать, где роботы будут в будущем. К счастью, все они, похоже, движутся по кафельному полу по предсказуемым прямым линиям.
Вы создаете список (ваш пазл-вход) всех текущих позиций роботов ( p) и скоростей ( v), по одному роботу в строке. Например:
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3Позиция каждого робота задается как , p=x,yгде xпредставляет собой количество плиток, на которые робот отстоит от левой стены, а yпредставляет собой количество плиток от верхней стены (если смотреть сверху). Таким образом, позиция p=0,0означает, что робот находится в верхнем левом углу.
Скорость каждого робота задается как , v=x,yгде xи yзадаются в плитках в секунду. Положительное xзначение означает, что робот движется вправо , а положительное yзначение означает, что робот движется вниз. Таким образом, скорость v=1,-2означает, что каждую секунду робот перемещается 1на плитку вправо и 2на плитку вверх.
Роботы снаружи ванной комнаты находятся в пространстве 101шириной и 103высотой плиток (если смотреть сверху). Однако, в этом примере роботы находятся в пространстве 11шириной и 7высотой.
Роботы хорошо перемещаются друг над другом/под другом (благодаря комбинации пружин, выдвижных ног и квадрокоптеров), поэтому они могут делить одну и ту же плитку и не взаимодействовать друг с другом. Визуально количество роботов на каждой плитке в этом примере выглядит следующим образом:
1.12.......
...........
...........
......11.11
1.1........
.........1.
.......1...Эти роботы обладают уникальной функцией для максимальной безопасности ванной комнаты: они могут телепортироваться. Когда робот сталкивается с краем пространства, в котором он находится, он вместо этого телепортируется на другую сторону, эффективно огибая края. Вот что p=2,4 v=2,-3делает робот в течение первых нескольких секунд:
Исходное состояние:
...........
...........
...........
...........
..1........
...........
...........
После 1 секунды:
...........
....1......
...........
...........
...........
...........
...........
После 2 секунд:
...........
...........
...........
...........
...........
......1....
...........
После 3 секунд:
...........
...........
........1..
...........
...........
...........
...........
После 4 секунд:
...........
...........
...........
...........
...........
...........
..........1
После 5 секунд:
...........
...........
...........
.1.........
...........
...........
...........Историк не может ждать долго, поэтому вам не придется долго моделировать роботов. Где будут роботы через 100несколько секунд?
В приведенном выше примере количество роботов на каждой плитке по истечении 100 секунд выглядит следующим образом:
......2..1.
...........
1..........
.11........
.....1.....
...12......
.1....1....Чтобы определить самую безопасную зону, подсчитайте количество роботов в каждом квадранте через 100 секунд. Роботы, которые находятся точно посередине (по горизонтали или вертикали), не считаются находящимися ни в одном квадранте, поэтому единственные соответствующие роботы:
..... 2..1.
..... .....
1.... .....
..... .....
...12 .....
.1... 1....В этом примере квадранты содержат 1, 3, 4, и 1робот. Умножение их вместе дает общий коэффициент безопасности12 .
Предскажите движение роботов в вашем списке в пространстве 101шириной в плитки и 103высотой в плитки. Каким будет коэффициент безопасности после того, как пройдет ровно 100 секунд?
--- Часть вторая ---
Во время перерыва на туалет кто-то замечает, что эти роботы ужасно похожи на тех, что были построены и использовались на Северном полюсе. Если это роботы того же типа, у них должно быть жестко запрограммированное пасхальное яйцо: очень редко большинство роботов должны выстраиваться в изображение рождественской елки.
Какое наименьшее количество секунд должно пройти, чтобы роботы показали пасхальное яйцо?
Часть 1
Описанное в условии свойство "телепортации" робота описывает его поведение на поверхности тора.
В этом случае координаты каждого робота в любой момент времени легко вычисляются как "остаток от деления на" ширину/высоту площадки:
nx = x + (vx + w) * t) % w
ny = y + (vy + h) * t) % h
Поэтому самое сложное в нашем запросе - аккуратно вычислить количество роботов в каждом из квадрантов:
WITH arena AS (
SELECT
11 w
, 7 h
, 100 t
)
, bot AS (
SELECT
line[1]::bigint x
, line[2]::bigint y
, line[3]::bigint vx
, line[4]::bigint vy
FROM
regexp_matches($$
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3
$$
, 'p=(\d+),(\d+) v=(-?\d+),(-?\d+)' -- не забываем про возможные отрицательные значения
, 'g'
) line
)
SELECT -- количество роботов в каждом из квадрантов
count(*) FILTER(WHERE nx < w / 2 AND ny < h / 2) *
count(*) FILTER(WHERE nx < w / 2 AND ny > h / 2) *
count(*) FILTER(WHERE nx > w / 2 AND ny < h / 2) *
count(*) FILTER(WHERE nx > w / 2 AND ny > h / 2)
FROM
(
SELECT -- положения роботов в момент времени t
*
, (x + (vx + w) * t) % w nx
, (y + (vy + h) * t) % h ny
FROM
bot
, arena
) T;По условию, ширина и высота площадки нечетны, поэтому w / 2 дает в PostgreSQL результат деления нацело, и для w = 101 вернет результат 50, что как раз и является координатой разделяющей квадранты "средней линии".
Часть 2
Во второй части нас просят найти минимальный номер шага, на котором роботы выстраиваются в изображение-"пасхалку". Минимального, потому что из правил вычисления координат очевидно, что через каждые w * h шагов состояния заведомо повторяются.
Точнее, конечно, через
НОК(w, h), но в нашем примере они заранее известны (101и103), и взаимно просты, поэтому - произведение.
Поскольку мы знаем, что роботы образуют некоторый "компактный" рисунок, то многие из них должны находиться недалеко друг от друга - то есть "вес" всей этой системы относительно центра масс должен быть минимальным.
При равных "массах", как в нашем случае, и так не слишком сложная формула становится еще немного попроще.
Переберем все w * h возможных состояний и найдем шаг, на котором достигается минимум "веса" (вычислением квадратного корня для расстояния можно пренебречь):
WITH arena AS (
SELECT
11 w
, 7 h
)
, bot AS (
SELECT
line[1]::bigint x
, line[2]::bigint y
, line[3]::bigint vx
, line[4]::bigint vy
FROM
regexp_matches($$
p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3
$$
, 'p=(\d+),(\d+) v=(-?\d+),(-?\d+)'
, 'g'
) line
)
, iter AS (
SELECT
t
, (
WITH state AS ( -- состояние роботов на момент t
SELECT
(x + (vx + w) * t) % w nx
, (y + (vy + h) * t) % h ny
FROM
bot
, arena
)
, center AS ( -- центр масс состояния
SELECT
avg(nx) cx
, avg(ny) cy
FROM
state
)
SELECT
sum((nx - cx) ^ 2 + (ny - cy) ^ 2) m -- общая масса системы
FROM
state
, center
)
FROM
arena
, generate_series(0, w * h - 1) t -- через w * h состояния заведомо повторяются
)
SELECT
t -- искомый момент
FROM
iter
ORDER BY
m -- минимальная масса системы среди всех итераций
LIMIT 1;На реальных данных, где роботов 500, а возможных состояний 101 * 103 = 10403, моделирование занимает чуть меньше 11 секунд:
Итак, мы получили некоторое значение t - давайте убедимся, что именно оно и дает искомую "пасхалку", подставив его в первый запрос и добавив визуализацию состояния:
...
SELECT
string_agg(
CASE WHEN state IS DISTINCT FROM NULL THEN '*' ELSE ' ' END, ''
ORDER BY x
) собираем строку из упорядоченных по x символов
FROM
( -- генерируем все клетки
SELECT
x
, y
FROM
arena
, generate_series(0, w - 1) x
, generate_series(0, h - 1) y
) map
LEFT JOIN
state
ON (nx, ny) = (x, y)
GROUP BY
y
ORDER BY
y; -- выводим строки по порядкуЕсли мы все сделали правильно, то результат будет примерно таким:
*
* * * *
*
*
*
*
*
* *
* *
* * *
* * *
* *
* *
* *
*
* *
* *
*
* * * * *
* *
*
* *
* * * *
** * *
* * * * *
* *
* *
*
*
* *******************************
* *
* *
* *
* *
* * * *
* * *** * *
* ***** *
* ******* *
* ********* * * *
* ***** * *
* ******* *
* ********* * *
* *********** * *
* ************* *
* ********* *
* *********** * * * *
* * ************* *
* *************** *
* ***************** * *
* ************* * * * *
* *************** * * *
* * * ***************** *
** * ******************* *
* ********************* * *
* *** * *
* *** * *
* *** *
* * *
* *
* * * *
* * *
******************************* * *
*
* *
* * *
*
* * **
* *
*
* *
*
*
* *
* *
*
*
*
*
* * * *
*
*
* * *
*
* *
* *
* *
* * *
* * *
*
* *
*
* *
commanderxo
На шаге с пасхалкой у всех роботов уникальные координаты - никакие два робота не находятся на одной клетке. Если догадаться, что туманно сформулированное условие "robots should arrange themselves" означает именно уникальность координат, то решение находится проще.
Kilor Автор
По факту, да, на искомом шаге у всех роботов позиции оказываются уникальны, но с точки зрения решения это не приносит пользы - как среди всех состояний с уникальными координатами выбрать нужное?
commanderxo
Шаг с пасхалкой - первый, на котором все координаты уникальны. Во всех предыдущих шагах у роботов есть пересечения.
Kilor Автор
Возможно (не проверял), это верно для конкретного примера, но не в общем случае, увы - достаточно легко сконструировать "состояние уникальности" пасхалке предшествующее: