day19/solution_gpt-4o.py

file = "input.txt"

def count_ways_to_construct(design, patterns):
    n = len(design)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: one way to construct the empty string

    for i in range(1, n + 1):
        for pattern in patterns:
            if design.startswith(pattern, i - len(pattern)):
                dp[i] += dp[i - len(pattern)]

    return dp[n]

def main():
    with open(file, 'r') as f:
        lines = f.read().strip().split('\n')
    
    # First line is the available towel patterns
    patterns = lines[0].split(', ')
    
    # Remaining lines are the desired designs
    designs = lines[2:]  # Skip the blank line after patterns

    total_ways = 0
    for design in designs:
        total_ways += count_ways_to_construct(design, patterns)

    print(total_ways)

main()