Advent Of Code 2024 Day 19

from pathlib import Path
from functools import cache


def parse(input: str) -> tuple[set[str], list[str]]:
    lines = input.splitlines()
    towels = [s.strip() for s in lines[0].split(",")]
    return set(towels), lines[2:]


def part1(towels: set[str], patterns: list[str]) -> int:
    @cache
    def can_solve(pattern: str) -> bool:
        if not pattern:
            return True
        for i in range(1, len(pattern) + 1):
            t = pattern[:i]
            if t in towels and can_solve(pattern[i:]):
                return True
        return False

    return sum(1 if can_solve(p) else 0 for p in patterns)


TEST_TOWELS, TEST_PATTERNS = parse(Path("input/day19-test.txt").read_text())
assert part1(TEST_TOWELS, TEST_PATTERNS) == 6

INPUT_TOWELS, INPUT_PATTERNS = parse(Path("input/day19.txt").read_text())
part1_total = part1(INPUT_TOWELS, INPUT_PATTERNS)
print(f"{part1_total=:,}")


def part2(towels: set[str], patterns: list[str]) -> int:
    longest_towel = max(len(t) for t in towels)

    @cache
    def solve(pattern: str) -> int:
        if not pattern:
            return 1
        solutions = 0
        for i in range(1, min(longest_towel, len(pattern)) + 1):
            t = pattern[:i]
            if t in towels:
                solutions += solve(pattern[i:])
        return solutions

    return sum(solve(p) for p in patterns)


assert part2(TEST_TOWELS, TEST_PATTERNS) == 16

part2_total = part2(INPUT_TOWELS, INPUT_PATTERNS)
print(f"{part2_total=:,}")  # 572,248,688,842,069