summaryrefslogtreecommitdiff
path: root/12_2023.py
blob: ce595095b998630bc877508a57a2b4e77b607da1 (plain)
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)