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
- The easy part (I hope?): extracting the positions
- Understanding how the velocity is calculated and positions are updated
- Another easy part: calculating the
total energy of the system
- 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=
matchesx=
,y=
,z=
-
(-?\d+)
matches2
,-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:
- Update the velocity of every moon by applying gravity
- 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
- Another challenge of algorithm performance and optimization, I presume?
- LCM & GCD
- 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!
Top comments (0)