DEV Community

loading...

[Advent of Code 2020] Day 7 Step-by-Step Tutorial (TypeScript)

kais_blog profile image Kai Originally published at kais.blog Updated on ・8 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

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!

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.",
  
];
Enter fullscreen mode Exit fullscreen mode

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."
Enter fullscreen mode Exit fullscreen mode

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."
Enter fullscreen mode Exit fullscreen mode

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/;
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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"]
Enter fullscreen mode Exit fullscreen mode

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,
    
  },
  
}
Enter fullscreen mode Exit fullscreen mode

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>>;
Enter fullscreen mode Exit fullscreen mode

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

const bags: Bags = {};
Enter fullscreen mode Exit fullscreen mode

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);
  }
});
Enter fullscreen mode Exit fullscreen mode

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,
    
  },
  
}
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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.
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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);
});
Enter fullscreen mode Exit fullscreen mode

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);
  });
}
Enter fullscreen mode Exit fullscreen mode

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>>;
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode
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);
  });
}
Enter fullscreen mode Exit fullscreen mode

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>>;
Enter fullscreen mode Exit fullscreen mode
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);
  }
});
Enter fullscreen mode Exit fullscreen mode

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`.
}
Enter fullscreen mode Exit fullscreen mode

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

getBagCount(bags, "shiny gold");
Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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,
    
  },
  
}
Enter fullscreen mode Exit fullscreen mode

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;
});
Enter fullscreen mode Exit fullscreen mode

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>>;
Enter fullscreen mode Exit fullscreen mode
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");
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

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!

This post was originally published at kais.blog.

Discussion (0)

pic
Editor guide