Advent of Rust 14 and 15: Bits And/Or Pieces

This blog: chronicling my adventure of teaching myself the Rust programming language since December 1, courtesy of the programming puzzles at Advent of Code 2020. I’m not sure if anyone is reading anymore at this point 😆

Day 14, Part 1

Today’s puzzle is once again simulating some computer instructions, although the model this time is simple enough that I don’t feel I have to write a struct with methods to simulate it.

We have to write values into memory addresses, with a bitmask: XX1100XX (left to right, most significant to least significant, which I’ll refer to as bit 7 through 0) means that bits 7 and 6 of the value to be written are left unchanged, bits 5 and 4 are overwritten with 0, bits 3 and 2 are overwritten with 1, and bits 1 and 0 are also left unchanged. The answer to the puzzle is the sum of all the values in memory.

Contrary to what people might expect about programmers, I have not memorized how to set a bit to 0 or 1 in a number, so I always look it up to make sure I’m doing it correctly, before I do it. To set a bit to 0, use the bitwise AND operator (& in most languages) with an integer consisting of all bits 1 except the bit you want to set to 0; and to set a bit to 1, use the bitwise OR operator (| in most languages) with the bit that you want to set to 1. Based on this, I decide to write a function to parse the bitmask string, and it will split the bitmask into two bitmasks: an AND-mask to set bits to 0, and an OR-mask to set them to 1. So in the example I gave above, the AND-mask would be 11110011 and the OR-mask would be 00110000.

To read the other lines in the file I’ll use my old friend scan_fmt!(). Finally, to emulate the memory, I’ll use a HashMap<u64, u64>. Naively emulating it in an array that spans the entire 236-word address space would be a bit big (288 GiB). I do quickly look up “rust sparse array” but don’t find anything that seems more compelling than a hash map.

While writing the program I do need to look up “rust exponentiation” and find that numbers have a pow() method. But I do get an error:

error[E0689]: can't call method `pow` on ambiguous numeric type `{integer}`
  --> puzzle14.rs:38:35
   |
38 |             b'0' => and_mask -= 2.pow(ix),
   |                                   ^^^
   |
help: you must specify a concrete type for this numeric value, like `i32`
   |
38 |             b'0' => and_mask -= 2_i32.pow(ix),
   |                                 ^^^^^

That syntax (2_i32) is new to me, I haven’t seen it (or seen it suggested by the compiler) before.

error[E0308]: mismatched types
  --> puzzle14.rs:38:43
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix),
   |                                           ^^ expected `u32`, found `usize`
   |
help: you can convert an `usize` to `u32` and panic if the converted value wouldn't fit
   |
38 |             b'0' => and_mask -= 2_u64.pow(ix.try_into().unwrap()),
   |                                           ^^^^^^^^^^^^^^^^^^^^^^

This I’m also surprised at, why does u64::pow() take u32 specifically and not u64 or usize?

error[E0599]: no method named `try_into` found for type `usize` in the current scope
  --> puzzle14.rs:41:45
   |
41 |             b'1' => or_mask += 2_u64.pow(ix.try_into()?),
   |                                             ^^^^^^^^ method not found in `usize`
   |
   = help: items from traits can only be used if the trait is in scope
help: the following trait is implemented but not in scope; perhaps add a `use` for it:
   |
1  | use std::convert::TryInto;
   |

It would be nice if the compiler would suggest that when suggesting try_into() in the first place!

Otherwise, writing the solution to Part 1 goes smoothly:1

use std::collections::HashMap;
use std::convert::TryInto;
use std::num;

#[macro_use]
extern crate scan_fmt;

fn main() -> Result<(), Box<dyn Error>> {
    let mut memory = HashMap::new();
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    let file = fs::File::open("input")?;
    for line in read_lines(file) {
        if line.starts_with("mask") {
            let (new_or_mask, new_and_mask) = parse_mask(&line[7..])?;
            or_mask = new_or_mask;
            and_mask = new_and_mask;
            continue;
        }
        let (addr, value) = scan_fmt!(&line, "mem[{}] = {}", u64, u64)?;
        memory.insert(addr, value & and_mask | or_mask);
    }

    println!("{}", memory.values().sum::<u64>());

    Ok(())
}

