Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks

I'm on the computer a little later than usual, so I thought I'd get the post for tomorrow up now so I don't have to do it in the morning, since it's past midnight on the East coast anyway.

The Puzzle

Oh my gosh, today’s puzzle is a parsing, dependency graph nightmare. Maybe I'm just tired and overcomplicating things in my head, but I'm thinking that's the case. Our input is a series of lines describing how certain colors of bag (e.g. "vivid plum") can contain certain quantities of other bags (e.g. "shiny gold"). We are to decide which bags can contain our bag, the shiny gold one. Yoy.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 03:08PM 12/12/2020 PST.

Language	Count
JavaScript	4
Ruby	3
Haskell	2
Clojure	2
Python	2
Rust	1
TypeScript	1
COBOL	1
Elixir	1
C#	1
Go	1
C	1

Merry Coding!

Comments

[Benjamin Trent]

moar rust. My brain ran into so many fence post errors on this one. I should have drank more coffee before attempting.

use std::collections::HashMap;

#[derive(Debug, Hash, Eq, PartialEq)]
struct BagRule {
    num: usize,
    bag_type: String,
}

impl BagRule {
    fn contains_recur(&self, bag: &str, collection: &HashMap<String, Vec<BagRule>>) -> bool {
        if self.bag_type == bag {
            return true;
        }
        collection
            .get(&self.bag_type)
            .unwrap()
            .iter()
            .any(|br| br.contains_recur(bag, collection))
    }

    fn bag_count(&self, collection: &HashMap<String, Vec<BagRule>>, prev_count: usize) -> usize {
        let rules = collection.get(&self.bag_type).unwrap();
        if rules.is_empty() {
            prev_count
        } else {
            rules
                .iter()
                .map(|br| br.bag_count(collection, br.num * prev_count))
                .sum::<usize>()
                + prev_count
        }
    }
}

impl From<&str> for BagRule {
    fn from(s: &str) -> Self {
        match s.find(" ") {
            Some(n) => {
                let num: usize = s[0..n].parse().unwrap();
                BagRule {
                    num,
                    bag_type: String::from(s[n + 1..].trim_end_matches("s")),
                }
            }
            // no bags
            None => {
                panic!("boom")
            }
        }
    }
}

#[aoc_generator(day7)]
fn to_hashmap(input: &str) -> HashMap<String, Vec<BagRule>> {
    input
        .lines()
        .map(|i| {
            let mut splt = i.split(" contain ");
            let bag = splt.next().unwrap().trim_end_matches("s");
            let unparsed_rules = splt.next().unwrap().trim_end_matches(".");
            let rules: Vec<BagRule> = if unparsed_rules == "no other bags" {
                vec![]
            } else {
                unparsed_rules.split(", ").map(|s| s.into()).collect()
            };
            (String::from(bag), rules)
        })
        .collect()
}

#[aoc(day7, part1)]
fn how_many_shiny_gold(input: &HashMap<String, Vec<BagRule>>) -> usize {
    input
        .iter()
        .filter(|(bag, rules)| {
            if bag.as_str() == "shiny gold bag" {
                false
            } else {
                rules
                    .iter()
                    .any(|br| br.contains_recur("shiny gold bag", input))
            }
        })
        .count()
}

#[aoc(day7, part2)]
fn how_many_in_shiny_gold(input: &HashMap<String, Vec<BagRule>>) -> usize {
    let rules = input.get("shiny gold bag").unwrap();
    return rules
        .iter()
        .map(|br| br.bag_count(input, br.num))
        .sum::<usize>();
}

[Neil Gall]

Oh dear, I didn't look at the input and assumed there were just the nine colours in the example. Modelled them in an enum and wrote parsers for them all, which failed on the first line of input text. Lesson: look at the real data!

The problem is a directed acyclic graph one. I modelled the graph as a Vec of edges with the start and end nodes, which meant quite expensive searching. It only took 10 or 20 seconds to run but I knew it was a mistake. Reworked to a HashMap where the key is the start of each edge and the value is the Vec of possible end nodes.

The actual graph traversals are the bread and butter of my day job. Those were easy. I wasted a lot of time today on parsing and bad modelling.

use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;

mod parser;
use parser::*;

// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

// --- model

#[derive(Debug, Clone, Eq, Hash, PartialEq)]
struct BagColor(String, String);

impl BagColor {
    fn of(adj: &str, col: &str) -> Self {
        BagColor(String::from(adj), String::from(col))
    }
}

