1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
# i == current position within dots
# bi == current position within blocks
# current == length of current block of '#'
# state space is len(dots) * len(blocks) * len(dots)
DP = {}
def f(dots, blocks, i, bi, current):
key = (i, bi, current)
if key in DP:
return DP[key]
if i == len(dots):
if bi == len(blocks) and current == 0:
return 1
elif bi == len(blocks) - 1 and blocks[bi] == current:
return 1
else:
return 0
ans = 0
for c in [".", "#"]:
if dots[i] == c or dots[i] == "?":
if c == "." and current == 0:
ans += f(dots, blocks, i + 1, bi, 0)
elif (
c == "." and current > 0 and bi < len(blocks) and blocks[bi] == current
):
ans += f(dots, blocks, i + 1, bi + 1, 0)
elif c == "#":
ans += f(dots, blocks, i + 1, bi, current + 1)
DP[key] = ans
return ans
for part2 in [False, True]:
ans = 0
for line in L:
dots, blocks = line.split()
if part2:
dots = "?".join([dots, dots, dots, dots, dots])
blocks = ",".join([blocks, blocks, blocks, blocks, blocks])
blocks = [int(x) for x in blocks.split(",")]
DP.clear()
score = f(dots, blocks, 0, 0, 0)
ans += score
print(ans)
|