Advent of Code, Day 9

Day 9 of Advent of Code is here! Getting tired yet? I am, not of doing this, just of getting up extra early to work on these before work. It’s worth it ;) 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!

No more dev toolbar

I’ve moved from dev console to using NodeJS for my challenges. This will providing us with more capabilities to identify issues in our code much faster. Learn more about the move here. As a result, my input and scripts can be found on github. This one was simpler than day 7 and 8, and which makes me think I should’ve gone to Node much sooner ;)

Day 9: Encoding Error

Part I

“The data appears to be encrypted with the eXchange-Masking Addition System (XMAS) which, conveniently for you, is an old cypher with an important weakness.

XMAS starts by transmitting a preamble of 25 numbers. After that, each number you receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will have different values, and there might be more than one such pair. What is the first number that does not have this property?” ref

Easy peasy, if you’ve been following along, this should be a rather simply looper. Here’s the data (my full data set is now in github!)

Before we loop, let’s get our data

const fs = require('fs');
const nums = fs.readFileSync('./input.txt', 'utf-8').trim().split('\n').map((l) => Number(l));

This has changed some, since we’re in NodeJS now. Here we grab the inputs file and then basically do the same thing we were before. I added a .map() which will let us do a little more ETL on the data, by converting them all to numbers.

If you wanted to run this in dev console, you can use the similar method we used to get data in previous days.

Now we have an array of numbers, let’s loop and find the culprit

const preamble = 25
let index = preamble;
let doit = true

do {
  const checkList = nums.slice(index - preamble, index)
  const thisNum = nums[index]
  let invalidNumber = true
  
  checkList.forEach((c) => {
    for (let checkIndex = 0; checkIndex < checkList.length; checkIndex += 1) {
      if (c + checkList[checkIndex] === thisNum) {
        invalidNumber = false
        checkIndex = checkList.length
      }
    }
  })

  if(invalidNumber){
    doit = false
    console.warn(thisNum, ' does not follow the rule')
  } else {
    console.log(thisNum, 'is acceptable')
  }
  index += 1
} while (doit)

Here’s what we got:

• Awww…. no regex this time :(
• If you noticed in the story, the fun starts after the 25th number, so the preamble gives us that buffer
• We’re doing a do while, which will run at least once, and while doit is true
• We are slicing out the numbers we’re supposed to check, the 25 before the current index
• Then we loop through those numbers in the forEach()
• As we handle each number, we add the number to another number from the list (the second loop in the for loop)
• If any of these two add up to the number, then it’s good and we can move to the next number
• If none of the 25 numbers before a number can’t add to the number when adding 2, then it’s invalid, not following the rule, and that’s the answer.

Part 2 needs the output from Part 1…

Part II

“The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1. To find the encryption weakness, add together the smallest and largest number in this contiguous range.” ref

Let’s get crackin’. We will start with the same code from part 1, except I add a variable to store the invalid number, I lovingly named it bustedNumber

...... part 1 ......
  if(invalidNumber){
    doit = false
    console.warn(thisNum, 'does not follow the rule')
    bustedNumber = thisNum // *** new variable! *** 
  }
  index += 1
} while (doit)

// *** START PART 2 ***
let min = 0
let max = 0
let roundCnt = 0
nums.forEach((n, nindex) => {
  roundCnt += 1
  let keepAdding = true
  let sum = n
  let addIndex = nindex + 1
  min = n
  max = 0

  do {
    if(addIndex < nums.length) {
      const addThis = nums[addIndex]
      sum += addThis

      if(addThis < min) min = addThis
      if(addThis > max) max = addThis

      if(sum === bustedNumber) {
        keepAdding = false
        console.warn(min + max, 'is the encryption weakness')
      }
      if(sum > bustedNumber) {
        keepAdding = false
      }
      addIndex += 1
    } else {
      keepAdding = false
    }
  } while(keepAdding)
})

console.log('finished in' , roundCnt, 'rounds')

I tell ya, so much looping can get you dizzy…

• We kick it off by looping through all the numbers from the input (nums is defined in Part I)
• I have a few new variables
  • roundCnt is just a counter to see how many rows this runs through, just curios as I was debugging
  • keepAdding is a breaker variable, if we find the bustedNumber, or if sum exceeds the bustedNumber then break the loop and go to the next number
  • min and max are needed to store the lowest number in the series, and the highest. These two are added together to get our answer for Part 2
  • sum is the sum of the numbers we’re iterating through
• Now let’s loop in a do while again. As we go through each set number, we’re getting the next number, and the next number, and so on, until we add to (or exceed) the bustedNumber.
• As we go, I’m setting the min and max if the current number fits either.
• Finally, once we get the sum to match busterNumber we have the answer!!

How did it go for you?

I hope you tried it yourself! Looping can be fun, and very tricky, and when there’s this many loops, one can get lost. Don’t be afraid to write it out and mark how the loop is working on paper.

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.