07.md

Day 05

Part 1

Count how many bag colors can eventually contain at least one shiny gold bag.

Let's start by converting the input string into an object. We are not interested in the amounts in Part 1, so we can leave them out from the resulting object:

const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`

const ruleReducer = (rules, rule) => {
  const [color, contents] = rule.split(' bags contain ')
  rules[color] = contents.split(', ').reduce(contentsReducer, [])
  return rules
}

const contentsReducer = (contents, bag) => {
  const [, amount, color] = bag.match(/(\d+) ([a-z ]+) bags?/) || []
  if (color) contents.push(color)
  return contents
}

const rules = input.split('\n').reduce(ruleReducer, {})
// => {
//      'light red':    ['bright white', 'muted yellow'],
//      'dark orange':  ['bright white', 'muted yellow'],
//      'bright white': ['shiny gold'],
//      'muted yellow': ['shiny gold', 'faded blue'],
//      'shiny gold':   ['dark olive', 'vibrant plum'],
//      'dark olive':   ['faded blue', 'dotted black'],
//      'vibrant plum': ['faded blue', 'dotted black'],
//      'faded blue':   [],
//      'dotted black': [],
//    }

Then we can use recursion to find the possible parents of shiny gold bags:

const findParents = (targetColor) =>
  Object.entries(rules)
    .filter(([color, contents]) => contents.includes(targetColor))
    .flatMap(([color]) => [color, ...findParents(color)])
    .reduce((set, color) => set.add(color), new Set())

const parents = findParents('shiny gold')
console.log(parents.size)

Try it out on flems.io

Part 2

Count how many individual bags are required inside a single shiny gold bag.

Now we are interested in the amounts, so let's modify the reducers from Part 1 a bit:

 const ruleReducer = (rules, rule) => {
   const [color, contents] = rule.split(' bags contain ')
-  rules[color] = contents.split(', ').reduce(contentsReducer, [])
+  rules[color] = contents.split(', ').reduce(contentsReducer, {})
   return rules
 }

 const contentsReducer = (contents, bag) => {
   const [, amount, color] = bag.match(/(\d+) ([a-z ]+) bags?/) || []
-  if (color) contents.push(color)
+  if (color && amount) contents[color] = +amount
   return contents
 }

 const rules = input.split('\n').reduce(ruleReducer, {})
+// => {
+//      'light red':    {'bright white': 1, 'muted yellow': 2},
+//      'dark orange':  {'bright white': 3, 'muted yellow': 4},
+//      'bright white': {'shiny gold': 1},
+//      'muted yellow': {'shiny gold': 2, 'faded blue': 9},
+//      'shiny gold':   {'dark olive': 1, 'vibrant plum': 2},
+//      'dark olive':   {'faded blue': 3, 'dotted black': 4},
+//      'vibrant plum': {'faded blue': 5, 'dotted black': 6},
+//      'faded blue':   {},
+//      'dotted black': {},
+//    }

Now we can again use recursion to count the amount of children (inner bags) in a single shiny gold bag.

const countChildren = (targetColor) =>
  Object.entries(rules[targetColor]).reduce(
    (sum, [color, amount]) => sum + amount + amount * countChildren(color),
    0
  )

const result = countChildren('shiny gold')
console.log(result)

flems

What did I learn?

Nothing, but this puzzle was somewhat challenging at first because I had to think recursively.