В этой челлендж-серии статей попробуем использовать 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 (находим "елочку" с помощью центра масс)
Решение Day 15: Warehouse Woes (играем в сокобан с помощью json-карты и типа point)
Решение Day 16: Reindeer Maze (укрощаем рекурсию в лабиринте)
Решение Day 17: Chronospatial Computer (подбираем значение ветвлением)
Решение Day 19: Linen Layout (динамическое программирование)
Решение Day 20: Race Condition (кратчайший путь "туда и обратно" и его самосоединение)
Решение Day 21: Keypad Conundrum (моделирование против подсчета)
Оригинальная постановка задачи и ее перевод:
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; -- выводим строки по порядкуЕсли мы все сделали правильно, то результат будет примерно таким:
*
* * * *
*
*
*
*
*
* *
* *
* * *
* * *
* *
* *
* *
*
* *
* *
*
* * * * *
* *
*
* *
* * * *
** * *
* * * * *
* *
* *
*
*
* *******************************
* *
* *
* *
* *
* * * *
* * *** * *
* ***** *
* ******* *
* ********* * * *
* ***** * *
* ******* *
* ********* * *
* *********** * *
* ************* *
* ********* *
* *********** * * * *
* * ************* *
* *************** *
* ***************** * *
* ************* * * * *
* *************** * * *
* * * ***************** *
** * ******************* *
* ********************* * *
* *** * *
* *** * *
* *** *
* * *
* *
* * * *
* * *
******************************* * *
*
* *
* * *
*
* * **
* *
*
* *
*
*
* *
* *
*
*
*
*
* * * *
*
*
* * *
*
* *
* *
* *
* * *
* * *
*
* *
*
* * 