aoc2024day19.py

# === Parsing ===

with open("input.txt", "r") as f:
    towels = tuple(f.readline().strip().split(", "))
    _ = f.readline()
    patterns = [line.strip() for line in f]


# === Part 1 ===


def build_pattern(pattern, segments):
    if not pattern:
        return True

    return any(
        build_pattern(pattern.removeprefix(segment), segments)
        for segment in segments
        if pattern.startswith(segment)
    )


print(sum(build_pattern(pattern, towels) for pattern in patterns))


# === Part 2 ===
from functools import cache


@cache
def count_pattern(pattern, segments):
    if not pattern:
        return 1

    return sum(
        count_pattern(pattern.removeprefix(segment), segments)
        for segment in segments
        if pattern.startswith(segment)
    )


print(sum(count_pattern(pattern, towels) for pattern in patterns))