fn parse_mask(line: &str) -> Result<(u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;

    for (ix, byte) in line.bytes().rev().enumerate() {
        match byte {
            b'0' => and_mask -= 2_u64.pow(ix.try_into()?),
            b'1' => or_mask += 2_u64.pow(ix.try_into()?),
            b'X' => (),
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask))
}

I’m slightly surprised at a few of these type annotations:

  • memory has type HashMap<u64, u64>, so memory.values() has type Iterator<Item = u64>, so memory.values().sum() should unambiguously be u64?
  • and_mask and or_mask have type u64, so if I add or subtract 2ix then that could be assumed to be u64 as well?

Day 14, Part 2

In Part 2, the meaning of the bitmask changes. Now it applies to the address being written to, not the value being written. A zero in the mask now has no effect on the value, so we ignore the AND-mask; a one in the mask means the same thing as in Part 1, so we continue to use the OR-mask; and now the Xs mean that that bit in the mask is “floating”, meaning that we have to write the value to both of the memory addresses in which that bit is either 0 or 1. (And if we have two Xs in the mask, then we have to write to four memory addresses, etc.)

Nonetheless, the program can almost remain the same! First I change parse_mask() to return a third mask as well, the float_mask, which has 1s in the bits that are supposed to be floating:

fn parse_mask(line: &str) -> Result<(u64, u64, u64), num::TryFromIntError> {
    let mut or_mask: u64 = 0;
    let mut and_mask: u64 = u64::MAX;
    let mut float_mask: u64 = 0;

    for (ix, byte) in line.bytes().rev().enumerate() {
        let bit = 2_u64.pow(ix.try_into()?);
        match byte {
            b'0' => and_mask -= bit,
            b'1' => or_mask += bit,
            b'X' => float_mask += bit,
            _ => panic!("Bad byte {}", byte),
        }
    }
    Ok((or_mask, and_mask, float_mask))
}

I change the memory.insert(addr, value & and_mask | or_mask); line to instead do write_floating_memory(&mut memory, addr | or_mask, value, float_mask); if we are in Part 2.

The write_floating_memory() function is a bit more involved. I do know that we have to write the value to 2n addresses, where n is the number of 1-bits in the float mask, so I know I can iterate through the values from 0 to 2n − 1 and use each bit of each of those values in place of one of the floating bits. But I struggle somewhat with getting those bits into the right place.

I try a few things and then I realize that I can use the iterated value as a vector of bits, where I can pop bits off the end after I’ve used them, with the right shift operator (>>). So that’s what I write:

fn write_floating_memory(memory: &mut HashMap<u64, u64>, addr: u64, value: u64, float_mask: u64) {
    for mut floating_bits in 0..2_u64.pow(float_mask.count_ones()) {
        let mut masked_addr = addr;
        for bit_ix in 0..36 {
            let bit = 2_u64.pow(bit_ix);
            if float_mask & bit != 0 {
                match floating_bits & 1 {
                    0 => masked_addr &= !bit,
                    1 => masked_addr |= bit,
                    _ => panic!("Not possible"),
                };
                floating_bits >>= 1;
            }
        }
        memory.insert(masked_addr, value);
    }
}

There’s probably a more efficient way to do that by using bit-manipulation operators, but doing that intuitively is not my strong suit, and I’d rather not have to think hard about it when I can just solve the puzzle this way.

I initially get the wrong answer from the example input because I forgot to ignore the AND-mask (I had addr & and_mask | or_mask.) While debugging this, I learn the {:b} and {:036b} formats for println!(), which are useful for printing out the masks.

Once that is solved, though, I get the right answer for the example input, and then for the real puzzle.

Instead of “Not possible” it seems like it would be useful to have bit pattern matching in the match expression. I’m not the only one to have suggested this and I find the bitmatch package, but I don’t bother changing anything at this point now that I’ve got the answer.

Day 15, Part 1

I happened to solve the Day 15 puzzle within about 20 minutes after it was released, so I’m tacking it on to today’s entry.

