https://adventofcode.com/2023/day/12

day12.py

ans = 0
for l in open(0):
    P, G = l.split()
    G = tuple(map(int, G.split(',')))
    P, G = '?'.join([P]*5), G*5  # part 2
    P = P+'.'
    N, M = len(P), len(G)
    cdot = [P[i:].count('.') for i in range(N)]

    dp = [[0]*(M+1) for _ in range(N+1)]
    dp[N][M] = 1
    for i in range(N-1, -1, -1):
        for j in range(M, -1, -1):
            if P[i] in '.?': dp[i][j] += dp[i+1][j]
            if j==M or i+G[j]>=N: continue
            if P[i] in '#?' and cdot[i+G[j]]-cdot[i]==0 and P[i+G[j]]!='#':
                dp[i][j] += dp[i+G[j]+1][j+1]
    ans += dp[0][0]

print(ans)