day16_classes.py (5286B)
1 """Class definitions for day 16 problems (and maybe other days, we'll see)""" 2 # I'm finally breaking down and doing OOP. 3 4 from typing import List, Union, cast 5 from functools import reduce 6 from operator import mul 7 8 class BitReader: 9 """BitReader objects facilitate reading bits a few at a time from a stream 10 of hexidecimal digits""" 11 12 def __init__(self, hex_stream: str): 13 # Store the data as a list of integers. Remember that each integer only 14 # represents four bits of data (even though it takes up 64 bits of RAM 15 # on my computer lol) 16 self.int_stream: List[int] = [int(c, base=16) for c in \ 17 list(hex_stream.rstrip('\n'))] 18 19 # We'll maintain a current pointer that we advance as we read bits. 20 # Alan would be proud. 21 self.bit_pointer: int = 0 22 23 def read_one_bit(self) -> int: 24 """Return the bit at the pointer and advance the pointer""" 25 current_int, current_bit = divmod(self.bit_pointer, 4) 26 bit_mask = 1 << (3 - current_bit) 27 self.bit_pointer += 1 28 return int((self.int_stream[current_int] & bit_mask) > 0) 29 30 def read_bits(self, number_bits: int) -> int: 31 """Read n bits from the stream, returning the result as an integer""" 32 assert number_bits > 0 33 result: int = self.read_one_bit() 34 for _ in range(1, number_bits): 35 result = (result << 1) | self.read_one_bit() 36 return result 37 38 def read_value_from_bitstream(bit_stream: BitReader) -> int: 39 """Read a _literal value_ from a bit stream and return an integer""" 40 # This is AoC, so the encoding of literal values is naturally weird. We 41 # read five bits at a time, and the first bit indicates whether we're done 42 # with the number. Why isn't this a method of one of the classes? I don't 43 # know. Didn't feel like it? 44 keep_going = True 45 result = 0 46 while keep_going: 47 bit_quintet = bit_stream.read_bits(5) 48 result = (result << 4) | (bit_quintet & 0b01111) 49 keep_going = (bit_quintet & 0b10000) > 0 50 return result 51 52 class Packet: 53 """Packet objects encapsulate a version number, a type ID, and either 54 contain a value or one or more packets""" 55 56 def __init__(self, bit_stream: BitReader): 57 # We'll do all the work of parsing the tree of packets when we 58 # instantiate a packet 59 self.version: int = bit_stream.read_bits(3) 60 self.type_id: int = bit_stream.read_bits(3) 61 self.contents: List[Union[int, Packet]] = [] 62 63 if self.type_id == 4: 64 # This is a literal value packet; reat the value and stop 65 self.contents.append(read_value_from_bitstream(bit_stream)) 66 67 else: 68 # Check how the size of this packet is being represented 69 length_type_id = bit_stream.read_bits(1) 70 71 if length_type_id: 72 # The next 11 bits represents the number of packets inside this 73 # packet 74 num_packets = bit_stream.read_bits(11) 75 for _ in range(num_packets): 76 self.contents.append(Packet(bit_stream)) 77 else: 78 # The next 15 bits gives the total length in bits of the 79 # subpackets inside this packet 80 num_bits = bit_stream.read_bits(15) 81 start_position = bit_stream.bit_pointer 82 while bit_stream.bit_pointer < (start_position + num_bits): 83 self.contents.append(Packet(bit_stream)) 84 85 def version_sum(self) -> int: 86 """Return the sum of the version number of this packet, and all of its 87 children packets (if there are any)""" 88 return self.version + \ 89 sum([p.version_sum() for p in self.contents if isinstance(p, Packet)]) 90 91 def operation_result(self) -> int: 92 """Perform the operation encoded in the current packet and return its 93 result""" 94 result: int = 0 95 96 if self.type_id == 4: 97 # Literal value packet: return the value 98 result = cast(int, self.contents[0]) 99 100 else: 101 # We'll process all of this operator packet's children 102 child_results = [p.operation_result() for p in self.contents \ 103 if isinstance(p, Packet)] 104 105 if self.type_id == 0: 106 # sum Packet: return the sum of all subpackets 107 result = sum(child_results) 108 109 elif self.type_id == 1: 110 # product Packet 111 result = reduce(mul, child_results) 112 113 elif self.type_id == 2: 114 # minimum Packet 115 result = min(child_results) 116 117 elif self.type_id == 3: 118 # maximum Packet 119 result = max(child_results) 120 121 elif self.type_id == 5: 122 # greater than Packet: 1 if the first subpacket is greater than 123 # the second, otherwise 0 124 result = int(child_results[0] > child_results[1]) 125 126 elif self.type_id == 6: 127 # less than Packet 128 result = int(child_results[0] < child_results[1]) 129 130 else: 131 # equal Packet 132 result = int(child_results[0] == child_results[1]) 133 134 return result