day12_part2.py

day12_part2.py

#!/usr/bin/env python3

from functools import cache

def solve(pattern: str, groups: list[int]) -> int:
    @cache
    def dp(start_pos: int, g: int) -> int:
        if start_pos == len(pattern):
            return int(g == len(groups))
        
        result = 0
        if pattern[start_pos] != '#':
            result += dp(start_pos + 1, g)
        
        try:
            end_pos = start_pos + groups[g]
            if not '.' in pattern[start_pos:end_pos] and pattern[end_pos] != '#':
                result += dp(end_pos + 1, g + 1)
        except IndexError:
            pass
    
        return result
    return dp(0, 0)


with open("input.txt") as f:
    ans = 0
    for line in f:
        pattern, groups = line.strip().split()
        groups = list(map(int, groups.split(','))) * 5

        pattern = "?".join([pattern] * 5)

        ans += solve(f"{pattern}.", groups)
    print(ans)