Day 16: Packet Decoder

I messed around a little bit with bitwise operators, but quickly decided that it'd be simpler to just convert the whole input to a string of '1's and '0's and work with that. I couldn't just use hex.to_i(16).to_s(2), because I'd lose the leading zeros that are actually important, so I use the string interpolation/formatter to make sure that the string is 0-padded to the right multiple of 4.

def hex_to_bitstr(hex)
  "%0#{hex.length * 4}b" % hex.to_i(16)
end

Once we have the bit-string in memory, it's not hard to write the helpers for packet version and type, as well as the logic to read groups of bits for the variable-length literal values.

def parse_packet_version(bitstr)
  bitstr[0..2].to_i(2)
end

def parse_packet_type(bitstr)
  bitstr[3..5].to_i(2)
end

def parse_literal_groups(bitstr, offset)
  value = ''
  idx = offset
  loop do
    group = bitstr[idx..idx+4]
    value += group[1..]
    idx += 5
    break if group[0] == '0'
  end
  [value.to_i(2), idx-offset]
end

Note that parse_literal_groups returns the parsed value, and also the number of bits used. This is important later when we need to know where a packet ends.

This gives us enough to parse a complete "type 4"/literal packet:

def parse_literal_packet(bitstr, offset)
  ver = parse_packet_version(bitstr[offset..])
  typ = parse_packet_type(bitstr[offset..])
  raise "Tried to parse packet-type #{typ} as literal!" unless typ == 4

  value, value_size = parse_literal_groups(bitstr, offset+6)
  [{version: ver, type: :literal, value: value, size: value_size+6}, value_size+6]
end

Here we take an offset/index into the bit-string and use the helpers to parse out the fields of the packet, keeping track of how many bits we've used so that we can return the full size of the packet along with a hash object representing its properties.

Next up are "operator" packets, which are a little more complex since we need to account for nested packets (and two different ways to encode the number/size of those packets).

def parse_operator_packet(bitstr, offset)
  ver = parse_packet_version(bitstr[offset..])
  typ = parse_packet_type(bitstr[offset..])
  raise "Tried to parse literal packet (#{typ}) as operator!" if typ == 4

  op = case typ
       when 0 then :sum
       when 1 then :product
       when 2 then :minimum
       when 3 then :maximum
       when 5 then :greater_than
       when 6 then :less_than
       when 7 then :equal_to
       end

  base = offset
  offset+=6
  length_mode, length_length = case bitstr[offset]
                               when '0' then [:len_bits, 15]
                               when '1' then [:len_packets, 11]
                               end
  offset+=1

  length = bitstr[offset...offset+length_length].to_i(2)
  offset+=length_length

  packets = case length_mode
            when :len_bits then parse_packets_bits(bitstr, offset, length)
            when :len_packets then parse_packets_count(bitstr, offset, length)
            end
  offset+=packets.map {_1[:size]}.sum

  [{version: ver, type: :operator, op: op, packets: packets, size: offset-base}, offset-base]
end

def parse_packets_bits(bitstr, offset, num_bits)
  packets = []
  while num_bits > 0 && offset < bitstr.length
    packet, size = parse_packet(bitstr, offset)
    packets << packet
    num_bits -= size
    offset += size
  end
  return packets
end

def parse_packets_count(bitstr, offset, num_packets)
  packets = []
  while num_packets > 0 && offset < bitstr.length
    packet, size = parse_packet(bitstr, offset)
    packets << packet
    num_packets -= 1
    offset+=size
  end
  packets
end

def parse_packet(bitstr, offset)
  case parse_packet_type(bitstr[offset..])
  when 4
    parse_literal_packet(bitstr, offset)
  else
    parse_operator_packet(bitstr, offset)
  end
end

Note that now we can actually define a general top-level parse_packet function that can be used for any kind of packet.

def version_sum(packet)
  case packet[:type]
  when :literal then packet[:version]
  when :operator then packet[:version] + packet[:packets].reduce(0) { |sum, sub_pkt| sum + version_sum(sub_pkt) }
  end
end

def compute_p1(input)
  packet, _size = parse_packet(hex_to_bitstr(input.chomp), 0)
  version_sum(packet)
