The Stars Align
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-28 15:33:48

## [Advent of Code 2018 Day 10](https://adventofcode.com/2018/day/10)

## [Try the simulator using your puzzle input!](https://aocthestarsalign.rmion.repl.co/)
![Simulator showing my answers to both parts](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qvrziazgklnrlchnhl4p.gif)

## 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,Y`s 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
```js
/\w+=<\s?(-?\d+),\s+(-?\d+)> \w+=<\s?(-?\d+),\s+(-?\d+)>/g
```

Just the parts I need: the (negative?) digits
```js
/-?\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!](https://aocthestarsalign.rmion.repl.co/)
![Simulator showing my answers to both parts](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qvrziazgklnrlchnhl4p.gif)

## 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!