DEV Community

Cover image for The N-Body Problem
Robert Mion
Robert Mion

Posted on

The N-Body Problem

#adventofcode #algorithms #computerscience #programming

Advent of Code 2019 Day 12

Try the simulator of Part 1 with your puzzle input!

Animation of moons orbiting Jupiter

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
Enter fullscreen mode Exit fullscreen mode

Part 2 

X = the step where all four moons repeat their initial state for the first time
Enter fullscreen mode Exit fullscreen mode

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>
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

With a regular expression:

/\w=(-?\d+),?\s?/g
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode 
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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

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!

Top comments (0)