Advent of Code 2024 Day 1, with Rust on an RP2040 microcontroller

Home | Archive

The first few problems in the Advent of Code are usually simple, so I thought maybe it would be interesting to try solving them on a microcontroller. The inability to use data structures like hash tables or vector, set etc might make even the simple problems more challenging.

I used a Raspberry Pi Pico (rp2040 controller with 264kB RAM, not the Pi that runs Linux) connected to my laptop using the raspberry pi debug probe. The debug probe provides a serial interface which is used to communicate with the rp2040 processor. Code is written in Rust, using the rp-hal.

Day 1, Part 1

A simple problem that involves sorting two arrays in ascending order, taking the absolute difference of the corresponding elements and summing them up.

Rust doesn’t have a sorting method in no_std (I was wrong), so we need to implement a sorting method. It is not reasonable to torture a microcontroller with an O(n^2) algorithm, so we need something that is O(nlogn).

A small Python script will stream the data in the two arrays (each array contains 1000 integers) to the UART - the code running on the microcontroller will store the numbers as two min-heaps:

// min-heap
fn sift_up(xs: &mut [i32], mut k: usize) {
    while k > 1 {
        if xs[k / 2] > xs[k] {
            (xs[k / 2], xs[k]) = (xs[k], xs[k / 2]);
        } else {
            break;
        }
        k /= 2;
    }
}

Once the two heaps are constructed, we continuously extract the min elements from both the heaps and do the required computation on those elements:

while i > 1 {
    // buf1[1] and buf2[1] are the smallest items on the
    // min-heap.
    sum += buf1[1].abs_diff(buf2[1]);
    (buf1[1], buf1[i]) = (buf1[i], buf1[1]);
    (buf2[1], buf2[i]) = (buf2[i], buf2[1]);
    i -= 1;
    sift_down(&mut buf1, i);
    sift_down(&mut buf2, i);
}
sum += buf1[1].abs_diff(buf2[1]);
writeln!(tx, "result = {}", sum).unwrap();

Check out the code here.

Sorting in no_std rust

A bit of googling later revealed that the sort_unstable method is no_std! So we can get rid of all that heap manipulation code and write something short and sweet:

buf1.sort_unstable();
buf2.sort_unstable();

let sum: u32 = buf1
   .iter()
   .zip(buf2.iter())
   .map(|(&x, &y)| x.abs_diff(y))
   .sum();
writeln!(tx, "result = {}", sum).unwrap();

This is the same high-level code that you will normally write to solve this problem, and it works perfectly on a small microcontroller! No need to worry about efficiency either; Rust/LLVM will aggressively optimize the code so that at the machine level you will see the equivalent of a simple loop that just takes the absolute difference between corresponding elements of two arrays and sums them up!

Check out the code here.

Day 1, Part 2

In Part 2, we do a different kind of computation with the elements of the two arrays; please check the Advent of code web site for the details. Here is the code that runs on the rp2040. I am sure there is some simple code we can write using iterators to solve this, but the implementation in score_new was what I was able to come up with at that moment.