В этой челлендж-серии статей попробуем использовать 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; -- выводим строки по порядку
Если мы все сделали правильно, то результат будет примерно таким:
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * ******************************* * * * * * * * * * * * * * * *** * * * ***** * * ******* * * ********* * * * * ***** * * * ******* * * ********* * * * *********** * * * ************* * * ********* * * *********** * * * * * * ************* * * *************** * * ***************** * * * ************* * * * * * *************** * * * * * * ***************** * ** * ******************* * * ********************* * * * *** * * * *** * * * *** * * * * * * * * * * * * * ******************************* * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
