December Adventure 2024

Day 1 - This website

I guess my first entry for this adventure is this very website! I had toyed with the idea of having a personnal website in addition to my social media presence, but I only acted upon it just now. Hurray!

I really didn't want to bother setting up some kind of blogging infrastructure like Hugo, and I wanted something custom and light. So everything here is written by hand in HTML and CSS! One part that is automated is code syntax highlighting. I use a small shell script that takes a file containing some code, runs it through Pandoc, and outputs HTML formatted so that each token family (keywords, string literals, ...) are in their own little spans. After that, I simply wrote some CSS that sets their colour! Check it out:

// my awesome fibo
fn fibo() -> impl Iterator<Item = u32> {
    std::iter::successors(Some((1u32, 0)), |&(a, b)| a.checked_add(b).map(|s| (b, s)))
        .map(|(_, u)| u)
}

fn main() {
    for n in fibo().take(10) {
        println!("{n}");
    }
}

Hopefully it's readable enough!

Day 4 - Advent of Code text parsing

Yeah yeah I said I'd rather do something low-key, but honestly work has been pretty hectic these days and I had very little time to work on projects myself. So the only thing I had time to do (at work hehe 😊) is AoC! I can't exactly share my progress on AoC since I'm publishing my code on my professional git repository which I'd rather not link to my online identity.

Not a lot to share on that front, since I can't exactly show my code. But I'm really proud of my solution of day 3! I could have used regular expressions but I'm not exactly versed in it and I wanted to use something quick and easy that I already know. Enter nom!

I really like that library because it lets you write pretty complicated parsers in, in my opinion, a pretty intuitive way. See for example what I did to parse the problem input:

fn decimal(input: &str) -> IResult<&str, &str> {
    recognize(many1(one_of("0123456789")))(input)
}

fn parse_mul(input: &str) -> IResult<&str, Instruction> {
    map(
        preceded(
            tag("mul"),
            delimited(
                tag("("),
                separated_pair(decimal, tag(","), decimal),
                tag(")"),
            ),
        ),
        |(a, b)| Instruction::Mul(a.parse::<u32>().unwrap() * b.parse::<u32>().unwrap()),
    )(input)
}

Nom is full of these little parser functions that perfectly combine and compose together. For example, preceded() will call two parsers and discard the first result, since we care about the thing being preceded by the first parser. In our case, we need to make sure "mul" is parsed before finding numbers, but we don't really care that it's there once we find it. We only need the numbers. In the same vein, separated_pair() takes 3 parsers and discards the middle one, as we care about the pair, and not the separator.

I hope I helped people discover this very handy library so that you may never have to write parsers by hand!

Day 7 - Website gallery

Oops several days passed without me noticing! In any case, I finished the gallery section of my website. I'll update it as I go, but I already put some artwork that I really like. I don't know yet how I'm going to handle doodles, but I put one such doodle in the gallery as a standalone piece. We'll see as I go!

Next, I think I'll finish a commission that has been piling up dust. Sorry to the commissionner! But at least this will count towards December Adventure and I'll be quite happy!

Day 12 - A cautionary tale about Itertools and ranges

A very interesting "bug" happened while doing today's Advent of Code, and I thought I'd share it! For my solution, I was working with a vector of Range<usize>, that needed to be merged down to contiguous ranges if they were overlapping or neighbouring. The function looks like this:

fn merge_range_array(v: &mut Vec<Range<usize>>) {
    let mut v2 = Vec::new();
    core::mem::swap(&mut v2, v);

    *v = v2.into_iter().fold(Vec::new(), |mut v, r| {
        if let Some(last) = v.last_mut() {
            if last.contains(&r.start) || last.end == r.start {
                last.end = r.end;
            } else {
                v.push(r);
            }
        } else {
            v.push(r);
        }

        v
    });
}

As an example, imagine the initial vector contains [2..3, 3..4]. This function should detect both ranges are contiguous, and merge them down into a single range: [2..4]. However, what I got was [3..4]!

After debugging with copious amount of println!, I determined that calling last.contains() somehow modifies the start field of that range. But that shouldn't be happening! That function is defined to be immutable, and its extremely simple. Here it is (after following the cast from Range to RangeBounds):

#[inline]
#[stable(feature = "range_contains", since = "1.35.0")]
fn contains<U>(&self, item: &U) -> bool
where
    T: PartialOrd<U>,
    U: ?Sized + PartialOrd<T>,
{
    (match self.start_bound() {
        Included(start) => start <= item,
        Excluded(start) => start < item,
        Unbounded => true,
    }) && (match self.end_bound() {
        Included(end) => item <= end,
        Excluded(end) => item < end,
        Unbounded => true,
    })
}

Nothing in this function modifies the start field! After scratching my head for a long while, I cautiously began to suspect some kind of miscompilation, but I couldn't reproduce the issue on the playground. After continuing all sorts of tests and debugging, I wanted to look at the definition of contains() again, but instead of going to the Rust documentation through my browser, I directly used LSP to go to the definition of the function in my IDE. And, to my greatest surprise, what I got was completely different than what I expected:

fn contains<Q>(&mut self, query: &Q) -> bool
where
    Self: Sized,
    Self::Item: Borrow<Q>,
    Q: PartialEq,
{
    self.any(|x| x.borrow() == query)
}

This is the source of the contains() function defined in the itertools https://docs.rs/itertools library! As it turned out, I often import itertools when solving Advent of Code problems as I often need a function or two from that library. What happens here is unfortunate: Range implements the Iterator trait. itertools defines all of its functions as extensions of the Iterator trait, meaning that a Range has access to all functions provided by itertools when it's imported. As trait functions take priority over strucure-defined functions, it overshadows the implementation I intended to use; and since they both have the same signature (save for the mutable self, which co-incidentally was allowed in my case), this overshadowing was completely silent.

This itertools-defined function advances the iterator to find an element in it. The way Range implements Iterator is by using its start field as a counter to know when iteration is finished. And since the range in our example is 2..3, it contains one element, 2, which is not 3. So the range gets entirely consumed, setting its start field to 3 and inducing the weird behaviour that drove me mad for a couple of hours!

In conclusion: watch out when using itertools and manipulating ranges! Don't forget they're iterators too!