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

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!

Comments

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

[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.

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

[Harshavardhan]

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

[Dirk Fraanje (the Netherlands)]

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

`

[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

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

[Matt Ellen-Tsivintzeli]

I'm not happy with this javascript solution. Part 1 is very slow, and part 2 is not regexy enough. I'll hide it behind this gist.

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

[Yuan Gao]

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

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)

[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