advent-of-code-2023/13-2.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
import sys
import pytest
from pathlib import Path
from textwrap import dedent


def find_middle(pattern: list[int], no_valid: int) -> int:
    for i in range(len(pattern) - 1):
        index = len(pattern) - i - 1
        start = index
        if start == no_valid:
            continue
        end = min((len(pattern) - index), index)
        for j in range(index, index + end):
            index -= 1
            if pattern[j] != pattern[index]:
                break
        else:
            return start
    return -1


def get_result(pattern: list[str]) -> int:
    vertical = []
    for j in range(len(pattern[0])):
        n = 0
        for i in range(len(pattern)):
            if pattern[i][j] == "#":
                n += 2**i
        vertical.append(n)

    original_index = find_middle(vertical, -1)
    for i in range(len(vertical)):
        original = vertical[i]
        for j in range(len(pattern)):
            # Flip bit
            vertical[i] = original ^ 2**j
            index = find_middle(vertical, original_index)
            if index != -1:
                return index
        vertical[i] = original

    horizontal = []
    for i in range(len(pattern)):
        n = 0
        for j in range(len(pattern[0])):
            if pattern[i][j] == "#":
                n += 2**j
        horizontal.append(n)

    original_index = find_middle(horizontal, -1)
    for i in range(len(horizontal)):
        original = horizontal[i]
        for j in range(len(pattern[0])):
            # Flip bit
            horizontal[i] = original ^ 2**j
            index = find_middle(horizontal, original_index)
            if index != -1:
                return index * 100
        horizontal[i] = original

    return 0


def solve(text: str) -> int:
    total = 0
    for patter in text.split("\n\n"):
        total += get_result(patter.splitlines())

    return total


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


def test():
    text = dedent(
        """
        #.##..##.
        ..#.##.#.
        ##......#
        ##......#
        ..#.##.#.
        ..##..##.
        #.#.##.#.

        #...##..#
        #....#..#
        ..##..###
        #####.##.
        #####.##.
        ..##..###
        #....#..#
        """
    ).strip()
    assert solve(text) == 400


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