The puzzle is a counting game played by the elves at the North Pole. Each person takes a turn reading off a list of starting numbers, and once the starting numbers are done, the game begins. The next player considers whether the last player’s number had been spoken before. If not, they say 0. If so, they say the number of turns between the previous time the number was spoken, and the last turn number. The puzzle answer is the number that’s spoken on turn 2020.

A few considerations that I made when writing the program below:

  • This time we don’t even have to read the input from a file, it’s given in the puzzle, so I delete read_lines() from the boilerplate.
  • I originally think I have to store the last two occurrences of the given number, and shift them along when the number occurs again, but the last occurrence is actually always the previous turn. I only have to store the second-to-last occurrence, and insert the previous turn’s number after the calculation for this turn.
  • I use 0-based turn numbers internally, but 1-based when printing them out. “Turn 2020” is a human-readable 1-based number, so it’s actually turn 2019 internally.
  • The number spoken after the starting numbers are done is always 0, because the starting numbers each occur for the first time.
fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<u16, u16> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn as u16))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() as u16 + 1)..2020 {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Day 15, Part 2

The answer to Part 2 is the number that is spoken on turn 30 million. I figure this will take an inconvenient amount of time to calculate, but not so inconvenient that I don’t want to try a brute force solution. I change the types of the integers to usize everywhere, to accommodate the larger numbers, and add an if expression, and that’s it, really. It takes a few minutes to run, but it’s done.

fn main() {
    let input = vec![15, 12, 0, 14, 3, 1];
    let mut last_seen: HashMap<usize, usize> = input
        .iter()
        .enumerate()
        .map(|(turn, starting_number)| (*starting_number, turn))
        .collect();
    let mut last_turn_number = 0;

    for turn in (input.len() + 1)..if is_part2() { 30000000 } else { 2020 } {
        let this_turn_number = match last_seen.get(&last_turn_number) {
            Some(prev_seen) => turn - 1 - prev_seen,
            None => 0,
        };
        last_seen.insert(last_turn_number, turn - 1);
        last_turn_number = this_turn_number;

        println!("Turn {}: {}", turn + 1, this_turn_number);
    }
}

Afterword

After Day 14 I was going to say that it seems like the puzzles follow a general pattern of having Part 1 be a fairly straightforward problem, and Part 2 adding a complication that makes you have to think harder about it. But Day 15 breaks that mold!


[1] For certain definitions of “smoothly,” that is. I’ve gotten used to always having a few rounds of compilation where I fix the borrow operators, and any program that I post here should be understood to have been bashed into shape by the compiler — I still can’t write Rust ↩

Advent of Rust 3: Once in ‘a Lifetime

Well, this is another long stream-of-consciousness chronicle of my attempt to learn how to program in Rust by doing the daily programming puzzles on Advent of Code 2020. It’s long, but on the plus side, this is the first time ever that I’ve published two blog posts in two days, let alone three in three days. And you know what they say, if I’d had more time, I would’ve written you a shorter letter.

I thought a bit about why it should even be interesting or valuable to write about my mistakes and thought process. Or put more bluntly, isn’t this just a waste of time? Who is this useful for?

Well, for one thing, at my job I’ve been working on Temporal, a standards-track proposal to add a modern API for dates and times to the JavaScript language. Earlier this year I conducted a survey of people who had tried out the proposed Temporal API, and one of the purposes was to try to figure out what was easy to understand and what was hard, for someone coming to Temporal with no prior knowledge. Even though I had been in exactly that position myself only a few months before, I had become so accustomed to using Temporal that I could literally remember nothing of my own experience.

It’s sometimes called the curse of knowledge. I’m sure I will look back in a year, or two years, when I have written lots of Rust code, and not remember any of this either, and I’ll be glad that I wrote it down. But maybe it’ll be valuable in the meantime to someone else!

Day 3, Part 1

Today we get a roguelike puzzle! We are sliding on a toboggan down a horizontally repeating grid of open spaces (.) and trees (#) that is defined in our input file. We slide at a certain angle (3 cells across for every 1 cell down), and the answer to Part 1 is how many trees we crash into by the time we get to the bottom.

By this time I’m familiar with how to start — cargo new puzzle3, download the input file and put it in the project directory, and copy the relevant code from yesterday. This time I’m not only copying the read_lines() function, but also the code that determines from the command line argument whether I want to run the code for Part 1 or Part 2.

Here’s what I start out with:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let lines: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();
    println!("grid is {} × {}", lines[0].len(), lines.len());
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

I still made a few minor mistakes when adapting this code from yesterday’s code: I forgot to add the Vec<String> type to lines, I forgot to handle errors with .map(|s| s.expect("Bad line in file")), and I guessed wrong that the length of a vector was length() and not len(). Happily, I am getting accustomed enough to this, that I’m able to correct those mistakes fairly quickly.

I will once again use my approach from the last two days, where I first try to get the data into the right data structure. Now that I’m no longer struggling with knowing what data structures even exist in Rust, and how do I even write Rust code, I can afford to think about this before I start writing any code.

It seems like the appropriate data structure is a two-dimensional array of booleans – true if there is a tree in the cell, false if the cell is an open space. I don’t know if Rust has two-dimensional arrays or vectors, so I first start by googling “rust two dimensional array”. I find several results (1, 2, 3, and the array2d package) but none of them really stand out as saying “this is the way to do it.”

What I do understand so far is that I’d use an array if the size was known at compile time, and a Vec of Vecs if I wanted to have variable-length rows or columns. The array2d package from my search results does look interesting because it seems like it gives you a rectangular array, where the length of each row and column is the same for the whole array, but doesn’t necessarily have to be known at compile time. In theory I do know the width and length at compile time, because I can look in the file and count the number of lines and the length of each line! I have a feeling that that would make my code too tied-up with this particular data file, though, and might mean that I would have to refactor the whole thing for Part 2, so I’d prefer not to take that approach.

(I think briefly about using a one-dimensional array and checking through it with a stride of width + 3, but because the grid repeats in the horizontal direction, I think that wouldn’t work.)

Taking the two-dimensional array approach would mean that unlike yesterday, I would not use iterators very much. Hmm, I feel like I’ve just gotten comfortable with iterators in Rust, I wonder what a solution would look like if it were based on iterators?

Maybe that would actually be easier! Thinking about it some more, I don’t actually need to store the entire grid in a 2-D array. I just need to read in each row, figure out my horizontal position on that row, and store a boolean indicating whether I have hit a tree on that row. I believe it can be done just by operating on the string representing each row, with a map(), filter(), and count().

Let’s see if my guess about how to do it is correct. Here’s the first version that I come up with:

fn main() {
    // [...args...]
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree(row_index: usize, row: String) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == '#'
}

Here, I’m assuming that it’s OK to index the string as bytes, because the only characters allowed are # and .. (I learned from yesterday’s exercise what the difference was between indexing a string by byte and iterating through it by character.) I’m taking a guess that '#' (with single quotes instead of double quotes) will give me a single byte rather than a string, like it does in C.

The compiler gives me quite a lot of errors, but I think I know what most of them mean:

error[E0593]: function is expected to take 1 argument, but it takes 2 arguments
  --> src/main.rs:17:17
   |
17 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected function that takes 1 argument
...
22 | fn hits_tree(row_index: usize, row: String) -> bool {
   | --------------------------------------------------- takes 2 arguments

error[E0599]: no method named `count` found for struct `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>` in the current scope
    --> src/main.rs:18:10
     |
18   |           .count();
     |            ^^^^^ method not found in `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>`
     |
     = note: the method `count` exists but the following trait bounds were not satisfied:
             `<fn(usize, String) -> bool {hits_tree} as FnOnce<(&(usize, std::result::Result<String, std::io::Error>),)>>::Output = bool`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `fn(usize, String) -> bool {hits_tree}: FnMut<(&(usize, std::result::Result<String, std::io::Error>),)>`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             which is required by `&mut Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`

error[E0308]: mismatched types
  --> src/main.rs:24:34
   |
24 |     row.as_bytes()[col_index] == '#'
   |                                  ^^^ expected `u8`, found `char`

The first error is probably because I need to make hits_tree() take a tuple of (row_index, row) as its one argument, instead of two arguments. The second error (reminiscent of those long template errors that you get from C++ compilers) I don’t understand, but it seems like it might be a consequence of the first error, and might go away if I solve that one? The third error shows that my guess that '#' is a byte, is wrong. I was close, it is a char, but a byte is type u8.

The third error seems like the easiest to solve, so first I google “rust byte literal” and land here, which makes me think that b'#' might be correct — and it is!

Next I need to make hits_tree() take a tuple as an argument. I wonder if I can destructure this tuple as I would be able to in JavaScript: function hits_tree([row_index, row]) { ... } I google “rust tuple function argument”, and I get this Stack Overflow answer which makes me think that I should be able to do (row_index, row): (usize, String).

But before I run that, I would like to try to get the & operator right this time. After yesterday, when every time I compiled my code, the compiler told me to add a &, I did spend some time reading the “Understanding Ownership” page. Now I feel like I should be better equipped to avoid these mistakes, or at least understand them when I do make them.

So for the first time in this series, I actually go to the API documentation for a function intentionally, instead of googling it and landing there! First I check enumerate() to check that usize is really the correct type for the index (it is,) then I check lines() to check that String is really the correct type for the row (it isn’t.) The type is actually io::Result<String> which reminds me that I need to expect() the value, so I add .map(|s| s.expect("Bad line in file")) before the call to enumerate().

Then there’s the question of whether the row parameter should be a reference or not. I remember reading this:

A more experienced Rustacean would write [s: &str] instead [of s: &String] because it allows us to use the same function on both &String values and &str values.

But on the other hand, I’m not sure that this parameter is actually a reference! It seems to me that since we get a io::Result<String> from read_lines(), the ownership of the string is passed from function to function in the iterator chain, so I would guess (but with only a little more than 50% confidence)1 that String is correct and &str is not. So I make the change of (row_index, row): (usize, String) and run it.

Unfortunately, sitting down and thinking about it is rewarded with an error that I really don’t understand:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, String)) -> bool {
   | ------------------------------------------------------- found signature of `fn((usize, String)) -> _`

I know from the reading I’ve done that 'r is a “lifetime”, but the page that I read told me that lifetimes were an advanced feature that would be explained later in the Rust book. Oops, I guess I should have read that chapter too!

I wonder if I can just fake it ’til I make it, by adding for<'r> and &'r to the function signature as the compiler is suggesting. I try that, but it’s a syntax error, “expected item, found keyword for“. I try removing the for<'r>, and I get another error about “unexpected lifetime” which makes me think that I should put the &'r on (usize, String) instead of (row_index, row). (That makes sense, somewhat, because it’s part of the type, not part of the destructured function arguments.) So I try that, and I get another error, but this one tells me exactly what to do:

error[E0261]: use of undeclared lifetime name `'r`
  --> src/main.rs:23:33
   |
23 | fn hits_tree((row_index, row): &'r (usize, String)) -> bool {
   |             -                   ^^ undeclared lifetime
   |             |
   |             help: consider introducing lifetime `'r` here: `<'r>`

Sure enough, when I add <'r>, it works (with some warnings about not using the part2 variable, which I’ll use soon enough) and I get a number out! I put the number into the Advent of Code website and it’s correct!

The lifetime thing is fairly unsatisfying: I have no idea what it does, why it’s necessary, or why it’s even called r!

I’ll try one more thing. Maybe I was wrong about the row needing to be a String. For example, I look back at yesterday’s code and see fn parse_line(line: &str), so maybe in today’s code I also need &str. So I try changing the function signature to fn hits_tree((row_index, row): (usize, &str)) -> bool, without any lifetimes. But I get the old errors back. I do notice one interesting thing in the error message this time:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, &str)) -> bool {
   | ----------------------------------------------------- found signature of `for<'r> fn((usize, &'r str)) -> _`

Now, for some reason, it thinks that my function signature already has a lifetime in it, even though I didn’t put one in! I wonder if the lifetime is implicitly when you include a reference. But it definitely wants a String and not a str. So I try changing the type of the argument to (usize, &String) without the lifetime. That doesn’t work either, but interestingly it does continue to think that the type of my function includes a lifetime. It’s telling me that the reference needs to be on the tuple, not on the string, so I try &(usize, String), once more without a lifetime, and that works.

So the message about having to add a lifetime was strange and confusing, but it turns out that I didn’t need to have it after all. Unfortunately I had to discover this by putting & operators in random places until my code compiled, which I had intended to stop doing today ☹️

On the plus side, I got the correct answer, so that’s the end of Part 1! Here’s the full code:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree((row_index, row): &(usize, String)) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Day 3, Part 2

My guess was that Part 2 of the puzzle might be to do the same thing but with the toboggan at a sharper angle such that you would have to skip rows entirely. (For example, 1 right for every 3 down.) I was both right and wrong. It’s actually that you have to check a list of five angles including a sharper one that makes you skip rows, and the answer to the puzzle is the results from those angles all multiplied together. So, my approach of using iterators for the whole thing should actually be refactored, because I don’t want to read the file five times!

I briefly think about using array2d to store the map of the trees after all, but I decide that Vec<String> would be more convenient since I can get it from my existing iterator pipeline by capping it after the expect() call with collect(), and I expect my existing code will continue to work on that with few modifications.

So before I start on Part 2 I decide to refactor it this way:

let landscape: Vec<String> = read_lines("input")
    .expect("Bad file")
    .map(|s| s.expect("Bad line in file"))
    .collect();

let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();

But oh no…

error[E0631]: type mismatch in function arguments
  --> src/main.rs:19:57
   |
19 |     let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();
   |                                                         ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, &String)) -> _`
...
23 | fn hits_tree((row_index, row): &(usize, String)) -> bool {
   | -------------------------------------------------------- found signature of `for<'r> fn(&'r (usize, String)) -> _`

OK, I’m back to adding & operators in random places! At least as far as I can tell from the error message, I will need to keep the one on the tuple, and add a second one to &String. And indeed that works.

Next I want to refactor the second part of that into a function count_trees_hit(landscape, right, down) so I can call it several times on the list of angles expressed as (right, down) pairs. I’ll start by omitting the down parameter and just making sure that the existing code works:

fn main() {
    // ...
    let trees_hit = count_trees_hit(&landscape, 3);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

It looks like this almost works, but I get one error:

error[E0308]: mismatched types
  --> src/main.rs:27:65
   |
27 |         .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
   |                                                                 ^^^^^^^^^
   |                                                                 |
   |                                                                 expected `usize`, found `&usize`
   |                                                                 help: consider dereferencing the borrow: `*row_index`

Since usize is an integer type I’m not sure why it has a reference, but I try changing the type of the row_index parameter to &usize and it works. It also works if I do what the compiler says and add *, but that’s an operator that I haven’t learned about (the page I read mentioned that it existed, but I don’t have a good idea of how it works.)

Next I want to add a down parameter. I think if we move multiple rows downwards for every column that we move to the right, then we can simply skip those rows. So it seems to me that I should be able to add another filter() step that skips the row if its index modulo down is not zero.

This new step doesn’t even need access to the row data so I wonder if I can simplify my code by ignoring the string parameter. I google “rust ignore parameter” and land on “Pattern Syntax” which I skim, and it looks like I should be able to use either .. or _ to ignore that parameter. I’ll try both and see what the compiler says. After a couple of tries, what works is: .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0).

Now I have this code:

    let trees_hit = count_trees_hit(&landscape, 1, 2);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0)
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

I am a bit suspicious that I might be getting the wrong row_index in the second filter() step, because I am filtering out the already-enumerated rows. So for testing, I try it with right 1 and down 2, and add the println!() statement in hits_tree() to print out the row index and column index.

It turns out my suspicion was correct. The indices that are printed out, are 0, 0, 2, 2, 4, 4, 6, 6 etc., while they should be 0, 0, 1, 2, 2, 4, 3, 6. I think what I need to do to fix this, is un-enumerate the items after the first filter() step and then re-enumerate them. I could write the un-enumerate step with map, but I have a feeling that there might be a built-in iterator method to take only the second element of a tuple, so I look at the API documentation for iterators again. I don’t see anything likely there. I look at the API documentation for Itertools as well, but don’t see anything there either. I try googling a few things (such as “rust iterator drop tuple element”) but that doesn’t give me any likely-looking results, so I decide to just write it myself. I insert .map(unenumerate).enumerate() into the iterator pipeline, after the first filter(), and define my unenumerate() function as follows:

fn unenumerate((.., row): &(_, &String)) -> &String {
    row
}

I get two errors that I haven’t seen before:

error[E0106]: missing lifetime specifier
  --> src/main.rs:34:45
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                           -------------     ^ expected named lifetime parameter
   |
   = help: this function's return type contains a borrowed value, but the signature does not say which one of argument 1's 2 lifetimes it is borrowed from
help: consider introducing a named lifetime parameter
   |
34 | fn unenumerate<'a>((.., row): &'a (_, &String)) -> &'a String {
   |               ^^^^            ^^^^^^^^^^^^^^^^     ^^^

error[E0121]: the type placeholder `_` is not allowed within types on item signatures
  --> src/main.rs:34:29
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                             ^ not allowed in type signatures
   |
help: use type parameters instead
   |
34 | fn unenumerate<T>((.., row): &(T, &String)) -> &String {
   |               ^^^              ^

From what I can understand from these errors, first it’s asking me to add a lifetime parameter, and second it seems like the .. trick is not allowed in named functions, only in inline functions?

The suggestion to use type parameters makes me think of how this might work in C++, so I try the following instead:

fn unenumerate<First, Second>((.., second): &(First, Second)) -> Second {
    second
}

Here, confusingly, the compiler does not want the & on the tuple type, so after a few tries of adding and removing & operators I do get this to compile and produce the debug output that I was expecting.

A bit too late, I realize that I could have done this much quicker with only one filter() step, skipping the rows by returning false in hits_tree(). Although what I have already works, this seems like it’s potentially a big enough improvement that I should try it:

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

Apart from forgetting the braces on the if statement (apparently, you cannot omit them in Rust for a single-statement block as you can in C-like languages) I get the same result as my previous code that used unenumerate(), so I feel good about this.

It’s time to remove the debug println!() and actually write the Part 2 code, that tries several different angles and multiplies the answers together:

if part2 {
    let total = count_trees_hit(&landscape, 1, 1)
        * count_trees_hit(&landscape, 3, 1)
        * count_trees_hit(&landscape, 5, 1)
        * count_trees_hit(&landscape, 7, 1)
        * count_trees_hit(&landscape, 1, 2);
    println!("{}", total);
} else {
    let trees_hit = count_trees_hit(&landscape, 3, 1);
    println!("{}", trees_hit);
}

With this, cargo run 2 gives me an answer, which I put into the Advent of Code website, and it’s correct. And as a nice note to end on, this last change marks the first time in this series that I actually write some Rust code that compiles right away!

The full code, also pushed to GitHub:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let landscape: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();

    if part2 {
        let total = count_trees_hit(&landscape, 1, 1)
            * count_trees_hit(&landscape, 3, 1)
            * count_trees_hit(&landscape, 5, 1)
            * count_trees_hit(&landscape, 7, 1)
            * count_trees_hit(&landscape, 1, 2);
        println!("{}", total);
    } else {
        let trees_hit = count_trees_hit(&landscape, 3, 1);
        println!("{}", trees_hit);
    }
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Afterword

I can tell that I’m starting to get more comfortable in Rust, which feels good. But I’m a bit disappointed that even though I did some extra studying about ownership and the & operator, I was still confused, still couldn’t understand some errors, and basically had to either do exactly what the compiler said without understanding why, or else add or delete & operators arbitrarily until the code compiled.

Maybe what I should do next is read the page in the Rust book on lifetimes, and read about the * operator. Even though the page on ownership said those were advanced topics, both of those came up today in error messages that I didn’t understand.


[1] It occurs to me that — at least for this series — I’m glad I haven’t set up my editor to show Rust compiler errors inline, because otherwise I wouldn’t consciously think about these things ↩