NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2022 Day 12

Advent of Code 2022 Day 14

1. Day 13: Distress Signal
2. Parsing
3. Part 1
4. Part 2
1. Final code
5. Final code

# Advent of Code 2022 Day 13

## Day 13: Distress Signal

You communication device is receiving a signal, it’s a distress signal!

It receives pairs of packets, and some of those pairs are out of order (because of course they are, it wouldn’t be a puzzle if everything was hunky dory now would it?).

You need to be able to identify when a pair is ordered wrong so you can swap the packets.

Today’s input are the pairs of packets you receive.

An example input looks like this:

input.txt
[1,1,3,1,1][1,1,5,1,1].css-13aqjzy{display:inline-block;}
[,[2,3,4]][,4]
[[8,7,6]]
[[4,4],4,4][[4,4],4,4,4]
[7,7,7,7][7,7,7]
[]
[[[]]][[]]
[1,[2,[3,[4,[5,6,7]]]],8,9][1,[2,[3,[4,[5,6,0]]]],8,9]

Each pair is seperated by an empty line. A packet is that array looking thing on a single line. And they look familiar.

A packet consists of lists and integers.

• A list starts with [ and ends with ].
• A list can be empty
• Each item in a list is seperated by a ,

The two packets in a pair are called left and right.

A pair where the left packet is smaller than the right packet is in the correct order.

To determine which of two packets is smaller, there are a few rules:

• If both values are integers, the lower integer is smaller.
• If both integers are identical, continue to the next part of the package.
• If both values are lists, compare each value in the 2 lists step by step.
• If the left list runs out of values to compare first, it is smaller.
• If the right list runs out of values to compare first, it is smaller.
• If one value is an integer and the other a list, turn the integer into a list of one integer, and run the comparison again.

## Parsing

I parsed the input into a list of pairs. Each item in a pair is a packet, so I used a Packet data structure.

enum Packet {    Num(u8),    List(Vec<Packet>),}

The main parse function splits the input in a double newline. Parses the 2 packets seperatly, and return a list of those pairs.

day_13.rs
fn parse() -> Vec<[Packet; 2]> {    let input = std::fs::read_to_string("src/day13.txt").unwrap();
input        .split("\n\n")        .map(|pair| {            let mut lines = pair.lines();            let left = lines.next().unwrap();            let right = lines.next().unwrap();
[parse_packet(left), parse_packet(right)]        })        .collect()}

Yeah, yeah, … show us parse_packet!

Now. If you wanted to be cheeky, every packet is valid JSON. So you could use your favourite way to parse JSON and call it a victory.

I didn’t.

parse_packet takes a string, and returns a Packet.