end

def compute_p2(input)
  packet, _size = parse_packet(hex_to_bitstr(input.chomp), 0)
  evaluate(packet)
end

def evaluate(packet)
  case packet[:type]
  when :literal then packet[:value]
  when :operator then case packet[:op]
                      when :sum then packet[:packets].map { evaluate(_1) }.inject(&:+)
                      when :product then packet[:packets].map { evaluate(_1) }.inject(&:*)
                      when :minimum then packet[:packets].map { evaluate(_1) }.min
                      when :maximum then packet[:packets].map { evaluate(_1) }.max
                      when :greater_than
                        values = packet[:packets].map { evaluate(_1) }
                        values[0] > values[1] ? 1 : 0
                      when :less_than
                        values = packet[:packets].map { evaluate(_1) }
                        values[0] < values[1] ? 1 : 0
                      when :equal_to
                        values = packet[:packets].map { evaluate(_1) }
                        values[0] == values[1] ? 1 : 0
                      else
                        raise "unknown operator type #{packet[:op]}"
                      end
  end
end

I built a recursive read packet function that basically returns anything it doesn't use. Just sliced everything up with a bunch of string manipulation and walked my way through the nested packets

import re
from collections import defaultdict

#data = test_data
data = real_data

data_len = len(data)

data = bin(int(data,16))[2:]
data = data.zfill(data_len*4)

#print(data)
#print(int(data[0:3],2))
#print(int(data[3:6],2))

version_num_sum = 0

def read_packet(packet):
    print("--------------")
    print("Packet: ", packet)
    if not packet or len(packet) < 11: #figure out what this number should be
        return ""
    #reads a single packet and subpackets. Returns any leftover bits
    version = int(packet[0:3],2)
    global version_num_sum
    version_num_sum = version_num_sum + version
    identity = int(packet[3:6],2)
    payload = packet[6:]
    
    print("Version: ", version)
    print("Identity: ", identity)
    print("Payload: ", payload)
    
    if identity == 4: #literal packet
        keep_reading = True
        bin_number = ""
        while keep_reading:
            segment = payload[0:5]
            payload = payload[5:]
            bin_number = bin_number + segment[1:]
            if segment[0] == '0':
                keep_reading = False
        print("Literal Value: ", int(bin_number, 2))
        return payload
        
    else: #operator packet
        length_id = payload[0]
        payload = payload[1:]
        if length_id == '0': #next 15 bits list total length in bits of subpackets
            num_subpacket_bits = int(payload[:15],2)
            payload = payload[15:]
            sub_payload = payload[:num_subpacket_bits]
            while sub_payload and len(sub_payload) > 0:
                print("Sub Packet:", sub_payload)
                sub_payload = read_packet(sub_payload)
            return payload[num_subpacket_bits:]
        else: #next 11 bits list number of sub packets
            num_subpackets = int(payload[:11],2)
            payload = payload[11:]
            for i in range(num_subpackets):
                print("Sub Packet:", payload)
                payload = read_packet(payload)
            return payload

                

read_packet(data)
        
print(version_num_sum)

Part A left me in a really good position, I just updated my return functions to pass the values between the levels, gathered them for anything with sub packets and added the operation to the end so that it could work with any gathered subpackets. It worked great

import re
from collections import defaultdict

#data = test_data
data = real_data

data_len = len(data)

data = bin(int(data,16))[2:]
data = data.zfill(data_len*4)

#print(data)
#print(int(data[0:3],2))
#print(int(data[3:6],2))

