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

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

Part2

    public class Part2 : Part1
    {
        public override long SampleAnswer => 32;

        public override long Solve(Dictionary<string, Node<Bag>> input)
            => CountInnerBagsRecursive(input, input[Target]) - 1;   // We counted the target bag, reduce count by 1.

        long CountInnerBagsRecursive(Dictionary<string, Node<Bag>> allNodes, Node<Bag> node)
            => node.Children.Aggregate(1L, (acc, cur) =>
                acc += cur.Value.Count * CountInnerBagsRecursive(allNodes, allNodes[cur.Name]));
    }

Node

    public class Node<T>
    {
        public string Name { get; }

        public T Value { get; }

        public List<Node<T>> Children { get; private set; } = new ();

        public Node(string name, T value)
        {
            Name = name;
            Value = value;
        }

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