Flawed Frequency Transmission
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-16 13:02:12

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

## Task: Solve for X where...
### Part 1
```
X = the first eight digits in the final output list after 100 phases
```
### Part 2
```
X = the eight-digit message embedded in the final output list after 100 phases
```

## Example input
```
12345678
```
It represents:
- A signal
- A series of single-digit numbers representing a sequence

## Part 1
1. Understanding the base pattern and how it interacts with the current phase of the input list
2. Writing an algorithm to generate each base pattern needed for any input list
3. Writing an algorithm to complete any number of phases
4. Testing on all the examples and phases, then on my input and 100 phases

### Understanding the base pattern and how it interacts with the current phase of the input list
The base pattern is four single-digit integers:
```
0, 1, 0, -1
```
For any input list larger than four integers, the base pattern will cycle back on itself after the fourth integer, like this:
```
0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1
```
Each integer in the pattern repeats N times, where N equals the location of the currently-processed integer.

Using the example input of `12345678`:
```
*
12345678
N = 1
0, 1, 0, -1, 0, 1, 0, -1

 *
12345678
N = 2
0, 0, 1, 1, 0, 0, -1, -1

  *
12345678
N = 3
0, 0, 0, 1, 1, 1, 0, 0
```

> When applying the pattern, skip the very first value exactly once. (In other words, offset the whole pattern left by one.)

Using the example input of `12345678` again:
```
*
12345678
N = 1
1, 0, -1, 0, 1, 0, -1, 0

 *
12345678
N = 2
0, 1, 1, 0, 0, -1, -1, 0

  *
12345678
N = 3
0, 0, 1, 1, 1, 0, 0, 0
```

### Writing an algorithm to generate each base pattern needed for any input list
- Now that I understand how the base pattern must work, how might I re-create the logic with code?

I'll start with an array:
```
[0,1,0,-1]
```
Then use `flatMap()` to mutate each element into an array of length equal to the current location, where each value is the original item, then flatten the array to just its values:
```
N = 1
[0,1,0,-1].flatMap((item, index) => new Array(N).fill(item))
[0,1,0,-1]

N = 2
[0,1,0,-1].flatMap((item, index) => new Array(N).fill(item))
[0,0,1,1,0,0,-1,-1]

N = 3
[0,1,0,-1].flatMap((item, index) => new Array(N).fill(item))
[0,0,0,1,1,1,0,0,0,-1,-1,-1]
```
Last step is to remove the first item:
```
[0,1,0,-1].flatMap(
  (item, index) => new Array(N).fill(item)
).slice(1)

N = 1: [1,0,-1]
N = 2: [0,1,1,0,0,-1,-1]
N = 3: [0,0,1,1,1,0,0,0,-1,-1,-1]
```

I need the pattern to loop back on itself as many times as the number of single digits in the input.

This expanded pattern must use the non-sliced base pattern at first, then slice off the first item at the end.

Here's a description of my algorithm using the example input:
```
Set base as [0,1,0,-1] for the number at location 1
Create repeatingBase as an empty array
Set example as 12345678, stringified, split at each character into an array of strings, then coerce each string to a number
For i from 0 up to and including example length:
  Set the item at i in repeatingBase equal to the item at the location equivalent to the remainder after dividing i by the length of base
Slice first item from repeatingBase
```

Altogether, my full base pattern generator for any length input goes like this:
```
Split the input at each character into an array of strings
  Coerce each string to a number

Set base as [0,1,0,-1]

Set patterns as an empty array

For each number in the input array
  Set expandedBase as the result of performing the flatMap operation described above on base using the current number's location + 1 as N
  Set repeatingBase as an empty array
  For i from 0 up to and including input array's length:
  Set the item at i in repeatingBase equal to the item at the remainder after dividing i by the length of base
  Remove the first item from repeatingBase
  Add repeatingBase as the new last item in patterns
```

After the loop finishes:
- `patterns` is an array of arrays
- where each nested array contains the same amount of single digits as the input array
- and each digit is the correct one from the repeating, extended base pattern that corresponds to each location

This way, when I perform each arithmetic equation for each digit for each base pattern, I'm not re-generating the same series of 100s of base patterns over and over.

### Writing an algorithm to complete any number of phases
```
Do as many times as there are phases
  Update the input array to the result of the following operations:
    For each nested array in patterns
      Return a single digit resulting from the following operations:
        For each number in the current nested array
          Accumulate a sum - starting at 0
            Add to the sum the product of the current number and the number at the current location in the input array
        Coerce the sum into a string
        Extract the last character in the string
    Coerce each string into a number
Return the first 8 items of the resulting input array, concatenated into a string
```

### Testing on all the examples and phases, then on my input and 100 phases
- 12345678 After 1 phase:  48226158 - CORRECT
- 12345678 After 2 phases: 34040438 - CORRECT
- 12345678 After 3 phases: 03415518 - CORRECT
- 12345678 After 4 phases: 01029498 - CORRECT
- 80871224585914546619083218645595 After 100 phases becomes 24176176 - CORRECT
- 19617804207202209144916044189917 After 100 phases becomes 73745418 - CORRECT
- 69317163492948606335995924319873 After 100 phases becomes 52432133 - CORRECT
- My input After 100 phases becomes 49254779 - CORRECT

## Part 2
1. As expected, a performance/stress test
2. Expanding the input to itself cloned 10,000 times
3. Attempting to run my algorithm...fails
4. Reading the sub-reddit thread

### As expected, a performance/stress test
- The challenge is still 100 phases
- But the input is 10,000 times larger!
- I'm confident I can build this new algorithm
- But I'm almost certain it won't finish in under a minute...or even an hour!

### Expanding the input to itself cloned 10,000 times
- I can leverage the loop I made earlier to generate the repeating base pattern
```
Set source as the input converted to an array of numbers
Create target as an empty array
For i from 0 up to the product of source's length and 10000:
  Set the item at i in target equal to the item at the location equivalent to the remainder after dividing i by the length of source
```

After checking to confirm, my new input array is indeed 10000 times the length of the original input array

### Attempting to run my algorithm...fails
- As anticipated, I get a giant error when running my program
- It seems that creating the patterns array for each of the over 6 million items in my input array is too much for the heap

I wonder what clever computer science skills are required to solve this part of the puzzle...

### Reading the sub-reddit thread
- Brute-force is definitely not the way to go
- The message offset was a clue to not care about roughly half of the scaled input
- And since the base pattern eventually becomes [0, ...0, 1], it is much smarter to calculate things starting from the end of the input rather than the start

I still am unsure how I would write an algorithm to solve this.

That's ok. I enjoyed practicing my skills to solve Part 1!

## Celebrating my accomplishments
- I solved Part 1!
- I got practice using `map`, `flatMap`, `reduce` and `modulo`
- I noticed how much slower creating a increasingly large arrays 10000 times from scratch is relative to creating and setting a 6.5 million item array in one go

Bummer:
- I didn't solve Part 2
- I didn't make any GIFs (though, I was a bit exhausted from making the last puzzle's GIF)
- I didn't make a simulator - this puzzle didn't seem like it would be interesting to visualize

I'll take my one gold star and carry on.