Particle Swarm

Advent of Code 2017 Day 20

Part 1

1. Objects moving...in space...again!
2. Creating the particle data structure
3. Executing each particle movement
4. Identifying the winner
5. How many ticks to find the unchanging winner?

Objects moving...in space...again!

The twist with this one appears to be:

• Some objects may start near - then ultimately move further away from - a central point
• Other objects may move in a circle of varying radii lengths around a central point
• Other objects may move toward but ultimately away from a central point

With the task being:
Solve for X where X =...

The particle that will stay closest to position <0,0,0> in the long term

Gauging my confidence:

• I can parse the input for each particle's nine values
• I can perform the necessary calculations which adjust each particle's position and velocity each iteration
• I can track each particle's Manhattan Distance from <0,0,0> after each iteration
• But how many iterations will I need to process to identify the correct particle?
• And how will I identify that particle? The one with the lowest average Manhattan Distance?

As of right now, I'm:

• Excited to write the necessary algorithms to generate a particle movement program
• Expecting to be unable to generate a correct answer for Part 1

Creating the particle data structure

Each particle has nine attributes:
The X, Y, and Z coordinates for the particle's position (p), velocity (v), and acceleration (a)

I'll need to track the Manhattan Distance of the particle's position, too.

This data structure should work:

{
  p: [X,Y,Z],
  a: [X,Y,Z],
  v: [X,Y,Z],
  md: [
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    (Math.abs(p[X]) + Math.abs(p[Y]) + Math.abs(p[Z])),
    ...
  ]
}

To generate it, I'll use this regular expression:

/-?\d+/g

• It extracts every integer - positive or negative - from a string
• I can feel assured that it will always match nine integers
• And that those integers will always be in the same order

Executing each particle movement

As stated in the instructions, each tick:

Increase the X velocity by the X acceleration.
Increase the Y velocity by the Y acceleration.
Increase the Z velocity by the Z acceleration.
Increase the X position by the X velocity.
Increase the Y position by the Y velocity.
Increase the Z position by the Z velocity.

• I do this algorithmically using map() on my array of particle objects
• Updating the appropriate list index associated with the appropriate key on each particle object

In addition, I insert a new Manhattan Distance at the end of each object's md array.

Identifying the winner

At the end of some arbitrary number of ticks:

Generate an identically-ordered list of particles
  But where each element is a single floating-point number:
    The average of each of that element's Manhattan Distances
Return the index of the item with the lowest average Manhattan Distance

How many ticks to find the unchanging winner?

Trial and error for the win:

• 10 ticks?
• 100 ticks?
• 1000 ticks?
• 10000 ticks?

See for yourself!

What I saw as my algorithm worked toward the correct answer:

Part 2

1. Collision detection? This complicates things...but by how much?
2. How many ticks to find the unchanging particles remaining?

Collision detection? This complicates things...but by how much?

In Part 1, my map() function was enough of a simultaneous movement simulation.

But this time, I'll have to go a step further:

Throughout the use of map()
  Flag any positions that appear twice within a tick
  As long as at least one position appears twice
    For each position at which point a collision occurred
      Filter the list of particles to include any at the current position
        For each identified particle
          Remove that particle from the original, working list
  Print the length of the working list of particles

How many ticks to find the unchanging particles remaining?

Trial and error for the win again:

• 10 ticks?
• 100 ticks?
• 1000 ticks?
• 10000 ticks?

What I saw as my algorithm worked toward the correct answer:

I did it!!

• I solved both parts!...
• Of a puzzle involving objects moving in three dimensions!...
• In what felt like record time!...
• And very little code!

At the onset of this puzzle, I had doubts that I'd solve Part 1.

Well, here I am only a few hours later with two more gold stars!

Either this puzzle ranks among the easier Day 20 puzzles, or I'm getting better at solving these puzzles.

Regardless, today's puzzle was a refreshing departure from the prior day's array slicing and merging nightmare.