commit dbeaa80a09e9536763b9d43aec12634492148d3f
parent 5478829a2bdfece833624da2f20828451d70702e
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Thu, 16 Dec 2021 15:23:41 -0500
Solution to day 16, part 1
Diffstat:
| A | day16_classes.py | | | 87 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | day16_part1.py | | | 28 | ++++++++++++++++++++++++++++ |
2 files changed, 115 insertions(+), 0 deletions(-)
diff --git a/day16_classes.py b/day16_classes.py
@@ -0,0 +1,87 @@
+"""Class definitions for day 16 problems (and maybe other days, we'll see)"""
+# I'm finally breaking down and doing OOP.
+
+from typing import List, Union
+
+class BitReader:
+ """BitReader objects facilitate reading bits a few at a time from a stream
+ of hexidecimal digits"""
+
+ def __init__(self, hex_stream: str):
+ # Store the data as a list of integers. Remember that each integer only
+ # represents four bits of data (even though it takes up 64 bits of RAM
+ # on my computer lol)
+ self.int_stream: List[int] = [int(c, base=16) for c in \
+ list(hex_stream.rstrip('\n'))]
+
+ # We'll maintain a current pointer that we advance as we read bits.
+ # Alan would be proud.
+ self.bit_pointer: int = 0
+
+ def read_one_bit(self) -> int:
+ """Return the bit at the pointer and advance the pointer"""
+ current_int, current_bit = divmod(self.bit_pointer, 4)
+ bit_mask = 1 << (3 - current_bit)
+ self.bit_pointer += 1
+ return int((self.int_stream[current_int] & bit_mask) > 0)
+
+ def read_bits(self, number_bits: int) -> int:
+ """Read n bits from the stream, returning the result as an integer"""
+ assert number_bits > 0
+ result: int = self.read_one_bit()
+ for _ in range(1, number_bits):
+ result = (result << 1) | self.read_one_bit()
+ return result
+
+def read_value_from_bitstream(bit_stream: BitReader) -> int:
+ """Read a _literal value_ from a bit stream and return an integer"""
+ # This is AoC, so the encoding of literal values is naturally weird. We
+ # read five bits at a time, and the first bit indicates whether we're done
+ # with the number. Why isn't this a method of one of the classes? I don't
+ # know. Didn't feel like it?
+ keep_going = True
+ result = 0
+ while keep_going:
+ bit_quintet = bit_stream.read_bits(5)
+ result = (result << 4) | (bit_quintet & 0b01111)
+ keep_going = (bit_quintet & 0b10000) > 0
+ return result
+
+class Packet:
+ """Packet objects encapsulate a version number, a type ID, and either
+ contain a value or one or more packets"""
+
+ def __init__(self, bit_stream: BitReader):
+ # We'll do all the work of parsing the tree of packets when we
+ # instantiate a packet
+ self.version: int = bit_stream.read_bits(3)
+ self.type_id: int = bit_stream.read_bits(3)
+ self.contents: List[Union[int, Packet]] = []
+
+ if self.type_id == 4:
+ # This is a literal value packet; reat the value and stop
+ self.contents.append(read_value_from_bitstream(bit_stream))
+
+ else:
+ # Check how the size of this packet is being represented
+ length_type_id = bit_stream.read_bits(1)
+
+ if length_type_id:
+ # The next 11 bits represents the number of packets inside this
+ # packet
+ num_packets = bit_stream.read_bits(11)
+ for _ in range(num_packets):
+ self.contents.append(Packet(bit_stream))
+ else:
+ # The next 15 bits gives the total length in bits of the
+ # subpackets inside this packet
+ num_bits = bit_stream.read_bits(15)
+ start_position = bit_stream.bit_pointer
+ while bit_stream.bit_pointer < (start_position + num_bits):
+ self.contents.append(Packet(bit_stream))
+
+ def version_sum(self) -> int:
+ """Return the sum of the version number of this packet, and all of its
+ children packets (if there are any)"""
+ return self.version + \
+ sum([p.version_sum() for p in self.contents if isinstance(p, Packet)])
diff --git a/day16_part1.py b/day16_part1.py
@@ -0,0 +1,28 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 16 (part 1): Packet Decoder
+Parsing packets using the Buoyancy Interchange Transmission System (BITS)"""
+
+# Okay, I finally made some custom classes to solve an AoC problem. I've heard
+# stories about the intcode computer stuff, and I figure this stuff might come
+# in handy in a future puzzle, but I didn't exactly _over_ engineer anything
+# either.
+
+from day16_classes import BitReader, Packet
+from utils import get_puzzle_input
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return Packet(BitReader(input_string)).version_sum()
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ assert solve_puzzle("8A004A801A8002F478") == 16
+ assert solve_puzzle("620080001611562C8802118E34") == 12
+ assert solve_puzzle("C0015000016115A2E0802F182340") == 23
+ assert solve_puzzle("A0016C880162017C3686B18A3D4780") == 31
+
+ print("Total packet version sum:",
+ solve_puzzle(get_puzzle_input(16)))
+
+if __name__ == "__main__":
+ main()
