One of The Historians needs to use the bathroom; fortunately, you know there's a bathroom near an unvisited location on their list, and so you're all quickly teleported directly to the lobby of Easter Bunny Headquarters.
Unfortunately, EBHQ seems to have "improved" bathroom security again after your last visit. The area outside the bathroom is swarming with robots!
To get The Historian safely to the bathroom, you'll need a way to predict where the robots will be in the future. Fortunately, they all seem to be moving on the tile floor in predictable straight lines.
You make a list (your puzzle input) of all of the robots' current positions (p) and velocities (v), one robot per line. For example:
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
Each robot's position is given as p=x,y where x represents the number of tiles the robot is from the left wall and y represents the number of tiles from the top wall (when viewed from above). So, a position of p=0,0 means the robot is all the way in the top-left corner.
Each robot's velocity is given as v=x,y where x and y are given in tiles per second. Positive x means the robot is moving to the right, and positive y means the robot is moving down. So, a velocity of v=1,-2 means that each second, the robot moves 1 tile to the right and 2 tiles up.
The robots outside the actual bathroom are in a space which is 101 tiles wide and 103 tiles tall (when viewed from above). However, in this example, the robots are in a space which is only 11 tiles wide and 7 tiles tall.
The robots are good at navigating over/under each other (due to a combination of springs, extendable legs, and quadcopters), so they can share the same tile and don't interact with each other. Visually, the number of robots on each tile in this example looks like this:
1.12.......
...........
...........
......11.11
1.1........
.........1.
.......1...
These robots have a unique feature for maximum bathroom security: they can teleport. When a robot would run into an edge of the space they're in, they instead teleport to the other side, effectively wrapping around the edges. Here is what robot p=2,4 v=2,-3 does for the first few seconds:
Initial state:
...........
...........
...........
...........
..1........
...........
...........
After 1 second:
...........
....1......
...........
...........
...........
...........
...........
After 2 seconds:
...........
...........
...........
...........
...........
......1....
...........
After 3 seconds:
...........
...........
........1..
...........
...........
...........
...........
After 4 seconds:
...........
...........
...........
...........
...........
...........
..........1
After 5 seconds:
...........
...........
...........
.1.........
...........
...........
...........
The Historian can't wait much longer, so you don't have to simulate the robots for very long. Where will the robots be after 100 seconds?
In the above example, the number of robots on each tile after 100 seconds has elapsed looks like this:
......2..1.
...........
1..........
.11........
.....1.....
...12......
.1....1....
To determine the safest area, count the number of robots in each quadrant after 100 seconds. Robots that are exactly in the middle (horizontally or vertically) don't count as being in any quadrant, so the only relevant robots are:
..... 2..1.
..... .....
1.... .....
..... .....
...12 .....
.1... 1....
In this example, the quadrants contain 1, 3, 4, and 1 robot. Multiplying these together gives a total safety factor of 12.
Predict the motion of the robots in your list within a space which is 101 tiles wide and 103 tiles tall. What will the safety factor be after exactly 100 seconds have elapsed?
Your puzzle answer was 231782040.
During the bathroom break, someone notices that these robots seem awfully similar to ones built and used at the North Pole. If they're the same type of robots, they should have a hard-coded Easter egg: very rarely, most of the robots should arrange themselves into a picture of a Christmas tree.
What is the fewest number of seconds that must elapse for the robots to display the Easter egg?
Your puzzle answer was 6475.
Part 1 is quite straightforward. It doesn't make much sense to even try to implement a simulation-based approach, as it's quite obvious that the robot positions can be computed for any timestep using simple modular arithmetic. The quadrant rules are a bit strange, but easily manageable.
Part 2, then, hits like a truck. There's no specification whatsoever as to what the tree should look like, so no pattern to search for or anything. Contrary to the classic Stars Align puzzle several years back, there's no obvious starting point. No, this puzzle requires coming up with several heuristics ... and I found three of them that work to various extents.
Heuristic 1: Unique Positions assumes that the input is constructed such that at the relevant time step, there's no spot covered by more than one robot (which turns out to be generally true), and that such a situation never occurs before – which turns out to be not the case for some users' inputs, but I was lucky. So it isn't the most general solution, but when it works, it works, and it's quite elegant as well: it requires even less code than part 1!
Heuristic 2: Run of Adjacent Spots assumes that the tree is filled, i.e. that there are a lot of covered spots close to each other. In particular, let's say there should be a run of ~10 horizontally adjacent spots, which is next to impossible at any other time step when the image is just noise. So we can just turn the playfield into a string at each time step and search for #########, and indeed that only happens at the requested time step. That method is the slowest of all, but it has a nice low-tech "whatever it takes" vibe to it. In fact, I've heard from people who solved the task by just dumping the playfield at each timestep into a giant text file and searching for such a run in an editor.
Heuristic 3: Minimum Variance also uses the assumption that the tree results in a compact cluster of covered spots, but it uses a more rigorous scientific/mathematical approach to detecting that – namely, it computes the variance of the covered positions in the first 101*103 = 10403 time steps finds the minimum there. Any variance metric will do here: I use standard variance without squaring and normalization, and adding the variances of the X and Y components, but it's been reported that using part 1's weird "safety factor" metric does the job too, if only because the tree isn't perfectly centered on the grid.
Heuristic 4: Independent Axis Minimum Variance takes the previous approach one step further by throwing even more maths at it. It's based on the observation that the X and Y axes are independent from each other (like in another (in)famous past puzzle), and that the X coordinates of all robots repeat every 101 steps, while the Y coordinates repeat every 103 steps. This also means that the minimum variance states of these axes occur periodically at x0 + nx * 101 and y0 + ny * 103; the time where both coincide is the puzzle answer. So it's sufficient to find the X variance minimum for the first 101 steps and the Y variance minimum for the first 103 steps, and from there on it's all about modular arithmetics – or maybe not, because the factors are small enough that we can just try X minimum-variance step times until we find one that's also a valid Y minimum-variance step time. The end result is the largest implementation, but also the fastest one by quite some margin.
- Part 1, Python: 198 bytes, <100 ms
- Part 2, Python (Unique Positions): 178 bytes, ~1.5 s
- Part 2, Python (Run of Adjacent Spots): 222 bytes, ~15 s
- Part 2, Python (Minimum Variance): 235 bytes, ~2.5 s
- Part 2, Python (Independent Axis Minimum Variance): 265 bytes, <100 ms