day19/solution_claude-3-5-sonnet-20241022.py

def can_make_design(design, patterns, memo=None, start=0):
    if memo is None:
        memo = {}
    
    if start in memo:
        return memo[start]
    
    if start == len(design):
        return 1
    
    total = 0
    for pattern in patterns:
        if start + len(pattern) <= len(design):
            if design[start:start+len(pattern)] == pattern:
                total += can_make_design(design, patterns, memo, start + len(pattern))
    
    memo[start] = total
    return total

def parse_input(filename):
    with open(filename, 'r') as f:
        lines = f.read().strip().split('\n')
    
    # Find the blank line
    separator_index = lines.index('')
    
    # Parse patterns
    patterns = [p.strip() for p in lines[0].split(',')]
    
    # Parse designs
    designs = lines[separator_index+1:]
    
    return patterns, designs

def solve_part1(patterns, designs):
    possible = 0
    for design in designs:
        if can_make_design(design, patterns) > 0:
            possible += 1
    return str(possible)

def solve_part2(patterns, designs):
    total = 0
    for design in designs:
        ways = can_make_design(design, patterns)
        total += ways
    return str(total)

# Read input and solve
patterns, designs = parse_input("input.txt")

# Part 1
print(solve_part1(patterns, designs))

# Part 2
print(solve_part2(patterns, designs))