aoc/python/2021/day10.py at main · SylvainDe/aoc · 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
# vi: set shiftwidth=4 tabstop=4 expandtab:
import datetime
import os


top_dir = os.path.dirname(os.path.abspath(__file__)) + "/../../"


def get_lines_from_file(file_path=top_dir + "resources/year2021_day10_input.txt"):
    with open(file_path) as f:
        return [l.strip() for l in f]


opening = {"(": ")", "{": "}", "<": ">", "[": "]"}


def parse_string(s):
    """Return tupe (first invalid char (or None), expected stack (or empty))."""
    stack = list()
    for char in s:
        if char in opening:
            stack.append(opening[char])
        elif stack and stack[-1] == char:
            stack.pop()
        else:
            return char, []
    return None, stack


# Part 1 - corruption score
corruption_score = {
    ")": 3,
    "]": 57,
    "}": 1197,
    ">": 25137,
}


def get_corruption_score(s):
    invalid, _ = parse_string(s)
    return corruption_score.get(invalid, 0)


def get_corruption_final_score(lines):
    return sum(get_corruption_score(l) for l in lines)


# Part 2 - completion score
completion_score = {
    ")": 1,
    "]": 2,
    "}": 3,
    ">": 4,
}


def get_completion_score(s):
    _, stack = parse_string(s)
    return sum(completion_score[c] * 5**i for i, c in enumerate(stack))


def get_completion_final_score(lines):
    scores = [get_completion_score(l) for l in lines]
    scores = sorted([s for s in scores if s])
    return scores[len(scores) // 2]


def run_tests():
    lines = [
        "[({(<(())[]>[[{[]{<()<>>",
        "[(()[<>])]({[<{<<[]>>(",
        "{([(<{}[<>[]}>{[]{[(<()>",
        "(((({<>}<{<{<>}{[]{[]{}",
        "[[<[([]))<([[{}[[()]]]",
        "[{[{({}]{}}([{[{{{}}([]",
        "{<[[]]>}<{[{[{[]{()[[[]",
        "[<(<(<(<{}))><([]([]()",
        "<{([([[(<>()){}]>(<<{{",
        "<{([{{}}[<[[[<>{}]]]>[]]",
    ]
    assert get_corruption_final_score(lines) == 26397
    assert get_completion_score("[({(<(())[]>[[{[]{<()<>>") == 288957
    assert get_completion_score("<{([{{}}[<[[[<>{}]]]>[]]") == 294
    assert get_completion_final_score(lines) == 288957
    assert parse_string(")") == (")", [])


def get_solutions():
    lines = get_lines_from_file()
    print(get_corruption_final_score(lines) == 339411)
    print(get_completion_final_score(lines) == 2289754624)


if __name__ == "__main__":
    begin = datetime.datetime.now()
    run_tests()
    get_solutions()
    end = datetime.datetime.now()
    print(end - begin)