Advent of Code 2022 - Day 13
Tags: adventofcode, rust, programming
Published: 2022-12-27 21:19:17

---
title: Advent of Code 2022 - Day 13
published: true
date: 2022-12-13 00:00:00 UTC
tags: adventofcode, rust, programming
canonical_url: https://www.ericburden.work/blog/2022/12/13/advent-of-code-2022-day-13/
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nmjrf5vbuon63waywtzy.png
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Rust](https://www.rust-lang.org/). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2022) as well. After finishing last year (and 2015-2019) in [Julia](https://julialang.org/), I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 13 - Distress Signal

Find the problem description [HERE](https://adventofcode.com/2022/day/13).

## The Input - Yo Dawg, I Heard You Like Packets

I won’t lie to you, I really don’t like dealing with recursive data structures in Rust. It probably stems from the fact that one of the early coding puzzles I cleverly decided to leverage to learn the language involved flattening arbitrarily nested lists. The puzzle itself was no big deal, but figuring out how to have _arbitrarily_ nested lists was probably more than I was ready for at the time. Which is why I was so surprised at how _readily_ `nom` was able to handle these recursive packets!

```rust
/// Represnts a Packet. Packet data consists of lists and integer (that's what the
/// puzzle says, anyway).
#[derive(Debug, Clone, PartialEq, Eq)]
enum Packet {
    Integer(u8),
    List(Vec<Packet>),
}

/// Represents a pair of packets. Riveting stuff!
#[derive(Debug, Clone)]
struct PacketPair(Packet, Packet);

/// Here's where the magic happens. This module wraps the parsers for the list of
/// packet pairs presented in the input.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::tag,
        character::complete::{newline, u8},
        combinator::map,
        multi::{separated_list0, separated_list1},
        sequence::{delimited, separated_pair},
        Finish, IResult,
    };

    /// Nom parser for "2" -> Packet::Integer(2)
    fn integer(s: &str) -> IResult<&str, Packet> {
        map(u8, Packet::Integer)(s)
    }

    /// This is where the recursion happens. This parser parses lists of
    /// packet information into their appropriate packet representation.
    /// Parses all of the following:
    /// - "[]" -> Packet::List([])
    /// - "[5]" -> Packet::List([Packet::Integer(5)])
    /// - "[1, 2]" -> Packet::List([Packet::Integer(1), Packet::Integer(2)])
    /// - "[1, [2]]" -> Packet::List([Packet::Integer(1), Packet::List([Packet::Integer(2)])])
    fn list(s: &str) -> IResult<&str, Packet> {
        let list_contents = separated_list0(tag(","), packet);
        map(delimited(tag("["), list_contents, tag("]")), Packet::List)(s)
    }

    /// Packet data consists of lists and integers. This parser will parse a `Packet`
    /// from a list or things or from a single integer.
    fn packet(s: &str) -> IResult<&str, Packet> {
        alt((integer, list))(s)
    }

    /// Parses two packets separated by a newline into a `PacketPair`
    fn packet_pair(s: &str) -> IResult<&str, PacketPair> {
        let (s, (first, second)) = separated_pair(packet, newline, packet)(s)?;
        Ok((s, PacketPair(first, second)))
    }

    /// Parses a list of packet pairs separated by an empty line into a `Vec<PacketPair>`
    pub fn parse(s: &str) -> Result<Vec<PacketPair>> {
        let result = separated_list1(tag("\n\n"), packet_pair)(s).finish();
        let (_, pair_list) = result.map_err(|e| anyhow!("{e}"))?;
        Ok(pair_list)
    }
}

const INPUT: &str = include_str!("../../input/13/input.txt");

/// Parse that input!
fn read() -> Vec<PacketPair> {
    parser::parse(INPUT).unwrap()
}

```

Three functions with four total lines for parsing a single line into a nested`Packet`. Not too shabby!

## Part One - Peter Piper Picked a Pair of Pretty Packets

Well, well, well. Looks like those elves who left us in the river are in need of some help. Probably mis-labeled the snacks or something else equally disastrous. Well, as it turns out, we have exactly the right pair of traits in Rust to deal with this sort of situation: `Ord` and `PartialOrd`.

```rust
use std::cmp::Ordering;

/// Solve Day 13, Part 1
fn solve(input: &Vec<PacketPair>) -> u32 {
    let mut total = 0; // The total index value of proper sorted pairs

    // For each pair of packets...
    for (idx, packet_pair) in input.iter().enumerate() {
        // If it's not sorted correctly, skip.
        if !packet_pair.is_sorted() {
            continue;
        }

        // Otherwise, add the value of its index to the total
        total += (idx as u32) + 1; // Packets are 1-indexed
    }
    total
}

impl PacketPair {
    /// Indicates if the first packet in a pair is less than the second
    /// packet in the pair.
    fn is_sorted(&self) -> bool {
        let Self(first, second) = self;
        first < second
    }
}

/// Partial ordering for `Packet`s. Defining this would be enough to use
/// `Packet` < `Packet`, but we won't be able to do a full sort without
/// implementing `Ord` as well.
impl PartialOrd for Packet {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Defines the result of comparing one `Packet` to another, used for ordinal
/// comparisons and sorting. Returns an enum that indicates whether `self` is
/// less than, greater than, or even equal to `other`.
impl Ord for Packet {
    fn cmp(&self, other: &Self) -> Ordering {
        use Packet::*; // For syntax
        match (self, other) {
            // When comparing two packet integers, just compare them by value
            (Integer(i1), Integer(i2)) => i1.cmp(i2),

            // When comparing a packet integer to a packet list, convert the integer
            // to a single item list and compare the two lists.
            (Integer(i), List(_)) => List(vec![Integer(*i)]).cmp(other),
            (List(_), Integer(i)) => self.cmp(&List(vec![Integer(*i)])),

            // When comparing two lists, compare item by item and return the first
            // result where the two items aren't equal. If one list has more items
            // than another and all the values up to the length of the shortest list
            // are equal, then we compare the length of the lists.
            (List(l1), List(l2)) => {
                for (first, second) in l1.iter().zip(l2.iter()) {
                    let result = first.cmp(second);
                    let Ordering::Equal = result else { return result; };
                }
                l1.len().cmp(&l2.len())
            }
        }
    }
}

```

Really, it’s mostly a matter of implementing the sorting rules as written. Granted, they are written a bit confusingly (for me, at least), but the examples help make it clear what we need to do. Once we know how to handle the three different situations, we implement those rules, and _voila_!

## Part Two - The Dividing Line(s)

Looks like implementing those traits was exactly the right call. Since we can sort `Packet`s without any extra work, all we need to do is flatten our list of packet pairs, add the dividers, and sort. Nice.

```rust
/// Solve Day 13, Part 2
fn solve(input: &Vec<PacketPair>) -> u32 {
    use Packet::*; // For syntax

    // Define the two divider packets and put them in an array to add them
    // to the list of all the packets.
    let divider1 = List(vec![List(vec![Integer(2)])]);
    let divider2 = List(vec![List(vec![Integer(6)])]);
    let dividers = [divider1, divider2];

    // Flatten all the pairs of packets into a list of packets with the two
    // divider packets added to the end.
    let mut all_packets = input
        .iter()
        .cloned()
        .flatten()
        .chain(dividers.iter().cloned())
        .collect::<Vec<_>>();

    // Sort all the packets! No need to do any more work than that, since
    // by implementing Ord and PartialOrd, we've done all we need to
    // sort them.
    all_packets.sort_unstable();

    // Find the indices of the two divider packets and return their product.
    let mut total = 1;
    for (idx, packet) in all_packets.iter().enumerate() {
        if dividers.contains(packet) {
            total *= (idx as u32) + 1;
        }
    }
    total
}

// It's easier to flatten the packet pairs into a 1D list when we can
// iterate over the two packets contained in them.
impl IntoIterator for PacketPair {
    type Item = Packet;
    type IntoIter = std::array::IntoIter<Self::Item, 2>;

    fn into_iter(self) -> Self::IntoIter {
        let PacketPair(first, second) = self;
        [first, second].into_iter()
    }
}

```

We could probably have done without the gnarly iterator chain to flatten the pairs, but I kind of _like_ iterator chains. They remind me of pipes in R and Julia, which I’m a big fan of.

## Wrap Up

Today represents the first day where I really felt like using `nom` made solving the puzzle _easier_. Frankly, I was a bit surprised when my initial attempt worked flawlessly. I just knew there would be something confusing in recursively parsing those packets, but it really just came down to writing rules and having the parser follow them. Beyond that, the Rust trait system really provided an ergonomic experience for solving this one. All in all, this was a puzzle that seemed almost designed for the language and approach I’ve been taking this year. About time! Let’s see what tomorrow brings.