#[derive(Debug, Eq, PartialEq)]
struct Content {
    color: BagColor,
    count: usize
}

#[derive(Debug, Eq, PartialEq)]
struct ContainsRule {
    container: BagColor,
    contents: Vec<Content>
}

#[derive(Debug)]
struct RuleSet {
    rules: HashMap<BagColor, Vec<Content>>
}

fn parse_rule<'a>() -> impl Parser<'a, ContainsRule> {
    fn bag_color<'b>() -> impl Parser<'b, BagColor> {
        let adjective = one_or_more(letter).map(|ls| ls.into_iter().collect());
        let color = one_or_more(letter).map(|ls| ls.into_iter().collect());

        pair(first(adjective, whitespace), color).map(|(a, c)| BagColor(a, c))
    }

    fn container<'b>() -> impl Parser<'b, BagColor> {
        first(bag_color(), string(" bags contain "))
    }

    let bag_or_bags = string(" bags, ").or(string(" bag, ")).or(string(" bags.")).or(string(" bag."));
    let contained = pair(first(integer, whitespace), first(bag_color(), bag_or_bags));

    let contents_rule = pair(container(), one_or_more(contained)).map(|(color, contents)| 
        ContainsRule {
            container: color.clone(),
            contents: contents.iter().map(|(n, c)| Content {
                color: c.clone(),
                count: *n as usize
            }).collect()
        }
    );

    let no_contents_rule = first(container(), string("no other bags.")).map(|color| 
        ContainsRule {
            container: color,
            contents: vec![]
        }
    );

    contents_rule.or(no_contents_rule)
}

fn parse_input(input: &str) -> ParseResult<RuleSet> {
    let rule_set = one_or_more(first(parse_rule(), whitespace));

    rule_set.parse(input).map(|(rest, rules)| {
        let rule_set = RuleSet { 
            rules: rules.into_iter().map(|r| (r.container, r.contents)).collect()
        };
        (rest, rule_set)
    })
}

impl RuleSet {
    fn can_contain(&self, from: &BagColor, to: &BagColor) -> bool {
        self.rules.get(from)
            .map(|contents| 
                contents.iter().any(|c| &c.color == to))
            .unwrap_or(false)
    }

    fn can_contain_indirectly(&self, from: &BagColor, to: &BagColor) -> bool {
        self.can_contain(from, to) 
            || self.rules.get(from).map(|contents|
                contents.iter().any(|c| self.can_contain_indirectly(&c.color, to)))
                .unwrap_or(false)
    }

    fn number_of_contained_bags(&self, from: &BagColor) -> usize {
        self.rules.get(from)
            .map(|contents| contents.iter()
                .map(|c| c.count * (1 + self.number_of_contained_bags(&c.color)))
                .sum())
            .unwrap_or(0)
    }

    // --- problems 

    fn part1(&self) -> usize {
        self.rules.keys()
            .filter(|color| self.can_contain_indirectly(&color, &BagColor::of("shiny", "gold")))
            .count()
    }

    fn part2(&self) -> usize {
        self.number_of_contained_bags(&BagColor::of("shiny", "gold"))
    }
}

fn main() {
    let input = read_file("./input.txt").unwrap();
    let rules: RuleSet = parse_input(&input).unwrap().1;

    println!("part1 {}", rules.part1());
    println!("part2 {}", rules.part2());
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_with_single_clause() {
        assert_eq!(
            parse_rule().parse("light red bags contain 1 bright white bag."),
            Ok(("", ContainsRule {
                container: BagColor::of("light", "red"),
                contents: vec![
                    Content { color: BagColor::of("bright", "white"), count: 1 }
                ]
            }))
        );
    }

    #[test]
    fn test_parse_with_two_clauses() {
        assert_eq!(
            parse_rule().parse("light red bags contain 1 bright white bag, 2 muted yellow bags."),
            Ok(("", ContainsRule { 
                container: BagColor::of("light", "red"),
                contents: vec![
                    Content { color: BagColor::of("bright", "white"), count: 1 },
                    Content { color: BagColor::of("muted", "yellow"), count: 2 }
                ]
            }))
        );
    }

    #[test]
    fn test_parse_with_many_clauses() {
        assert_eq!(
            parse_rule().parse("dotted silver bags contain 2 dotted orange bags, 3 bright fuchsia bags, 5 bright tomato bags, 3 faded turquoise bags."),
            Ok(("", ContainsRule {
                container: BagColor::of("dotted", "silver"),
                contents: vec![
                    Content { color: BagColor::of("dotted", "orange"), count: 2 },
                    Content { color: BagColor::of("bright", "fuchsia"), count: 3 },
                    Content { color: BagColor::of("bright", "tomato"), count: 5 },
                    Content { color: BagColor::of("faded", "turquoise"), count: 3 }
                ]
            }))
        );
    }

    #[test]
    fn test_parse_with_no_contents() {
        assert_eq!(
            parse_rule().parse("faded blue bags contain no other bags."),
            Ok(("", ContainsRule {
                container: BagColor::of("faded", "blue"),
                contents: vec![]
            }))
        );
    }

    #[test]
    fn test_parse_records_separated_by_lines() {
        let p = one_or_more(first(letter, whitespace));
        assert_eq!(p.parse("a\nb\nc\n"), Ok(("", vec!['a', 'b', 'c'])));
    }
}