def read_packet(packet):
    #print("--------------")
    #print("Packet: ", packet)
    if not packet or len(packet) < 11: #figure out what this number should be
        return "", None
    #reads a single packet and subpackets. Returns any leftover bits
    version = int(packet[0:3],2)
    global version_num_sum
    identity = int(packet[3:6],2)
    payload = packet[6:]
    
    #print("Version: ", version)
    #print("Identity: ", identity)
    #print("Payload: ", payload)
    
    if identity == 4: #literal packet
        keep_reading = True
        bin_number = ""
        while keep_reading:
            segment = payload[0:5]
            payload = payload[5:]
            bin_number = bin_number + segment[1:]
            if segment[0] == '0':
                keep_reading = False
        #print("Literal Value: ", int(bin_number, 2))
        value = int(bin_number, 2)
        return payload, value
        
    else: #operator packet
        length_id = payload[0]
        payload = payload[1:]
        values = []
        if length_id == '0': #next 15 bits list total length in bits of subpackets
            num_subpacket_bits = int(payload[:15],2)
            payload = payload[15:]
            sub_payload = payload[:num_subpacket_bits]
            while sub_payload and len(sub_payload) > 0:
                #print("Sub Packet:", sub_payload)
                sub_payload, val = read_packet(sub_payload)
                values.append(val)
            payload =  payload[num_subpacket_bits:]
        else: #next 11 bits list number of sub packets
            num_subpackets = int(payload[:11],2)
            payload = payload[11:]
            for i in range(num_subpackets):
                #print("Sub Packet:", payload)
                payload, val = read_packet(payload)
                values.append(val)
        if identity == 0: #Sum
            value = sum(values)
        elif identity == 1: #Product
            value = 1
            for val in values:
                value = value * val
        elif identity == 2:
            value = min(values)
        elif identity == 3:
            value = max(values)
        elif identity == 5: #greater than
            if values[0] > values[1]:
                value = 1
            else:
                value = 0
        elif identity == 6: #less than
            if values[0] < values[1]:
                value = 1
            else:
                value = 0
        elif identity == 7: #equal to
            if values[0] == values[1]:
                value = 1
            else:
                value = 0
        return payload, value

                

remaining, result = read_packet(data)
        
print(result)

• It took me several reads to figure out what the hell the problem was asking and how to divide up sub packets. I particularly got stuck on the "38006F45291200" example. The first 11 bits are a fully formed packet and the next 16 are what's left over. And you can tell the difference between them because the first one ends

• For the most part you can't tell how long a packet is until you're done reading it. You need a way to keep track of what is and isn't being used so you don't lose what you're not looking at at the moment

• Make sure not to lose track of your leading zeros when you convert from hex to binary. It will definitely mess up your results, if you do lose them you should be able to add them back in

• For me, recursion handled the bulk of traveling between different packet levels.

• For part B, each packet will only ever pass one value up

• I think this code will get expanded upon in later challenges, but I'm not sure

