Nime
Metadata
Table of contents

Advent of Code 2022 Day 13

Day 13: Distress Signal

https://adventofcode.com/2022/day/13

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]


[[1],[2,3,4]]
[[1],4]


[9]
[[8,7,6]]


[[4,4],4,4]
[[4,4],4,4,4]


[7,7,7,7]
[7,7,7]


[]
[3]


[[[]]]
[[]]


[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[0] {
            // 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.

[[2]]
[[6]]

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("[[2]]");
    let divider_2 = parse_packet("[[6]]");


    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
use std::cmp::Ordering;


use itertools::Itertools;


#[derive(Debug, PartialEq, Clone, 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))
    }
}


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


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
}


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[0] {
            // 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 just parsed
    (Packet::List(packets), &list[1..])
}


pub fn part_1() -> usize {
    let pairs = parse();


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


pub fn part_2() -> usize {
    let pairs = parse();
    let mut packets: Vec<_> = pairs.iter().flatten().collect();


    let divider_1 = parse_packet("[[2]]");
    let divider_2 = parse_packet("[[6]]");


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