Something went wrong. Try again.
My Advent of Code solutions in Python. kevinyap.ca/2019/12/going-fast-in-advent-of-code
advent-of-code python
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154import fileinputfrom utils import mul
HEX_MAPPING = { '0': '0000', '1': '0001', '2': '0010', '3': '0011', '4': '0100', '5': '0101', '6': '0110', '7': '0111', '8': '1000', '9': '1001', 'A': '1010', 'B': '1011', 'C': '1100', 'D': '1101', 'E': '1110', 'F': '1111',}
OPERATORS = { 0: '+', 1: '*', 2: 'min', 3: 'max', 5: '>', 6: '<', 7: '=='}
def parse_packets(bits, num_subpackets=None, bit_length=None, depth=0, quiet=False): """ Given a bitstring `bits`, parses `num_subpackets` subpackets, and returns ([packets], bit_length, version).
If the argument `num_subpackets` is given, this dictates the number of packets to parse from `bits` before returning.
If the argument `bit_length` is given, this dictates how many bits to process before returning however many packets the parser got through.
If `quiet` is False, the parser will print the operator and values processed, with various nesting levels based on `depth` (incremented per recursive call). """
i = 0 # current pointer into `bits` subs = [] # list of subpackets currently parsed version = 0 # the version so far (?)
try: while True: # Standard Packet Header
# Read 3-bit version version += int(bits[i:i+3], 2) i += 3
# Read 3-bit type ID ttype = int(bits[i:i+3], 2) i += 3
# Packets with type ID 4 represent a literal value. if ttype == 4: lit = ''
# Read groups of 5 bits until the final group # (prefixed 0) is seen. Then stop reading. while True: group = bits[i:i+5] i += 5 lit += group[1:] if group[0] == '0': break
try: lit = int(lit, 2) subs.append(lit) except Exception: print "bad literal, moving on"
# Otherwise, process an operator. else: # Operator packet mode is based on its 1-bit length type ID. len_type_id = bits[i] i += 1
# Specifies the bit length of contained subpackets. if len_type_id == '0': sub_len = int(bits[i:i+15], 2) i += 15 subpackets, new_i, new_version = parse_packets(bits[i:i+sub_len], bit_length=sub_len, depth=depth + 1, quiet=quiet)
i += new_i version += new_version
# Specifies total number of subpackets. elif len_type_id == '1': sub_packets = int(bits[i:i+11], 2) i += 11 subpackets, new_i, new_version = parse_packets(bits[i:], num_subpackets=sub_packets, depth=depth+1, quiet=quiet)
i += new_i version += new_version else: print "Unknown length type ID"
# Process operators if not quiet: print " " * depth, OPERATORS[ttype], subpackets
if ttype == 0: subs.append(sum(subpackets)) elif ttype == 1: subs.append(mul(subpackets)) elif ttype == 2: subs.append(min(subpackets)) elif ttype == 3: subs.append(max(subpackets)) elif ttype == 5: subs.append(1 if subpackets[0] > subpackets[1] else 0) elif ttype == 6: subs.append(1 if subpackets[0] < subpackets[1] else 0) elif ttype == 7: subs.append(1 if subpackets[0] == subpackets[1] else 0)
# Check exit conditions for loop. if num_subpackets is not None and len(subs) == num_subpackets: # IMPORTANT: return i and not len(i); it is not an invariant # that we read the full `bits`, since there may have been # some trailing data that we ignore since it falls out of # the range of `num_subpackets` subpackets. return subs, i, version elif bit_length is not None and i > bit_length: return subs, len(bits), version elif i >= len(bits): return subs, len(bits), version
except Exception as e: print "Unexpected parsing error:", e return subs, i, version
# Read problem input.BITS = ''.join(HEX_MAPPING[byte] for byte in fileinput.input()[0].strip())
# Problem guarantees the input consists of precisely 1 outer packet.packets, _, total_version = parse_packets(BITS, num_subpackets=1, quiet=True)
print "Part 1:", total_versionprint "Part 2:", packets[0]