defmodule AdventOfCode.Solution.Year2021.Day16 do
  def part1(input) do
    input
    |> String.trim()
    |> hex_to_bitstring()
    |> parse()
    |> version_sum()
  end

  def part2(input) do
    input
    |> String.trim()
    |> hex_to_bitstring()
    |> parse()
    |> eval()
  end

  defp parse(packet) do
    elem(do_parse(packet), 0)
  end

  defp do_parse(packet, packets_remaining \\ 1, parsed \\ [])

  # base case for parsing a specific length of bits
  defp do_parse(<<>>, _, parsed) do
    {Enum.reverse(parsed), <<>>}
  end

  # base case for parsing a specific number of packets
  defp do_parse(rest, 0, parsed) do
    {Enum.reverse(parsed), rest}
  end

  # literal
  defp do_parse(<<version::3, 4::3, literal::bits>>, packets_remaining, parsed) do
    {n, rest} = parse_literal(literal)
    do_parse(rest, packets_remaining - 1, [{:literal, n, version} | parsed])
  end

  # operator - total bit length
  defp do_parse(
         <<version::3, type::3, 0::1, len::15, packets::bits-size(len), rest::bits>>,
         packets_remaining,
         parsed
       ) do
    {parsed_sub_packets, <<>>} = do_parse(packets, -1)
    do_parse(rest, packets_remaining - 1, [{get_op(type), parsed_sub_packets, version} | parsed])
  end

  # operator - packet count
  defp do_parse(
         <<version::3, type::3, 1::1, sub_packet_count::11, sub_packets::bits>>,
         packets_remaining,
         parsed
       ) do
    {parsed_sub_packets, rest} = do_parse(sub_packets, sub_packet_count)
    do_parse(rest, packets_remaining - 1, [{get_op(type), parsed_sub_packets, version} | parsed])
  end

  defp parse_literal(literal, acc \\ [])

  defp parse_literal(<<0::1, last_part::4, rest::bits>>, acc) do
    literal_bits =
      [<<last_part::4>> | acc]
      |> Enum.reverse()
      |> :erlang.list_to_bitstring()

    n_size = bit_size(literal_bits)

    <<n::size(n_size)>> = literal_bits

    {n, rest}
  end

  defp parse_literal(<<1::1, n_part::4, rest::bits>>, acc) do
    parse_literal(rest, [<<n_part::4>> | acc])
  end

  for {op, id} <- [sum: 0, product: 1, min: 2, max: 3, gt: 5, lt: 6, eq: 7] do
    defp get_op(unquote(id)), do: unquote(op)
  end

  defp version_sum(parsed) do
    Enum.reduce(parsed, 0, fn
      {:literal, _n, version}, acc -> acc + version
      {_op, nested, version}, acc -> acc + version + version_sum(nested)
    end)
  end

  defp eval([expr]), do: eval(expr)

  defp eval({:literal, n, _}), do: n

  for {op, math_fun} <- [
        sum: &Enum.sum/1,
        product: &Enum.product/1,
        min: &Enum.min/1,
        max: &Enum.max/1
      ] do
    defp eval({unquote(op), args, _version}), do: unquote(math_fun).(Enum.map(args, &eval/1))
  end

  for {op, comp_fun} <- [gt: &Kernel.>/2, lt: &Kernel.</2, eq: &Kernel.==/2] do
    defp eval({unquote(op), [arg1, arg2], _version}),
      do: if(unquote(comp_fun).(eval(arg1), eval(arg2)), do: 1, else: 0)
  end

  defp hex_to_bitstring(input, acc \\ [])

  defp hex_to_bitstring(<<>>, acc) do
    acc
    |> Enum.reverse()
    |> :erlang.list_to_bitstring()
  end

  defp hex_to_bitstring(<<hex_digit::bytes-size(1), rest::bytes>>, acc) do
    hex_to_bitstring(rest, [<<String.to_integer(hex_digit, 16)::4>> | acc])
  end
end

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum PacketType {
    Literal,
    Sum,
    Product,
    Minimum,
    Maximum,
    GreaterThan,
    LessThan,
    EqualTo,
}

impl From<u8> for PacketType {
    fn from(t: u8) -> Self {
        match t {
            0 => PacketType::Sum,
            1 => PacketType::Product,
            2 => PacketType::Minimum,
            3 => PacketType::Maximum,
            4 => PacketType::Literal,
            5 => PacketType::GreaterThan,
            6 => PacketType::LessThan,
            7 => PacketType::EqualTo,
            _ => unreachable!(),
        }
    }
}

#[derive(Debug, Clone)]
pub struct Packet {
    version: u8,
    payload: Option<usize>,
    packet_type: PacketType,
    length: usize,
    sub_packets: Vec<Packet>,
}

Edit: I refactored this after the fact; I think it's reasonably clean now.

Uses the hex crate for parsing the hex string into a Vec<u8> and then noms it with a bit-level parser. This is probably fast, but it (a) took a while to write and (b) its verbose. I really hope this can be re-used tomorrow...

mod parse {
    use super::{Packet, PacketType};

    use hex::FromHex;
    use nom::{
        bits::complete::{tag, take},
        branch::alt,
        multi::{count, many0},
        IResult,
    };

    // 3-bit version number
    fn version(input: (&[u8], usize)) -> IResult<(&[u8], usize), u8> {
        take(3usize)(input)
    }

    // 3-bit packet type
    fn packet_type(input: (&[u8], usize)) -> IResult<(&[u8], usize), PacketType> {
        let (input, pt): ((&[u8], usize), u8) = take(3usize)(input)?;
        return Ok((input, PacketType::from(pt)));
    }

    // 5-bit literal group
    fn literal_group(input: (&[u8], usize)) -> IResult<(&[u8], usize), u8> {
        let (input, _): ((&[u8], usize), u8) = tag(1u8, 1usize)(input)?;
        let (input, group) = take(4usize)(input)?;

        Ok((input, group))
    }

