I fell into a trap today. I solved the first part without caching, by optimizing the initial set of patterns. If you apply even a non-cached search function to each pattern, you can shorten the list of patterns massively, because most of them consist of other smaller patterns. After that, all the design can be checked fast. So I though that was really clever, and continue with that approach. Alas, it doesn't really help to solve part 2 at all :)
same here - did a loop over the towels sorted with descending length and a startswith check on the design + recursive call on success. That is quite fast. Getting all combos required the design - combo count caching.
Here is the same in a funny one liner print(*(lambda a:(lambda b,c,d=[0,0]:(list(map(lambda e:b(d,e),c)),d)[1][-2:])(lambda f,g:f.extend([f[-2]+1 if g>0 else f[-2],f[-1]+g]),[(lambda f,*h:f(f,*h))((lambda i:lambda j,k,l,m={}:m[k] if k in m else (m.update({k:i(j,k,l)}),m[k])[1])(lambda n,o,p: 1 if not o else sum(n(n,o[len(q):],p) for q in p if o.startswith(q))),r,a[0]) for r in a[1]]))((lambda s,t:(s.split(", "),t.split(" ")))(*open("input").read().strip().split("
For part 1 we can also do design.startswith(pattern) and then send the design[len(pattern):] to the recursive function
This also works fine for part 2
I fell into a trap today.
I solved the first part without caching, by optimizing the initial set of patterns. If you apply even a non-cached search function to each pattern, you can shorten the list of patterns massively, because most of them consist of other smaller patterns. After that, all the design can be checked fast. So I though that was really clever, and continue with that approach. Alas, it doesn't really help to solve part 2 at all :)
you don't need caching for the first part, looping over each towel and checking design.startswith(towel) is performant enough for it to be instant
same here - did a loop over the towels sorted with descending length and a startswith check on the design + recursive call on success. That is quite fast. Getting all combos required the design - combo count caching.
Here is the same in a funny one liner
print(*(lambda a:(lambda b,c,d=[0,0]:(list(map(lambda e:b(d,e),c)),d)[1][-2:])(lambda f,g:f.extend([f[-2]+1 if g>0 else f[-2],f[-1]+g]),[(lambda f,*h:f(f,*h))((lambda i:lambda j,k,l,m={}:m[k] if k in m else (m.update({k:i(j,k,l)}),m[k])[1])(lambda n,o,p: 1 if not o else sum(n(n,o[len(q):],p) for q in p if o.startswith(q))),r,a[0]) for r in a[1]]))((lambda s,t:(s.split(", "),t.split("
")))(*open("input").read().strip().split("
"))))