## DEV Community

Ryan Palo

Posted on • Updated on

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

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
Clojure 2
Python 2
Rust 1
TypeScript 1
COBOL 1
Elixir 1
C# 1
Go 1
C 1

Merry Coding!

## Top comments (19)

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();
Ok(contents)
}

// --- model

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

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

#[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 {
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| {
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
}

#[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) • Edited

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;

{

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)
{
}
//Get the shinygoldbag
var shinygoldbag = bagtypes.Where(x => x.OwnColor == "shinygold").FirstOrDefault();

//And then count the bags
CountBags(shinygoldbag, 1);
}

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():
def search(color):
for b in bags:
if color in bags[b]:
search(b)
search('shiny gold')

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.

Ruby, part 1. Kinda ugly, but effective:

``````require 'set'

bag_descriptions = []

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
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
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));

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 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]:
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

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
.split(/\n/)

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

Kai • Edited

Today's puzzle was a little bit more complicated. However, like every other day before, I've created a step-by-step tutorial for my fellow TypeScript and JavaScript developers:

Thanks for reading! :)

Nicholas Treu

F#:

``````open System.IO

type InnerBag = {
InnerBagName: string
InnerBagQuantity: int
}

let rec parseInnerBags acc = function
| [] | "no"::"other"::["bags."] -> acc

let bagName = sprintf "%s %s" innerAdj innerColor
let bag = { InnerBagName=bagName; InnerBagQuantity=int innerQuantity }
parseInnerBags (bag::acc) rest

| pattern -> failwithf "cannot parse inner pattern %A" pattern

let parseLine acc (s: string) =
match List.ofArray <| s.Split(' ') with
let bagName = sprintf "%s %s" adj color
Map.add bagName [] acc

let bagName = sprintf "%s %s" adj color
Map.add bagName (parseInnerBags [] rest) acc

| pattern -> failwithf "cannot parse pattern %A" pattern

let rec findAllBagsContaining soughtBag allBags =
allBags
|> Map.filter (fun _ innerBags -> innerBags |> List.exists (fun bag -> bag.InnerBagName = soughtBag))
|> Map.toList
|> List.collect (fst >> fun bagName -> bagName::findAllBagsContaining bagName allBags)

let rec countBagsInsideOf bagName allBags =
match Map.tryFind bagName allBags with
| Some innerBags ->
innerBags |> List.sumBy (fun innerBag ->
innerBag.InnerBagQuantity + countBagsInsideOf innerBag.InnerBagName allBags * innerBag.InnerBagQuantity
)

| None -> 0 // this should never happen

let bags =
File.ReadAllLines "input.txt" |> Array.fold parseLine Map.empty

// Part 1
findAllBagsContaining "shiny gold" bags
|> Set.ofList
|> Set.count
|> printfn "%d"

// Part2
countBagsInsideOf "shiny gold" bags
|> printfn "%d"
``````

Anna

Sweet mother of everything, I've walked a graph in COBOL.

``````   IDENTIFICATION DIVISION.
PROGRAM-ID. AOC-2020-07-1.

ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT INPUTFILE ASSIGN TO "d07.input"
ORGANIZATION IS LINE SEQUENTIAL.

DATA DIVISION.
FILE SECTION.
FD INPUTFILE
RECORD IS VARYING IN SIZE FROM 1 to 128
DEPENDING ON REC-LEN.
01 INPUTRECORD PIC X(128).

WORKING-STORAGE SECTION.
01 FILE-STATUS PIC 9 VALUE 0.
01 REC-LEN PIC 9(2) COMP.
01 WS-BUFFER PIC X(32) OCCURS 32 TIMES.
01 WS-BAG PIC X(32).
01 WS-BAGS OCCURS 594 TIMES.
05 WS-BAG-COLOR PIC X(32).
05 WS-BAG-DONE PIC 9 VALUE 0.
05 WS-BAG-BAGS-NUMBER PIC 99 VALUE 0.
05 WS-BAG-BAGS PIC X(32) OCCURS 32 TIMES.
01 WS-BAGS-QUEUE PIC X(32) OCCURS 9999 TIMES.

LOCAL-STORAGE SECTION.
01 N UNSIGNED-INT VALUE 0.
01 RESULT UNSIGNED-INT VALUE 0.
01 BAG-IDX UNSIGNED-INT VALUE 1.
01 I UNSIGNED-INT VALUE 1.
01 J UNSIGNED-INT VALUE 1.
01 K UNSIGNED-INT VALUE 1.
01 STRING-PTR UNSIGNED-INT VALUE 1.
01 Q1 UNSIGNED-INT VALUE 1.
01 Q2 UNSIGNED-INT VALUE 1.

PROCEDURE DIVISION.
001-MAIN.
OPEN INPUT INPUTFILE.
PERFORM 002-READ UNTIL FILE-STATUS = 1.
CLOSE INPUTFILE.
PERFORM 005-WALK-GRAPH.
PERFORM 008-COUNT-RESULT.
DISPLAY Q2.
DISPLAY RESULT.
STOP RUN.

AT END MOVE 1 TO FILE-STATUS
NOT AT END PERFORM 003-PARSE-RECORD

003-PARSE-RECORD.
ADD 1 TO N.
MOVE 1 TO STRING-PTR.

PERFORM VARYING J FROM 1 BY 1 UNTIL J > 32
UNSTRING INPUTRECORD DELIMITED BY SPACE
INTO WS-BUFFER(J)
WITH POINTER STRING-PTR
END-PERFORM.

