#!/usr/bin/python3
"""I think this puzzle came from Advent of Code."""
import sys, pprint

bags = {}
for line in sys.stdin:
    w = line.split()
    bags[w[0]] = w[1:]

# Transitive closure: what colors are contained within each bag color?
tc = {}
def compute_tc(bag):
    if bag in tc:
        return tc[bag]
    result = {bag} | set().union(*[compute_tc(child) for child in bags[bag]])
    tc[bag] = result
    return result
    
# Transitive count: how many bags are transitively contained in a bag?
count = {}
def compute_count(bag):
    if bag in count:
        return count[bag]
    result = 1 + sum(compute_count(child) for child in bags[bag])
    count[bag] = result
    return result

for bag in bags:
    compute_tc(bag)
    compute_count(bag)

pprint.pprint(tc)
pprint.pprint(count)

# The above took about ten minutes, but
# <https://adventofcode.com/2020/day/7> is the original problem, and
# it’s actually asking for the transitive closure of the *inverse*
# relation.  So, let’s invert the transitive-containment relation:

bagsi = {}
for bag in tc:
    for child in tc[bag]:
        if child not in bagsi:
            bagsi[child] = set()
            
        bagsi[child].add(bag)

pprint.pprint({'transitive containment': bagsi})

# And that took another ten minutes to get right, because I first
# implemented it in a different and more complicated way that was also
# buggy.