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 12, 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 39, 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 =&gt; a <= currentJolt+3 &amp;&amp; a &gt; 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) =&gt; Number(l)).sort((a,b) =&gt; a &gt; b ? 1 : -1);

let iterationCount = 1

console.log(new Date())
var getAdapters = (jolt) =&gt; {
  const compatibleAdapters = adapters.filter(a =&gt; a <= jolt+3 &amp;&amp; a &gt; jolt)
  compatibleAdapters.forEach((ca, index) =&gt; {
    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) =&gt; {
  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) =&gt; {
  let response = [];
  let lastThreeResponses = [0, 0, 0];
  const minValue = 1;
  for(let i = 0; i <= count; i++) {
      let possible = lastThreeResponses.reduce((a, b) =&gt; 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.

10 thoughts on “Advent of Code, Day 10, check back in 629 days

Add yours

  1. My solution did not use the Tribonacci number, but I did use some dynamic programming.

    Here is the idea. I’m going to ignore the nitty details: Let N(L) be the number of ways to put the list of L adapters. Let’s take a look at the last removable adapter (we call it X) in the list. X is either removed or not removed. These two cases are disjoint and covering (covering all possibilities). If X is removed, the number of ways is N(L, with X removed). If X is not removed, then the number of ways is N(L, except the last element). Hence,

    N(L) = N(L with X removed) + N(L with the last element removed).

    At each iteration, the problem becomes smaller. Let’s talk about base cases. This happens when the length of input list equals 3, i.e. |L|=3. Then, just check the middle element. Can you remove it? If so, there are two ways, and hence N(L)=2. If not, then there is only one way, and hence N(L)=1.

    But to use dynamic programming you probably need to hash lists. Maybe something with prime numbers.

    My approach is very very similar to this one, except I didn’t really remove any elements from the list. I just marked which elements are currently not to be considered.

  2. Sorry for taking top spot on your leaderboard! I’ve finally had time to read through your blog posts. I joined your leaderboard because you had posted something on reddit and I wanted to see how I stood up against real devs. I wish I could say I was a good developer, but programming is a hobby for me and Advent of Code is like candy.

    I didn’t realize the thing about the tribonnaci sequence until well after the fact. The way I came upon a fast solution was to calculate the number of combinations in sets of consecutive numbers.

    Knowing that each adapter could only connect to a max of three other possible adapters, I converted my list simply to display number of connections for each adapter.

    You end up with a list like 1,1,3,2,1,1,2,1,3,3,2,1,1,1,2,1….

    When I looked at the output of this I noticed that the same patterns appear throughout:
    3,3,2,1
    3,2,1
    2,1

    I realized that each of these patterns have a set number of combinations that are possible, meaning each set represents a number of branching paths. Consecutive 1s could all be thrown out as there is only one path.

    3,3,2,1 has 7 possible combinations/paths
    3,2,1 has 4 possible combinations/paths
    2,1 has 2 possible combinations/paths

    I looped through this string and counted the appearance of each of these and came up with the formula 2^x * 4^y * 7^z.
    This accounts for all the possible branching paths and how they quickly multiply down the line.

    So the following sequence:
    1,1,3,2,1,1,2,1,3,3,2,1,1,1,2,1

    Would reduce down to:
    [3,2,1][2,1][3,3,2,1][2,1]

    Count the occurrences and apply the formula:
    2^2 * 4^1 * 7^1 = 112

    As an additional hint, you’re going to see more problems crop up that reach ridiculously large numbers (If you want a challenge go see 2019 Day 22). The creator of Advent of Code is not a mathematician (by his own admission), so all of these problems are solvable with “a few programming tricks”, as he once stated. All problems are also designed to finish within a maximum runtime of 15 seconds on 10 year-old hardware (assuming you have a reasonably optimal solution).

    I hope my insights were helpful and I look forward to reading more of your posts on this event!

  3. I got here all excited – someone who had figured out part 2 and written a post to explain why it worked. Oh well, I guess we’re both in the same boat :-). I’m not letting myself claim the star (yet…) until I understand why, and if I do I’ll drop you a link to my blog post! Thanks for the explanation anyway.

Leave a Reply

Powered by WordPress.com.

Up ↑

%d bloggers like this: