Day 16: Packet Decoder

Day #16 problem description │ Problem input

Dear lord, this problem was brutal. It consisted of roughly three parts:

Parse a hex string into a binary string by parsing each hex character into a quartet — trivial
(Part 1) Parse this binary string into a tree of packets according to rules set out in the problem statement — “easy” in the sense that I wrote up an almost correct solution in no time at all. Very very hard in the sense that it required precise bookkeeping and it took forever for me to get it all exactly correct. But from a theoretical standpoint it wasn’t really that hard.
(Part 2) Evaluate the packet tree as an expression tree (more or less like parsing S-expressions) — easy.

Setup

The main function here is Binary::as_packets. There’s a lot to unpack here, but roughly the algorithm is as follows:

Maintain a cursor into the original data
Maintain a stack of parse states, which consist of:
1. The depth in the parse tree
2. The length of remaining data for this packet. Packets tell us how much data they expect; when there isn’t any left, we head back up a level in the tree. So we have to track how much of their data we’ve consumed so far. This “amount of data” quantity comes in two flavors:
  Number of bits that the children comprise
  
  Number of direct children, i.e., number of child packets
  One tricky bit is that packets share bits-remaining with their children. In other words, if a child consumes some bits from the input, so have all of its ancestors that count their data in bits. (Packets that are expecting a fixed number of child packets are unaffected when their descendants consume data.) In either case, if the current packet has no more data remaining — 0 bits or 0 child packets — continue on to the next parse state on the stack.
Looking at the data beginning at the cursor, parse the stream into a single packet.
Advance the cursor the number of bits this packet consumed.
If this packet was an operator, increment the depth, as its children will follow. Otherwise the depth remains unchanged.
Push a new parse state onto the stack, containing the incremented depth and the length of remaining data for this packet.
If this packet was the last of its parent’s children, decrement the depth.

use crate::{utils::to_big_decimal, Answer};
use std::fmt::{Display, Write};

type Number = i64;

struct Binary(Vec<bool>);

impl Binary {
	fn from_hex(s: &str) -> Option<Self> {
		let mut binary = Vec::with_capacity(s.len() * 4);
		for c in s.trim().chars() {
			let n = c.to_digit(16)?;
			let digits = [3, 2, 1, 0usize].map(|place| ((1 << place) & n) != 0);
			binary.extend_from_slice(&digits);
		}

		Some(Self(binary))
	}
}

impl Display for Binary {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		for &digit in &self.0 {
			let c = if digit { '1' } else { '0' };
			f.write_char(c)?;
		}
		Ok(())
	}
}

impl Binary {
	fn as_packets(&self) -> Vec<Packet> {
		#[derive(Debug)]
		enum RemainingData {
			NBits(usize),
			NPackets(usize),
		}

		impl RemainingData {
			fn is_empty(&self) -> bool {
				matches!(self, RemainingData::NBits(0) | RemainingData::NPackets(0))
			}
		}

		#[derive(Debug)]
		struct ParseState {
			depth: usize,
			remaining: RemainingData,
		}

		let mut packets = vec![];

		let orig_data = &self.0;
		let header_length = 6;
		let mut cursor = 0;
		let mut stack = vec![ParseState {
			depth: 0,
			remaining: RemainingData::NPackets(1),
		}];

		while let Some(parse_state) = stack.pop() {
			let ParseState { depth, remaining } = parse_state;

			if remaining.is_empty() {
				continue;
			}

			let packet_bits = &orig_data[cursor..];

			let version_number = to_big_decimal(&packet_bits[0..3]);
			let kind_number = to_big_decimal(&packet_bits[3..6]);
			let data_bits = &packet_bits[header_length..];

			let parent_packet_length = match remaining {
				RemainingData::NBits(n) => RemainingData::NBits(n),
				RemainingData::NPackets(n) => RemainingData::NPackets(n - 1),
			};
			stack.push(ParseState {
				depth,
				remaining: parent_packet_length,
			});

			let packet;
			let n_bits_consumed;
			match kind_number {
				4 => {
					let chunk_size = 5;
					let mut bin_bits = vec![];

					let mut n_chunks = 0;
					for chunk in data_bits.chunks_exact(5) {
						n_chunks += 1;
						bin_bits.extend_from_slice(&chunk[1..]);
						if !chunk[0] {
							break;
						}
					}

					let value = i64::try_from(to_big_decimal(bin_bits)).unwrap();

					n_bits_consumed = header_length + n_chunks * chunk_size;
					packet = Packet {
						version_number,
						kind: PacketKind::Literal { value },
						depth,
					};
				}
				op => {
					let op_data_length;
					let n_bits_for_length;

					let length_type = data_bits[0];
					if length_type {
						// length in packets
						n_bits_for_length = 12;
						let n_packets =
							usize::try_from(to_big_decimal(&data_bits[1..n_bits_for_length]))
								.unwrap();
						op_data_length = RemainingData::NPackets(n_packets);
					} else {
						// length in bits
						n_bits_for_length = 16;
						let n_bits =
							usize::try_from(to_big_decimal(&data_bits[1..n_bits_for_length]))
								.unwrap();
						op_data_length = RemainingData::NBits(n_bits);
					};

					n_bits_consumed = header_length + n_bits_for_length;
					// A hack; we're going to subtract n_bits_consumed from this later
					// despite the fact that in theory we shouldn't (because the newly added
					// packet hasn't consumed any data yet), so we we pre-add n_bits_consumed
					// here so that when we subtract it later we end up with the right number
					// of bits
					let op_data_length = match op_data_length {
						RemainingData::NBits(n) => RemainingData::NBits(n + n_bits_consumed),
						rd @ RemainingData::NPackets(_) => rd,
					};

					packet = Packet {
						version_number,
						kind: PacketKind::Operator { op: op.into() },
						depth,
					};

					stack.push(ParseState {
						depth: depth + 1,
						remaining: op_data_length,
					});
				}
			};

			cursor += n_bits_consumed;

			for ps in &mut stack {
				if let RemainingData::NBits(n) = &mut ps.remaining {
					if *n > 0 {
						// The hack above is to counteract this subtraction; if we just pushed
						// a RemainingData::NumBits, we won't actually have consumed any of
						// its input yet
						//
						// If our code has no bugs, and the input is trustworthy, this will
						// never underflow.
						*n -= n_bits_consumed;
					}
				}
			}

			packets.push(packet);
		}

		packets
	}
}