[Christopher Kruse]

I went way overboard with my Rust solution.

I found a graph library to model the actual structure of the nested bags. Spent more time trying to reason out the graph structure and figure out what I was doing, than I did actually getting the problem solved.

A fun exercise, to be sure, but not the fastest way to row the boat.

As always, available on Github.

use aoc_runner_derive::{aoc, aoc_generator};
use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::visit::Dfs;
use petgraph::Direction;
use regex::Regex;

#[aoc_generator(day7)]
fn parse_input_day7(input: &str) -> DiGraph<String, usize> {
    let id_re = Regex::new("^(?P<color>\\D+) bags contain").unwrap();
    let rule_re = Regex::new("(?P<count>\\d+) (?P<color>\\D+) bag[s]?").unwrap();
    let mut bag_graph = DiGraph::<String, usize>::new();

    let rules: Vec<&str> = input.lines().collect();

    // Create graph nodes.
    let nodes: Vec<NodeIndex> = rules
        .iter()
        .map(|line| {
            bag_graph.add_node(String::from(
                id_re
                    .captures(line)
                    .unwrap()
                    .name("color")
                    .unwrap()
                    .as_str(),
            ))
        })
        .collect();

    // Connect graph nodes
    nodes.iter().for_each(|node| {
        let rule_str = rules.iter().find(|rule| {
            rule.contains(&format!(
                "{} bags contain",
                bag_graph.node_weight(*node).unwrap()
            ))
        });
        rule_re.captures_iter(rule_str.unwrap()).for_each(|mat| {
            let target_str = mat.name("color").unwrap().as_str();
            let edge_weight = str::parse(mat.name("count").unwrap().as_str())
                .expect("Couldn't build number from count!");
            let target_node = nodes
                .iter()
                .find(|n| bag_graph.node_weight(**n).unwrap() == target_str)
                .unwrap();
            bag_graph.add_edge(*node, *target_node, edge_weight);
        })
    });
    bag_graph
}

#[aoc(day7, part1)]
fn contains_bag(input: &DiGraph<String, usize>) -> usize {
    let mut flip = input.clone();
    flip.reverse();
    let shiny_gold_index = flip
        .node_indices()
        .find(|i| flip[*i] == "shiny gold")
        .unwrap();
    let mut count = 0;
    let mut dfs = Dfs::new(&flip, shiny_gold_index);
    while let Some(node) = dfs.next(&flip) {
        count += 1;
    }
    count - 1
}

#[aoc(day7, part2)]
fn total_bags(input: &DiGraph<String, usize>) -> usize {
    let shiny_gold_index = input
        .node_indices()
        .find(|i| input[*i] == "shiny gold")
        .unwrap();
    input
        .neighbors_directed(shiny_gold_index, Direction::Outgoing)
        .map(|node| edge_counts(input, shiny_gold_index, node))
        .sum()
}

fn edge_counts(graph: &DiGraph<String, usize>, parent: NodeIndex, node: NodeIndex) -> usize {
    let bag_count_edge = graph.find_edge(parent, node).unwrap();
    let bag_count = *(graph.edge_weight(bag_count_edge).unwrap());
    let neighbors = graph.neighbors_directed(node, Direction::Outgoing);
    let nested_count: usize = if neighbors.count() == 0 {
        0
    } else {
        graph.neighbors_directed(node, Direction::Outgoing).map(|n| bag_count * edge_counts(graph, node, n)).sum()
    };
    bag_count + nested_count
}

[Dirk Fraanje (the Netherlands)]

