Advent of Code 2020 Day 7 - 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 = [
  "shiny olive bags contain 2 dull blue bags.",
  "pale violet bags contain 1 light purple bag, 1 pale tomato bag, 4 plaid aqua bags, 4 light magenta bags.",
  "dotted white bags contain 3 bright purple bags, 4 dull orange bags, 2 plaid salmon bags.",];

Solution

Puzzle

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

Day 7: Handy Haversacks

Part 1

The puzzle description sounds like Bagception. We have to find all bags that can contain shiny gold bags. Either direct or indirect. Well, first we'll have to parse the input somehow.

Let's look at some sample input again:

"shiny gold bags contain 4 drab blue bags, 4 posh purple bags, 2 drab silver bags, 4 wavy turquoise bags."

We can extract some information from this. We get to know the bag type and its contents:

//   type                     contents            contents               contents              contents
"[shiny gold] bags contain [4 drab blue] bags, [4 posh purple] bags, [2 drab silver] bags, [4 wavy turquoise] bags."

It's always a good thing to look at the input first. That's how we know what we can learn from it and how to extract it. If we want to extract segments of a string, we usually can use a regular expression.

First, let's get the bag type for each line:

const regex1 = /^([a-z]+ [a-z]+) bags/;

That should work. We extract the two words from the start of each line. From our example above we'd get "shiny gold". Nice. Now, how do we extract information about the bag's contents?

Well, all contents are described by the same pattern. The information starts with a number followed by two words and ends with bag or bags. Let's write a RegExp literal to extract this.

const regex2 = /(\d) ([a-z]+ [a-z]+) bags?/g;

Good! From our example above, we can now extract the following information:

["shiny gold"],
["4", "drab blue"], ["4", "posh purple"], ["2", "drab silver"], ["4", "wavy turquoise"]

This information can be used to populate a dictionary. Then, we can always look up the information for each bag type. Basically, what we want is a structure like this:

// type definition
type Bags = Record<string, Record<string, number>>;

// looks like this
{
  "shiny gold": {
    "drab blue": 4,
    "posh purple": 4, 
    "drab silver": 2, 
    "wavy turquoise": 4
  },
  "dotted white": {
    "bright purple": 3,},}

Using our regexes and iterating over all lines, we can create this. Let's go:

We'll reuse our newly defined type several times. Create the following type definition:

type Bags = Record<string, Record<string, number>>;

Also, let's initialize a variable to hold our bag dictionary:

const bags: Bags = {};

Now, we want to populate this dictionary. Therefore, let's iterate over each line and use our regexes. I'll annotate the following code to make it more comprehensible:

// The regexes we've discussed before.
const regex1 = /^([a-z]+ [a-z]+) bags/;
const regex2 = /(\d) ([a-z]+ [a-z]+) bags?/g;

lines.forEach((line) => {
  // Use our first regex to extract the bag type.
  const match1 = regex1.exec(line);

  if (!match1) {
    // Should never happen.
    throw new Error();
  }

  // Get the type from the regex result.
  const type = match1[1];
  
  // Prepare an object to hold our bag contents information.
  const contents: Record<string, number> = {};

  // Add the bag to the dictionary.
  bags[type] = contents;

  // Now, we have to populate the bag's contents.
  // We'll use our second regex and reuse it as often as possible.
  // Each match is then added to the bag's contents.
  let match2 = regex2.exec(line);

  while (match2) {
    // Convert the count to a number. Easier to work with.
    const count = parseInt(match2[1]);
    const type = match2[2];

    // Add the bag type and count to the outer bag's contents.
    contents[type] = count;

    // Reuse the regex to match until there is nothing to match left.
    match2 = regex2.exec(line);
  }
});

Phew, that was quite a bit of code. I hope my comments made it a bit clearer. Now, our bags resemble something like this:

{
  "shiny gold": {
    "drab blue": 4,
    "posh purple": 4, 
    "drab silver": 2, 
    "wavy turquoise": 4
  },
  "dotted white": {
    "bright purple": 3,},}

Awesome! Parsing the lines into a usable format took some time. However, now we are ready to find all bags that either directly or indirectly contain shiny gold bags.

So, the thing is, we have this bags object where every key is a bag type. We just have to filter out every key that cannot contain shiny gold bags. We will find our solution with something like this:

Object.keys(bags).filter((type) => {
  // TODO: Return false here if the bag `type` cannot contain shiny gold bags.
}).length;

Let's think about what we are going to do. For each bag type we have to check, if the type contains "shiny gold" bags. If it does contain them, we can keep the bag type. If not, we still have to check the contents. So for each bag type in the outer bag's contents, we also have to check whether it contains "shiny gold" bags. Therefore, we have to check if this bag type contains ...

WAIT! This sounds like we have to do it again and again and again. For each child and for each grandchild and so on. That tells us, that we can use a recursive function. Let's define a function that returns a boolean, whether a certain bag type can contain shiny gold bags.

function containsShinyGoldBags(bags: Bags, type: string): boolean {
  // TODO: Somehow determine if `type` contains `"shiny gold"` bags.
}

Okay, we pass bags and type as parameters, so we can lookup the information about different bag types.

First, let's check if the passed type already contains "shiny gold" bags. Then, we can immediately return true.

const contents = bags[type];

if (contents["shiny gold"]) {
  return true;
}

Easy. However, for bags that do not contain shiny gold bags directly, we have to check their contents.

return Object.keys(contents).some((type) => {
  return containsShinyGoldBags(bags, type);
});

