Advent of Code 2024, Day 14

We have robots guarding the restrooms that move in a straight line in an infinite grid. I mean one where they just wrap around the edges. Very similar solution to yesterday’s.

adventofcode2024/day14 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

We got a bunch of starting points, and then vectors per second. How much do they move after n seconds if they’re constrained in a room, but wrap around whenever they encounter a wall?

Well, starting point + vector * seconds % size. It’s a one liner for each direction.

The hardest thing was figuring out the off–by–one errors, but tests helped here.

Separating the coördinates meant four distinct filters where I compare the quadrant bounds to the end coördinates. And that’s about it.

Intermission for some Christmas shopping and movie time!

Part 2

This is going to be annoying, because what does “looks like a Christmas tree” even mean?!

It is now about 24 hours later.

I absolutely hated this. The problem wording is vague and there’s not a lot of help. I didn’t read a lot of the r/adventofcode solutions, only some of the memes, but they didn’t help much. Anyways, let’s try to brute force this.

Important details: both the width of 103 and the height of 101 are prime numbers, which means that any stepping of a robot’s coordinates are only going to loop every 101 or 103 seconds, depending on what we’re looking at: its horizontal or vertical coordinates.

The entire process was manual, because I can’t really figure out a programmatic way to match against something where I don’t know what that something is.

I thought maybe generating all unique coordinates after each step, and then flood filling that cloud of coordinates, and then comparing the length of the flood filled area with the length of the input coordinates would do. I thought if the lengths match, all robots touch, and that surely is a Christmas tree.

I let this run for about an hour while I played some Path of Exile 2, but did not finish. Ugh...

Manual it is.

First assumptions: Christmas trees are pointy, so let’s see frames where the topmost row only has one robot in it. Turns out that there’s actually quite a lot of seconds for that. I also had the thought of measuring the distance between each second. Turns out frames 12, 22, 79, 126, 136, 182, 229 all have only one robot on the topmost row. Adding the differences between each frame we get 10, 46, 47, 10, 46, 47... huh. Repeating. And their sum comes to 103.

All right, next up let’s only look at frames where I already know there is only one robot in the topmost row. A Christmas tree is a triangle at top, so let’s find cases where the next row has 3 robots. Create a loop, iterate through the frames that have one robot, and check if the second row has three robots, and collect those. Pseudo code looks like this:

let mut i = 0;
let mut current = 12;
let mut distance = 10;

loop {
  let mut robot_coords: Vec<(i32, i32)> = Vec::new();
  let mut robots_per_vert: HashMap<i32, i32> = HashMap::new();

  self.robots.iter().for_each(|r| {
    let coords = r.move_robot(bounds, current);
    robot_coords.push(coords);
    *robots_per_vert.entry(coords.1).or_default() += 1;
  });

  seconds += distance;
  distance = generate(distance);
}

fn generate(in: i32) -> i32 {
  match in {
    10 => {46}
    46 => {47}
    47 => {10}
    _ => {103}
  }

Three robots in second row wasn’t a thing.

So I thought: okay, a Christmas tree is symmetric, so what if the one robot in the first row is actually in the middle. That gave me another cycle, though these distances were 767, 2107, 7529. Those numbers sum up to 10,403, which is 101 * 103.

At this point I was getting frustrated, so I wrote a function to draw what the room looks like on those seconds:

fn visualise(iteration: i32, bounds: (i32, i32), input: Vec<(i32, i32)>) {
    let mut s = String::from("Iteration ") + &iteration.to_string() + "\n";
    for vertical in 0..=bounds.0 {
        for horizontal in 0..=bounds.1 {
            match input.contains(&(horizontal, vertical)) {
                true => {s.push('#');}
                false => {s.push('.');}
            }
        }
        s.push('\n');
    }

    let mut file = File::create(iteration.to_string() + "tree.txt").unwrap();
    file.write_all(s.as_bytes()).unwrap();
}

I generated a thousand images (text files) or so, opened them in the Mac’s Finder, and quickly stepped through them with the file preview thing you get when you press Space on a file.

I noticed that the topmost robot is indeed in one place, however the rest of the pattern exhibited two weird behaviours:

1. it didn’t seem to converge, and
2. it looped? Like... every third or so looked eerily similar

That looping similarity and non–convergence made me think of brute forcing the state of the room by second, so this time I generated a thousand or so images second by second.

I noticed that every so often there’s a convergent column in the middle of the room, but with no discernible image. There was another set of convergence, horizontally, at different points, but I focused on the vertical columns.

I took mental notes of roughly where they have been: ninety-something, one hundred ninety something, two hundred ninety something, and then at around 600 I took note of the actual number. Then I went back to see where the column formed, and turns out they form every 101 frames starting from 97.

So I generated another thousand or so room states starting at 97 seconds, and stepping 101 seconds. Every image there had the column, and sure enough, after 75 iterations of that, a picture of a Christmas tree emerged!

The code is a mess, I will not clean it up, it’s the software equivalent of leaving all my tools just laying around in a woodworking shop. If you step somewhere without due care and attention, you will cut your whatever. I hated this.

But also feels weirdly satisfying. ⭐⭐

Spoiler photo by Ashkan Forouzani on Unsplash