Advent of Code 2024 - Day 19: Linen Layout

Advent of Code 2024 – C# and Python (23 Part Series)

Day 19: Linen Layout

GitHub Solution

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.


<span>for</span> <span>arrangement</span> <span>in</span> <span>arrangements</span><span>:</span>
    <span>if</span> <span>arrangement</span> <span>in</span> <span>memo</span> <span>and</span> <span>memo</span><span>[</span><span>arrangement</span><span>]:</span>
        <span>ways</span> <span>=</span> <span>count_arrangements</span><span>(</span><span>arrangement</span><span>,</span> <span>towels</span><span>,</span> <span>memo_count</span><span>)</span>
        <span>total_arrangements</span> <span>+=</span> <span>ways</span>
<span>for</span> <span>arrangement</span> <span>in</span> <span>arrangements</span><span>:</span>
    <span>if</span> <span>arrangement</span> <span>in</span> <span>memo</span> <span>and</span> <span>memo</span><span>[</span><span>arrangement</span><span>]:</span>
        <span>ways</span> <span>=</span> <span>count_arrangements</span><span>(</span><span>arrangement</span><span>,</span> <span>towels</span><span>,</span> <span>memo_count</span><span>)</span>
        <span>total_arrangements</span> <span>+=</span> <span>ways</span>
for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

Enter fullscreen mode Exit fullscreen mode

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

Advent of Code 2024 – C# and Python (23 Part Series)

原文链接：Advent of Code 2024 – Day 19: Linen Layout

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END