Day 19

For the Day 19 of our little adventure we land in the hot springs on Gear Island! This time nothing is catastrophic, except for the fact we are short on cash to explore the onsen. To get the money we agree to figure out if the towels can be arranged into specified patterns!

Read the full story on the official Day 19 of Advent of Code 2024 website.

And the usual ChatGPT generated illustration (tho I must admit it is hard to get it to generate what I want, I might try ChatGPT 4 again, cause 4o seems to be less good at images and, unrelated, emails) to get us started:

Setting up

from misc.helper import verify_answer

example_input_file = "../inputs/example_day_19.txt"
input_file = "../inputs/day_19.txt"

Part 1: Combine patterns

Our task here is from a given set of towels, count how many of the patterns can be assembled.

Towels can have stipes that are white (w), blue (u), black (b), red (r), or green (g).

Let’s say we have towels with the following patterns: wub, ggb, rrggbb, rr, b.

And we want to see if the following patterns can be assembled: ggbrrb, wurggb, rrrrrr, rrggbbrr, brr and rgb.

• ggbrrb can be assembled from ggb and rr and b,
• wurggb cannot be assembled,
• rrrrrr can be assembled from rr and rr and rr,
• rrggbbrr can be assembled from rr and ggb and b and rr or rrggbb and rr,
• brr can be assembled from b and rr,
• rgb cannot be assembled.

The number of patterns that can be assembled from the given set of towels is 4.

from pathlib import Path

example = """
wub, ggb, rrggbb, rr, b

ggbrrb
wurggb
rrrrrr
rrggbbrr
brr
rgb
"""


def parse_input(input):
    if Path(input).exists():
        with open(input) as f:
            input = f.read()
    patterns = []
    towels = []
    for line in input.strip().split("\n"):
        if "," in line:
            towels = line.split(", ")
        elif line == "":
            continue
        else:
            patterns.append(line)
    return towels, patterns


parse_input(example)

(['wub', 'ggb', 'rrggbb', 'rr', 'b'],
 ['ggbrrb', 'wurggb', 'rrrrrr', 'rrggbbrr', 'brr', 'rgb'])

def is_pattern_possible(towels, pattern):
    if pattern == "":
        return True
    
    possible_towels = [towel for towel in towels if pattern.startswith(towel)]
    matching_patterns = [pattern[len(towel):] for towel in possible_towels]

    if matching_patterns:
        return any(is_pattern_possible(towels, pattern) for pattern in matching_patterns)
    else:
        return False

def part_one(input):
    towels, patterns = parse_input(input)
    return sum(is_pattern_possible(towels, pattern) for pattern in patterns)

verify_answer(part_one, example, 4)

✔️ That's right! The answer is 4.

verify_answer(part_one, example_input_file, 6)

✔️ That's right! The answer is 6.

%time part_one(input_file)

CPU times: user 50.8 ms, sys: 2.03 ms, total: 52.9 ms
Wall time: 58.8 ms

296

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Part 2: All the patterns!

The staff is not in love with just one option to arrange the towels into patterns. They want to know all the possible patterns that can be assembled from the given set of towels.

Since this time we need to count all the possible patterns, we need to be more careful about the

def all_possible_patterns(towels, pattern, cache=None):
    # create a cache to store the results of already calculated patterns
    # this is created here instead of cache={} in the function signature
    # to avoid mutable default arguments
    if cache is None:
        cache = {}

    # if we have already calculated the result for this pattern, return it
    if pattern in cache:
        return cache[pattern]

    # if the pattern is empty, we have found a valid pattern
    if pattern == "":
        return 1  

    possible_towels = [towel for towel in towels if pattern.startswith(towel)]
    matching_patterns = [pattern[len(towel) :] for towel in possible_towels]

    if matching_patterns:
        result = sum(
            all_possible_patterns(towels, subpattern, cache)
            for subpattern in matching_patterns
        )
    else:
        result = 0

    # cache the result to only test subpatterns once
    cache[pattern] = result

    return result


def part_two(input):
    towels, patterns = parse_input(input)
    return sum(all_possible_patterns(towels, pattern) for pattern in patterns)

verify_answer(part_two, example, 5)

✔️ That's right! The answer is 5.

verify_answer(part_two, example_input_file, 16)

✔️ That's right! The answer is 16.

%time part_two(input_file)

CPU times: user 112 ms, sys: 3.69 ms, total: 116 ms
Wall time: 123 ms

619970556776002

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.