The Stars Align

Advent of Code 2018 Day 10

Try the simulator using your puzzle input!

Task: Solve for X where...

Part 1

X = a discernible message that eventually appears in the sky

Part 2

X = the number of seconds needed to wait for that message to appear

Example input snippet

position=<-4,  3> velocity=< 2,  0>
position=<10, -3> velocity=<-1,  1>
position=< 5, 11> velocity=< 1, -2>
position=< 4,  7> velocity=< 0, -1>
position=< 8, -2> velocity=< 0,  1>

It represents:

• Points of light in the sky
• Each line is a single point's position and velocity
• A rate of speed each point moves per second, horizontally and vertically
• Position X,Ys are all given relative to a central point at 0,0

Part 1

1. A memory-lane-inducing puzzle
2. My proposed recipe for success
3. Parsing each point's attributes using a regular expression
4. Calculating the side lengths of the stars array
5. Creating the stars array from relative coordinates
6. Adjusting each position based on velocity
7. Wrapping around the array correctly
8. Success with the example input
9. Building the simulator
10. Hitting a brick wall with my puzzle input
11. An epiphany upon further inspecting my puzzle input
12. Rethinking my whole algorithm
13. Refactoring most of my algorithm
14. Alas, the message revealed itself!

A memory-lane-inducing puzzle

Array index wrapping in one dimension:

• 2020 Day 3 - Toboggan Trajectory

Creating an array using min/max values in both directions:

• 2021 Day 17 - Trick Shot
• 2021 Day 2 - Dive!
• 2020 Day 12 - Rain Risk

My proposed recipe for success

• 1 cup: Regular expression
• 6 oz: Minimum and maximum numbers in two axes
• 1/4 cup: Array creation using relative coordinates
• 2 tbsps: Array index wrapping
• 1: Array method to update some values based on others
• 1 tsp: Re-drawing an array after each iteration

Parsing each point's attributes using a regular expression

Input to parse

position=<-6, 10> velocity=< 2, -2>

Pattern as regex pseudocode

word=< ?-?digits?, -?digits?> word=< ?-?digits?, ?-?digits?>

Literal, full string match

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

Just the parts I need: the (negative?) digits

/-?\d+/g

Calculating the side lengths of the stars array

Among all X positions:
  The largest number
+ The absolute value of the smallest number
+ 1
-------------------------------------------
  Width

Among all Y positions:
  The largest number
+ The absolute value of the smallest number
+ 1
-------------------------------------------
  Height

Creating the stars array from relative coordinates

This point:

position=< 2, -4>

Corresponds to this cell:

stars[0][8]

Where:

Smallest X position is -6
Smallest Y position is -4

Arithmetically, this equation works:

-4 - -4 = 0
 2 - -6 = 8

Thus, my algorithm is:

For each point
  Update the value of the cell in the following row and column to a '#':
    Row: point's Y position - smallest Y position
    Column: point's X position - smallest X position

Adjusting each position based on velocity

For a point like this:

position=< 5, 11> velocity=< 1, -2>

Which I store like this:

[5,11,1,-2]

I need to perform this math:

 5     11
+1   + -2

Seems easy enough algorithmically:

For each point
  Update the number at location 1 to the sum of the numbers at locations 1 and 3
  Update the number at location 2 to the sum of the numbers at locations 2 and 4

Wrapping around the array correctly

Suppose this is the grid:

.....
.....
.....

That has a point grid[0][1]:

.#...
.....
.....

Who's velocity is:

<-2,-2>

It would next be placed at grid[1][4]:

.....
....#
.....

How could I express that operation algorithmically?

• The grid is 5x3
• Height indices range 0-2
• Width indices range 0-4
• 0 becomes 1
• 1 becomes 4

What arithmetic is happening here?

• 0 + -2 = -2
• Height is 3
• 3 + -2 = 1

Hmmmm.

• 1 + -2 = -1
• Width is 5
• 5 + -1 = 4

Cool!

A better description of what I'm doing:

If the new position is negative
  Set as the new position the sum of the appropriate side length and the temporary new position

That works when the point moves up or left.

What about when the point moves down or right?

Suppose this is the grid:

.....
.....
.....

That has a point grid[2][3]:

.....
.....
...#.

Who's velocity is:

<2,2>

It would next be placed at grid[1][0]:

.....
#....
.....

How could I express that operation algorithmically?

• The grid is 5x3
• Height indices range 0-2
• Width indices range 0-4
• 2 becomes 1
• 3 becomes 0

What arithmetic is happening here?

• 2 + 2 = 4
• Height is 3
• 4 % 3 = 1

