<jupyter_start><jupyter_text>[Day 7](https://adventofcode.com/2020/day/7): Handy Haversacks<jupyter_code>import numpy as np
import re

rule = re.compile(r"(.*) bags contain (.*)\.")
bags = re.compile(r"(\d+) (.*?) bag")

with open("../data/07.txt", "r") as f:
    rules = rule.findall(f.read())
    enum = {bag: i for i, (bag, _) in enumerate(rules)}
    contents = np.zeros((len(enum), len(enum)), dtype=int)
    for bag, items in rules:
        for n, item in bags.findall(items):
            contents[enum[bag], enum[item]] = int(n)<jupyter_output><empty_output><jupyter_text>Part 1  Solution by recursion<jupyter_code>import operator as op

arithmetic = {np.dtype(bool): (op.or_, op.and_), # Part 1
              np.dtype(int):  (op.add, op.mul)}  # Part 2

def expander(b):
    add, mul = arithmetic[b.dtype]
    sigma = lambda ys: np.sum(list(ys), axis=0, dtype=b.dtype)
    def expand(y):
        if (y == 0).all():
            return y
        return add(y, sigma(mul(a, expand(z)) for a, z in zip(y, b) if a))
    return expand

shinygold = enum["shiny gold"]
contains = contents.T.astype(bool)

assert 222 == np.sum(expander(contains)(contains[shinygold]))<jupyter_output><empty_output><jupyter_text>Solution by iteration (linear algebra)Given a *nilpotent*, square $(0,1)$-matrix $B$, solve the equation $X=B+BX$. The solution is given by the geometric series $X=(1-B)^{-1}B=B+B^2+B^3+\cdots$, which is finite because $B$ is nilpotent. This also yields the solution over the boolean semiring, for which "$1-B$" would be undefined.<jupyter_code>from itertools import accumulate, repeat, takewhile
from scipy.sparse import csr_matrix

def geomseries(x):
    """Geometric series starting from x, assuming x is nilpotent (and sparse)."""
    x = csr_matrix(x)
    pows = accumulate(repeat(x), op.matmul, initial=x)
    return np.sum(list(takewhile(csr_matrix.count_nonzero, pows)), axis=0)

assert 222 == np.sum(geomseries(contains)[shinygold])<jupyter_output><empty_output><jupyter_text>NB: Without sparsity the geometric series would be much slower to compute.  Part 2  Solution by recursion<jupyter_code>assert 13264 == np.sum(expander(contents)(contents[shinygold]))<jupyter_output><empty_output><jupyter_text>Solution by iteration<jupyter_code>assert 13264 == np.sum(geomseries(contents)[shinygold])<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup