adventofcode2024/day19/sol2.py

from functools import cache
def solve(file):
    designs = file.readline().strip().split(", ")
    assert file.readline() == '\n'

    ds = set(designs)

    @cache
    def ways(x):
        n = 0
        if x in ds:
            n += 1
        if len(x) > 1:
            for i in range(1,len(x)):
                # note: i originally tried to compute this as
                # n += ways(x[i:]) * ways(x[i:])
                # however that gives an overcount as, for example,
                # rrr can be broken up as (r)[(r)(r)] or [(r)(r)](r) but
                # for the purpose of the puzzle those are both equivalent -
                # only the leaf nodes count (r r r), not the structure of the tree.
                # the fix is to only recurse on one side of the cut (doesn't
                # matter which one).
                if x[:i] in ds:
                    n += ways(x[i:])
        #print("ways(%s) = %s"%(x,n))
        return n

    t = 0
    for line in file:
        towel = line.strip()
        w = ways(towel)
        #print(w, towel)
        t += w

    print(t)
        

solve(open('sample1.in'))
solve(open('input'))