AoC 2022 Day 13: List Parsinator

Source: Distress Signal

Part 1

Given pairs of Signals (where a Signal is a nested list ;example: [[1],[2,3,4]]), count how many pairs are ‘in order’.

One Signal is less than the other if:

  • Both are an integer and the first is less than the second
  • Both are a list and the first value is less than the second
    • If the first values are the same, compare the second
    • If the first has fewer elements, it is treated as less than the second
  • When comparing an integer and a list, wrap the integer as a single element list and compare them

This is actually a pretty fun problem. Basically, it breaks down into two halves:

  • Parse a recursive list structure From<String>
  • Implement PartialOrd for two lists

So let’s do it!

First, parsing:

#[derive(Clone, Debug, Ord, Eq, PartialEq)]
enum Signal {

impl From<String> for Signal {
    fn from(line: String) -> Self {
        let stack = RefCell::new(Vec::new());
        let current_number = RefCell::new(String::new());

        // Push an initial 'wrapper' list that we'll remove before returning

        // Helper function that will check if we're currently parsing a number
        // If so, push it onto the current list (malformed input if it's not a list)
        let try_push_number = || {
            if current_number.borrow().is_empty() {
            let value = current_number
                .expect("number should be a number");


            match stack
                .expect("must still have one item to push to")
                Signal::List(v) => {
                _ => panic!("malformed stack, expected list to put thing in"),

        // Process the input one char at a time
        for c in line.chars() {
            match c {
                // Start a new nested list
                '[' => {
                // Finish the most recent nested list
                // Make sure to finish a number if we were parsing one
                // Then push this list into the one before it as an element
                ']' => {

                    let thing = stack.borrow_mut().pop().expect("mismatched []");
                    match stack
                        .expect("must still have one item to push to")
                        Signal::List(v) => {
                        _ => panic!("malformed stack, expected list to put thing in"),
                // Finish the current number and start a new one
                ',' => {
                // Building up a number one digit at a time
                c if c.is_digit(10) => {
                // Anything else is bad input
                _ => panic!("unexpected char {}", c),

        // Verify that we have exactly one element left
        assert_eq!(stack.borrow().len(), 1);
        let wrapper = stack.borrow_mut().pop().unwrap();

        // Unwrap the initial 'wrapper' list we made at the beginning
        match wrapper {
            Signal::List(v) if v.len() == 1 => v[0].clone(),
            _ => panic!("must end with the final wrapper list with only one element"),

I’ve commented the heck out of it, but what it boils down to is that you have three special characters:

  • [ starts a sublist
  • , delimits elements, finishing the parsing of a number
  • ] ends a sublist (and also finishing the parsing of a number)

Anything else is part of a digit. So we build up the numbers and keep a stack of which list we’re currently building up on. When we finish a list, attach it to the parent.

There’s one interesting bit in that we wrap the whole thing up in an initial List. This mostly makes the parsing easier. We don’t need a special case for the first level, just remove the wrapper at the end.

Now that we have the lists, we want to PartialOrd them:

// Doing PartialOrd instead of Ord to get the 'correct' default behavior for Vecs in List
impl PartialOrd for Signal {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        use Signal::*;

        match (self, other) {
            // Two values or two lists use the built in partial_cmp functions
            (Value(a), Value(b)) => a.partial_cmp(b),
            (List(a), List(b)) => a.partial_cmp(b),
            // One of each turns the value into a singleton list and then compares
            (Value(a), List(..)) => List(vec![Value(*a)]).partial_cmp(other),
            (List(..), Value(b)) => self.partial_cmp(&List(vec![Value(*b)])),

We do have two choices here: implementing Ord or PartialOrd. In this case, since we’re relying on the Ord/PartialOrd implementation of u8 and Vec, we want PartialOrd. Specifically, Ord will return the opposite value we want for lists of unequal length.

And there we have it:

fn part1(filename: &Path) -> String {
    let mut lines = iter_lines(filename).peekable();
    let mut sum_of_ordered = 0;

    // Iterate over pairs of input
    for index in 1.. {
        // If is_none, we've reached the end of the file
        if lines.peek().is_none() {

        // Read the signals, consume the next newline if there is one (otherwise EOF)
        let s1 = Signal::from("must have first signal"));
        let s2 = Signal::from("must have second signal"));

        if s1 < s2 {
            sum_of_ordered += index;


Grab the pairs of Signal, compare with s1 < s2 (how cool is that) and sum of the indexes in the right order.

Part 2

Take all Signals and add two special ‘divider’ values: [[2]] and [[6]]. Sort the entire list and return the product of the indices where the ‘dividers’ end up.

Nothing new to do here, just literally turn it into code:

fn part2(filename: &Path) -> String {
    // Remove newlines and parse everything else as signals
    let mut signals = iter_lines(filename)
        .filter(|line| !line.is_empty())

    // Define and add our 'divider' signals
    let dividers = vec![

    for divider in dividers.iter() {


    // Extract the indices of any dividers and multiply as requested
        .map(|d| 1 + signals.iter().position(|s| s == d).unwrap())

signals.iter().position was a fun little bit to find the dividers. I do like writing mostly-functional programming style Rust.


We’re really not doing much, the heavy part is the parsing honestly. So it’s fast:

$ ./target/release/13-list-parsinator 1 data/13.txt

took 1.420833ms

./target/release/13-list-parsinator 2 data/13.txt

took 2.013041ms