STRING
WS-BUFFER(1) DELIMITED BY SPACE
' ' DELIMITED BY SIZE
WS-BUFFER(2) DELIMITED BY SPACE
INTO WS-BAG-COLOR(I)
END-STRING.

IF NOT WS-BUFFER(5) = "no" THEN
PERFORM 004-PARSE-SUB-BAGS
END-IF.
ADD 1 TO I.

004-PARSE-SUB-BAGS.
* 1, 2 are color, 3=bags, 4=contains
MOVE 1 TO K.
PERFORM VARYING J FROM 5 BY 4 UNTIL J > 32
IF NOT WS-BUFFER(J)(1:1) = " " THEN
STRING
WS-BUFFER(J + 1) DELIMITED BY SPACE
' ' DELIMITED BY SIZE
WS-BUFFER(J + 2) DELIMITED BY SPACE
INTO WS-BAG-BAGS(I, K)
END-STRING
ADD 1 TO K
END-IF
END-PERFORM.
COMPUTE WS-BAG-BAGS-NUMBER(I) = K - 1.

005-WALK-GRAPH.
* Queue starts containing 'shiny gold', Q1 = 1, Q2 = 1
MOVE 'shiny gold' TO WS-BAGS-QUEUE(1).
PERFORM 006-WALK-GRAPH-LOOP UNTIL Q1 > Q2.

006-WALK-GRAPH-LOOP.
MOVE WS-BAGS-QUEUE(Q1) TO WS-BAG.
ADD 1 TO Q1.
PERFORM 007-FIND-BAG-INDEX.
MOVE 1 TO WS-BAG-DONE(BAG-IDX).

PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
*    Find bags with WS-BAG among sub-bags
IF WS-BAG-DONE(I) = 0 THEN
PERFORM VARYING J FROM 1 by 1
UNTIL J > WS-BAG-BAGS-NUMBER(I)
IF WS-BAG = WS-BAG-BAGS(I, J)
ADD 1 TO Q2
MOVE WS-BAG-COLOR(I) TO WS-BAGS-QUEUE(Q2)
EXIT PERFORM
END-IF
END-PERFORM
END-IF
END-PERFORM.

* Note: no hashtables in COBOL, so linear lookup
007-FIND-BAG-INDEX.
PERFORM VARYING K FROM 1 BY 1 UNTIL K > N
IF WS-BAG = WS-BAG-COLOR(K) THEN
MOVE K TO BAG-IDX
END-IF
END-PERFORM.

008-COUNT-RESULT.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
IF WS-BAG-DONE(I) = 1 THEN
ADD 1 TO RESULT
END-IF
END-PERFORM.
* Shiny gold bag doesn't count
SUBTRACT 1 FROM RESULT.
``````

Yuan Gao • Edited

I pull out that PEG parser again to handle my input, I feel it's more readable than a full regex solution, since you define the entire syntax of the input file up-front for everyone to see. But it's not as compact as a pure regex solution, and there's a lot of extra nodes (could probably golf it, but it would be less readable). One benefit is the NodeVisitor is already doing a depth-first visit of the generated AST, so you can piggy back the graph generation in there to save a loop or two.

I used the NetworkX graph library in Python to get the `ancestors` for free, but unfortunately still had to write a recursive traversal of the DAG to get the sums for Part 2.

Made some nice graphs while I was at it too, more on my post

``````from parsimonious.grammar import Grammar, NodeVisitor
import networkx as nx

grammar = Grammar(r"""
DOCUMENT  = LINE+
LINE      = (ENTRY / TERMINAL)

TERMINAL  = PARENT "no other bags." "\n"?
ENTRY     = PARENT CHILDREN "." "\n"?

PARENT    = COLOR " bags contain "
CHILDREN  = CHILD+
CHILD     = NUMBER " " COLOR " " BAGBAGS SEPARATOR

NUMBER    = ~r"\d+"
COLOR     = ~r"\w+ \w+"
BAGBAGS   = ("bags" / "bag")
SEPARATOR = ~r"(, |(?=\.))"
""")

class BagVisitor(NodeVisitor):
def parse(self, *args, **kwargs):
self.graph = nx.DiGraph()
super().parse(*args, **kwargs)
return self.graph

def visit_ENTRY(self, node, visited_children):
parent, children, *_ = visited_children
for count, child in children:

def visit_PARENT(self, node, visited_children):
return visited_children[0]

def visit_CHILD(self, node, visited_children):
return (visited_children[0], visited_children[2])

def visit_COLOR(self, node, visited_children):
return node.text

def visit_NUMBER(self, node, visited_children):
return int(node.text)

def generic_visit(self, node, visited_children):
return visited_children or node

bv = BagVisitor()
bv.grammar = grammar

# Part 1
print("ancestor bags", len(nx.ancestors(graph, "shiny gold")))

# Part 2
def get_count(parent):
return 1 + sum(get_count(child) * graph.edges[parent, child]["count"] for child in graph.neighbors(parent))

print("total bags", get_count("shiny gold")-1)
``````

Ruby, part 2. Oddly much easier than part 1. Parsing modified to suit the problem better:

``````require 'set'

bag_descriptions = {}

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.to_i]
end
end

bag_descriptions[bag_type] = contents.to_h
end

def total_bag_count(bag_descriptions, bag_type)
# Count this bag
count = 1

bag_descriptions[bag_type].each do |inner_bag, bag_count|
count += bag_count * total_bag_count(bag_descriptions, inner_bag)
end

count
end

# Subtract one as the shiny gold bag itself is not counted
puts total_bag_count(bag_descriptions, 'shiny gold') - 1
``````