Solution for Advent of Code 2017 - Day 20: Particle Swarm

Link to the puzzle text

Part 1

In this puzzle, we have a list of particles with their velocity and acceleration in 3 dimensions. We should do a time discrete simulation and find the particle which stays closest to the origin in the long run.

For the simulation, we can add the acceleration to the velocity and add the velocity to the position for each particle. This process is run in a loop and we search for the closest particle at each step. Once the closest particle does not change for a while, we return it as the solution:

if last_score != score:
    last_score = score
    num_stable = 0
else:
    num_stable += 1

if num_stable > 500:
    return last_score

A closed form solution for this part would be sorting the particles by magnitude of the acceleration first, then magnitude of the velocity and finally magnitude of the initial position. This will find the closest particle since in the long run, the acceleration dominates.

Part 2

In part 2, we particles can collide if they are at the same position at the same time. In this case, all colliding particles are removed from the simulation. We should return the number of particles in the long run.

We reuse the simulation from part 1 and added an is_alive flag for each particle. After the position update, we check each particle pair for the same position and switch is_alive to false. Finally we remove all particles with is_alive set to false. Again we run the simulation until the number of particles stabilizes.

Link to my solutions