Home Log in

Dec 14, 2022

6 min #rust · #advent-of-code

Day 13 (Advent of Code 2022)

From the series Advent of Code 2022

👋 This page was last updated ~2 years ago. Just so you know.

The day 13 puzzle needs a speech therapist.

???

...because it has an awful lisp!! Ahhhahahahhhh

Are you ok? What is.. what is going on with you?

No but seriously we have what are ostensibly S-expressions, except they use JSON-adjacent notation:

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

And you know the saying: if it looks like JSON, and it quacks like JSON, you can just use serde_json.

Shell session

$ cargo add serde -F derive
(cut)
$ cargo add serde_json

Rust code

use serde::Deserialize;

#[derive(Deserialize, Clone, PartialEq, Eq)]
#[serde(untagged)]
enum Node {
    Number(u64),
    List(Vec<Node>),
}

Let's add a nice Debug impl:

Rust code

impl fmt::Debug for Node {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Number(n) => write!(f, "{n}"),
            Self::List(n) => f.debug_list().entries(n).finish(),
        }
    }
}

Part 1

For Part 1, we need to sum the (1-based) indices of pairs of nodes that are in the correct order (ie. l < r).

Comparing two values in Rust is just the PartialOrd trait (and its infallible sibling, the Ord trait).

Wait wha? Comparing values is fallible now?

Yeah, because IEEE 754. Some floating point numbers are... not numbers. And cannot be compared.

Rust code

fn main() {
    dbg!(f64::NAN > f64::NAN);
    dbg!(f64::NAN < f64::NAN);
    dbg!(f64::NAN == f64::NAN);
    dbg!(f64::NAN.partial_cmp(&f64::NAN));
}

Shell session

$ cargo run
   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.85s
     Running `target/debug/playground`
[src/main.rs:2] f64::NAN > f64::NAN = false
[src/main.rs:3] f64::NAN < f64::NAN = false
[src/main.rs:4] f64::NAN == f64::NAN = false
[src/main.rs:5] f64::NAN.partial_cmp(&f64::NAN) = None

Anyway, the problem statement tells us how to compare "a list and a number", and it's to pretend that the number is a list of size 1, so, let's pretend:

Rust code

impl Node {
    fn with_slice<T>(&self, f: impl FnOnce(&[Node]) -> T) -> T {
        match self {
            Self::List(n) => f(&n[..]),
            Self::Number(n) => f(&[Self::Number(*n)]),
        }
    }
}

This implementation is interesting: if we returned a Vec<T>, we wouldn't need to take a closure. Returning a &[T] works for the Self::List arm, but not for the Self::Number arm (try it!).

So, this is a common-ish pattern in Rust: just let the caller do whatever with borrowed locals, in a closure. This gets dicier with async (for now), but here it works beautifully.

Now we can implement PartialOrd and Ord:

Rust code

impl std::cmp::PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match (self, other) {
            (Node::Number(a), Node::Number(b)) => a.partial_cmp(b),
            (l, r) => Some(l.with_slice(|l| {
                r.with_slice(|r| {
                    l.iter()
                        .zip(r.iter())
                        .map(|(aa, bb)| aa.cmp(bb))
                        // return the first ordering that isn't `Equal`
                        .find(|&ord| ord != Ordering::Equal)
                        // or compare the lengths
                        .unwrap_or_else(|| l.len().cmp(&r.len()))
                })
            })),
        }
    }
}

impl std::cmp::Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

And then the part 1 solution simply becomes:

Rust code

fn main() {
    let mut sum = 0;
    for (i, groups) in include_str!("sample-input.txt").split("\n\n").enumerate() {
        let i = i + 1;

        let mut nodes = groups
            .lines()
            .map(|line| serde_json::from_str::<Node>(line).unwrap());
        let l = nodes.next().unwrap();
        let r = nodes.next().unwrap();
        println!("\n== Pair {i} ==");
        println!("l = {l:?}");
        println!("r = {r:?}");
        println!("l < r = {}", l < r);
        if l < r {
            sum += i;
        }
    }
    dbg!(sum);
}

You can golf that down with iterators, but I wanted the output to be somewhat verbose as I didn't want any bad surprises.

Simplifying the `Ord` implementation

As it turns out, the comparison described in the problem statement has the same semantics as the comparison for slices (&[T] where T implements Ord), so we can simplify our implementation to:

Rust code

impl std::cmp::PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        match (self, other) {
            (Node::Number(a), Node::Number(b)) => a.partial_cmp(b),
            (l, r) => l.with_slice(|l| r.with_slice(|r| l.partial_cmp(r))),
        }
    }
}

Thanks to korrat on GitHub, DelinquentFlower on Reddit, and many others for the suggestion.

Part 2

In part 2, we need to sort all inputs plus two "divider packets", [2], and [6], and multiply the (1-based) indices of those two divider packets, once sorted.

Because sorting a slice of T where T: Ord is in the Rust standard library, this is straightforward:

Rust code

fn main() {
    let dividers = vec![
        Node::List(vec![Node::Number(2)]),
        Node::List(vec![Node::Number(6)]),
    ];

    let mut packets = include_str!("input.txt")
        .lines()
        .filter(|s| !s.is_empty())
        .map(|line| serde_json::from_str::<Node>(line).unwrap())
        .chain(dividers.iter().cloned())
        .collect::<Vec<_>>();

    packets.sort();

    let decoder_key = dividers
        .iter()
        .map(|d| packets.binary_search(d).unwrap() + 1)
        .product::<usize>();

    dbg!(decoder_key);
}

Note that we're able to use binary_search rather than find because at that point, packets is sorted.

Cool bear's hot tip

We don't have to sort the packets, we can simply count the packets below each divider packet, thanks korrat on GitHub for the suggestion!

And voilà! Shortest Advent of Code article yet.

You're reading the Advent of Code 2022 series.

Thanks to my sponsors: Lyssieth, Nicholas Bishop, Lev Khoroshansky, Matt Heise, Marty Penner, Alejandro Angulo, Andrew Neth, Boris Dolgov, Steven McGuire, Richard Pringle, Raine Tingley, Brandon Piña, Ryan, Ivo Murrell, Guillaume E, jer, Christian Bourjau, Max Heaton, Sam, henrique-pinto and 227 more

Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Donate on GitHub Donate on Patreon

Here's another article just for you:

Cracking Electron apps open

Jul 03, 2023

29 min #electron · #rust · #asar

I use the draw.io desktop app to make diagrams for my website. I run it on an actual desktop, like Windows or macOS, but the asset pipeline that converts .drawio files, to .pdf, to .svg, and then to .svg again (but smaller) runs on Linux.

So I have a Rust program somewhere that opens headless chromium, and loads just the HTML/JS/CSS part of draw.io I need to render my diagrams, and then use Chromium's "print to PDF" functionality to save a PDF.

Part 1
Simplifying the Ord implementation
Part 2

Day 13 (Advent of Code 2022)

Part 1

Simplifying the Ord implementation

Part 2

Contents

Simplifying the `Ord` implementation