fn parse_packet(s: &str) -> Packet {    let chars: Vec<_> = s.chars().collect();    // parse_list returns the first parsed packet and the rest of the input    // the rest of the input will be empty when it is done    let (packet, _) = parse_list(&chars);    packet}

It uses the parse_list function, what’s that?

It’s one of 2 other helper functions. A packet is either a Num(u8) or a List(Vec<Packet>).

• The number variant gets parsed by parse_num.
• The list variant gets parsed by parse_num.

They both use the same pattern. It consumes a part of what is passed in, and returns the thing it parsed, and the remaining input after that thing.

• for parse_num it returns (Packet::Num(u8), &[char])
• for parse_list it returns (Packet::List(Vec<Packet>, &[char])

Where that &[char] bit is the remaining input.

At the very top, when we first call parse_list in parse_packet. We call parse_list on an entire packet, the remaining part will be empty. That’s why I throw it away with that _.

fn parse_num(list: &[char]) -> (Packet, &[char]) {    // find the index where the first number ends    let mut i = 0;    while i < list.len() && list[i].is_ascii_digit() {        i += 1;    }
// parse the number    // uses math to concatenate numbers instead of turning them into a string first to parse that    let mut num = 0;    let mut offset = 1;    for c in list[..i].iter().rev() {        num += (*c as u8 - b'0') * offset;        offset *= 10;    }
// return the number and the rest of the packet    (Packet::Num(num), &list[i..])}
fn parse_list(list: &[char]) -> (Packet, &[char]) {    // start by removing the starting [ of the passed in list    // at the end of this function, we remove the ending ] of the passed in list    let mut list = &list[1..];    let mut packets = Vec::new();
loop {        match list {            // list ended, break the loop            ']' => break,            // skip over ,            ',' => list = &list[1..],            // beginning of new list, time for recursion to parse the inner list            '[' => {                let (packet, rest) = parse_list(list);                packets.push(packet);                list = rest;            }            // beginning of a number            _ => {                let (n, rest) = parse_num(list);                packets.push(n);                list = rest;            }        }    }
// return the parsed list and the remaining characters minus the ] that terminates the list this function just parsed    (Packet::List(packets), &list[1..])}

## Part 1

The question asks what the sum of the indices of the pairs that arrived correctly is.

in pseudocode:

pseudocode.rs
pairs    .iter()    .positions(|[left, right]| left < right)    .map(|idx| idx + 1)    .sum()

It’s that comparison where the next bit of interesting code happens.

I wanted to tell my code how it can compare two Packets. Make it understand what a less than operation means.

The rules for such a comparison are described in the intro.

### Helpers

To make that comparison possible, I implemented the Ord trait in Rust.

Basically, I wrote the code that Rust uses when you do a comparison.

Turns out that you can not only compare 2 numbers, but you can compare 2 lists! And the logic it uses happens to be the same one described in the problem statement. That’s convenient!

I take the inner “thing” out of a Packet, and call them a and b. Both are either a u8, or a Vec.

a.cmp(b), and if only one of them is a vec, wrap the other in a vec and compare that instead!

#[derive(PartialEq, Eq)]enum Packet {    Num(u8),    List(Vec<Packet>),}
impl Ord for Packet {    fn cmp(&self, other: &Self) -> std::cmp::Ordering {        match (self, other) {            (Self::List(a), Self::List(b)) => a.cmp(b),            (Self::List(a), Self::Num(b)) => a.cmp(&vec![Self::Num(*b)]),            (Self::Num(a), Self::List(b)) => vec![Self::Num(*a)].cmp(&b),            (Self::Num(a), Self::Num(b)) => a.cmp(b),        }    }}
impl PartialOrd for Packet {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }}

With this trait implemented, that skeleton code from earlier works.

### Final code

day_13.rs
use itertools::Itertools;
pub fn part_1() -> usize {    let pairs = parse();
pairs        .iter()        .positions(|[left, right]| left < right)        .map(|idx| idx + 1)        .sum()}

## Part 2

We need to put all packets in the correct order now. Ignoring the empty lines.

Two divider packets are inserted too.

[][]

The question asks what the decoder key is.

The decoder key is the product of the indices of those 2 divider packets when all packets are in the correct order.

I reused the parsing logic for pairs. Since we only care about individual packages, I turned the list of pair into a single list with flatten.

I parsed those 2 divider packets and inserted them into the list of packets.

Then, sort all packets and search for the divider packets.

The product of their indices (reminder: 1 based indices!) is the answer to part2!

### Final code

day_13.rs
use itertools::Itertools;
pub fn part_2() -> usize {    let pairs = parse();    let mut packets: Vec<_> = pairs.iter().flatten().collect();
let divider_1 = parse_packet("[]");    let divider_2 = parse_packet("[]");
packets.push(&divider_1);    packets.push(&divider_2);
packets.sort_unstable();
packets        .into_iter()        .positions(|packet| packet == &divider_1 || packet == &divider_2)        .map(|idx| idx + 1)        .product()}

## Final code

day_13.rs
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}1use std::cmp::Ordering;2
3use itertools::Itertools;4
5#[derive(Debug, PartialEq, Clone, Eq)]6enum Packet {7    Num(u8),8    List(Vec<Packet>),9}10
11impl Ord for Packet {12    fn cmp(&self, other: &Self) -> std::cmp::Ordering {13        match (self, other) {14            (Self::List(a), Self::List(b)) => a.cmp(b),15            (Self::List(a), Self::Num(b)) => a.cmp(&vec![Self::Num(*b)]),16            (Self::Num(a), Self::List(b)) => vec![Self::Num(*a)].cmp(&b),17            (Self::Num(a), Self::Num(b)) => a.cmp(b),18        }19    }20}21
22impl PartialOrd for Packet {23    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {24        Some(self.cmp(other))25    }26}27
28fn parse() -> Vec<[Packet; 2]> {29    let input = std::fs::read_to_string("src/day13.txt").unwrap();30
31    input32        .split("\n\n")33        .map(|pair| {34            let mut lines = pair.lines();35            let left = lines.next().unwrap();36            let right = lines.next().unwrap();37
38            [parse_packet(left), parse_packet(right)]39        })40        .collect()41}42
43fn parse_packet(s: &str) -> Packet {44    let chars: Vec<_> = s.chars().collect();45    // parse_list returns the first parsed packet and the rest of the input46    // the rest of the input will be empty when it is done47    let (packet, _) = parse_list(&chars);48    packet49}50
51fn parse_num(list: &[char]) -> (Packet, &[char]) {52    // find the index where the first number ends53    let mut i = 0;54    while i < list.len() && list[i].is_ascii_digit() {55        i += 1;56    }57
58    // parse the number59    // uses math to concatenate numbers instead of turning them into a string first to parse that60    let mut num = 0;61    let mut offset = 1;62    for c in list[..i].iter().rev() {63        num += (*c as u8 - b'0') * offset;64        offset *= 10;65    }66
67    // return the number and the rest of the packet68    (Packet::Num(num), &list[i..])69}70
71fn parse_list(list: &[char]) -> (Packet, &[char]) {72    // start by removing the starting [ of the passed in list73    // at the end of this function, we remove the ending ] of the passed in list74    let mut list = &list[1..];75    let mut packets = Vec::new();76
77    loop {78        match list {79            // list ended, break the loop80            ']' => break,81            // skip over ,82            ',' => list = &list[1..],83            // beginning of new list, time for recursion to parse the inner list84            '[' => {85                let (packet, rest) = parse_list(list);86                packets.push(packet);87                list = rest;88            }89            // beginning of a number90            _ => {91                let (n, rest) = parse_num(list);92                packets.push(n);93                list = rest;94            }95        }96    }97
98    // return the parsed list and the remaining characters minus the ] that terminates the list this just parsed99    (Packet::List(packets), &list[1..])100}101
102pub fn part_1() -> usize {103    let pairs = parse();104
105    pairs106        .iter()107        .positions(|[left, right]| left < right)108        .map(|idx| idx + 1)109        .sum()110}111
112pub fn part_2() -> usize {113    let pairs = parse();114    let mut packets: Vec<_> = pairs.iter().flatten().collect();115
116    let divider_1 = parse_packet("[]");117    let divider_2 = parse_packet("[]");118
119    packets.push(&divider_1);120    packets.push(&divider_2);121
122    packets.sort_unstable();123
124    packets125        .into_iter()126        .positions(|packet| packet == &divider_1 || packet == &divider_2)127        .map(|idx| idx + 1)128        .product()129}