Day 12: The N-Body Problem

---

Links:

• Puzzle on adventofcode.com
• Source Code

Today was a bit of a busy day for me. I’m writing this at around midnight and because of that I’m going to keep it relatively short for today. Narrator: He didn’t keep it short

There isn’t really much wiggle room for the first part. It serves as a good test for whether you’ve understood the problem, but it doesn’t take you anywhere beyond that. Instead of just using type aliases - like I often do - I implemented structs for vectors and moons (yes, of course I created my own 3d vectors. Why would you even ask at this point).

I instantly knew I wanted to use the LCM (least common multiple) for the second part. Because I couldn’t remember the exact formula for calculating it, I looked it up and you can imagine my surprise when I found out that the Wikipedia article on it has a section dedicated to “Planetary alignment”. This describes pretty much the same situation we have in part 2. I’m not just mentioning this because it’s a “funny fact”. The section explicitly outlines where I went wrong with my first attempt. Because I already had this nice struct for the moon, I really wanted to keep using it. You know, to get the most bang for my buck. So what I wanted to do was to track each moon’s period separately and then use the LCM to get the total period. This, to me, sounded like a really nice solution to the problem. Turns out that not a single moon reverts back to its initial state in a reasonable amount of time.

You might say that I should’ve noticed this might not work because there are only four moons, but I really wasn’t thinking about this at the time.

I felt quite stumped at this point and only after looking at the moons’ positions over time did I realise that the dimensions were entirely independent. I should’ve noticed this way sooner because of the way “gravity” is calculated, but I was so focused on my sweet little solution that I didn’t pay any attention. This is the part where my decision to use a moon struct came back to haunt me because it doesn’t provide an easy way to simulate each dimension independently. I still wasn’t even convinced that searching for the period of each dimension separately would yield a result, therefore I wasn’t ready to commit to changing or writing new code.

Instead, I hacked together a solution:

type AxisTuples = Vec<(isize, isize)>;

fn get_state_tuples(moons: &[Moon]) -> (AxisTuples, AxisTuples, AxisTuples) {
    let mut x = Vec::with_capacity(moons.len());
    let mut y = Vec::with_capacity(moons.len());
    let mut z = Vec::with_capacity(moons.len());

    for m in moons {
        x.push((m.position.x, m.velocity.x));
        y.push((m.position.y, m.velocity.y));
        z.push((m.position.z, m.velocity.z));
    }

    (x, y, z)
}

This function converts a list of moons to three lists, one for each dimension, containing the position and velocity of the dimension. Thanks to this function I could keep using the logic from part one.

I used the following algorithm:

Capture the initial state of all dimensions (using the function).
Run the simulation and after each step capture the state of each dimension (using the function).
Compare the current state with the initial one.
    If both are equal, store how many steps were required to reach this point
    and mark the dimension as done, excluding it from being checked the next time.
Continue until all three dimensions are marked done.
Return the LCM of the amount of steps it took for each dimension.

It’s rather inefficient to run the get_state_tuples function after each call. After all, it creates three new lists every time. But it doesn’t affect the runtime all that much (who cares about memory usage these days cough cough) and it does make things a whole lot easier for me, so I didn’t bother with another approach.

I’m honestly kind of disappointed that it came down to the dimensions. Obviously I’m biased because of the way I implemented the first part, but I think getting the period of each moon would have made for a better puzzle. Now that I think about it, there might be other ways to solve this puzzle that I just couldn’t come up with. Be that as it may, I did enjoy today’s struggle.

I am aware that the path of each moon is influenced by all other moons, therefore their movement is very sporadic. The reason why determining the period of each moon separately didn’t work is that each moon has the period of the entire system. Even if a moon’s path were to roughly describe a circle, other moons would cause the path to shift ever so slightly. Two rotations would only be equal if all the other moons were at the exact same position.

---

Overview
Previous day Next day