DEV Community

Cover image for Explosives in Cyberspace
Robert Mion
Robert Mion

Posted on

Explosives in Cyberspace

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
}
Enter fullscreen mode Exit fullscreen mode

An animation of how my recursive algorithm works:

Animation of my algorithm

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!

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay