DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 7: Handy Haversacks
Ryan Palo
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.

The Leaderboards

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

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (19)

Collapse
 
benwtrent profile image
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>();
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
neilgall profile image
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'])));
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
ballpointcarrot profile image
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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
dirkfraanje profile image
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;

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

Enter fullscreen mode Exit fullscreen mode


`

Collapse
 
flwidmer profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cnille profile image
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
Enter fullscreen mode Exit fullscreen mode

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

Collapse
 
readyready15728 profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mgasparel profile image
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]));
    }
Enter fullscreen mode Exit fullscreen mode

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

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));
    }
Enter fullscreen mode Exit fullscreen mode
Collapse
 
harrygibson profile image
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")
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sleeplessbyte profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kais_blog profile image
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! :)

Collapse
 
ntreu14 profile image
Nicholas Treu

F#:

open System.IO

type InnerBag = {
  InnerBagName: string
  InnerBagQuantity: int
}

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

  | innerQuantity::innerAdj::innerColor::_::rest ->
    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
    | adj::color::_::_::"no"::"other"::["bags."] ->
      let bagName = sprintf "%s %s" adj color
      Map.add bagName [] acc

    | adj::color::_::_::rest ->
      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"
Enter fullscreen mode Exit fullscreen mode
Collapse
 
galoisgirl profile image
Anna

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

   IDENTIFICATION DIVISION.
   PROGRAM-ID. AOC-2020-07-1.
   AUTHOR. ANNA KOSIERADZKA.

   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.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-PARSE-RECORD
        END-READ.

   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.
Enter fullscreen mode Exit fullscreen mode
Collapse
 
meseta profile image
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
Screenshot 2020-12-08 015149

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:
            self.graph.add_edge(parent, child, count=count)

    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):
        self.graph.add_node(node.text)
        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

graph = bv.parse(open("input.txt").read())

# 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)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
readyready15728 profile image
readyready15728

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

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