# Day 13 (Advent of Code 2022)

This article is part of the Advent of Code 2022 series.

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.

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

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

Let's add a nice `Debug`

impl:

implfmt::DebugforNode{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{matchself{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.

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

$ 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:

implNode{fnwith_slice<T>(&self,f:implFnOnce(&[Node])->T)->T{matchself{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`

:

implstd::cmp::PartialOrdforNode{fnpartial_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()))})})),}}}implstd::cmp::OrdforNode{fncmp(&self,other:&Self)->Ordering{self.partial_cmp(other).unwrap()}}

And then the part 1 solution simply becomes:

fnmain(){letmutsum =0;for(i,groups)ininclude_str!("sample-input.txt").split("\n\n").enumerate(){leti = i +1;letmutnodes = groups.lines().map(|line| serde_json::from_str::<Node>(line).unwrap());letl = nodes.next().unwrap();letr = nodes.next().unwrap();println!("\n== Pair {i} ==");println!("l = {l:?}");println!("r = {r:?}");println!("l < r = {}", l < r);ifl < 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:

implstd::cmp::PartialOrdforNode{fnpartial_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:

fnmain(){letdividers =vec![Node::List(vec![Node::Number(2)]), Node::List(vec![Node::Number(6)]),];letmutpackets =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();letdecoder_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.

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.

This article is part 13 of the Advent of Code 2022 series.

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