AdventOfCode2021/day16_task2.py at master · HenrikSZ/AdventOfCode2021 · 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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
###############################################################################
# Day x, Task y                                                               #
###############################################################################

import aoc_util, sys


day = 16
data_str = """880086C3E88112"""


class BitParser():
    def __init__(self, string):
        self.string = string
        self.int_bit_count = 0
        self.index = 0
        self.parsed_bits_count = 0
        self.current_hex = int(string[self.index], base=16)


    def get_next_n_bits(self, n: int) -> int:
        acc = 0
        while n > 0:
            if self.int_bit_count == 4:
                self.int_bit_count = 0
                self.index += 1
                self.current_hex = int(self.string[self.index], base=16)

            significant_bit = self.current_hex & 0b1000
            significant_bit >>= 3

            acc <<= 1
            acc |= significant_bit

            self.current_hex <<= 1
            self.int_bit_count += 1
            n -= 1
            self.parsed_bits_count += 1

        return acc


    def get_parsed_bits_count(self) -> int:
        return self.parsed_bits_count


class Packet():
    def add_version_numbers(self) -> int:
        return 0


    def evaluate(self) -> int:
        return 0


class LiteralPacket(Packet):
    def __init__(self, version, bit_parser):
        self.version = version
        self.value = 0
        while 1:
            bits = bit_parser.get_next_n_bits(5)
            self.value <<= 4
            self.value |= bits & 0b01111
            if (bits & 0b10000) == 0b00000:
                break


    def add_version_numbers(self) -> int:
        return self.version


    def evaluate(self) -> int:
        return self.value


class OperatorPacket(Packet):
    def __init__(self, version: int, type: int, bit_parser: BitParser):
        self.version = version
        self.type = type
        self.packet_list: list[Packet] = []

        self.length_type = bit_parser.get_next_n_bits(1)
        if self.length_type == 1:
            sub_packet_num = bit_parser.get_next_n_bits(11)
            for _ in range(sub_packet_num):
                self.packet_list.append(parse_packet(bit_parser))
        else:
            sub_packet_len = bit_parser.get_next_n_bits(15)
            pre_parser_count = bit_parser.get_parsed_bits_count()
            while bit_parser.get_parsed_bits_count() - pre_parser_count < sub_packet_len:
                self.packet_list.append(parse_packet(bit_parser))


    def add_version_numbers(self) -> int:
        acc = self.version
        for packet in self.packet_list:
            acc += packet.add_version_numbers()

        return acc


    def evaluate(self) -> int:
        if self.type == 0:
            acc = 0
            for p in self.packet_list:
                acc += p.evaluate()

            return acc

        elif self.type == 1:
            acc = 1
            for p in self.packet_list:
                acc *= p.evaluate()

            return acc

        elif self.type == 2:
            min_val = sys.maxsize
            for p in self.packet_list:
                val = p.evaluate()
                if val < min_val:
                    min_val = val

            return min_val

        elif self.type == 3:
            max_val = 0
            for p in self.packet_list:
                val = p.evaluate()
                if val > max_val:
                    max_val = val

            return max_val

        elif self.type == 5:
            return 1 if self.packet_list[0].evaluate() > self.packet_list[1].evaluate() else 0

        elif self.type == 6:
            return 1 if self.packet_list[0].evaluate() < self.packet_list[1].evaluate() else 0

        elif self.type == 7:
            return 1 if self.packet_list[0].evaluate() == self.packet_list[1].evaluate() else 0


def parse_packet(bit_parser: BitParser) -> Packet:
    version = bit_parser.get_next_n_bits(3)
    type = bit_parser.get_next_n_bits(3)
    if type == 4:
        return LiteralPacket(version, bit_parser)
    else:
        return OperatorPacket(version, type, bit_parser)


def task(data_set: list[str]) -> int:
    bit_parser = BitParser(data_set[0])
    packet = parse_packet(bit_parser)

    return packet.evaluate()


aoc_util.run_with_data_str(task, data_str)
aoc_util.run_with_data_set(task, day)