Advent of Code, Day 8

Day 8 of Advent of Code is here! Check out Day 1 for what this is all about. See all of my solutions here.

Did you join my leaderboard? Too bad, stay off my leaderboard, there’s too many good developers on it and I’m not in the top 3 anymore ;). Ok, fine you can join, just you! Go to “Leaderboard” in the top nav of AoC and enter 1030369-e174b794 to join my board. See your leaderboard in Slack! See my other post, written by a friend of mine, on how to get your leaderboard into your Slack channel with a fun lambda function and slash command!

Don’t cheat!

I highly encourage you to get through the day’s challenge on your own. Certainly refer to this and other’s examples to help you get through. I certainly have. I would love to hear how you did! Did you find a better approach than I did? Do tell!

Day 8: Handheld Halting

Part I

“Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.

Their handheld game console won’t turn on! They ask if you can take a look.

You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device.” ref

The code looks like

The challenge is to find the total of the numbers, on the right, for whenever the code hits acc. jmp means jump ahead or behind (-) the current index. nop does nothing, just moves to the next line. There is an infinite loop here, which I hit a few times, so we need to know what the total of the number, I call the accumulator, before the infinite loop repeats.

I mentioned this in Day 7, I think I’m going to start writing JS files and running this in Node in VSCode, instead of running in dev console. The dev console is getting to be too inefficient. Don’t fret, I’ll share how the transition it goes and what you need to do to follow along. I left comments and debuggers in the code this time, to illustrate how you might debug in the dev console.

Let’s load up those code instructions

var instructions = document.getElementsByTagName('pre')[0].innerText.split('\n')

Now that we have the instructions, one per line, rather, one per item in our array, let’s get processin!

var accumulator = 0
var stepIndex = 0
var stepsCompleted = []
 
var processStep = (index) => {
    var cmd = instructions[index]
 
    if(!stepsCompleted.some(s => s.command === cmd && s.index === index)){
        var iArray = cmd.match(/([a-z]{3})\s([-+0-9]+)/i)
        if(iArray){
            var instruction = { command: cmd, index, operation: iArray[1], argument: Number(iArray[2]) } 
            console.log(instruction)
            switch (instruction.operation) {
                case 'acc':
                    accumulator += instruction.argument
                    stepIndex += 1
                    break;
                case 'jmp':
                    stepIndex += instruction.argument
                    break;
                case 'nop':
                default:
                    stepIndex += 1
                    break;
            }
            // debugger
            stepsCompleted.push(instruction)
            processStep(stepIndex)
        }
    }
}
 
processStep(stepIndex)
console.log(stepIndex, accumulator)

Here’s what we got:

• Knowing we’d have to loop through commands, but not just loop through in order, 1 to 100, but 1 to 40 to 87 to 33 to 29, etc., we’ll create a function, called processStep
• The function collecting what index it’s processing. You’ll see below the function, at the bottom, I initiate this whole process by sending in stepIndex, which is 0. This will start with the first item in the array
• I have an array, stepsCompleted, that tracks what steps have been completed. I check that array for the current command at the current index, if it exists already, that’s the start of the loop, so don’t continue and we’re done!
• If it doesn’t exist, let’s process it. We have another .match() (gah who doesn’t love regex?!)
  • ([a-z]{3}) – give me anything between a-z and it has to be 3 characters long
  • \s([-+0-9]+) – get the number, after the space
  • Note the ( ), that will put those values into groups in the output for us to use
• I then create a little instruction object (named as an instruction of code, this line is telling the code to do something, it’s instructing…. yea I hate naming variables). I store the full line as command so we can easily check it later, and the index and the parsed command into to separate parameters.
• Now we process the command. Do you know what each command is doing? Read through it.
• We push this instruction into stepsCompleted so we know we ran it, in the event we hit it again, we can stop the process.
  • I’ve mentioned this in Day 7 as well. I like to work with little objects like this. I could’ve just stored the index in the array, and would’ve been fine. But in troubleshooting, exploring that array, or adding some fun to the code later, I have the entire object. Also, it’s easier to read { index: 2, command: 'acc 23' ... } to know exactly what it is, instead of just seeing 2.
• Once all done, we log it out to get the answer

Phew, that was a fun one…. Part II gets really interesting…

Part II

“After some careful analysis, you believe that exactly one instruction is corrupted.

Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)” ref

Ug, there’s always one line that breaks everything. Seems straight forward enough though, or so I thought….

Here’s our new code:

var instructions = document.getElementsByTagName('pre')[0].innerText.trim().split('\n')
var accumulator = 0
var stepIndex = 0
var stepsCompleted = []
var swapped = []
var didSwap = false
 
var processStep = (index) => {
    if(index < instructions.length) {
        var cmd = instructions[index]
        if(cmd) {
          if(!stepsCompleted.some(s => s.command === cmd && s.index === index)){
              var iArray = cmd.match(/([a-z]{3})\s([-+0-9]+)/i)
              if(iArray){
                var instruction = { command: cmd, index, operation: iArray[1], argument: Number(iArray[2]) } 
                stepsCompleted.push(instruction)
                  // console.log(instruction)
                  switch (instruction.operation) {
                      case 'acc':
                          accumulator += instruction.argument
                          stepIndex += 1
                          break;
                      case 'jmp':
                          if(!didSwap && !swapped.some(s => s.command === cmd && s.index === index)) {
                              // swap with nop, do nothing
                              // debugger
                              // console.log('swapped',instruction)
                              didSwap = true
                              swapped.push(instruction)
                              stepIndex += 1
                          } else {
                              stepIndex += instruction.argument
                              // console.log('not swapped',instruction)
                          }
                          break;
                      case 'nop':
                          if(!didSwap && !swapped.some(s => s.command === cmd && s.index === index)) {
                              // swap with jmp, do jump
                              // debugger
                              // console.log('swapped',instruction)
                              didSwap = true
                              swapped.push(instruction)
                              stepIndex += instruction.argument
                          } else {
                              stepIndex += 1
                              // console.log('not swapped',instruction)
                          }
                          break;
                      default:
                        stepIndex += 1
                          break;
                  }
                  // debugger
                  setTimeout(() => processStep(stepIndex), 1)
              } else {
                console.error('invalid instructions at index', index)
              }
          } else {
              //console.warn('looped, trying again', accumulator, swapped.length, swapped.slice(-1)[0])
              accumulator = 0
              stepIndex = 0
              didSwap = false
              stepsCompleted = []
              // debugger
              processStep(stepIndex)
          }
        }
    } else {
      console.error('total accumulator:', accumulator, 'index:', index)
    }
}
 
processStep(stepIndex)

Lots of changes. Read through it. In the middle, you’ll see in the case for jmp and nop the code to handle the switch. I created a new array to store which one I switched last, so we can switch the jmp or nop and, run the entire process and if it loops, clear it all, and switch the next one.

Once it errors, it should only error once the provided index exceeds the array, which implies it finished, we log out the accumulator, the answer.

Note the little setTimeout? I was getting a call stack size exceeded, as seen here:

I just had to slow the code down, just a hair, like 1 millisecond. That fixed that issue nicely.

How did it go for you?

Whoo, what a doosey, but a fun challenge for sure! I hope you tried it yourself! How did you find the answer on your own? How did you do it? Anything stump you? I’d love to hear how you did! Please comment below! I have also loaded up just the challenge and code from this and my other days on github, you can follow along there too: pretty Git pages or the code in the repo.