Comments 5
На шаге с пасхалкой у всех роботов уникальные координаты - никакие два робота не находятся на одной клетке. Если догадаться, что туманно сформулированное условие "robots should arrange themselves" означает именно уникальность координат, то решение находится проще.
По факту, да, на искомом шаге у всех роботов позиции оказываются уникальны, но с точки зрения решения это не приносит пользы - как среди всех состояний с уникальными координатами выбрать нужное?
Шаг с пасхалкой - первый, на котором все координаты уникальны. Во всех предыдущих шагах у роботов есть пересечения.
Возможно (не проверял), это верно для конкретного примера, но не в общем случае, увы - достаточно легко сконструировать "состояние уникальности" пасхалке предшествующее:
...A... vA = 1,0
.B.C.D. vB = 1,1 | vC = 0,1 | vD = -1,1
.......
.......
EF.G.HI vE,vF = 1,-1 | vG = 0,-1 | vH,vI = -1,-1
.......
...J... vJ = 0,-2.......
...A...
..BCD..
.EFGHI.
...J...
.......
.......Вы знаете хоть одного человека, кому в AoC 2024-14 выпал пример, где пасхалка не первая уникальная комбинация? Задачи в Advent of Code подобраны так, что если выбрать правильный алгоритм, то решение находится быстро и "просто". В этом же году 14-й день это единственная задача с крайне неясным условием, потому как "picture of a Christmas tree" может означать что угодно. Думаю, что ключевая фраза в условии это "robots should arrange themselves".
SQL HowTo: находим «елочку» с помощью центра масс (Advent of Code 2024, Day 14: Restroom Redoubt)