This is part of the series Advent of Code 2022.
Day 13 - Advent of Code 2022
7 minute read  (1203 words)
rust advent-of-code

Day 13 starts with getting a distress signal that needs to be decoded correctly using the somewhat broken handheld device. The signal got decoded out of order, you need to re-order the list of received packets to decode the message.

The input looks as follows:

[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]

Packets come in pairs, packet data consists of lists ([]) and integers (e.g. 3). Each list starts with a opening bracket [, with zero or more comma separated values, which can either be nested lists or integers. Integers are single digits from 1 to 9.

To compare to values, the first value is left, the second is right.

  • if both values are integers, the lower integer comes first
  • if both values are lists, compare first value of each list, then second etc.
  • if one value is an integer, the other a list, convert the integer into a list with a single value, then retry comparison
  • overall the order is right when the left packet is smaller than the right

Part 1

Determine the indices of the pairs that are already in the right order and then sum them. Given the input example above the indices are 1, 2, 4 and 6. Indices start at one. The sum of these indices is 13.

First we model the packet into a nestable enum, then parse the packets using the nom crate again.

#[derive(Debug, PartialEq, Eq, Ord)]
enum Entry {
    List(Vec<Entry>),
    Int(u8),
}

impl From<&str> for Entry {
    fn from(input: &str) -> Self {
        let (_, entry) = parse_entry(input).expect("Failed to parse list");
        entry
    }
}

fn parse_entry(input: &str) -> IResult<&str, Entry> {
    alt((
        map(
            delimited(tag("["), separated_list0(tag(","), parse_entry), tag("]")),
            Entry::List,
        ),
        map(u8, Entry::Int),
    ))(input)
}

fn parse(input: &str) -> Vec<Entry> {
    input
        .lines()
        .map(str::trim)
        .filter(|line| !line.is_empty())
        .map(|line| Entry::from(line))
        .collect()
}

fn part1(pairs: &[Entry]) -> u32 {
    todo!()
}

fn main() {
    let pairs = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&pairs));
}

#[cfg(test)]
mod tests {
    use super::*;

    const INPUT: &str = include_str!("test.txt");

    #[test]
    fn check_part1() {
        assert_eq!(13, part1(&parse(INPUT)));
    }
}

The Entry enum is either an Int or a List. The latter uses a Vec to nest its own Entry items. An upside is we don't need to use a Box to hold child elements, because Vec already implements Sized.

The parse_entry function is a helper to parse either a list or a number using alt combinator. Either it parses a list [...] or a single integer using [nom::number::complete::u8]. Parsing the list is slightly more complex, the delimited function takes three parameters to specify a starting pattern, middle and end pattern. In this case the start and end brackets [ & ] are required, the inner part is parsed by separated_list0. It takes two parameters, a separator pattern (,) and another function. Passing in the parse_entry will recursively parse the lists.

The parse function reads in all lines, maps them to Entry while ignoring all empty lines. A test is set up with the expected outcome of the given example.

Packets are compared pair wise, only the pairs are of interested which are in the right order. Rust has support to compare most of its standard types, e.g. integers. It also provides a trait one can implement for custom types to compare one with another. By implementing PartialOrd correctly we should be able to compare two objects of type Entry.

impl PartialOrd for Entry {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        match (self, rhs) {
            (Entry::Int(l), Entry::Int(r)) => l.partial_cmp(r),
            (Entry::Int(l), Entry::List(r)) => vec![Entry::Int(*l)].partial_cmp(r),
            (Entry::List(l), Entry::List(r)) => l.partial_cmp(r),
            (Entry::List(l), Entry::Int(r)) => l.partial_cmp(&vec![Entry::Int(*r)]),
        }
    }
}

The trait PartialOrd allows types to form a partial order by implementing the partial_cmp function. Its output is an Option of Ordering. Either the returned variant is Less, Equal or Greater. There are four possible scenarios to compare

  • both values are integers
  • left is an integer, right is a list, convert left into a list
  • both are lists
  • left is a list, right is an integer, convert right into a list

The comparison adjusts the values if necessary, it also handles nested lists. With this comparison in place it becomes fairly straightforward to implement part1.

fn part1(pairs: &[Entry]) -> usize {
    pairs
        .iter()
        .as_slice()
        .chunks(2)
        .enumerate()
        .filter(|(_index, pair)| pair[0] < pair[1])
        .map(|(index, _)| index + 1)
        .sum()
}

The first part of this function is to group items pair-wise using chunks, which is available on the slice type. Therefore the call as_slice is required first. This returns all elements in pairs.

As we are interested in the index of the pairs enumerate is called. The filter statement compares both objects of the pair and yields only the ones that are in the right order. The map call is to pick the index only and adjust it by one. Lastly sum returns the final value.

The test should pass now, running the program outputs the solution for part 1.

Part 2

Instead of comparing pairs of packets all packets have to be put in the right order, blank lines are ignored. Furthermore the distress signal protocol requires two additional divider packets [[2]] & [[6]].

The goal is to organize all packets, including the divider packets, into the correct order then locate the divider packets in the sorted list, take their indices and multiply them. Given the sample input with the additional divider packets results in indices 10 and 14.

Let's update the tests.

fn part2(mut pairs: Vec<Entry>) -> usize {
    todo!()
}

fn main() {
    let pairs = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&pairs));
    println!("Part 2: {}", part2(pairs));
}

#[cfg(test)]
mod tests {
    // ...

    #[test]
    fn check_part2() {
        assert_eq!(140, part2(parse(INPUT)));
    }
}

The test is in place, but currently fails.

By implementing PartialOrd & deriving Eq we are also able to derive Ord on the Entry enum, which allows us to call sort_unstable on a Vec of Entry. First we add the divider entries, then we can sort the list. Lastly the indices of both divider packets are determined and then multiplied.

fn part2(mut pairs: Vec<Entry>) -> usize {
    let left = Entry::from("[[2]]");
    let right = Entry::from("[[6]]");

    pairs.push(left.clone());
    pairs.push(right.clone());
    pairs.sort_unstable();

    let first = pairs.iter().position(|p| *p == left).unwrap() + 1;
    let second = pairs.iter().position(|p| *p == right).unwrap() + 1;

    first * second
}

the pairs parameter is mutable so it can be modified inside the function. First both divider packets are created and added to pairs (Entry needs a Clone derive), then it is sorted. Lastly the indices are determined their product returned.

The test should pass now & we get the solution for the second part.