293 lines
7.9 KiB
Rust
293 lines
7.9 KiB
Rust
use std::str::FromStr;
|
|
|
|
use bitvec::bitvec;
|
|
use bitvec::order::Msb0;
|
|
use bitvec::prelude::BitVec;
|
|
use yap::TokenLocation;
|
|
use yap::Tokens;
|
|
|
|
use crate::day_16::model::Length;
|
|
use crate::day_16::Operator;
|
|
|
|
use super::model::Operation;
|
|
use super::{Kind, Packet};
|
|
|
|
pub fn parse_packet(tokens: &mut impl Tokens<Item = bool>) -> Option<Packet> {
|
|
yap::one_of!(tokens;
|
|
parse_literal_value(tokens),
|
|
parse_operator(tokens),
|
|
)
|
|
}
|
|
|
|
pub fn parse_literal_value(tokens: &mut impl Tokens<Item = bool>) -> Option<Packet> {
|
|
tokens.optional(|t| {
|
|
let (version, type_id) = parse_version_and_type(t)?;
|
|
|
|
if type_id != 4 {
|
|
return None;
|
|
}
|
|
|
|
let mut value = 0usize;
|
|
let mut last_group_reached = false;
|
|
loop {
|
|
match t.next() {
|
|
Some(true) => (),
|
|
Some(false) => last_group_reached = true,
|
|
None => return None,
|
|
}
|
|
|
|
value <<= 4;
|
|
value |= read_number(t, 4)?;
|
|
|
|
if last_group_reached {
|
|
break;
|
|
}
|
|
}
|
|
Some(Packet {
|
|
version,
|
|
kind: Kind::LiteralValue(value),
|
|
})
|
|
})
|
|
}
|
|
|
|
pub fn read_number(tokens: &mut impl Tokens<Item = bool>, bits: usize) -> Option<usize> {
|
|
tokens.optional(|t| {
|
|
let mut value = 0usize;
|
|
for _ in 0..bits {
|
|
value <<= 1;
|
|
value |= t.next()? as usize;
|
|
}
|
|
Some(value)
|
|
})
|
|
}
|
|
|
|
pub fn parse_operator(tokens: &mut impl Tokens<Item = bool>) -> Option<Packet> {
|
|
tokens.optional(|t| {
|
|
let (version, opcode) = parse_version_and_type(t)?;
|
|
|
|
let operation = get_op_from_code(opcode)?;
|
|
|
|
let length = match t.next()? {
|
|
true => Length::Count(read_number(t, 11)?),
|
|
false => Length::Length(read_number(t, 15)?),
|
|
};
|
|
|
|
let mut sub_packets = Vec::new();
|
|
|
|
match length {
|
|
Length::Count(count) => {
|
|
for _ in 0..count {
|
|
sub_packets.push(parse_packet(t)?)
|
|
}
|
|
}
|
|
Length::Length(length) => {
|
|
let sub_start = t.offset();
|
|
while t.offset() - sub_start < length {
|
|
sub_packets.push(parse_packet(t)?)
|
|
}
|
|
if t.offset() - sub_start != length {
|
|
return None;
|
|
}
|
|
}
|
|
}
|
|
|
|
Some(Packet {
|
|
version,
|
|
kind: Kind::Operator(Operator {
|
|
operation,
|
|
length,
|
|
sub_packets,
|
|
}),
|
|
})
|
|
})
|
|
}
|
|
|
|
fn get_op_from_code(opcode: usize) -> Option<Operation> {
|
|
Some(match opcode {
|
|
0 => Operation::Sum,
|
|
1 => Operation::Product,
|
|
2 => Operation::Minimum,
|
|
3 => Operation::Maximum,
|
|
5 => Operation::GreaterThan,
|
|
6 => Operation::LessThan,
|
|
7 => Operation::EqualTo,
|
|
_ => return None,
|
|
})
|
|
}
|
|
|
|
pub fn parse_version_and_type(tokens: &mut impl Tokens<Item = bool>) -> Option<(usize, usize)> {
|
|
tokens.optional(|t| {
|
|
let version = read_number(t, 3)?;
|
|
let opcode = read_number(t, 3)?;
|
|
Some((version, opcode))
|
|
})
|
|
}
|
|
|
|
pub struct BinTokens {
|
|
bits: BitVec,
|
|
location: BinLocation,
|
|
}
|
|
|
|
impl FromStr for BinTokens {
|
|
type Err = &'static str;
|
|
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let mut vec = BitVec::new();
|
|
for hex in s.chars() {
|
|
vec.append(&mut match hex {
|
|
'0' => bitvec![Msb0, u8; 0, 0, 0, 0],
|
|
'1' => bitvec![Msb0, u8; 0, 0, 0, 1],
|
|
'2' => bitvec![Msb0, u8; 0, 0, 1, 0],
|
|
'3' => bitvec![Msb0, u8; 0, 0, 1, 1],
|
|
'4' => bitvec![Msb0, u8; 0, 1, 0, 0],
|
|
'5' => bitvec![Msb0, u8; 0, 1, 0, 1],
|
|
'6' => bitvec![Msb0, u8; 0, 1, 1, 0],
|
|
'7' => bitvec![Msb0, u8; 0, 1, 1, 1],
|
|
'8' => bitvec![Msb0, u8; 1, 0, 0, 0],
|
|
'9' => bitvec![Msb0, u8; 1, 0, 0, 1],
|
|
'A' => bitvec![Msb0, u8; 1, 0, 1, 0],
|
|
'B' => bitvec![Msb0, u8; 1, 0, 1, 1],
|
|
'C' => bitvec![Msb0, u8; 1, 1, 0, 0],
|
|
'D' => bitvec![Msb0, u8; 1, 1, 0, 1],
|
|
'E' => bitvec![Msb0, u8; 1, 1, 1, 0],
|
|
'F' => bitvec![Msb0, u8; 1, 1, 1, 1],
|
|
_ => return Err("string contains non-hex characters"),
|
|
})
|
|
}
|
|
|
|
Ok(BinTokens {
|
|
bits: vec,
|
|
location: BinLocation { offset: 0 },
|
|
})
|
|
}
|
|
}
|
|
|
|
impl Iterator for BinTokens {
|
|
type Item = bool;
|
|
|
|
fn next(&mut self) -> Option<Self::Item> {
|
|
if self.bits.len() > self.location.offset {
|
|
let bit = self.bits.get(self.location.offset)?;
|
|
self.location.increment();
|
|
Some(*bit)
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
}
|
|
|
|
#[derive(PartialEq, Eq, Debug, Copy, Clone)]
|
|
pub struct BinLocation {
|
|
offset: usize,
|
|
}
|
|
|
|
impl BinLocation {
|
|
fn increment(&mut self) {
|
|
self.offset += 1;
|
|
}
|
|
}
|
|
|
|
impl TokenLocation for BinLocation {
|
|
fn offset(&self) -> usize {
|
|
self.offset
|
|
}
|
|
}
|
|
|
|
impl Tokens for BinTokens {
|
|
type Location = BinLocation;
|
|
|
|
fn location(&self) -> Self::Location {
|
|
self.location
|
|
}
|
|
|
|
fn set_location(&mut self, location: Self::Location) {
|
|
self.location = location
|
|
}
|
|
|
|
fn is_at_location(&self, location: &Self::Location) -> bool {
|
|
self.location == *location
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use crate::day_16::model::{Length, Operation};
|
|
|
|
use super::super::{Kind, Packet};
|
|
use super::BinTokens;
|
|
|
|
#[test]
|
|
fn hex_binary_tokens() {
|
|
let mut tokens = "D2FE28".parse::<BinTokens>().unwrap();
|
|
let expected = vec![
|
|
true, true, false, true, false, false, true, false, true, true, true, true, true, true,
|
|
true, false, false, false, true, false, true, false, false, false,
|
|
];
|
|
for val in expected.iter() {
|
|
assert_eq!(tokens.next(), Some(*val));
|
|
}
|
|
assert!(tokens.next().is_none());
|
|
}
|
|
|
|
#[test]
|
|
fn parse_version_and_type() {
|
|
assert_eq!(
|
|
super::parse_version_and_type(&mut "D2FE28".parse::<BinTokens>().unwrap()),
|
|
Some((6, 4))
|
|
)
|
|
}
|
|
|
|
#[test]
|
|
fn parse_literal_value_first_example() {
|
|
let packet = Packet {
|
|
version: 6,
|
|
kind: Kind::LiteralValue(2021),
|
|
};
|
|
assert_eq!(
|
|
super::parse_literal_value(&mut "D2FE28".parse::<BinTokens>().unwrap()),
|
|
Some(packet)
|
|
)
|
|
}
|
|
|
|
#[test]
|
|
fn parse_operator_first_example() {
|
|
let packet =
|
|
super::parse_operator(&mut "38006F45291200".parse::<BinTokens>().unwrap()).unwrap();
|
|
assert_eq!(packet.version, 1);
|
|
if let Kind::Operator(operator) = packet.kind {
|
|
assert_eq!(operator.operation, Operation::LessThan);
|
|
assert_eq!(operator.length, Length::Length(27));
|
|
assert_eq!(operator.sub_packets.len(), 2);
|
|
} else {
|
|
panic!();
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn parse_operator_second_example() {
|
|
let packet =
|
|
super::parse_operator(&mut "EE00D40C823060".parse::<BinTokens>().unwrap()).unwrap();
|
|
assert_eq!(packet.version, 7);
|
|
if let Kind::Operator(operator) = packet.kind {
|
|
assert_eq!(operator.operation, Operation::Maximum);
|
|
assert_eq!(operator.length, Length::Count(3));
|
|
assert_eq!(operator.sub_packets.len(), 3);
|
|
} else {
|
|
panic!();
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn other_examples() {
|
|
for (string, sum) in [
|
|
("8A004A801A8002F478", 16),
|
|
("620080001611562C8802118E34", 12),
|
|
("C0015000016115A2E0802F182340", 23),
|
|
("A0016C880162017C3686B18A3D4780", 31),
|
|
] {
|
|
let packet = super::parse_packet(&mut string.parse::<BinTokens>().unwrap()).unwrap();
|
|
assert_eq!(packet.sum_of_version_numbers(), sum);
|
|
}
|
|
}
|
|
}
|