Welcome to the latest installment of the stream-of-consciousness log of me trying to learn the Rust programming language by doing the programming puzzles on Advent of Code 2020.
I’ve noticed that these logs, while still long, are becoming shorter. On Day 1 I wrote 6000 words, on Day 2 5000, and on Day 3 and 4 just under 4000. (Today’s is a bit over 3000.) I think that’s because I’m solving the puzzles with fewer mistakes that I have to write about solving! Eventually I expect that I won’t keep writing one post per day because that level of detail won’t be interesting anymore, but let’s see how today goes.
I start off today having gotten several pieces of advice from commenters on the earlier blog posts and from the Rust ❤️ GNOME chat channel, and will use them to improve the boilerplate read_lines() and is_part2() functions that I copy every day. Jan Alexander Steffens noted that to return an iterator of Strings (the task that I failed at yesterday), I don’t have to specify the exact return type, which is what I struggled with, producing a long unreadable type signature that I couldn’t get correct in the end. Instead, I can specify impl Iterator<Item = String>, meaning that it returns a type that implements the iterator interface and the iterator yields String, but that you don’t care about the particulars. Nice!
Perry Lorier mentioned, among other things, that you can make the return type of main() a Result and so use the ? operator to pass errors back to the caller. This is the concise error handling that I was looking for originally on Day 1! Perry also pointed me at this diagram which looks very complicated, but after studying it a bit, I understand better what Ok() and Some() are for, and how to get from one type to the other. This diagram is particularly helpful for shortening the is_part2() function.
Day 5, Part 1
I start out as usual with cargo new puzzle5, copy over read_lines() and is_part2() from yesterday, and start to refactor them using the new knowledge that others have helped me acquire. After some experimentation which I forget to take notes on (but is mostly dealing with compiler errors telling me that I got the Result and Option types slightly wrong,) I have the following boilerplate to start with:
use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;
fn main() -> Result<(), io::Error> {
let lines = read_lines("input")?.collect::<Result<Vec<_>, _>>()?;
if is_part2() {
println!("Part 2");
} else {
println!("{:?}", &lines[..10]);
}
Ok(())
}
fn is_part2() -> bool {
env::args().nth(1).map(|val| val == "2").unwrap_or(false)
}
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())
}
The final thing that Perry told me about is cargo clippy, which seems to be a command that checks your code and makes suggestions on how to write it more idiomatically. It tells me, for example, that the .and_then(|val| Some(val == "2") that I had at one point in is_part2(), is more cleanly expressed as .map(|val| val == "2").
Now, on to the puzzle! Today’s puzzle is to figure out seat numbers on a weirdly-numbered airplane, where there are 128 rows with 8 seats each, and your boarding pass has seat designations like FBFBBFFRLR where the first F tells you to go to the front half of the airplane, the second character B tells you to go to the back quarter of the front half, etc. The first 7 characters are F or B, telling you which row to go to, and the last three are similarly L or R telling you which seat in that row to sit in (right or left.) Each seat has a “seat ID” that is row × 8 + seat. The answer to the puzzle is the highest seat ID in the given input file containing boarding pass codes.
I spend a moment thinking about how to calculate the range of row numbers that is the back quarter of the front half. Since the airplane has 128 rows, the ranges will all be powers of 2. I briefly think about using nested match statements but that jogs something in my memory and I think: maybe these are actually binary digits in disguise. So I go to my JavaScript console1 and input the example code FBFBBFFRLR as 0b0101100101 — replacing each F and L with a zero, and B and R with a one, and indeed I get 357, which is the seat ID given in the example. I try the next example, BFFFBBFRRR, which is 0b1000110111 or 567, and it checks out too. If this were a real application I’d want to think about it some more, but as it is, I’m satisfied enough to start writing the program.
There are two approaches I could take here: manually turning each B and R into the appropriate power of 2 and adding them all together, or I could use a string replace, followed by parse() (which I know about from Day 1, and I assume it ought to be able to parse binary numbers as well as decimal.) I decide on the latter. Even though it is probably less efficient, it’s not so inefficient that it will make a difference, and I expect it will be faster to write.
For the first time, I’m feeling like I don’t need to google anything, but instead I can go straight to the API documentation. I need to look at the documentation for String to find out how the replace() method works, and how to specify a different arithmetic base to the parse() method. I also guess that there will probably be an iterator method that will exhaust the iterator and give me the largest item, but if there isn’t then I can write one with reduce(), which I’m familiar with from JavaScript.
First I read about replace() but then I realize that since I’m replacing every character in the string anyway, I don’t need it. I actually need something like map(), which I don’t see in the list of methods. But I do know that map() is an iterator method, and to get an iterator over the characters of a string I can use chars(). Then I see char_indices() which will give me each character along with its position in the string, and that makes me think that it might be easier after all to turn the letters into powers of 2 and add them together. And then I see bytes(), which would be even more appropriate because there are only four possible one-byte characters in the strings, but I don’t see a corresponding byte_indices() method. But anyway, it doesn’t matter, because we can use enumerate() on the iterator returned from bytes().
I will then need to get the sum of the elements in one iterator (the powers of 2), and the greatest element of the other iterator (the boarding pass codes in the file), and so I click through to the Iterator documentation and see that these methods are called sum() and max(), respectively.
There is one thing that I do have to google: how to do exponentiation and/or bit shifts in Rust. I find that there is a left-shift << operator which will work fine for me.
Here’s the program I write:
let lines = read_lines("input")?;
let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
println!("{}", largest_seat_id);
// [...]
fn code_to_seat_id(line: String) -> u16 {
let maxbyte = line.len() - 1;
line.bytes()
.enumerate()
.map(|(index, byte): (usize, &u8)| {
let digit = match byte {
b'B' | b'R' => 1,
_ => 0,
};
digit << (maxbyte - index);
})
.sum()
}
I was so hoping that I might have understood things well enough to write a program that ran the first time, but no such luck:
error[E0277]: the `?` operator can only be used in a closure that returns `Result` or `Option` (or another type that implements `Try`)
--> src/main.rs:12:61
|
12 | let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
| --------------------^^-
| | |
| | cannot use the `?` operator in a closure that returns `u16`
| this function should return `Result` or `Option` to accept `?`
|
= help: the trait `Try` is not implemented for `u16`
= note: required by `from_error`
error[E0277]: `Option<u16>` doesn't implement `std::fmt::Display`
--> src/main.rs:13:24
|
13 | println!("{}", largest_seat_id);
| ^^^^^^^^^^^^^^^ `Option<u16>` cannot be formatted with the default formatter
|
= help: the trait `std::fmt::Display` is not implemented for `Option<u16>`
= note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
= note: required by `std::fmt::Display::fmt`
= note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
error[E0631]: type mismatch in closure arguments
--> src/main.rs:23:10
|
23 | .map(|(index, byte): (usize, &u8)| {
| ^^^ ----------------------------- found signature of `for<'r> fn((usize, &'r u8)) -> _`
| |
| expected signature of `fn((usize, u8)) -> _`
error[E0599]: no method named `sum` found for struct `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>` in the current scope
--> src/main.rs:30:10
|
23 | .map(|(index, byte): (usize, &u8)| {
| -----------------------------
| |
| doesn't satisfy `<_ as FnOnce<((usize, u8),)>>::Output = _`
| doesn't satisfy `_: FnMut<((usize, u8),)>`
...
30 | .sum()
| ^^^ method not found in `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>`
|
= note: the method `sum` exists but the following trait bounds were not satisfied:
`<[closure@src/main.rs:23:14: 29:10] as FnOnce<((usize, u8),)>>::Output = _`
which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
`[closure@src/main.rs:23:14: 29:10]: FnMut<((usize, u8),)>`
which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
`Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
which is required by `&mut Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
The third and fourth errors I’ve dealt with before; in that case I was missing a & operator on the tuple type of the argument of the function that I passed to map(). Here, though, judging from the error message, it seems I have an & operator that isn’t supposed to be there, so I remove it and the last two error messages disappear. I’m not sure why this is; it seems like the byte should be owned by the string, but maybe bytes are passed by value?
For the first error, I understand why it’s complaining: I need to use unwrap() there, because |s| code_to_seat_id(...) doesn’t return a Result or Option, so I cannot use the ? operator to handle errors.
The second error I do understand what it’s asking me to do, but I don’t understand why, until I go and read the documentation for max() again, and see that it returns an Option which is None in the case where the iterator is empty. This is a really nice example of how Rust forces you to handle all possible errors, because that is definitely a case that I would have forgotten about! So I add an extra ? to the end of that line.
Now I have two new errors:
error[E0277]: `?` couldn't convert the error to `std::io::Error`
--> src/main.rs:12:79
|
6 | fn main() -> Result<(), io::Error> {
| --------------------- expected `std::io::Error` because of this
...
12 | let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max()?;
| ^ the trait `From<NoneError>` is not implemented for `std::io::Error`
|
= note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
= help: the following implementations were found:
<std::io::Error as From<ErrorKind>>
<std::io::Error as From<IntoInnerError<W>>>
<std::io::Error as From<NulError>>
= note: required by `from`
help: consider converting the `Option<T>` into a `Result<T, _>` using `Option::ok_or` or `Option::ok_or_else`
|
12 | let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().ok_or_else(|| /* error value */)?;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
error[E0277]: the trait bound `u16: Sum<()>` is not satisfied
--> src/main.rs:30:10
|
30 | .sum()
| ^^^ the trait `Sum<()>` is not implemented for `u16`
|
= help: the following implementations were found:
<u16 as Sum<&'a u16>>
<u16 as Sum>
It seems that my last adjustment wasn’t correct, the ? unwraps the Option but the return type of main() is Result, not Option. So I guess I can’t directly use the ? operator there either. The compiler suggests providing the Error value using ok_or_else(), but I decide to unwrap() this as well.
I have to stare at the second error for a while, but the () in Sum<()>, which I learned a few days ago means “the empty type”, finally gives me the clue. I have put a semicolon at the end of digit << (maxbyte - index) and if I delete the semicolon, the program works. I’m guessing the semicolon turns that line into a statement which doesn’t do anything, instead of the expression to be returned from the function! This makes it seem like you have to be really careful when writing an inline function without an explicit return type! This seems like something that the compiler could generate a better error message about. For example, my function here is used as an argument to map(), and it seems probable that you would want the mapped function to return a value.
Anyway, the answer I get is the correct answer according to the Advent of Code website, so on to Part 2.
Here’s the correct code (without the boilerplate):
fn main() -> Result<(), io::Error> {
let lines = read_lines("input")?;
let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().unwrap();
println!("{}", largest_seat_id);
Ok(())
}
fn code_to_seat_id(line: String) -> u16 {
let maxbyte = line.len() - 1;
line.bytes()
.enumerate()
.map(|(index, byte): (usize, u8)| {
let digit = match byte {
b'B' | b'R' => 1,
_ => 0,
};
digit << (maxbyte - index)
})
.sum()
}
Day 5, Part 2
Part 2 seems really simple at first glance, but that probably means it’s more difficult than it looks. The puzzle is to find your seat ID. Some seats at the front and the back of the plane are missing, but all the others are full, and you know you are not sitting in the very first or very last seat. So your seat ID is the one that is missing in the input file, but with the IDs on either side of it present.
I think we should probably start by sorting the seat IDs. I look up in the Vec documentation how to sort a vector, and I read under sort() that sort_unstable() is preferred if it’s OK for equal elements to be reordered. We should not have any equal elements at all in this vector anyway, so I use that. I change the main() function into this:
fn main() -> Result<(), io::Error> {
let lines = read_lines("input")?;
let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));
if is_part2() {
let sorted = seat_ids.collect().sort_unstable();
println!("{:?}", sorted);
} else {
let largest_seat_id = seat_ids.max().unwrap();
println!("{}", largest_seat_id);
}
Ok(())
}
There’s one error, suggesting that I should specify the type on collect(), which is actually an error I’ve run into before. Perry explained to me why this happens: collect() can actually do several things, so sometimes you need to specify the type so that it knows which thing you want it to do. I change it to collect::<Vec<u16>>() and the program runs.
I get no output though! Or, to be precise, I get the output () which is the empty type. I go back and read again about what sort_unstable() does: the signature is sort_unstable(&mut self) and I don’t see a return value! So it’s a method that changes the original vector. I change that line to the following, also taking the opportunity to specify the type as an annotation on the variable sorted instead of as a type parameter to collect():
let mut sorted: Vec<u16> = seat_ids.collect();
sorted.sort_unstable();
I run the program and get a bunch of numbers! Looks like it’s working. Theoretically, if I spotted the missing number in here, then I’d have the answer to the problem — but I don’t happen to see it, and I don’t want to search through 800 numbers.
I think a simple way to find out which number is missing would be to iterate through the list and stop at the first number that isn’t equal to the previous number plus one. If this were Python and I was using NumPy, I might have the data in an ndarray, where I could rotate the array by 1 and subtract the rotated array from the original array; but I assume Rust arrays don’t work like that.
Instead I remember seeing a method for examining successive elements in an iterator, when I was browsing the itertools package on Day 1. I go to the documentation and find the method, which is called tuple_windows(). I can use that to iterate over all windows of two adjacent seat numbers, and then use find_position() to give me the first one where the two numbers are not sequential!
Here’s what I write:
let seat_number = sorted
.iter()
.tuple_windows()
.find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
.unwrap()
.1
.0
+ 1;
println!("{}", seat_number);
The .1.0 + 1 at the end is a bit cryptic: find_position().unwrap() will give me a tuple of (position, item) from the iterator, which is iterating over pairs of u16, so the type is something like (usize, (u16, u16)). I add one at the end, because .1.0 gives me the seat before the missing seat, so I add one to get the missing seat ID.
Of course it doesn’t work the first time; I’ve forgotten to add use itertools::Itertools; But after doing that I get the following errors:
error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
--> src/main.rs:16:14
|
16 | .tuple_windows()
| ^^^^^^^^^^^^^ expected `u16`, found `&u16`
error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
--> src/main.rs:17:14
|
17 | .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
| ^^^^^^^^^^^^^ expected `u16`, found `&u16`
|
= note: required because of the requirements on the impl of `Iterator` for `TupleWindows<std::slice::Iter<'_, u16>, (u16, u16)>`
error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
--> src/main.rs:14:27
|
14 | let seat_number = sorted
| ___________________________^
15 | | .iter()
16 | | .tuple_windows()
17 | | .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
| |_______________________________________________________________________^ expected `u16`, found `&u16`
I’m still not getting the & operators right! I think this might mean that the type of seats has to be &(&u16, &u16), which I don’t understand, because I just had to remove the & operator from something similar in Part 1! Maybe an explanation that makes sense could be that the tuple_windows() values are borrowed from the original iterator? When I make that change, the errors disappear, and I get a different error:
error[E0277]: can't compare `&u16` with `u16`
--> src/main.rs:17:59
|
17 | .find_position(|seats: &(&u16, &u16)| seats.1 != seats.0 + 1)
| ^^ no implementation for `&u16 == u16`
|
= help: the trait `PartialEq<u16>` is not implemented for `&u16`
Now this error I find really puzzling. Why shouldn’t I be able to compare a reference to u16 with a u16? I google “rust compare u16 with &u16” and I find a Stack Overflow post with the relevant title “Why isn’t it possible to compare a borrowed integer to a literal integer?” The answer isn’t all that satisfying because I’m skeptical of the rationale that the answer gives, but it does tell me what to do: seats.1.clone() or *seats.1.
I also take the opportunity to refactor the code to use destructuring to get rid of that ugly .1.0:
let (_, (seat_before, _)) = sorted
.iter()
.tuple_windows()
.find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
.unwrap();
println!("{}", seat_before + 1);
This gives me an answer, which I put in to the Advent of Code website, and it’s correct! Hooray!
Here’s the full code, again minus boilerplate:
use itertools::Itertools;
fn main() -> Result<(), io::Error> {
let lines = read_lines("input")?;
let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));
if is_part2() {
let mut sorted: Vec<u16> = seat_ids.collect();
sorted.sort_unstable();
let (_, (seat_before, _)) = sorted
.iter()
.tuple_windows()
.find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
.unwrap();
println!("{}", seat_before + 1);
} else {
let largest_seat_id = seat_ids.max().unwrap();
println!("{}", largest_seat_id);
}
Ok(())
}
fn code_to_seat_id(line: String) -> u16 {
let maxbyte = line.len() - 1;
line.bytes()
.enumerate()
.map(|(index, byte): (usize, u8)| {
let digit = match byte {
b'B' | b'R' => 1,
_ => 0,
};
digit << (maxbyte - index)
})
.sum()
}
Afterword
I am starting to feel more and more confident writing Rust. I do still feel like the code I write is clunky and not idiomatic, and probably will for quite some time yet! So by “confident” I don’t mean I’m a good Rust programmer, but what I mean is I’m just starting to lose the feeling of having no idea what I’m doing.
It has been very helpful to get comments on these posts, as I was able to put some of the tips to good use today. It’s good to not be learning in a vacuum! Another thing that really made today’s exercises go faster was the experience of getting errors that I had already encountered a few days ago, and knowing roughly how to solve them.
[1] Is there a Rust REPL? ↩
The Mad Scientist Review 