advent-of-code-2023/12.py at main · stsewd/advent-of-code-2023 · GitHub

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import sys
import pytest
from pathlib import Path
from textwrap import dedent


def get_valid_arrangements(
    acc: int,
    springs: str,
    spring_i: int,
    groups: list[int],
    group_i: int,
    spring: str | None = None,
) -> int:
    if spring_i >= len(springs):
        if acc:
            if group_i == len(groups) - 1 and acc == groups[group_i]:
                return 1
            return 0

        if group_i >= len(groups):
            return 1

        return 0

    spring = spring or springs[spring_i]
    if spring == ".":
        if acc:
            if group_i >= len(groups):
                return 0
            if acc != groups[group_i]:
                return 0
            return get_valid_arrangements(
                acc=0,
                springs=springs,
                spring_i=spring_i + 1,
                groups=groups,
                group_i=group_i + 1,
            )

        return get_valid_arrangements(
            acc=0,
            springs=springs,
            spring_i=spring_i + 1,
            groups=groups,
            group_i=group_i,
        )

    if spring == "#":
        if group_i >= len(groups):
            return 0
        return get_valid_arrangements(
            acc=acc + 1,
            springs=springs,
            spring_i=spring_i + 1,
            groups=groups,
            group_i=group_i,
        )

    if spring == "?":
        a = get_valid_arrangements(
            acc=acc,
            springs=springs,
            spring_i=spring_i,
            groups=groups,
            group_i=group_i,
            spring="#",
        )
        b = get_valid_arrangements(
            acc=acc,
            springs=springs,
            spring_i=spring_i,
            groups=groups,
            group_i=group_i,
            spring=".",
        )
        return a + b

    return 0


def solve(text: str) -> int:
    springs_and_groups = [line.split() for line in text.splitlines()]
    total = 0
    for springs, groups in springs_and_groups:
        groups = [int(x) for x in groups.split(",")]
        total += get_valid_arrangements(
            acc=0,
            springs=springs,
            spring_i=0,
            groups=groups,
            group_i=0,
        )
    return total


if __name__ == "__main__":
    p = Path(sys.argv[1])
    print(solve(p.read_text()))


def test():
    text = dedent(
        """
        ???.### 1,1,3
        .??..??...?##. 1,1,3
        ?#?#?#?#?#?#?#? 1,3,1,6
        ????.#...#... 4,1,1
        ????.######..#####. 1,6,5
        ?###???????? 3,2,1
        """
    ).strip()
    assert solve(text) == 21


def test_input():
    p = Path("12.txt")
    if not p.exists():
        pytest.skip(f"{p} does not exist")
    text = p.read_text()
    assert solve(text) == 6488