Here’s mine.
My solution for part 1 is extremely simple.
However, for part 2 it’s quite involved (and not very fast). On the upside, I think I cover all the edge cases, and the correct solution is determined in finite time. I also had to reach for some long forgotten maths to solve it.
Basically, I went for a brute force approach. For each pair of particles, I calculate their collision points. Then I group, so I get a list [collision_2, [p1, p2, p3, ...], [collision_2, [...], ...] sorted by the collision point. After that calculating survivors is pretty trivial.
I wonder if there is a better approach, but couldn’t really think of any. I though about simulating the universe by moving particles one step at a time, and removing the collided ones in each step. However, it wasn’t clear to me when to terminate the loop. When should I stop and decide that there are no collisions?
A friend of mine picked a magical number (I think it was 10000), and stopped if no collision happened in that time. I don’t really like such approach, since it’s trivial to construct an input where the collision happens after the magical number.
I’m still not proud with my solution for day 16 (the dance), which detects a cycle. Once I find the time, I’ll recode it.
