# 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 {
break;
}
}

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 `mut`s 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 {
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;

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> {
}
```

## 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

## 1 thought on “Advent of Rust 9: Find That Number, (F)or Else”

1. Thanks for the minmax suggestion in Itertools. It added a nice touch over my clumsy approach. I don’t reach for Itertools enough, so this is at least a step in the right direction for me.

This site uses Akismet to reduce spam. Learn how your comment data is processed.