Advent of Code 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 eightdigit message embedded in the final output list after 100 phases
Example input
12345678
It represents:
 A signal
 A series of singledigit numbers representing a sequence
Part 1
 Understanding the base pattern and how it interacts with the current phase of the input list
 Writing an algorithm to generate each base pattern needed for any input list
 Writing an algorithm to complete any number of phases
 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 singledigit 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 currentlyprocessed 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 recreate 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 nonsliced 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 regenerating 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
 As expected, a performance/stress test
 Expanding the input to itself cloned 10,000 times
 Attempting to run my algorithm...fails
 Reading the subreddit 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 subreddit thread
 Bruteforce 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
andmodulo
 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.
Top comments (0)