Advent of Code - Day 14

Adrien Foucart

2024-12-14

@=programming @=python @=adventofcode

[Go to index] [Advent of Code website] [My code on Gitlab]

I got done with today’s puzzle early in the day for once. I was a little bit worried about Part 2 for a while, but in the end it was another one where I had the right idea at the start, so all went well.

The puzzle

There is a bunch of robots moving on a grid, which has a certain width and height. Each robot has a starting position and velocity, encoded in our inputs:

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

So that the first robot here is in position x=0, y=4 and has a velocity of x=3, y=-3 (in “grid positions per second”).

The robots move in straight lines, can’t collide, and teleport to the other side of the map if they cross the border (so they “wrap” around the map).

Part 1: dude, where are my robots?

We first have to compute where every robot will be after 100 seconds. Here is where you need to not get tricked into trying to make something complicated to handle the “wrapping around the map” thing.

This is actually a straightforward computation: first, we compute the position as if we had an infinite map, so that \(\vec{p}(t) = \vec{p}(0) + t\vec{v}\). Or, if x and y contain the initial position and vx, vy the velocities:

xt = x + vx*t
yt = y + vy*t

Then we reduce everything to the constrained grid thanks to the modulo operation, which performs the “wrapping around” for us as many times as needed. Taking one dimension at a time, if we have a grid of size 10 and we end up at position 11, we want to “wrap around to 1, which is the result of \(11\%10\). If we end up at 22, we need to wrap around twice and end up at 2, which is the result of \(22\%10\). So we end up with:

xt = (x + vx*t)%width
yt = (y + vy*t)%height

But first we need to parse the inputs, wich calls for some RegEx again:

def parse_input() -> list[tuple[Vector, Vector]]:
    with open("day14", 'r') as fp:
        data = fp.read()
    pattern = r"p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)"
    initial_positions = re.findall(pattern, data)
    robots = []
    for x, y, vx, vy in initial_positions:
        robots.append((Vector(int(x), int(y)), Vector(int(vx), int(vy))))
    return robots

I reused my Position class from Day 8, adapted to x, y notation rather than row, column, to be able to easily do vector arithmetics

class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x+other.x, self.y+other.y)
    
    def __sub__(self, other):
        return Vector(self.x-other.x, self.y-other.y)
    
    def __mul__(self, other):
        if type(other) is Vector:
            return Vector(self.x*other.x, self.y*other.y)
        
        return Vector(self.x*other, self.y*other)
    
    def __repr__(self):
        return f"Vector(x={self.x}, y={self.y})"
    
    def __eq__(self, other):
        return (self.x == other.x) and (self.y == other.y)
    
    def __hash__(self):
        return (self.x, self.y).__hash__()

With that, updating the positions for “after x iterations” is easy:

def update_positions(robots: list[tuple[Vector, Vector]], 
                     iterations: int,
                     width: int,
                     height: int) -> list[tuple[Vector, Vector]]:
    new_positions = []
    for position, velocity in robots:
        end_position = position + velocity*iterations
        new_positions.append((Vector(end_position.x%width, end_position.y%height), 
                              velocity))
    return new_positions

The final score is the product of the number of robots in each quadrant of the grid, ignoring those in the middle row or column. To compute that, we need to go through all final positions, determine which quadrant they are in, and increment quadrant counters:

def compute_score(positions: list[Vector],
                  width: int,
                  height: int):
    robots_per_quadrant = [0, 0, 0, 0]
    middle_x = width//2
    middle_y = height//2
    for position in positions:
        if position.x == middle_x or position.y == middle_y:
            continue
        if position.x < middle_x:
            if position.y < middle_y:
                robots_per_quadrant[0] += 1
            else:
                robots_per_quadrant[1] += 1
        else:
            if position.y < middle_y:
                robots_per_quadrant[2] += 1
            else:
                robots_per_quadrant[3] += 1
    print(robots_per_quadrant)
    return reduce(mul, robots_per_quadrant)

To get the final product, I used functools.reduce to be fancy but with just four values writing the multiplications explicitly would have been fine.

Putting all of this together gets us the first part answer:

width = 101
height = 103
robots = parse_input("")
final_positions = update_positions(robots, 100, width, height)
print(f"Part 1 answer: {compute_score([pos for pos, _ in final_positions], width, height)}")

Part 2: dude, where’s my tree?

I was very close to giving up on part 2, even though I hadn’t spent much time on it, because I just couldn’t see the start of a solution.

We need to find the number of seconds, from the initial conditions, before the robots form a picture of a Christmas tree.

I was stuck. I quickly tried to visualize the grid for a few iterations, but clearly I wasn’t going to get anywhere with that unless it happened in the first few iterations, which was unlikely. But what was I even looking for? What kind of shape?

My first (bad) guess was to think: a Christmas tree should be symmetrical and have something on top, so maybe I can just visualize the tree whenever there’s a robot on the center-top position? That got me nowhere.

But I reasoned that there must be some kinda-obvious criterion that I could check and that didn’t depend on the precise meaning of what a Christmas tree looks like, otherwise Eric would have given us a precise description.

And eventually I got the idea that, if the robots arrange themselves into some sort of predetermined shape, the key thing should be that they should all occupy a different position. In other words: there shouldn’t be any overlapping robots, so the shape is “clean”. I wasn’t super satisfied with the robustness of this reasoning, but it’s the only testable idea I got so I implemented that:

for i in tqdm.tqdm(range(100_000)):
    robots = update_positions(robots, 1, width, height)
    grid = positions_to_grid([pos for pos, _ in robots], width, height)

    if max(grid.values()) == 1:
        show_grid(grid, width, height)
        print(f"Part 2 answer: {i+1}")
        break

