Advent of Code 2020 Day 10 - Solution + Tutorial (TypeScript)

published
All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.


Prerequisites

I assume you've put your puzzle input into an array called lines where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const lines = [
  "39",
  "3",
  "77",
  "85",
  "103",];

Solution

Preface

Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.

Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.

I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post: 14 Awesome JavaScript Array Tips You Should Know About

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 10: Adapter Array

Part 1

For part 1, we have to make sure the joltages are numbers and sorted in ascending order. Then, we also have to add the joltage from our built-in adapter. After that, we want to find the chain of adapters connecting the charging outlet to our device's built-in adapter. Slowly increasing the rating and trying if any adapter fits gives us the count of 1-jolt- and 3-jolt-differences.

Here's the full solution:

// Convert input to numbers and sort in ascending order.
const joltages = lines.map(Number).sort((a, b) => a - b);

// Add our device's built-in adapter.
const builtInJoltage = Math.max(...joltages) + 3;
joltages.push(builtInJoltage);

// Initialize counters for the differences.
let oneJolt = 0;
let threeJolt = 0;

// Slowly increase rating and see if an adapter fits.
let rating = 0;
while (rating < builtInJoltage) {
  if (joltages.includes(rating + 1)) {
    oneJolt++;
    rating++;
    continue;
  }

  if (joltages.includes(rating + 2)) {
    rating += 2;
    continue;
  }

  if (joltages.includes(rating + 3)) {
    threeJolt++;
    rating += 3;
  }
}

// Return product of 1-jolt- and 3-jolt-differences.
return oneJolt * threeJolt;

Part 2

Again, for part 2, we have to make sure the joltages are numbers and sorted in ascending order. Then, like in part 1, we don't forget to add the joltage from your built-in adapter. This time, we'll have to find the total number of distinct ways we can arrange our adapters. For that we can use a dynamic programming approach. We'll break down our problem into smaller subproblems. We calculate the distinct ways for an ever-increasing chain until we've reached the end.

Here's the full solution:

// Convert input to numbers and sort in ascending order.
const joltages = lines.map(Number).sort((a, b) => a - b);

// Add our device's built-in adapter.
const builtInJoltage = Math.max(...joltages) + 3;
joltages.push(builtInJoltage);

// Prepare a map for a dynamic programming approach.
// Basically, we'll break down our problem into subproblems.
const sol = new Map<number, number>();
sol.set(0, 1);

// We'll use this to check for all differences.
const differences = [1, 2, 3];

// Check each joltage.
joltages.forEach((joltage) => {
  sol.set(joltage, 0);

  // Try with each possible jolt difference.
  // Also, add our precomputed value to find the distinct number of ways until here.
  differences.forEach((difference) => {
    if (sol.has(joltage - difference)) {
      sol.set(joltage, sol.get(joltage)! + sol.get(joltage - difference)!);
    }
  });
});

// Our total number of distinct ways is in the map's value for the maximum joltage.
return sol.get(Math.max(...joltages))!;

Conclusion

Today's puzzle got a bit more complicated. Either you'll use a recursive approach our you are using a dynamic programming approach. Both ways are valid.

Thanks a lot for reading this post. Please consider sharing it with your friends and colleagues. See you tomorrow!


If you like my content and you want to see more, please follow me on Twitter!
Questions, feedback or just wanna chat? Come and join my Discord!

You May Also Be Interested in the Following Posts

All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.