#[derive(Debug)]
enum PacketKind {
	Literal { value: Number },
	Operator { op: Operation }, // Defined in pt2
}

#[derive(Debug)]
struct Packet {
	version_number: u64,
	kind: PacketKind,
	depth: usize,
}

fn read_input(input: &str) -> Vec<Packet> {
	let b = Binary::from_hex(input).unwrap();
	b.as_packets()
}

fn ans_for_input(input: &str) -> Answer<u64, Number> {
	let p = read_input(input);
	(16, (pt1(&p), pt2(&p).unwrap())).into()
}

pub fn ans() -> Answer<u64, Number> {
	ans_for_input(include_str!("input.txt"))
}

Part 1

Part 1 just asks us to compute some summary data of all the packets in the parse tree. As long as we have the right packets (regardless of their depths) we’ll get the right answer.

fn pt1(packets: &[Packet]) -> u64 {
	packets.iter().map(|packet| packet.version_number).sum()
}

Part 2

Part 2 asks us to actually evaluate the packet tree as a tree of an expressions, akin to S-expressions. While this wasn’t hard, one challenge was to implement it without code duplication. The way I achieved this was to split the operators into two families, Reducers (+, *, min, and max) and Operatorss (≤, ==, ≥) which essentially comprise their own interfaces that specify how they should be applied to values in the stack.

#[derive(Debug)]
enum Reducer {
	Sum,
	Product,
	Min,
	Max,
}

impl Reducer {
	fn identity(&self) -> Number {
		use Reducer::*;
		match self {
			Sum => 0,
			Product => 1,
			Min => Number::MAX,
			Max => Number::MIN,
		}
	}

	fn combine(&self, x: Number, y: Number) -> Number {
		use Reducer::*;
		match self {
			Sum => x + y,
			Product => x * y,
			Min => x.min(y),
			Max => x.max(y),
		}
	}
}

#[derive(Debug)]
enum Comparitor {
	Gt,
	Lt,
	Eq,
}

impl Comparitor {
	fn apply(&self, x: Number, y: Number) -> Number {
		use Comparitor::*;
		i64::from(match self {
			Gt => x > y,
			Lt => x < y,
			Eq => x == y,
		})
	}
}

#[derive(Debug)]
enum Operation {
	Reduce(Reducer),
	Compare(Comparitor),
}

impl From<u64> for Operation {
	fn from(n: u64) -> Self {
		use Comparitor::*;
		use Operation::*;
		use Reducer::*;
		match n {
			0 => Reduce(Sum),
			1 => Reduce(Product),
			2 => Reduce(Min),
			3 => Reduce(Max),
			5 => Compare(Gt),
			6 => Compare(Lt),
			7 => Compare(Eq),
			_ => unreachable!(),
		}
	}
}

fn pt2(packets: &[Packet]) -> Option<Number> {
	struct Arg {
		depth: usize,
		value: Number,
	}
	let mut arg_stack = vec![];

	for Packet {
		kind: packet_kind,
		depth: packet_depth,
		..
	} in packets.iter().rev()
	{
		let packet_depth = *packet_depth;

		match packet_kind {
			&PacketKind::Literal { value } => arg_stack.push(Arg {
				depth: packet_depth,
				value,
			}),
			PacketKind::Operator { op } => {
				use Operation::*;
				let value = match op {
					Reduce(reducer) => {
						let mut result = reducer.identity();
						while let Some(arg @ Arg { depth, value }) = arg_stack.pop() {
							if depth <= packet_depth {
								arg_stack.push(arg); // oops, went too far
								break;
							}
							result = reducer.combine(result, value);
						}
						result
					}
					Compare(comparitor) => {
						let Arg { value: first, .. } = arg_stack.pop()?;
						let Arg { value: second, .. } = arg_stack.pop()?;

						comparitor.apply(first, second)
					}
				};

				arg_stack.push(Arg {
					depth: packet_depth,
					value,
				});
			}
		}
	}

	Some(arg_stack.first()?.value)
}