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
andvelocity
 A rate of speed each point moves per second, horizontally and vertically
 Position
X,Y
s are all given relative to a central point at0,0
Part 1
 A memorylaneinducing puzzle
 My proposed recipe for success
 Parsing each point's attributes using a regular expression
 Calculating the side lengths of the stars array
 Creating the stars array from relative coordinates
 Adjusting each position based on velocity
 Wrapping around the array correctly
 Success with the example input
 Building the simulator
 Hitting a brick wall with my puzzle input
 An epiphany upon further inspecting my puzzle input
 Rethinking my whole algorithm
 Refactoring most of my algorithm
 Alas, the message revealed itself!
A memorylaneinducing 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: Redrawing 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 02
 Width indices range 04

0
becomes1

1
becomes4
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 02
 Width indices range 04

2
becomes1

3
becomes0
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 hardcoded 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
andY
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 10thousands 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 recalculate the distance between min and max X and Y points: eventually they should reach a nondecreasing 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 relabeled buttons and to use my new code:
 Press a button to jump ahead and reveal the stars
 Then press a button to redraw the stars at each subsequent second
Try the simulator using your puzzle input!
Part 2
 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 pointmoving 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, messagerevealing puzzle!
Discussion (0)