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) 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.
The Mad Scientist Review 