    // 5-bit literal group (trailer)
    fn literal_group_trailer(input: (&[u8], usize)) -> IResult<(&[u8], usize), u8> {
        let (input, _): ((&[u8], usize), u8) = tag(0u8, 1usize)(input)?;
        let (input, group) = take(4usize)(input)?;

        Ok((input, group))
    }

    // variable-sized int
    fn var_int(input: (&[u8], usize)) -> IResult<(&[u8], usize), (usize, usize)> {
        let (input, groups) = many0(literal_group)(input)?;
        let (input, trailer) = literal_group_trailer(input)?;

        // Each group and the trailer are 5 bits
        let len = 5 * (groups.len() + 1);

        let varint = groups
            .into_iter()
            .chain(std::iter::once(trailer))
            .fold(0usize, |acc, val| (acc << 4) + val as usize);

        Ok((input, (varint, len)))
    }

    fn operator_packet_lt0(input: (&[u8], usize)) -> IResult<(&[u8], usize), (Vec<Packet>, usize)> {
        let (input, _): ((&[u8], usize), u8) = tag(0u8, 1usize)(input)?;
        let (input, mut remaining_length): ((&[u8], usize), usize) = take(15usize)(input)?;

        let mut input = input;
        let mut packets = Vec::new();

        let length = 16 + remaining_length;

        while remaining_length > 0 {
            let (inp, packet) = packet(input)?;
            input = inp;

            remaining_length -= packet.length;
            packets.push(packet);
        }

        Ok((input, (packets, length)))
    }

    fn operator_packet_lt1(input: (&[u8], usize)) -> IResult<(&[u8], usize), (Vec<Packet>, usize)> {
        let (input, _): ((&[u8], usize), u8) = tag(1u8, 1usize)(input)?;
        let (input, num_subpackets) = take(11usize)(input)?;
        let (input, packets) = count(packet, num_subpackets)(input)?;
        let length = 12 + packets.iter().map(|p| p.length).sum::<usize>();

        Ok((input, (packets, length)))
    }

    fn operator_packet(input: (&[u8], usize)) -> IResult<(&[u8], usize), (Vec<Packet>, usize)> {
        alt((operator_packet_lt0, operator_packet_lt1))(input)
    }

    fn packet(input: (&[u8], usize)) -> IResult<(&[u8], usize), Packet> {
        let (input, vsn) = version(input)?;
        let (input, packet_type) = packet_type(input)?;

        match packet_type {
            PacketType::Literal => {
                let (input, (num, len)) = var_int(input)?;

                return Ok((
                    input,
                    Packet {
                        version: vsn,
                        packet_type: PacketType::Literal,
                        payload: Some(num),
                        length: 6 + len,
                        sub_packets: vec![],
                    },
                ));
            }

            _ => {
                let (input, (sub_packets, len)) = operator_packet(input)?;

                return Ok((
                    input,
                    Packet {
                        version: vsn,
                        packet_type,
                        payload: None,
                        length: 6 + len,
                        sub_packets,
                    },
                ));
            }
        };
    }

    pub fn parse(input: &str) -> Packet {
        let mut input = input.trim().to_owned();

        // Pad to an even number of hex-characters so the hex crate doesn't complain.
        if input.len() % 2 == 1 {
            input += "0"
        }

        let input: Vec<u8> = Vec::from_hex(input).unwrap();

        packet((&input, 0)).unwrap().1
    }
}

fn evaluate(p: Packet) -> usize {
    let sub_packets: Vec<usize> = p.sub_packets.into_iter().map(|p| evaluate(p)).collect();

    match p.packet_type {
        PacketType::Literal => p.payload.unwrap(),
        PacketType::Sum => sub_packets.iter().sum::<usize>(),
        PacketType::Product => sub_packets.iter().product::<usize>(),
        PacketType::Minimum => *sub_packets.iter().min().unwrap(),
        PacketType::Maximum => *sub_packets.iter().max().unwrap(),
        PacketType::GreaterThan => {
            if sub_packets[0] > sub_packets[1] {
                1
            } else {
                0
            }
        }
        PacketType::LessThan => {
            if sub_packets[0] < sub_packets[1] {
                1
            } else {
                0
            }
        }
        PacketType::EqualTo => {
            if sub_packets[0] == sub_packets[1] {
                1
            } else {
                0
            }
        }
    }
}