With show_grid a method to check if I could see that tree in the result:

def show_grid(grid: dict[tuple[int, int], int],
              width: int,
              height: int):
    for r in range(height):
        print(''.join(str(grid[(r, c)]) if grid[(r, c)] > 0 else '.' for c in range(width)))

Which fortunately gave me the right answer… and a Christmas tree:

..........1....................................................1.....1...............................      
..................................................................1..................................     
.......................................1..............................................1..............     
...1.........11......................................................................................     
.....................................................................................................     
....1.........1....................1............................................1....................     
.........................................................................................1...........     
..............................................................................................1......     
.....................................................................................................     
.....................................................................................................     
....................................................1..............1.................................     
.........1......................................................1.......1.......................1....     
.....................................................................................................     
.1......................1............................................................................     
.......................................1.............................................................     
.....................................................................................................     
.................1..........................................................................1.......1     
...............................................................11............................1.......     
.....................................................................................................     
.........1...........................................................................................     
.....................................................................................................     
.....................................................................................................     
...................1.................................................................................     
..................................11...................................1.............................     
....................................................................................................1     
..........................................................1..........................................     
.....1............1..........................................................1.......................     
......................1..............................................................................     
.............................................................................1......1................     
..1......................................1...........................................................     
................................................................................................1....
...........................1..............................................................1..........     
.............................................................................................1.......     
.....................................................1111111111111111111111111111111........1........     
........................1............................1.............................1........1........     
......................1..............................1.............................1.................     
...............1................1....................1.............................1.................     
............................1........................1.............................1.................     
..1..................................................1..............1..............1.................     
.....................................................1.............111.............1.................     
..............................1......................1............11111............1.................     
.....................................................1...........1111111...........1.................     
....................................1.1..............1..........111111111..........1.................     
..1..................................................1............11111............1.................     
.....................................................1...........1111111...........1.................     
.....................................................1..........111111111..........1.................     
.....................................................1.........11111111111.........1......1.....1....     
................................................1....1........1111111111111........1..............1..     
.....................................................1..........111111111..........1.................     
.....................................................1.........11111111111.........1.................     
............................1.....................1..1........1111111111111........1.................     
.............................................1.......1.......111111111111111.......1.................     
.........................1...........................1......11111111111111111......1.1...............     
.....................................................1........1111111111111........1.................     
.............................................1.......1.......111111111111111.......1.......1.........     
.1................................1..................1......11111111111111111......1.................     
.................................1...........1.......1.....1111111111111111111.....1.................     
.....................................................1....111111111111111111111....1.................     
...................................................1.1.............111.............1.....1..........1
.................................................1...1.............111.............1.................     
...1.................................................1.............111.............1.................     
.............................................1.......1.............................1.................     
..................................1..................1.............................1.................     
............1........................................1.............................1.................     
.....................................................1.............................1.................     
.....................................................1111111111111111111111111111111.................     
..........1.............................1...................................................1........     
.....................................................................................................     
.....................................................................................................     
...........1.........................................................................................     
...............................................1...............................................1....1     
.....................................................................................................     
................................................................................................1....     
.....................................................................................................     
............................................................1........................................     
.....................................................................................................     
...............................................................1...1.................................     
......................................................1..............................................     
.....................................1.....................1.1.......................................     
.......................................................................1.............................
........................................................1...................................1.....1..     
..............1.....................................1..................1.............................     
...............................1...........................................1.........................     
..........................................................................................1.......1..     
.................1...................................................................................     
..........................1..........................................................................     
................................1.....................................1.............1...........1....     
...1........................................................................1..1.....................     
..............................................................................1...................1..     
.....1....1..........................................................................................     
.....................................................................................................     
................................................................................1..........1.1.....1.     
.....................................................................................................     
..............................................1......................................................     
.....................1....................1..........................................................     
...................................................................................................1.     
.....................................................1...............................................     
....................................................................1................................     
...............1........1.........................1..................................................     
...............................1................1......1.............................................     
..............................1.1.............................................1......................     
.................................................................1...1...............................     
..................................1...............................................1.....1............

Not entirely convinced by this one, especially since the puzzle states that “most of the robots should arrange themselves into a picture of a Christmas tree” (emphasis mine), so it wasn’t a given at all that all robots should be at unique positions. Fortunately for me, I didn’t notice that until after I solved the puzzle, so my own carelessness saved me.

UPDATE later in the day

Was that it?

I’ve looked at some other solutions on the Advent of Code subreddit to see if I missed something, and so far it seems like there are four types of solutions:

Spend a lot of time browsing through renders of of the grid.
My solution of finding a grid with no overlapping robots.
Pattern-matching by making some guess about the shape of the tree (e.g. that there would be more than x vertically aligned robots).
Entropy!

1 is what I clearly wanted to avoid.

2, it turns out, isn’t actually correct. I just realized reading the solutions that not everyone gets the same input, and apparently – according to some redditor, which is always a trustworthy sentence – that method doesn’t work on every input. If that’s true, then I was lucky.

3 wouldn’t be much more satisfying and also require a fair amount of luck, as we don’t even know the size of the tree. I had (incorrectly) assumed that it would take up the whole grid, but it wasn’t the case. It could have been drawn empty or full, symmetrical or not… so I’m not a big fan of those solutions either.

4 is actually clever and, IMO, the best solution. The idea is: if the robots group into some sort of ordered shape at some point, then the entropy of the grid at that point will be lower. There are several ways to practically do that, from the hacky-but-easy-to-understand way of just looking for the appearance of a large cluster of neighbouring robots, to binning the map into small NxN sectiosn and computing Shannon entropy, to the mad solution of saving every frame as a PNG file and look for the smallest file size, since the compression rate of the file will depend on the entropy. Mad, but clever.