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 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.