Advent of Code 2016 Day 9

Part 1

1. Same day, different year
2. Writing the spec for a loop
3. Running each unit test, then my puzzle input

Same day, different year

2017 Day 9 offered a similar-themed challenge: processing a stream of characters.

This time, the unique aspects are:

• Based on the existence of certain characters, the stream length will grow substantially once it's been processed
• All that Part 1 asks for is a length, not the contents of the processed stream - that may make my algorithm less complicated and more performant...since I just have to accumulate a sum instead of a string

Writing the spec for a loop

Set answer to 0
Set pointer to 0
Do as long as pointer is not beyond the length of the input string
  Increment answer and pointer depending on the value at pointer:
    1. Value is (
       Create marker as an empty string
       Append to marker one character at a time for all characters after the ( and before the next )
       Split the resulting string at the x into an array of two strings
         Coerce each string to a number
       Increment answer by the product of both numbers
       Increment pointer by the sum of the length of marker, the first of the two numbers, and 2 
    2. Value is anything else
       Increment answer by 1
       Increment pointer by 1
Return answer

The equation I struggled most to figure out:

Increment pointer by the sum of the length of marker, the first of the two numbers, and 2

After some tinkering in the code, then a break from the code, I discovered the winning ingredients, given how my algorithm works.

Running each unit test, then my puzzle input

• This puzzle graciously offers six unit tests
• I passed the first couple
• But failed a middle one
• Then passed the middle one
• But failed some early ones
• Then fixed my algorithm to become what is shown above
• And passed every unit test

Then, running it on my puzzle input:

• Generated the correct answer!

My core loop in JavaScript:

let answer = 0, pointer = 0
while (pointer < input.length) {
  switch (input[pointer]) {
    case "(":
      let marker = ""
      for (let j = pointer + 1; input[j] !== ')'; j++) {
        marker += input[j]
      }
      let [chars, times] = marker.split('x').map(Number)
      answer += chars * times
      pointer += marker.length + 2 + chars
      break;
    default:
      answer++
      pointer++
  }
}
return answer

Part 2

1. Still just the length, but now...recursion?
2. Updating my algorithm to use recursion
3. Running each unit test, then my puzzle input

Still just the length, but now...recursion?

So...I guess that's good and bad news.

I've got to study the second example closer:

X(8x2)(3x3)ABCY

• X is normal: add 1 to sum
• (8x2) targets (3x3)ABC
• Instead of adding 16 to my sum and moving to Y
• I need to decompress that bit
• (3x3) targets ABC
• Attempting to decompress it just results in 3
• So, (3x3)ABC decompressed has length 9
• Instead of 8x2 I now have 9x2 = 18
• Add 18 to sum then move to Y
• Y is normal: add 1 to sum
• Final sum: 1 + 18 + 1 = 20

Hmm. That seems complicated.

But I have a hunch I only have to make a few adjustments to my Part 1 algorithm to get this to work.

Updating my algorithm to use recursion

• My entire algorithm must now become a function
• Instead of incrementing answer by the product of chars and times, I'll increment answer by the number returned from calling the function, but with the number of characters referenced in the parentheses sliced from the string just after pointer

I think that's it!

Running each unit test, then on my puzzle input

• This part graciously offers four more unit tests
• I passed them all!

Then, running it on my puzzle input:

• Generated the correct answer!

My new core loop in JavaScript:

function decompress(stream) {
  let answer = 0, pointer = 0
  while (pointer < input.length) {
    switch (input[pointer]) {
      case "(":
        let marker = ""
        for (let j = pointer + 1; input[j] !== ')'; j++) {
          marker += input[j]
        }
        let [chars, times] = marker.split('x').map(Number)
        answer += times * decompress(
          stream.slice(
            pointer + marker.length + 2, 
            pointer + marker.length + 2 + chars
          )
        )
        pointer += marker.length + 2 + chars
        break;
      default:
        answer++
        pointer++
    }
  }
  return answer
}

An animation of how my recursive algorithm works:

I did it!!

• I solved both parts!
• I solved another recursion algorithm puzzle!
• I smartly recognized I should focus on incrementing a sum equivalent to a length, avoiding the trap of accumulating some massive string!
• That strategy saved me from having to re-think my entire algorithm for Part 2!