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 memory-lane-inducing 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 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
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 0-2
- Width indices range 0-4
-
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 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
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 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
- 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!
Top comments (0)