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

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