# Day 16: Packet Decoder

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python` with any of the "short names" listed in this page of supported languages):

``````<details>
<summary>Part 1</summary>

```python
```

</details>
``````

1. Crespyl
This kind of thing is exactly up my alley, and I really enjoyed working on this puzzle. Unfortunately, this sort of bit-level work isn't really a strong suit of Ruby, so I ended up "cheating" by...

This kind of thing is exactly up my alley, and I really enjoyed working on this puzzle.

Unfortunately, this sort of bit-level work isn't really a strong suit of Ruby, so I ended up "cheating" by just converting the input to a string of `'0'` and `'1'` characters in memory, which was a little easier to work with.

There's a lot of extra code and helper functions this time, so I'll try to thread some extra comments in to explain things as I go.

Parsing

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.

Once we have everything we need to parse our bit-string into a tree of packet objects, we can actually solve the puzzle.

Part 1 Ruby
``````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
``````
Part 2 Ruby
``````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
``````

Now that everyone who solves this has a functioning AST parser and evaluator, there's a chance that some future puzzle will involve extending this format to something Turing-complete, which would allow for some pretty cool puzzles a-la Intcode from 2019. Here's hoping :p

2. PapaNachos
After being Big Mad about yesterday's problem I really enjoyed this one. It was much more satisfying, for me at least. It definitely took a few tries to understand part of the problem description...

After being Big Mad about yesterday's problem I really enjoyed this one. It was much more satisfying, for me at least. It definitely took a few tries to understand part of the problem description though

Day 16 Part A - Python

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

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)

print("Version: ", version)
print("Identity: ", identity)

if identity == 4: #literal packet
bin_number = ""
bin_number = bin_number + segment[1:]
if segment[0] == '0':
print("Literal Value: ", int(bin_number, 2))

else: #operator packet
if length_id == '0': #next 15 bits list total length in bits of subpackets
else: #next 11 bits list number of sub packets
for i in range(num_subpackets):

print(version_num_sum)
``````
Day 16 Part B - Python

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))

#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)

#print("Version: ", version)
#print("Identity: ", identity)

if identity == 4: #literal packet
bin_number = ""
bin_number = bin_number + segment[1:]
if segment[0] == '0':
#print("Literal Value: ", int(bin_number, 2))
value = int(bin_number, 2)

else: #operator packet
values = []
if length_id == '0': #next 15 bits list total length in bits of subpackets
values.append(val)
else: #next 11 bits list number of sub packets
for i in range(num_subpackets):
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

print(result)
``````
Tips
• 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

3. [3]
wycy
Question I'm still on part 1 and having a bit of trouble totally understanding the premise. For reading literal values, is the idea that you don't know how long the value is, so you have to try...

Question

I'm still on part 1 and having a bit of trouble totally understanding the premise.

For reading literal values, is the idea that you don't know how long the value is, so you have to try multiple options? i.e., try to read it as though each of the 4 chunks is 2 bits long (checking for 1, 1, 1, and 0 leading chars), then try to read it as though each of the 4 chunks is 3 bits, then each of the chunks as 4 bits, etc, until the pattern of leading digits 1, 1,1, 0 is met?

1. [2]
PapaNachos
Yeah, the problem description definitely could have used a few more editorial passes. For the literal values you look at 5-bit chunks. The leading bit determines if you keep reading or it this...

Yeah, the problem description definitely could have used a few more editorial passes. For the literal values you look at 5-bit chunks. The leading bit determines if you keep reading or it this will be the last one. The other 4 bits are data.

Edit: You keep going until you hit a 0 leading bit

1. wycy
(edited )
Oooh it's groups of 4 (5) bits, not 4 groups. Gotcha--that's much more straightforward. So glad I asked rather than waste time trying to implement what I thought it was. Thanks! Edit: oof I really...

Oooh it's groups of 4 (5) bits, not 4 groups. Gotcha--that's much more straightforward. So glad I asked rather than waste time trying to implement what I thought it was. Thanks!

Edit: oof I really just needed to read more carefully. It's pretty clear my original interpretation was wrong given even the example didn't have 4 groups of bits.

4. jzimbel
(edited )
Elixir Fun! This problem is something that Elixir (or really Erlang, which Elixir is built on top of/interops with) has batteries-included support for. It has a bitstring type and a whole special...

Elixir
Fun! This problem is something that Elixir (or really Erlang, which Elixir is built on top of/interops with) has batteries-included support for. It has a bitstring type and a whole special subset of pattern matching syntax that makes for fast, concise, declarative code for parsing bitstrings. This strong support exists because Erlang was purpose-built for low latency communication gateways and distributed systems.

Runtime: My solution runs in about 260 - 270Î¼s for each part.

Both parts
``````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
``````
5. DataWraith
(edited )
Day 16 (Rust) What a mess. But it seems like this is what you would do to parse a real-world file-format such as .PNG, so I'm kind of happy with it. Data structures #[derive(Debug, Clone,...

#### Day 16 (Rust)

What a mess. But it seems like this is what you would do to parse a real-world file-format such as .PNG, so I'm kind of happy with it.

Data structures
``````#[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,
packet_type: PacketType,
length: usize,
sub_packets: Vec<Packet>,
}
``````
Parsing...

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 `nom`s 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,
length: 6 + len,
sub_packets: vec![],
},
));
}

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

return Ok((
input,
Packet {
version: vsn,
packet_type,
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
}
}
``````
Helper functions
``````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::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
}
}
}
}
``````
Solving
``````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));
}
``````
1 vote
6. bhrgunatha
I love parsing and language evaluation stuff. Something really wrong with me today though. Had to put it down, step away and return later. Ranked 10103/10995. I'm still upset and embarrassed. No...

I love parsing and language evaluation stuff.
Something really wrong with me today though. Had to put it down, step away and return later. Ranked 10103/10995. I'm still upset and embarrassed.

No Comment
``````(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))
``````
1 vote
7. wycy
(edited )
Rust Many thanks to PapaNachos, without whom I'd still be trying to parse the literals. Edit: Cleaned up more and added tests. Rust use std::env; use std::io::{self}; #[derive(Debug)] enum...

Rust

Many thanks to PapaNachos, without whom I'd still be trying to parse the literals.

Edit: Cleaned up more and added tests.

Rust
``````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);

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 {
}

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 = 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)
}
}
``````
1 vote