Advent of Rust 9: Find That Number, (F)or Else

Welcome again to the not-so-stream-of-consciousness log, where the puns in the titles get worse every day. Today’s topic is the same as every day’s topic: me teaching myself the Rust programming language by doing programming puzzles from Advent of Code 2020.

Day 9, Part 1

Today’s puzzle is to analyze a long list of numbers, pretending that we are breaking an encryption scheme! The answer to the puzzle is the first number in the list (starting at position 26) that is not the sum of two numbers out of the “preamble” consisting of the previous 25 numbers in the list. Wow, that’s a technically correct but very confusing way to say it. Imagine, if you will, a snake moving through the list whose head is one number and whose tail is 25 numbers. If the snake’s head does not equal the sum of any two of the numbers from the snake’s tail, then the head number is the answer.1

As usual I start with cargo new puzzle9, download the input file, and set up puzzle9.rs with the boilerplate, as I did with puzzle8.rs yesterday.

Someone else might know a more efficient way to solve this,2 but I’m going to try to solve it with brute force and Itertools! I will use tuple_windows() to iterate through windows of length 26, and check the tuple_combinations() of the first 25 numbers of the window. I add itertools to Cargo.toml and use itertools::Itertools; to the top of the file.

First I write a map(|s| s.parse().unwrap()) that parses the numbers, then I try to iterate through windows. I’m soon disappointed that tuple_windows() only supports up to a window length of 4! I put the items into a vector instead and implement the window iteration myself, by taking a slice of &numbers[from..to].

Since I need to stop the tuple_combinations() loop when a sum is found, but stop the tuple_windows() loop when the inner loop is not stopped, I am wondering if Rust has a for-else construct like Python does. I google “rust for else” but find that it does not, although I do read that the loop expression (which I am seeing now for the first time) can actually return a value by using break value;, which is something I’ve never encountered before in a programming language! I wonder if the for loop can do this too? I read a bit more and find that no, it cannot.

Ugh, I don’t much like the found = true idiom ever since I learned about Python’s for-else, but nothing to do I guess, unless I want to refactor this into a separate function. And I don’t! I just cram it all in one main() function:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let window_size = 25;
    let mut answer = None;
    for ix in window_size..numbers.len() {
        let preamble = &numbers[(ix - window_size)..ix];
        let mut valid = false;
        for (a, b) in preamble.iter().tuple_combinations() {
            if a + b == numbers[ix] {
                valid = true;
                break;
            }
        }
        if !valid {
            answer = Some(numbers[ix]);
            break;
        }
    }

    println!("{}", answer.unwrap());

    Ok(())
}

Some interesting mistakes that I made:

  • I originally tried to parse the file as a list of u32 because I didn’t scroll down far enough and see that there were huge numbers, so I got a panic on parse().
  • I made the window_size 5 initially instead of 25, because I was confused with the example given in the text.
  • I forgot all the muts on my variables.
  • I thought I was being clever by making answer an Option, but then I was not clever enough to remember to assert that the answer was actually found, with unwrap().

Despite the mistakes I was happy to see that the compiler could infer the type of parse() without having to specify parse::<u64>().

This program gives me the answer, and so I can unlock Part 2 of the puzzle.

Day 9, Part 2

This is the first Part 2 of a puzzle that actually uses the answer from Part 1! So I don’t need the is_part2() function today.

This time, I must find a contiguous set of at least two numbers in the list that add up to the answer of Part 1. The answer to Part 2 is the sum of the smallest and largest number in that set.

I’m going to have to do a lot more iteration over sliding windows of the list in this one! That tuple_windows() iterator sure would be nice. I do a bit more searching and find what I hadn’t realized before: you can do sliding windows of arbitrary size with windows(), on a slice, just not on an iterator. I’d really prefer to use windows(),3 so maybe I can refactor Part 1 to do that before I write Part 2.

for window in numbers.windows(window_size + 1) {
    let preamble = &window[..window_size];
    let number = *window.last().unwrap();
    let mut valid = false;
    for (a, b) in preamble.iter().tuple_combinations() {
        if a + b == number {
            valid = true;
            break;
        }
    }
    if !valid {
        answer = Some(number);
        break;
    }
}

