The N-Body Problem

Advent of Code 2019 Day 12

Try the simulator of Part 1 with your puzzle input!

Task: Solve for X where...

Part 1

X = the total energy in the system after simulating 1000 steps of the four moons' motion given in my scan

Part 2

X = the step where all four moons repeat their initial state for the first time

Example input

<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>

It represents:

• The x,y,z positions of four moons of Jupiter

Part 1

1. The easy part (I hope?): extracting the positions
2. Understanding how the velocity is calculated and positions are updated
3. Another easy part: calculating the total energy of the system
4. A written outline of my working algorithm

The easy part (I hope?): extracting the positions

Without a regular expression:

<x=2, y=-10, z=-7>

Trim off both ends
'x=2, y=-10, z=-7'

Split at ', '
['x=2','y=-10','z=-7']

Trim off the first two characters in each
['2','-10','-7']

Coerce to numbers
[2,-10,-7]

With a regular expression:

/\w=(-?\d+),?\s?/g

Matches <x=2, y=-10, z=-7>:

• \w= matches x=,y=,z=
• (-?\d+) matches 2,-10,-7
• ,?\s? matches ,,,

For each moon's position, I then get the same list of three matches associated with the x,y,z positions.

Understanding how the velocity is calculated and positions are updated

Facts:

• Each moon has a 3-dimensional position (x, y, and z) - that's given in my input
• Each moon has a 3-dimensional velocity (x, y, and z) - all starting at 0

Motion is simulated in time steps.

During each one:

1. Update the velocity of every moon by applying gravity
2. Update the position of every moon by applying velocity

Update the velocity of every moon by applying gravity

To apply gravity, consider every pair of moons.

There are four moons, so:

1,2
1,3
1,4
2,3
2,4
3,4

For i from 1 to (1 less than the number of moons):
  For j from i + 1 to (the number of moons):
    Compare moon i's x,y,z to j's x,y,z

Walkthrough:
i=1, j=2
i=1, j=3
i=1, j=4
i=2, j=3
i=2, j=4
i=3, j=4

On each axis (x, y, and z), the velocity of each moon changes by exactly +1 or -1 to pull the moons together

Given two numbers - the velocities of a pair of moon's shared axis:
  If both are equal
    Do nothing
  Else, each differ
    Decrement the greater number by 1
    Increment the lesser number by 1

Walkthrough:
 5 <>  3
-1    +1

 2 <>  2
 -     -

 1 <>  4
+1    -1

Update the position of every moon by applying velocity

Simply add the velocity of each moon to its own position

Example given:

Where positions are:
x= 1, y=2, z=3

And velocities are:
x=-2, y=0, z=3


New positions are:
   1    2    3
  -2   +0   +3
-----------------
x=-1, y=2, z=6

Velocities remain unchanged:
x=-2, y=0, z=3

Another easy part: calculating the total energy of the system

For each moon:
Calculate the product of two sums:
  1. Sum of the absolute values of the x,y,z positions
  2. Sum of the absolute values of the x,y,z velocities
Return the sum of all products

A written outline of my working algorithm

Split the input at each newline character to create an array of strings

Modify each string according to the following operations:
  Use the regular expression on each string to create a 3-element array of strings
  Coerce each string to a number
  Based on the order of the match (0,1,2), set each as value of the respective x,y,z keys inside an object that stores positions and velocities
  Return the object with stored x,y,z key-value pairs for position and velocity

For each step from 0 to i - as defined by the input parameter
  Compare each pair of moons
    Update each moon's velocity x,y,z based on whether the position x,y,z is <,>,== the other moon's position
  Update each moon's position x,y,z by adding the current velocity x,y,z

Calculate the total energy by following these operations:
Accumulate a sum - starting at 0
  For each moon
    Calculate the product of two sums:
      1. Sum of the absolute values of the x,y,z positions
      2. Sum of the absolute values of the x,y,z velocities
  Add the product to the accumulating sum

Return the sum

The instructions in this puzzle offer a great visual for most of what is described above.

It seems redundant to create an animation.

Part 2

1. Another challenge of algorithm performance and optimization, I presume?
2. LCM & GCD
3. I tried, but failed

Another challenge of algorithm performance and optimization, I presume?

• That's what I thought
• But soon after 'giving up' and skimming the Solution Megathread for today, it seems I was wrong

LCM & GCD

• Lowest Common Multiple
• Greatest Common Denominator
• You need the latter to calculate the former, as I discovered
• And the former is how several solvers generated the correct answer in record time

I tried, but failed

• I wrote an algorithm that identifies the step when each positional coordinate for each moon cycles back upon itself
• I re-created both utility functions for LCM & GCD after finding articles online that illustrate the code
• I wrote a few reducers that calculate the LCMs among different values (e.g. each moon's similar axes, each axis among one moon)
• The LCMs were always exponentially larger than the correct answers provided in the instructions

I feel like I'm really close.

But I sense that any further work would just make me frustrated in an unfruitful way.

Celebrating my accomplishments

• I solved Part 1, which turned out to be easier than I presumed when first glancing at this puzzle!
• I understand and re-created algorithms to calculate LCM & GCD
• I built a simulator of the four moons orbiting an invisible Jupiter

Bummer:

• I didn't solve Part 2
• No GIFs this time since the instructions did a great job illustrating how my algorithms work

Time to move on!