Explosives in Cyberspace
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-08-27 14:51:14

## [Advent of Code 2016 Day 9](https://adventofcode.com/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](https://adventofcode.com/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:
```js
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:
```js
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:
![Animation of my algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/70eep7q1xurolijkouu6.gif)

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