@@MarkJanssen76 Really? I tried it and it turned out 3 times slower than the following: hold the towels in a set and when checking whether a design is possible, take the first n (up to max len of towel for towel in towels) characters and see if one towel matches them... which is the solution displayed in the video (i just noticed that...). But even with that approach and functools.cache my solution has an endless loop.
for part 1 I solved this using dynamic programming with no recursion and a trie.. placed the towels in a trie and then search for each design slice within the trie if I found 1 combination then I would break since no more were needed.. so basically my dp array was storing booleans.. for part 2 I removed the early break since we actually care about all combinations and then instead of a dp array that stores booleans this I would store integers and them kept summing the up as combinations were found. it was pretty fast
There is another way to do the recursion without using recursion: start at the end and find the number of possible ways for the last letter, then the last 2 letters, last 3... on each case you can look for the 1-letter part-sequence, then 2-letter etc to 8-letter, and if it is in the towel set add the number of options for the rest of the end past the towel found. I combined this reverse-array-scan method with a bitmap of all the available towels (one bit in an array set for each towel color combination, hashed as base5 enumeration of the towel stripes with a 1 in the top digit so 0 is different from 00, 000 etc.) which resulted in each scan taking about 1µs. whole program runtime < 440µs.
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.
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 :)
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
@@MarkJanssen76 Really? I tried it and it turned out 3 times slower than the following: hold the towels in a set and when checking whether a design is possible, take the first n (up to max len of towel for towel in towels) characters and see if one towel matches them... which is the solution displayed in the video (i just noticed that...). But even with that approach and functools.cache my solution has an endless loop.
for part 1 I solved this using dynamic programming with no recursion and a trie.. placed the towels in a trie and then search for each design slice within the trie if I found 1 combination then I would break since no more were needed.. so basically my dp array was storing booleans.. for part 2 I removed the early break since we actually care about all combinations and then instead of a dp array that stores booleans this I would store integers and them kept summing the up as combinations were found. it was pretty fast
There is another way to do the recursion without using recursion: start at the end and find the number of possible ways for the last letter, then the last 2 letters, last 3...
on each case you can look for the 1-letter part-sequence, then 2-letter etc to 8-letter, and if it is in the towel set add the number of options for the rest of the end past the towel found.
I combined this reverse-array-scan method with a bitmap of all the available towels (one bit in an array set for each towel color combination, hashed as base5 enumeration of the towel stripes with a 1 in the top digit so 0 is different from 00, 000 etc.) which resulted in each scan taking about 1µs. whole program runtime < 440µs.
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.
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 :)
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("
"))))