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

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

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

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

"""Day 7: Handy Haversacks

Figure out which and how many luggage pieces in various colors
are contained inside other ones.
"""

def parse(filename):
    """Parse the input file to form two digraphs: one showing
    which bags are able to be contained in which and the other
    showing which bags contain what numbers of which other bags.
    """
    parents = dict()
    children = dict()

    with open(filename, "r") as f:
        lines = f.readlines()

    # Figure out which colors we have
    for line in lines:
        color = " ".join(line.split()[:2])
        parents[color] = []
        children[color] = []

    # Fill in the digraphs
    for line in lines:
        words = line.split()
        if "no other" in line:
            continue
        parent_color = " ".join(words[:2])

        child_words = iter(words[4:])
        while True:
            count = int(next(child_words))
            child_adj = next(child_words)
            child_color = next(child_words)
            child_name = f"{child_adj} {child_color}"
            parents[child_name].append(parent_color)
            children[parent_color].append((child_name, count))
            if next(child_words)[-1] == ".":
                break
    return parents, children


def holders(color, parents_graph):
    """Build a set of all unique bags which can contain the 
    requested bag color.
    """
    result = set(parents_graph[color])
    for c in parents_graph[color]:
        result |= holders(c, parents_graph)
    return result


def count_contents(color, children_graph):
    """Add up the bags inside a given bag plus all of the bags within
    each of each child bags.
    """
    return sum(count + count * count_contents(child_color, children_graph) 
                for child_color, count in children_graph[color])

def part1(parents_graph):
    gold_holders = len(holders("shiny gold", parents_graph))
    print(f"{gold_holders} different colors can contain 'shiny gold.'")


def part2(children_graph):
    print(f"{count_contents('shiny gold', children_graph)} bags are in a 'shiny gold.'")


if __name__ == "__main__":
    parents, children = parse("data/day7.txt")
    part1(parents)
    part2(children)

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

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
}

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

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)

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

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

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

import re


adj = {}
visited = {}
with open("Problem-7/Day 7: Handy Haversacks.txt") as file:
    for line in file:
        # Every line in the input was in the format outerbags contain x innerbags, y innerbags, so on..
        # So we can split every line into two parts using the word "contain " as separator.
        # As split funtion returns a list, we now have outerbag name as first element and it's dependencies as second element. Unpacked them into two variables as shown below.
        outer_bag, innerbags = line.split("contain ")
        # Now the outer_bag variable has outerbagname with suffix bags in it. We can just slice the string to remove the suffix
        # Similarly, innerbags will now has a string in the format x innerbags, y innerbags, so on..
        # We can extract the count and the innerbag name using regex and grouping as shown below
        innerbags = re.findall(r"(\d{1,}) ([a-z ]+) bag|bags", innerbags)
        # visited list is useful when we are exploring the graph to avoid cycles. Initially we should mark every bag as not visited
        visited[outer_bag[:-6]] = False
        if outer_bag[:-6] not in adj:
            adj[outer_bag[:-6]] = {}
        # Adding edges from outer bag to each inner bag
        for count, bag in innerbags:
            if count and bag:
                if bag not in adj:
                    adj[bag] = {}
                adj[outer_bag[:-6]][bag] = int(count)
# Now we have our adjacency list ready for our directed graph


def part_one(adj, visited, bag_name):
    # dfs of a graph
    def dfs(adj, visited, start, count):
        for edge in adj[start].keys():
            if not visited[edge]:
                visited[edge] = True
                count = dfs(adj, visited, edge, count + 1)
        return count

    # reverse the graph
    adj_reverse = {}
    for outer, inner in adj.items():
        if outer not in adj_reverse:
            adj_reverse[outer] = {}
        for key, count in inner.items():
            if key in adj_reverse:
                adj_reverse[key][outer] = count
            else:
                adj_reverse[key] = {outer: count}
    # Now as the graph is reversed, we can find the vertices that previously had a directed edge towards the shiny gold bag now in new adjacency list at shiny gold vertex.
    # Simply exploring and counting the number of vertices explored from shiny gold bag vertex will be the result
    return dfs(adj_reverse, visited, bag_name, 0)


def part_two(adj, start, count):
    if not adj[start]:
        return 0
    temp = 0
    for edge, c in adj[start].items():
        temp += c + c * part_two(adj, edge, count)
    count += temp
    return count


print("Part 1: Total number of bag colors that contain at least one shiny gold bag :",
      part_one(adj, visited, "shiny gold"))
print("Part 2: Shiny gold bag contains total {} number of bags".format(
    part_two(adj, "shiny gold", 0)))

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"

   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.

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