Advent of Code, Day 10, check back in 629 days

Day 10 of Advent of Code is here! 629 days? See Part 2….

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 did here, see Part II. 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 made going to node worth it :D

Day 10: Adapter Array

Part I

“You’ll need to plug it in. There’s only one problem: the charging outlet near your seat produces the wrong number of jolts. Always prepared, you make a list of all of the joltage adapters in your bag.

Each of your joltage adapters is rated for a specific output joltage (your puzzle input). Any given adapter can take an input 1, 2, or 3 jolts lower than its rating and still produce its rated output joltage.

In addition, your device has a built-in joltage adapter rated for 3 jolts higher than the highest-rated adapter in your bag. (If your adapter list were 3, 9, and 6, your device’s built-in adapter would be rated for 12 jolts.) What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?” ref

Here’s a sampling of the data

Before we loop, let’s get pull this data in

const fs = require('fs');
const adapters = fs.readFileSync('./input.txt', 'utf-8').trim().split('\n').map((l) => Number(l)).sort((a,b) => a > b ? 1 : -1);

adapters.push(adapters[adapters.length-1]+3)

Right off the bat, we’re doing a little transformation of the data. After we get and split it, we’re converting the strings to numbers and then sorting it so the smallest is first. Then we add 1 more. The challenge was tricky, if you didn’t catch that, then you won’t find your answer.

Once we have the data, let’s get looping

let currentJolt = 0
let adapterCount = 0
let oneJoltDiff = 0
let threeJoltDiff = 0

while(adapterCount < adapters.length) {
  const compatibleAdapters = adapters.filter(a => a <= currentJolt+3 && a > currentJolt)
  const nextAdapter = compatibleAdapters[0]
  if(nextAdapter - currentJolt === 1) oneJoltDiff += 1
  if(nextAdapter - currentJolt === 3) threeJoltDiff += 1
  currentJolt = nextAdapter
  adapterCount += 1
}

console.warn(oneJoltDiff * threeJoltDiff, 'WINNER WINNER')

Here’s what we got:

• Nope, no regex this time :(
• This time, we’re using a while, instead of yesterday’s do while. Why? Why not :D
• We grab all adapters that are greater than the current jolt, and less than or equal to 3 over.
• We grab the first one from that array (remember we sorted them when we got the data)
• Then we check what the difference is and increment the appropriate variable
• Finally, we multiple the two to find our winner!

Incredibly easy, especially in comparison to part II…

Part II

“To completely determine whether you have enough adapters, you’ll need to figure out how many different ways they can be arranged. Every arrangement needs to connect the charging outlet to your device. The previous rules about when adapters can successfully connect still apply.What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?“

DO NOT RUN THIS SCRIPT :D

This script runs GREAT on a few dozen, or even several dozen items. When I run this against my entire dataset, it takes FOR-EVER! I ran it against their sample data and I got the same answer, so I know it works.

const fs = require('fs');

const adapters = fs.readFileSync('./input.txt', 'utf-8').trim().split('\n').map((l) => Number(l)).sort((a,b) => a > b ? 1 : -1);

let iterationCount = 1

console.log(new Date())
var getAdapters = (jolt) => {
  const compatibleAdapters = adapters.filter(a => a <= jolt+3 && a > jolt)
  compatibleAdapters.forEach((ca, index) => {
    if(index !== 0) iterationCount += 1
    getAdapters(ca)
  })
  if(iterationCount % 100000000 === 0) console.log(iterationCount, 'found', new Date())
}

getAdapters(0)

console.log(new Date())
console.log(iterationCount, 'total iterations')

It took so long to run, that I threw some date/time checks in there to give me a feeling for how long it’ll take

Every million takes about 2 minutes to run. The correct answer (solution coming) is 453,551,299,002,368. Rough calculation tells me it’ll take 629 days to get the answer. It would be right! But I’d be through 1 more advents of code, pandemic would be over (I hope), my oldest would be out of high school, I’d be slimmer and wiser, by the time it finished.

So needed to find another way. I spent some good amount of time on it, but couldn’t figure it out. So I went to my team, and sure enough, someone figured it out. Connor, yes that Connor, had the answer. He’s apparently a genius. I reversed engineered some of what he did to make it my own. See his original in his github.

There’s the first loop that builds some counts

let iterationCount = 0
let lastJolt = 0
const consecutiveJolts = {}

console.log(new Date())
adapters.forEach((jolt, index) => {
  const diffJolt = jolt - lastJolt
  if(diffJolt === 1) {
    iterationCount += 1
  } else {
    if(!consecutiveJolts[iterationCount]) {
      consecutiveJolts[iterationCount] = 1
    } else {
      consecutiveJolts[iterationCount] += 1
    }
    iterationCount = 0
  }
  lastJolt = jolt

  if(index === (adapters.length - 1)) { // also close out the last row
    if(consecutiveJolts[iterationCount] === undefined) {
      consecutiveJolts[iterationCount] = 1
    } else {
      consecutiveJolts[iterationCount] ++;
    }
}
})

This first part is rather straight forward. We loop through the numbers, and load a counter into a new object called consecutiveJolts. This makes an object with a count of each consecutive grouping (this took me a little to figure it out). If there’s a sequence, like 1, 2, 3, 5, 6, 8, then in 1,2,3 is one consecutive sequence of three, 5,6 is one consecutive sequence of two, and so on.

Then here’s the genius, this function, I have no idea what it actually does and why it works. I’ve debugged it, and stepped through it, seeing the values. I can see what it does but I just don’t know “why” it works. It’s calculating a tribonacci sequence. If fibonacci adds the previous two numbers together, tribonacci adds the previous three. I get it, but don’t get it.

const getPossibleCombos = (count) => {
  let response = [];
  let lastThreeResponses = [0, 0, 0];
  const minValue = 1;
  for(let i = 0; i <= count; i++) {
      let possible = lastThreeResponses.reduce((a, b) => a + b, 0);
      lastThreeResponses.shift();
      if(possible < minValue) {
          possible = minValue;
      }
      lastThreeResponses.push(possible);
      response[i] = possible;
  }
  return response;
}

Figure it out? I need to buy Connor a drink and have him walk me through it, rather, owe him one and walk through it remotely. ;) If I learn anything, I’ll update this post.

Finally, we access the above and finish it off with

var joltGroupCnt = Object.keys(consecutiveJolts).length
let numPossibilities = getPossibleCombos(joltGroupCnt);
let total = 1
for(let i = 0; i < joltGroupCnt; i+=1) {
  total = total * (numPossibilities[i] ** consecutiveJolts[i])
}

console.log(total)
console.log(new Date())

We grab the magical numbers the tribonacci outputted, then we loop one last time and multiply the number by the tribonacci to the power ( 2^4 would be like 2 * 2 * 2 * 2, or 2 ** 4 of the number).

How did it go for you?

This was a tricky puzzle, a few people have figured it out. The rest of us, being good developers, referenced their code ;). I hope to understand it, it’s really fascinating. Check out the adventofcode subreddit, there’s some great solutions there with explanations.

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.