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

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

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 

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 

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

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 

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']))); } } 

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 

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 } 

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

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

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