How little green men helped me solve a puzzle

Okay, so first of all it is all Serge’s fault. On the train back from Schiphol he introduced me to https://www.adventofcode.com and together we solved the first puzzle, which also marked my first steps into Python.

I was hooked instantly.

Every year I try to learn at least one new language or skill, but the last few years it felt like cheating. First I learned AppleScript then Blender and last summer I settled for kOS scripting, interesting, but not very deep and most of all not very practical. Python proved to be something else. It reminded me of C, Pascal, Bash and everything else. It seemed to come very naturally and at the same time it continued to surprise me with simple constructs that allow you to do things elegantly and efficiently.

But that was not the only thing I was hooked on.

The advent of code is a series of puzzles that are released daily for 25 days prior to Christmas. Each puzzle consists of two parts and resembles a mathematical problem that is described in a narrative. This year Santa was lost on the edge of the solar system and we would need to rescue him. Being a bit of a space-nerd this narrative sounded amazing to me, especially since the stories were rooted in some kind of real-world alternative such as the Tsiolkovsky rocket equation.

“Santa has become stranded at the edge of the Solar System while delivering presents to other planets! To accurately calculate his position in space, safely align his warp drive, and return to Earth in time to save Christmas, he needs you to bring him measurements from fifty stars.”

What about those green men?

Ah well, I admit, it is an obscure reference and mainly click-bait, but I’ve been a great fan of https://kerbalspaceprogram.com ever since it was in alpha. I even created some mods for it. Part of that game is getting the little green men to other planets in their solar system which can only be done efficiently if the planetary alignment is correct. Which brings us to the puzzle of day 12.

Hold on, planetary alignment?

Yes, rather than flying straight to a planet, a spacecraft picks up some speed (when going outwards) and sort of catches up with a slower moving planet. At the highest point of its orbit, it will encounter the target and voila. So speed and time of departure is important but so the time of departure. Here is a picture of the insight spacecraft catching up with Mars that I stole from Wikipedia.

Kerbal Space Program uses a simplified model where the planets won’t influence each other, so basically you can calculate how often a certain alignment occurs by looking at the common denominator between the product of their cycle time. This happens in 3-axis of course but since most planets, (except for Moho) are almost in the same plane, players tend to ignore that. So part 2 of day 12 was a pleasant surprise.

The N-Body problem that wasn’t

Day 12 introduces the N-body problem of the moons of Jupiter, well not all of them, just the Galilean ones. Each moon affects the other, so rather than moving in a continuous fashion the moons perform a celestial dance (or judo match) pushing and pulling each other, affecting speed and position. This is called the N-body problem, however, there was a small hint hidden in the notes that made life a lot easier: the initial velocity was 0. This meant that over time the moons would get back at their initial position with their initial velocity (being 0).

Our mission was to calculate how long it would take for the universe to return to its original state. My first attempt was to write a simulator, but the universe is a big thing and it simulating it step by step would take a very long time. This is where I thought back of the little green men in Kerbal Space Program and the answer came.

We can first check for an alignment of all the planets in the x plane, then the y plane and then the z plane. This is 3 times an O(n) problem rather than an O(n^3) so then we have:

align_x = steps to align whole system in x plane

align_y = steps to align whole system in y plane

align_z = steps to align whole system in z plane<br />

Which gives us align_x * align_y * align_z combinations, but there might be earlier alignments. Let’s look at two planes as in Kerbal Space Program:

align_xy = align_x * align_y / gcd(align_x, align_y)

That already looked better, but how quickly does that align with the z-plane:

align_xyz = align_xy * align_z / gcd(align_xy, align_z)<br />

Because of the initial velocity of zero, the system basically resets every n cycles, which is kind of cool! I loved solving this puzzle which has produced some elegant code, in far contrast to the int computer (based on the agc) which has become a steaming pile of junk.

Now what?

I’ll keep puzzling, so far I have managed to solve all the puzzle, but day 16 part 2 keeps eluding me for now. There is a pattern there that I am not seeing but it will come. I’ve also managed to enlist the help of other little men. 

My son managed to solve the maze puzzle more than an hour before I managed to implement a breadth first algorithm in Python for the maze solver 😉