Advent of Code 2024 - Day 19: Linen Layout

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
from advent import parse, words, cache

pats, designs = parse(19, words, sep='\n\n')

@cache
def check_design(design):
    if design == '':
        return 1
    else:
        return sum(check_design(design.removeprefix(pat)) for pat in pats if design.startswith(pat))

counts = [ cnt for design in designs if (cnt := check_design(design)) > 0 ]

assert len(counts) == 353             # Part 1
assert sum(counts) == 880877787214477 # Part 2

NOTE: see Postscript below for a version that’s about 10x faster!

Parsing

We’re given input of the following form:

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb

I’d like two lists of words, one for the patterns and one for the designs:

1
 
pats, designs = parse(19, words, sep='\n\n')

Solution

I spent a lot of time messing around with a regex solution for part 1, but I ran into “catastrophic backtracking” issues. I expect the patterns are designed to cause that issue! One good thing that came out of that struggle was finding the regular expressions 101 website, which seems to be very handy for debugging regexes. It had a couple suggestions for dealing with the issue, but in the end, I figured part 2 may make it difficult for a pure regex solution anyway, so I switched gears to doing a search.

I originally did a breadth first search for part 1, but when I saw part 2, I felt a depth first solution might be better, since we want an exhaustive search, so I unified the parts to use on depth first search function. Adding the @cache decorator to memoize the function made it perform well enough for the stars, but it’s not blazingly fast by any stretch!

1
2
3
4
5
6
 
@cache
def check_design(design):
    if design == '':
        return 1
    else:
        return sum(check_design(design.removeprefix(pat)) for pat in pats if design.startswith(pat))

Rather than do the work twice, I compute a list of counts for each design (excluding zeros):

1
 
counts = [ cnt for design in designs if (cnt := check_design(design)) > 0 ]

With that, the parts are easy:

  • Part 1 is the length of the counts
  • Part 2 is the sum of the counts

New Python Concepts

  • removeprefix()
  • startswith()

Conclusion

The leaderboard showed this to be a very easy puzzle, but it took me longer than I would’ve liked. I bet there is an even more straightforward approach, and I’m sure there are definitely solutions that compute the answer quicker, but I’m satisfied enough with my solution to move on :)

Postscript

I found an idea from reddit user TheZigerionScammer that speeds things up by a factor of 10! In my version I iterate over all the patterns, and if the design starts with one of the patterns, I recur. The following version only loops over the first N characters of the design (up to the maximum pattern length), and if the prefix matches one of the patterns (fast lookup in a set), it recurs.

My original took 800 ms, this improved version takes 35 ms.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
from advent import parse, words, cache, timeit

towels, designs = parse(19, lambda s: set(words(s)), sep='\n\n')
max_len         = max(len(pat) for pat in towels)

def prefixes_suffixes(design):
    for prefix_len in range(1, min(max_len, len(design)) + 1):
        yield design[0:prefix_len], design[prefix_len:]

@cache
def check_design(design):
    arrangements = 1 if design in towels else 0

    for prefix, suffix in prefixes_suffixes(design):
        if prefix in towels:
            arrangements += check_design(suffix)

    return arrangements

counts = [ cnt for design in designs if (cnt := check_design(design)) > 0 ]

assert len(counts) == 353             # Part 1
assert sum(counts) == 880877787214477 # Part 2