Hmmmm.

• 3 + 2 = 5
• Width is 5
• 5 % 5 = 0

Cool!

A better description of what I'm doing:

If the new position is negative
  Set as the new position the sum of the appropriate side length and the temporary new position
Else, if the new position is positive
  Set as the new position the remainder after dividing the temporary new position by the appropriate side length

Success with the example input

• I hard-coded four iterations for my algorithm to run on the example input
• I saw things exactly as illustrated in the instructions
• It was time to build the simulator so I could run my algorithm on my puzzle input...but with the text super small

Building the simulator

• This was a fairly easy task
• It worked as expected on the example input: showing consecutive seconds of the stars
• Sadly, the page froze whenever I tried it on my puzzle input

Hitting a brick wall with my puzzle input

• I knew that the X and Y positions of my puzzle input spanned ~100k numbers: from -50k to 50k in both axes
• I neglected to realize that, as a nested array, that meant building - and cloning! - a 100k item array whose items were each 100k item arrays!
• That requires a lot of RAM - that which a browser can't fully utilize, especially not quickly
• Furthermore, I attempt to create a string by concatenating each value - well, that string's length isn't supported by browsers either
• Even if it was, the text would have to be microscopic to fit it all within a single viewport

How, then, am I going to solve this puzzle?

An epiphany upon further inspecting my puzzle input

Here are a few of the points from my puzzle input:

position=< 31652,  42178> velocity=<-3, -4>
position=<-20873,  31671> velocity=< 2, -3>
position=< 52717,  42181> velocity=<-5, -4>
position=<-10350,  10650> velocity=< 1, -1>
position=< 31691, -10372> velocity=<-3,  1>

Interestingly, the number in the 10-thousands digit of each X,Y position is the opposite sign - but same digit - as the corresponding X,Y velocity:

           3    ,  4                -3, -4
          -2    ,  3                 2, -3
           5    ,  4                -5, -4
          -1    ,  1                 1, -1
           3    , -1                -3,  1

That means:

• Each point is crawling its way toward - then eventually across - 0,0

Like this:

.....#.....
.....|.....
..#..|..#..
...\.|./...
....\^/....
#--<-|->--#
..../v\....
.../.|.\...
..#..|..#..
.....|.....
.....#.....

Rethinking my whole algorithm

• No arrays until last possible moment: when all points are closest to the center
• Each second, I should re-calculate the distance between min and max X and Y points: eventually they should reach a non-decreasing number...which marks the second after the message likely appeared
• Therefore, I likely need to save the most recent state of the points
• That's ok, though, since there are only about 400 points

Refactoring most of my algorithm

• The initial frame around all of my input's points is ~100k by ~100k
• Each point's velocity moves it closer to a near 0,0 point
• I need to iterate enough times to move each point close enough to 0,0 that I can safely generate and display the stars leading up to - and exactly in - the moment that the stars align to form a message

The while loop that jumps to the moments just prior to the message being formed

Do as long as the sum of the differences between min and max X and Y boundaries is greater than...say...100
  Move each point according to its velocity
  Recalculate each pair of min/max

Rendering the sky for the next few moments

Create a set of points that converts their relative coordinates to precise ones that be used as indices in an array
Calculate temporary min/max pairs for X and Y
Create an array that fully frames the points, filling each cell with a .
For each set of precise points
  Update the value in the appropriate cell with a #
Print the array as a stack of strings generated by concatenating each character in the nested arrays

Thankfully, I wrote the pieces of this new algorithm earlier.

This process required moving the pieces, encapsulating code into reusable functions, and adjusting some variable names where necessary.

Alas, the message revealed itself!

I updated my simulator with re-labeled buttons and to use my new code:

• Press a button to jump ahead and reveal the stars
• Then press a button to re-draw the stars at each subsequent second

Try the simulator using your puzzle input!

Part 2

1. Add counter: easy!

Add counter: easy!

• Whew! An easy Part 2!
• I updated my simulator to track and display a seconds tracker that increments each time the point-moving function runs
• As expected, it generated the correct answer!

I did it!!

• I solved both parts!
• To do so, I had to - and successfully did so - shift my approach toward solving this puzzle: away from rendering an array each step, toward moving the points as close together as possible first!
• I built a simulator that helped me understand my algorithm's deficiencies enough to shift my approach, and later revealed both correct answers!

Wow, this puzzle was an unexpected curveball!

I wish I recognized earlier the difference between example input and my input: how the example was deceivingly more complicated - rarely the case!

Ultimately, another fun, visual, message-revealing puzzle!