Solution for C# (part 2).
Just wanted to finish it, so don't expect any beauty :) :

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace AdventOfCode2020
{

    static class Day7Part2
    {
        static List<string> input = new List<string>(File.ReadAllLines("//inputfile"));
        static List<Bag> bagtypes = new List<Bag>();
        static int countbags = 0;
        public static void Execute()
        {
            //First make a list of the Bag class
            foreach (var rule in input)
            {
                bagtypes.Add(DefineColorsForBag(rule));
            }
            //Get the shinygoldbag
            var shinygoldbag = bagtypes.Where(x => x.OwnColor == "shinygold").FirstOrDefault();

            //And then count the bags
            CountBags(shinygoldbag, 1);
            Console.WriteLine($"Answer: {countbags}");
        }

        private static void CountBags(Bag bag, int times)
        {
            foreach (var rule in bag.ContainerRules)
            {
                //Count is used to add to the total and to set the times in the next recursion
                var count = rule.number * times;
                countbags += count;
                var getBagForRuleColor = bagtypes.Where(x => x.OwnColor == rule.color).ToList();
                if (getBagForRuleColor.Count() == 1)
                    CountBags(getBagForRuleColor[0], count);
            }
        }

        private static Bag DefineColorsForBag(string rule)
        {
            var splitrule1 = rule.Split(' ');
            var bag = new Bag(splitrule1[0] + splitrule1[1]);

            var splitrule2 = rule.Split(' ').Skip(3).ToArray();
            int i = 0;
            while (true)
            {
                var stringToCompare = splitrule2[i];
                if (stringToCompare.Contains(".") || string.Equals("no", stringToCompare))
                    return bag;
                if (stringToCompare.Contains(',') || stringToCompare.Contains("bag") || string.Equals("contain", stringToCompare))
                {
                    i++;
                    stringToCompare = splitrule2[i];
                    if (string.Equals("no", stringToCompare) || string.Equals("0", stringToCompare))
                        return bag;
                    int.TryParse(stringToCompare, out int t);
                    bag.ContainerRules.Add(new Rule(t, splitrule2[i + 1] + splitrule2[i + 2]));
                    i += 3;
                }

            }
            return bag;
        }
    }
}

