Day 19: Linen Layout
Today's challenge was a refreshing change from the usual 2D puzzles and Dijkstra's algorithms. Here's how I approached it:
Part 1
The goal was straightforward: check if the given towel arrangements can be created using the available towels.
What NOT to do:
Initially, I tried generating all possible towel combinations with itertools.combinations. It quickly became clear this wasn't practical or efficient.
What worked:
Using recursion combined with a dictionary (memo) to cache already processed designs. This prevents redundant computations and makes the solution much more efficient.
How it works:
For each design, try matching the beginning with one of the towel patterns.
If there's a match, strip the matched part and recurse on the remainder.
Use memo to cache results for designs we've already checked, avoiding duplicate work.
The recursive approach with memoization keeps the complexity manageable, even for larger inputs, and makes the solution run efficiently.
Part 2
The second part upped the ante: count the number of ways to make each towel design using the available patterns.
Key insight:
The count_arrangements function extends the recursive logic from Part 1, but now calculates all possible ways to construct a design.
For each matching towel, recurse on the remainder of the design.
Use another dictionary (memo_count) to cache results for previously solved subproblems.
Example:
If "brgr" can be constructed in 2 ways, we simply return 2 from the cache instead of recalculating it.
Optimisation:
Thanks to Part 1, we already know which designs are possible. We only calculate arrangements for those.
for arrangement in arrangements:
if arrangement in memo and memo[arrangement]:
ways = count_arrangements(arrangement, towels, memo_count)
total_arrangements += ways
By summing up all the valid ways, we get the final answer for Part 2, simple as that.
Like I say I found today's challenge quite fun and was a nice change. I hope this article has helped for future challenges / coding.
As always feel free to give me a follow or reach out on Twitter