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

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    input
32        .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 input
46    // the rest of the input will be empty when it is done
47    let (packet, _) = parse_list(&chars);
48    packet
49}
50
51fn parse_num(list: &[char]) -> (Packet, &[char]) {
52    // find the index where the first number ends
53    let mut i = 0;
54    while i < list.len() && list[i].is_ascii_digit() {
55        i += 1;
56    }
57
58    // parse the number
59    // uses math to concatenate numbers instead of turning them into a string first to parse that
60    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 packet
68    (Packet::Num(num), &list[i..])
69}
70
71fn parse_list(list: &[char]) -> (Packet, &[char]) {
72    // start by removing the starting [ of the passed in list
73    // at the end of this function, we remove the ending ] of the passed in list
74    let mut list = &list[1..];
75    let mut packets = Vec::new();
76
77    loop {
78        match list[0] {
79            // list ended, break the loop
80            ']' => break,
81            // skip over ,
82            ',' => list = &list[1..],
83            // beginning of new list, time for recursion to parse the inner list
84            '[' => {
85                let (packet, rest) = parse_list(list);
86                packets.push(packet);
87                list = rest;
88            }
89            // beginning of a number
90            _ => {
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 parsed
99    (Packet::List(packets), &list[1..])
100}
101
102pub fn part_1() -> usize {
103    let pairs = parse();
104
105    pairs
106        .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("[[2]]");
117    let divider_2 = parse_packet("[[6]]");
118
119    packets.push(&divider_1);
120    packets.push(&divider_2);
121
122    packets.sort_unstable();
123
124    packets
125        .into_iter()
126        .positions(|packet| packet == &divider_1 || packet == &divider_2)
127        .map(|idx| idx + 1)
128        .product()
129}

Date

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2022 Day 13

Day 13: Distress Signal

Parsing

Part 1

Helpers

Final code

Part 2

Final code

Final code