`

[flwidmer]

I start to like parsing these kind of rules in Haskell, it's very intuitive to me.
The association list was a nice fit for this problem; had I done it in Java, I would have used a Map with Lists as a value. Even though it's not the most time efficient approach, it was allright for this size problem.

solve1 :: String -> Int
solve1 input =
    let assocList = createInvertedMap $ map parseRule $ lines input
        recursion = recurse1 assocList "shinygold"
    in length $ nub recursion

recurse1 :: [(String, String)] -> String -> [String]
recurse1 assocList search  =
    let current = lookupAll assocList search
        next = concatMap (recurse1 assocList) current
    in current ++ next

solve2 :: String -> Int
solve2 input =
    let assocList = map parseRule $ lines input
        recursion = recurse2 assocList "shinygold"
    in recursion

recurse2 :: [(String, [(String, Int)])] -> String -> Int
recurse2 assocList search  =
    let current = concat $ lookupAll assocList search
        next = sum $ map recurseValue current
    in sum (map snd current) + next
    where recurseValue (bag, multiplier) = multiplier * recurse2 assocList bag

-- parse one line into an association list
parseRule :: String -> (String, [(String, Int)])
parseRule a =
    let keyValue = splitOn " contain " a
        key = concat $ take 2 $ words $ head keyValue
        value =map parseContains $ splitOn "," $ keyValue !! 1
    in (key , value)

-- "contain 2 shiny gold bags." -> ("shinygold", 2)
parseContains :: String -> (String, Int)
parseContains "no other bags." = ("none", 0)
parseContains a =
    let removePeriod = filter (/= '.') a
        noBags = filter (\x -> x /="bags" && x /= "bag") $ words removePeriod
    in (concat $ tail noBags, read $ head noBags)

-- unwrap the association list
createInvertedMap :: [(String, [(String, b)])] -> [(String, String)]
createInvertedMap = concatMap invert
    where invert (outer, inner) = map ((, outer) . fst) inner

-- a lookup that returns more than one result
lookupAll :: [(String, b)] -> String -> [b]
lookupAll assocList key  = map snd $ filter (\(k,_) -> k == key) assocList

[Christopher Nilsson]

Python

import re
from collections import defaultdict

bags = defaultdict(dict)
for l in lines:
    bag = re.match(r'(.*) bags contain', l).groups()[0]
    for count, b in re.findall(r'(\d+) (\w+ \w+) bag', l):
        bags[bag][b] = int(count)

def part1():
    answer = set()
    def search(color):
        for b in bags:
            if color in bags[b]:
                answer.add(b)
                search(b)
    search('shiny gold')
    return len(answer)

def part2():
    def search(bag):
        count = 1
        for s in bags[bag]:
            multiplier = bags[bag][s]
            count += multiplier * search(s)
        return count
    return search('shiny gold' ) - 1  # Rm one for shiny gold itself

My cleanest solution! Wrote more about it, even tested networkx in my blogpost.

[readyready15728]

Ruby, part 1. Kinda ugly, but effective:

require 'set'

bag_descriptions = []

File.readlines('07.txt').each do |line|
  bag_type = line.match('\A(.*?) bags')[1]
  contents = []

  unless line.match('contain no other bags')
    line.scan(/(\d+) (.*?) bags?/).each do |count, color|
      contents.push [color, count]
    end
  end

  bag_descriptions.push({"bag_type" => bag_type, "contents" => contents.to_h})
end

def scan_for_possible_containers(bag_descriptions, previous_possible_containers)
  new_containers = Set.new

  bag_descriptions.each do |bag_description|
    # Direct container of shiny gold bags
    if bag_description['contents'].include? 'shiny gold'
      # Don't need to check if already present because Set class is used
      new_containers.add bag_description['bag_type']
    end

    # Indirect containers of shiny gold bags
    unless previous_possible_containers.intersection(Set.new bag_description['contents'].keys).empty?
      # Again, no need to check if already present
      new_containers.add bag_description['bag_type']
    end
  end

  new_containers
end

previous_possible_containers = Set.new
# Initial scan
current_possible_containers = scan_for_possible_containers(bag_descriptions, previous_possible_containers)

# Keep iterating until all possible choices are exhausted
until previous_possible_containers == current_possible_containers
  previous_possible_containers = current_possible_containers
  current_possible_containers = scan_for_possible_containers(bag_descriptions, previous_possible_containers)
end

puts current_possible_containers.length

[Mike Gasparelli]

Struggled on this one more than I probably should have. I started with a recursion bug that was right in front of my eyes, then went on to part2 to realize that I would need to re-think my model (can't say I didn't see that one coming).

Part 1

public class Part1 : Puzzle<Dictionary<string, Node<Bag>>, long>
    {
        protected const string Target = "shiny gold";

        public override long SampleAnswer => 4;

        public override Dictionary<string, Node<Bag>> ParseInput(string rawInput)
            => rawInput
                .Split(Environment.NewLine)
                .Where(line => line.Length > 0)
                .Select(ParseBagDescription)
                .ToDictionary(node => node.Name, node => node);

        Node<Bag> ParseBagDescription(string description)
        {
            var parts = description.Split(" bags contain ");
            var name = parts[0];

            var node = new Node<Bag>(name, new Bag(name));

            var innerBagNodes = parts[1]
                .Split(',')
                .Where(description => description != "no other bags.")
                .Select(bag => bag.TrimStart())
                .Select(bag => ParseBagContents(bag))
                .Select(bag => new Node<Bag>(bag.Name, bag));

            node.AddChildren(innerBagNodes);

            return node;
        }

        Bag ParseBagContents(string contents)
        {
            int space = contents.IndexOf(' ');
            string name = contents[(space + 1)..contents.LastIndexOf(' ')];
            int.TryParse(contents[..space], out int count);

            return new Bag(name, count);
        }

        public override long Solve(Dictionary<string, Node<Bag>> input)
            => input.Count(x => HasDescendent(input, Target, x.Value));

        bool HasDescendent(Dictionary<string, Node<Bag>> allNodes, string name, Node<Bag> node)
            => node.Children.Any(n => n.Name == Target || HasDescendent(allNodes, name, allNodes[n.Name]));
    }

Part2

    public class Part2 : Part1
    {
        public override long SampleAnswer => 32;

        public override long Solve(Dictionary<string, Node<Bag>> input)
            => CountInnerBagsRecursive(input, input[Target]) - 1;   // We counted the target bag, reduce count by 1.

        long CountInnerBagsRecursive(Dictionary<string, Node<Bag>> allNodes, Node<Bag> node)
            => node.Children.Aggregate(1L, (acc, cur) =>
                acc += cur.Value.Count * CountInnerBagsRecursive(allNodes, allNodes[cur.Name]));
    }

Node

    public class Node<T>
    {
        public string Name { get; }

        public T Value { get; }

        public List<Node<T>> Children { get; private set; } = new ();

        public Node(string name, T value)
        {
            Name = name;
            Value = value;
        }

        public void AddChild(Node<T> node) => Children.Add(node);

        public void AddChildren(IEnumerable<Node<T>> nodes) => Children.AddRange(nodes);

        public bool HasDescendent(string name)
            => Children.Any(node => node.Name == name || node.HasDescendent(name));
    }

[Harry Gibson]

Urgh this was horrible. I should have taken the opportunity to learn some kind of graph library to do this, but I've spent way enough time looking at it now.

from collections import defaultdict

class RuleParser():

    def __init__(self):
        self.containment_tree = defaultdict(lambda: defaultdict(list))


    def parse_row(self, row):
        if row.strip()=="": return
        row = row.replace(' bags', '').replace(' bag', '').replace('.','').strip()
        outer, contents = row.split(' contain ')
        content_rules = contents.split(', ')
        for contained_rule in content_rules:
            words = contained_rule.split(' ')
            n = 0 if words[0] == "no" else int(words[0])
            colour = " ".join(words[1:])
            colour = colour if n > 0 else "no other"
            self.containment_tree[outer][colour]=n


    def find_in_subtree(self, target_color):
        outers = set()
        def search_subtree(for_colour):
            for outer in self.containment_tree:
                if for_colour in self.containment_tree[outer]:
                    outers.add(outer)
                    search_subtree(outer)
        search_subtree(target_color)
        return len(outers)


    def _n_in_subtree(self, outer_bag):
        total_children = 1
        for inner_bag in parser.containment_tree[outer_bag]:
            n_this_colour = parser.containment_tree[outer_bag][inner_bag]
            n_children = self._n_in_subtree(inner_bag)
            total_children += n_this_colour * n_children
        return total_children


    def n_in_children(self, outer_bag):
        return self._n_in_subtree(outer_bag)-1


parser = RuleParser()

with open ("input.txt", "r") as input:
    for row in input:
        parser.parse_row(row)

goal_colour = 'shiny gold'
part_1 = parser.find_in_subtree(goal_colour)
print(f"Part 1 solution: {part_1} colours can ultimately contain a {goal_colour} bag")

part_2 = parser.n_in_children(goal_colour)
print(f"Part 2 solution: a {goal_colour} bag has to contain {part_2} other bags")

[Derk-Jan Karrenbeld]

Part 1 is a reachability problem, Part 2 is a Depth first search. But instead of building a graph, I was lazy and kept a Map of edges.

Here's Ruby:

require 'benchmark'

class BagsContent
  def initialize(name, count:)
    self.name = name
    self.count = Integer(count)
  end

  def to_s
    name
  end

  def to_i
    count
  end

  def inspect
    "#{name} (#{count})"
  end

  private

  attr_accessor :name, :count
end

class BagsBabushka
  def self.from_rules(lines)
    parsed = lines.each_with_object({}) do |line, rules|
      subject, contents = line.split(' contain ')
      subject = subject.gsub(/bags?/, '').strip

      next rules[subject] = [] if contents == 'no other bags.'

      rules[subject] = contents.split(', ').map do |bag|
        match = /^([0-9]+) (.*?) bags?\.?$/.match(bag)
        BagsContent.new(match[2], count: match[1])
      end
    end

    new(parsed)
  end

  def initialize(rules)
    self.rules = rules
  end

  def shiny(target = 'shiny gold')
    potentials = [target]
    targets = {}

    while potentials.length > 0
      matcher = potentials.shift

      self.rules.each do |container, contents|
        contents.each do |content|
          color = content.to_s

          if color == matcher
            potentials.push(container) unless targets.key?(container)
            targets[container] = true
          end
        end
      end
    end

    targets.keys
  end

  def shiny_contents(target = 'shiny gold')
    self.rules[target].inject(0) do |count, content|
      count + content.to_i + content.to_i * shiny_contents(content.to_s)
    end
  end

  private

  attr_accessor :rules
end

rules = File
  .read('input.txt')
  .split(/\n/)

Benchmark.bmbm do |b|
  b.report do
    puts BagsBabushka.from_rules(rules).shiny_contents
  end
end