fn part1(parsed: &Packet) -> usize {
    fn sum_vsn(v: Packet) -> usize {
        v.version as usize + v.sub_packets.into_iter().map(|p| sum_vsn(p)).sum::<usize>()
    }

    sum_vsn(parsed.clone())
}

fn part2(parsed: &Packet) -> usize {
    evaluate(parsed.clone())
}

fn main() {
    let input = include_str!("../../input-16.txt");
    let parsed = parse::parse(input);

    println!("Part I:  {}", part1(&parsed));
    println!("Part II: {}", part2(&parsed));
}

(define (part-02 input)
  (define bs (bits (string-trim input)))
  (define-values (s v) (packet bs))
  v)

(define (bits s)
  (define (hex v)
    (match v
      [#\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"]))
  (apply string-append (map hex (string->list s))))

(define (packet s)
  (define type (string->number (substring s 3 6) 2))
  (define-values (s+ ops)
    (case type
      [(4) (literal (substring s 6))]
      [(0 1 2 3 5 6 7) (if (eq? #\0 (string-ref s 6))
                           (operands/length (substring s 7))
                           (operands/count  (substring s 7)))]))
  (values s+ (evaluate type ops)))

(define (evaluate type os)
  (match type
    [0 (apply + os)]
    [1 (apply * os)]
    [2 (apply min os)]
    [3 (apply max os)]
    [4 os]
    [5 (if (> (first os) (second os)) 1 0)]
    [6 (if (< (first os) (second os)) 1 0)]
    [7 (if (= (first os) (second os)) 1 0)]))

(define (literal s)
  (define (nibbles s ns)
    (cond [(eq? #\1 (string-ref s 0))
           (nibbles (substring s 5) (cons (substring s 1 5) ns))]
          [else
           (define bin (apply string-append (reverse (cons (substring s 1 5) ns))))
           (values (substring s 5) (string->number bin 2))]))
  (nibbles s null))

(define (operands/length s)
  (define (operands s os)
    (cond [(non-empty-string? s)
           (define-values (s+ o) (packet s))
           (operands s+ (cons o os))]
          [else (reverse os)]))
  (define L (string->number (substring s 0 15) 2))
  (define os (operands (substring s 15 (+ L 15)) null))
  (values (substring s (+ L 15)) os))

(define (operands/count s)
  (define (operands s L os)
    (cond [(zero? L) (values s (reverse os))]
          [else (define-values (s+ o) (packet s))
           (operands s+ (sub1 L) (cons o os))]))
  (define L (string->number (substring s 0 11) 2))
  (operands (substring s 11) L null))

use std::env;
use std::io::{self};

#[derive(Debug)]
enum PacketKind {
    Literal,
    Operator(i64),
}
impl PacketKind {
    fn from(version: i64) -> Self {
        match version {
            4 => PacketKind::Literal,
            z @ (0 | 1 | 2 | 3 | 5 | 6 | 7) => PacketKind::Operator(z),
            _ => unreachable!(),
        }
    }
}
enum LengthType {
    Unapplicable,
    LengthInBits(usize),
    NumberOfSubpackets(usize),
}

fn parse_packets(s: &str) -> (String,i64,i64) {

    let mut code = String::from(s);
    
    // Packet header
    let version = b2i(code[0..3].to_string());
    let ptype   = b2i(code[3..6].to_string());
    let ptype   = PacketKind::from(ptype);
    code = code[6..].to_string();
    
    // Packet properties
    let mut version_sum = version;
    let mut literal: i64 = 0;
    let mut subpackets: Vec<i64> = Vec::new();

    // Determine packet length type
    let ltype = match ptype {
        PacketKind::Operator(_) => {
            match code[0..1].parse::<u8>().unwrap() {
                0 => {
                    let len = b2i(code[1..=15].to_string()) as usize;
                    code = code[16..].to_string();
                    LengthType::LengthInBits(len)
                },
                1 => {
                    let len = b2i(code[1..=11].to_string()) as usize;
                    code = code[12..].to_string();
                    LengthType::NumberOfSubpackets(len)
                },
                _ => unreachable!(),
            }
        },
        _ => LengthType::Unapplicable,
    };

    // Process packet or get subpackets
    match ptype {
        PacketKind::Literal => {
            // Parse literal value
            let mut literal_str: String = String::new();
            'literal_scan: loop {
                let chunk = code[0..5].to_string();
                literal_str.push_str(&chunk[1..]);
                code = code[5..].to_string();
                if chunk[0..1] == "0".to_string() { break 'literal_scan; }
            }
            literal = b2i(literal_str);
        },
        PacketKind::Operator(_) => {
            // Collect subpackets
            match &ltype {
                LengthType::LengthInBits(len) => {
                    // Parse next *len* bits
                    let mut remain = code[0..*len].to_string();
                    while remain.len() > 0 {
                        let (sub_remain,sub_version,sub_value) = parse_packets(&remain);
                        subpackets.push(sub_value);
                        remain = sub_remain.clone();
                        version_sum += sub_version;
                    }
                    code = code[*len..].to_string();
                },
                LengthType::NumberOfSubpackets(num) => {
                    // Parse *num* subpackets
                    let mut collected = 0;
                    while collected < *num {
                        let (sub_remain,sub_version,sub_value) = parse_packets(&code);
                        subpackets.push(sub_value);
                        code = sub_remain.clone();
                        version_sum += sub_version;
                        collected += 1;
                    }
                },
                _ => {},
            }
        }
    }

    // Process packet operations on subpackets
    let value: i64 = match ptype {
        PacketKind::Operator(op) => {
            match op {
                0 => subpackets.iter().sum::<i64>(),                     // sum
                1 => subpackets.iter().product::<i64>(),                 // product
                2 => *subpackets.iter().min().unwrap(),                  //min
                3 => *subpackets.iter().max().unwrap(),                  // max
                5 => if subpackets[0] >  subpackets[1] { 1 } else { 0 }, // greater than
                6 => if subpackets[0] <  subpackets[1] { 1 } else { 0 }, // less than
                7 => if subpackets[0] == subpackets[1] { 1 } else { 0 }, // equal to
                other => panic!("Unknown operation type: {}", other),
            }
        },
        PacketKind::Literal => { literal },
    };
    
    // Returned values
    (code.to_string(),version_sum,value)
}

fn b2i(s: String) -> i64 {
    i64::from_str_radix(&s, 2).unwrap()
}

fn h2b(s: String) -> String {
    s.chars().map(|ch| {
        match ch {
            '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",
            _ => unreachable!(),
        }})
    .collect::<String>()
}

fn solve(input: &str) -> io::Result<()> {
    // Input
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();

    // Part 1
    let (_,part1,part2) = parse_packets(&h2b(input_str.to_string()));
    println!("Part 1: {}", part1); // 873
    println!("Part 2: {}", part2); // 402817863665

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

#[cfg(test)]
mod tests {
    use super::*;
    fn test_hex_p1(hex: String) -> i64 {
        let converted = h2b(hex);
        let (_,part1,_) = parse_packets(&converted);
        part1
    }

    #[test]
    fn test1() {
        let input = "8A004A801A8002F478".to_string();
        let part1 = test_hex_p1(input);
        assert!(part1 == 16)
    }

    #[test]
    fn test2() {
        let input = "620080001611562C8802118E34".to_string();
        let part1 = test_hex_p1(input);
        assert!(part1 == 12)
    }

    #[test]
    fn test3() {
        let input = "C0015000016115A2E0802F182340".to_string();
        let part1 = test_hex_p1(input);
        assert!(part1 == 23)
    }

    #[test]
    fn test4() {
        let input = "A0016C880162017C3686B18A3D4780".to_string();
        let part1 = test_hex_p1(input);
        assert!(part1 == 31)
    }
}