This is a bit more readable!

Now to write Part 2. I will start with sliding windows of 2 contiguous elements and keep increasing the window size until I find the answer:

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                return Some(window.first().unwrap() + window.last().unwrap());
            }
        }
    }
    None
}

I get this to compile without too much trouble. I have to specify the type of sum::<u64> and I don’t understand why, similar to an error I got a few days ago. Helpfully, cargo clippy tells me to use &[u64] as the type of the first parameter instead of &Vec<u64>. Nonetheless, it doesn’t work. The answer is wrong, and this time the website doesn’t say if it’s too high or too low (probably because it’s not relevant.) I debug-print the window of numbers to try to get a clue about why the answer is wrong, and I find out that I added the first and last number in the window, not the largest and smallest number as I was supposed to.

This is a nice excuse to use the Itertools minmax() method, which I scrolled past a few days ago and thought was cool! I now read that it has an enum return type, which luckily I learned about yesterday, so I think I should know how to get an answer out of it. I try this:

let itertools::MinMaxResult::MinMax(largest, smallest) = window.iter().minmax();

I wasn’t sure if let with an enum-pattern would even work, but I decided to try it, as I thought I had seen it elsewhere in an example. I originally thought this would assert that the result was not one of the other variants of the enum (NoElements or OneElement.) But instead, the compiler tells me “let bindings require an ‘irrefutable pattern’, like a struct or an enum with only one variant”, and suggests using if let. That seems like a good suggestion, but instead I peeked into the documentation for itertools::MinMaxResult and decided to use into_option() instead:

let (largest, smallest) = window.iter().minmax().into_option().unwrap();

Other than that, it worked well! I got the right answer and solved the puzzle.

Now that I have a nice-looking encryption_weakness() function, I’d really like to refactor Part 1 to remove this horrible valid = true thing. I create a function invalid_number and that lets me return instead of the outer break statement. In addition, I realize that I can use Iterator::any() to get rid of the inner break statement.

Full code:

use itertools::Itertools;
use std::fs;
use std::io::{self, BufRead};

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let answer = invalid_number(&numbers, 25).unwrap();

    println!("Part 1: {}", answer);
    println!("Part 2: {}", encryption_weakness(&numbers, answer).unwrap());

    Ok(())
}

fn invalid_number(numbers: &[u64], window_size: usize) -> Option<u64> {
    for window in numbers.windows(window_size + 1) {
        let preamble = &window[..window_size];
        let number = window[window_size];
        if !preamble
            .iter()
            .tuple_combinations()
            .any(|(a, b)| a + b == number)
        {
            return Some(number);
        }
    }
    None
}

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                let (largest, smallest) = window.iter().minmax().into_option().unwrap();
                return Some(largest + smallest);
            }
        }
    }
    None
}

fn read_lines(file: fs::File) -> impl Iterator<Item = String> {
    io::BufReader::new(file).lines().map(|res| res.unwrap())
}

Afterword

I solved this puzzle fairly quickly. I can think of two reasons why: I was relatively familiar with Itertools because I’ve been using it often in the past few days, and I also managed to think of a solution for both parts of the puzzle that was able to be implemented by composing parts of Itertools and the standard library that I was already familiar with, or at least knew what to look for.

What can I say? I just love Itertools. I think having practiced solving Advent of Code puzzles with it, will also make me reach for Python’s itertools more often when I’m programming in Python.

Having now written two functions that return Option<u64>, I do wonder how Rust stores this type internally! Is it two 8-byte words with 63 wasted bits, or is it 9 bytes with 7 wasted bits?

I’m liking the abbreviated style that I’ve been using for the past couple of days and I think I’ll continue it.


[1] I’m not sure that’s clear either, but hopefully it will become clear from the code. Code might be difficult to read, but at least it’s unambiguous

[2] Writing this later, I wonder if a more efficient solution would involve sorting the arrays to eliminate some of the combinations? I don’t plan to spend time on it though

[3] Never thought I’d be writing those words on this blog