Here, we use the keys of contents. This way, we get all bag types in the outer bag. Then, we just have to check if ANY of the bags contains shiny gold bags. Therefore, we'll recursively call our defined function. So each bag checks its contents, checks the contents of the inner bags, and so on.

The full function looks like this:

function containsShinyGoldBags(bags: Bags, type: string): boolean {
  const contents = bags[type];

  if (contents["shiny gold"]) {
    return true;
  }

  return Object.keys(contents).some((type) => {
    return containsShinyGoldBags(bags, type);
  });
}

Perfect! We now just have to combine everything we've done so far. Then, we have our solution:

type Bags = Record<string, Record<string, number>>;
const bags: Bags = {};

const regex1 = /^([a-z]+ [a-z]+) bags/;
const regex2 = /(\d) ([a-z]+ [a-z]+) bags?/g;

lines.forEach((line) => {
  const match1 = regex1.exec(line);

  if (!match1) {
    throw new Error();
  }

  const type = match1[1];
  const contents: Record<string, number> = {};

  bags[type] = contents;

  let match2 = regex2.exec(line);

  while (match2) {
    const count = parseInt(match2[1]);
    const type = match2[2];

    contents[type] = count;

    match2 = regex2.exec(line);
  }
});

return Object.keys(bags).filter((type) => {
  return containsShinyGoldBags(bags, type);
}).length;
function containsShinyGoldBags(bags: Bags, type: string): boolean {
  const contents = bags[type];

  if (contents["shiny gold"]) {
    return true;
  }

  return Object.keys(contents).some((type) => {
    return containsShinyGoldBags(bags, type);
  });
}

Part 2

Phew, part 1 took some time to implement. In part 2 we'll have to check our bags again. This time, we want to find out, how many bags a shiny gold bag contains.

Like in part 1, we'll create our dictionary to lookup the bag information.

type Bags = Record<string, Record<string, number>>;
const regex1 = /^([a-z]+ [a-z]+) bags/;
const regex2 = /(\d) ([a-z]+ [a-z]+) bags?/g;

lines.forEach((line) => {
  const match1 = regex1.exec(line);

  if (!match1) {
    throw new Error();
  }

  const type = match1[1];
  const contents: Record<string, number> = {};

  bags[type] = contents;

  let match2 = regex2.exec(line);

  while (match2) {
    const count = parseInt(match2[1]);
    const type = match2[2];

    contents[type] = count;

    match2 = regex2.exec(line);
  }
});

Nothing has changed here. You'll find the explanation in part 1, if you need it.

However, we don't want to find all bags that contain shiny gold bags now. We have to count the bags inside a shiny gold bag and then count the bags inside those bags and then count the bags inside those and then...

Wow! We can use a recursive function again. Let's define a new function:

function getBagCount(bags: Bags, type: string): number {
  // TODO: Somehow get the count of bags inside the `type`.
}

If we use this function, we should have our solution:

getBagCount(bags, "shiny gold");

Perfect! We are done. See you tomorrow!

Sorry, what did you just think? There's something I forgot? Oh...

Joking aside, we still need the implementation for getBagCount.

So, let's initialize a variable to count up the total number of bags.

let total = 0;

// TODO: Here we are missing something.

return total;

Okay, let's look at our bag dictionary again:

{
  "shiny gold": {
    "drab blue": 4,
    "posh purple": 4, 
    "drab silver": 2, 
    "wavy turquoise": 4
  },
  "dotted white": {
    "bright purple": 3,},}

For each bag we know the inner bags. We also know, how many of those are inside any bag. Let's use this information to get the total count:

const contents = bags[type];
Object.entries(contents).forEach(([type, count]) => {
  total += count;
  total += getBagCount(bags, type) * count;
});

First, we get the contents for the bag type from our dictionary. Then, we'll use the Object#entries method to iterate through the contents. Using array destructuring we can get the type and count from each of the inner bags. Now, we have to add their count to the total.

However, for each inner bag we also have to add their inner bags and so on. This count per inner bag is then multiplied by their count. Why? Well, if a bag contains 5 "pale orange" bags, and they contain 3 "shiny olive" bags each... you'll have 15 bags total.

Adding all together, we have our total count. Using "shiny gold" as type parameter for this function returns us the total bag count. Nice!

Here's the full solution:

type Bags = Record<string, Record<string, number>>;
const bags: Bags = {};

const regex1 = /^([a-z]+ [a-z]+) bags/;
const regex2 = /(\d) ([a-z]+ [a-z]+) bags?/g;

lines.forEach((line) => {
  const match1 = regex1.exec(line);

  if (!match1) {
    throw new Error();
  }

  const type = match1[1];
  const contents: Record<string, number> = {};

  bags[type] = contents;

  let match2 = regex2.exec(line);

  while (match2) {
    const count = parseInt(match2[1]);
    const type = match2[2];

    contents[type] = count;

    match2 = regex2.exec(line);
  }
});

return getBagCount(bags, "shiny gold");
function getBagCount(bags: Bags, type: string): number {
  let total = 0;

  const contents = bags[type];
  Object.entries(contents).forEach(([type, count]) => {
    total += count;
    total += getBagCount(bags, type) * count;
  });

  return total;
}

Conclusion

So, this is the first time we've used recursive functions to solve the puzzle. Probably, we'll also need them for future puzzles. We'll see.

Writing this tutorial took quite some time. I'm not sure whether I can keep up with publishing these daily. I'll try my best!

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!
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.