Sean McLemon | Advent of Code

2021-12-16 - Packet Decoder

(original .ipynb)

Day 16 puzzle input is a sequence of hex digits which represent a nested structure of packets (mine is here). Part 1 involves doing parsing and expanding the nested packets, retrieving the "version" and summing this for each packet. Part 2 involves fully parsing the packets, interpreting them as mathematical operators finding the value of the calculation the input represents.

puzzle_input_str = open("puzzle_input/day16.txt").read()


def chunks(l, n):
    for i in range(0, len(l), n): 
        yield l[i:i + n]

        
def decode_input(input_str):
    bit_chunks = []
    for chunk in chunks(input_str, 2):
        bit_string = bin(int(chunk, 16))[2:]
        padding = "0" * (8 - len(bit_string))
        bit_chunks.append(padding + bit_string)
    
    return "".join(bit_chunks)


def parse_literal(packet_version, body):
    bit_chunks = []
    for chunk in chunks(body, 5):
        keep_going = chunk[0]
        chunk_bits = chunk[1:]
        bit_chunks.append(chunk_bits)
        if keep_going == "0":
            break
    
    literal = "".join(bit_chunks)
    bits_read = len(literal) + len(literal)//4
    return (packet_version, 4, int(literal, 2), []), body[bits_read:]


def parse_operator(packet_version, packet_type_id, body):
    bit_mode_length = body[0] == "0" 
    length_bits = 15 if bit_mode_length else 11
    length = int(body[1:1+length_bits], 2)
    packets = []
    body = body[1+length_bits:]
    
    while length != 0:
        packet, rest = parse_packet(body)    
        packet_length = len(body) - len(rest)
        packets.append(packet)
        body = rest
        if bit_mode_length:
            length -= packet_length            
        else:
            length -= 1
        
    return (packet_version, packet_type_id, None, packets), body            


def parse_packet(packet):
    packet_version = int(packet[ :3], 2)
    packet_type_id = int(packet[3:6], 2)
    packet_body = packet[6:]
    
    if packet_type_id == 4:
        return parse_literal(packet_version, packet_body)
    else:
        return parse_operator(packet_version, packet_type_id, packet_body)
    
    
def sum_versions(packet):
    version, type_id, value, subpackets = packet
    return version + sum(versions(p) for p in subpackets)


def part_one(input_str):
    packet_bits = decode_input(input_str)    
    packet, _ = parse_packet(packet_bits)
    return versions(packet)


assert 16 == part_one("8A004A801A8002F478")
assert 12 == part_one("620080001611562C8802118E34")
assert 23 == part_one("C0015000016115A2E0802F182340")
assert 31 == part_one("A0016C880162017C3686B18A3D4780")

print("part one:", part_one(puzzle_input_str))

part one: 920

from functools import reduce

op = [
    lambda packets,v: sum(evaluate(p) for p in packets),
    lambda packets,v: reduce(lambda a,b:a*b, (evaluate(p) for p in packets)),
    lambda packets,v: min(evaluate(p) for p in packets),
    lambda packets,v: max(evaluate(p) for p in packets),
    lambda packets,v: v,
    lambda packets,v: 1 if evaluate(packets[0]) > evaluate(packets[1]) else 0,
    lambda packets,v: 1 if evaluate(packets[0]) < evaluate(packets[1]) else 0,
    lambda packets,v: 1 if evaluate(packets[0]) == evaluate(packets[1]) else 0
]

def evaluate(packet):
    version, type_id, value, subpackets = packet
    return op[type_id](subpackets, value)


def part_two(input_str):
    packet_bits = decode_input(input_str)    
    packet, _ = parse_packet(packet_bits)
    return evaluate(packet)


assert 3 == part_two("C200B40A82")
assert 7 == part_two("880086C3E88112")
assert 9 == part_two("CE00C43D881120")
assert 1 == part_two("D8005AC2A8F0")
assert 0 == part_two("9C005AC2F8F0")
assert 1 == part_two("9C0141080250320F1802104A08")

print("part two:", part_two(puzzle_input_str))

part two: 10185143721112