Please use rustfmt (easily done project-wide with cargo fmt
) to give your source files consistent formatting. You might not like all of the changes it makes (neither do I) but when sharing code with other people it's more important to have predictable, consistent formatting. You'll get used to it, anyway.
Part 1
let mut count: u16 = 0;
let mut last: u16 = 0;
These variables aren't used here. It's usually a good idea to declare variables with the smallest possible scope; in this case, right before the for
.
Using u16
is harmless in this program but doesn't really buy you anything in terms of size (the data will almost certainly be stored in 32- or 64-bit registers anyway), so I would prefer u32
or usize
for count
, and u32
or perhaps i32
for last
(I don't think the problem states the depths can't be negative). Note that u16
is not big enough to solve the next day's problem.
let args: Vec<String> = env::args().collect();
let filename = args
.get(1)
.unwrap_or_else(|| panic!("Please provide file name"));
When you have an iterator and you only need one item from it, use nth
instead of collecting into a Vec
. Use &
to borrow the result if you need a reference like get
returns.
.unwrap_or_else(|| panic!(...))
is common enough there is a shortcut for it, .expect(...)
.
let file = File::open(filename).unwrap_or_else(|_| panic!("Couldn't open file {}", filename));
let reader = BufReader::new(file);
expect
doesn't quite work here, since you want to add additional information to the error message (the filename). This is fine (for prototyping, at least; for libraries and user-facing errors, you'll probably want to handle errors in some way other than panicking, but for coding challenges, it's fine).
On the other hand, this way of reading files might be how you would do it if you were concerned about memory usage, but it's a bit cumbersome for quick scripts and coding challenges. Instead, you can use std::fs::read_to_string
to slurp a whole file at once into a String
and use .lines()
on that.
for (index, line) in reader.lines().enumerate() {
Starting at last = 0
means you have to keep track of the index
and check whether it is 0 on every iteration. What if you had an iterator over integers? Then you could set last
initially to the first value in the iterator, and check as you iterate over the rest of them.
if line.trim().is_empty() { continue; }
The input shouldn't have any blank lines in it. I would not check for this.
last = line.parse().unwrap();
You already did line.parse().unwrap()
a few lines above; why not store that in a variable and reuse it?
With all the above suggestions applied here's what I came up with for the first challenge program:
use std::fs;
fn main() {
let filename = env::args().nth(1).expect("Please provide file name");
let file =
fs::read_to_string(&filename).unwrap_or_else(|_| panic!("Couldn't open file {}", filename));
let mut count: usize = 0;
let mut lines = file
.lines()
.map(|line| line.parse().expect("invalid number"));
let mut last = lines.next().unwrap_or(0);
for this in lines {
if last < this {
count += 1;
println!("{} (increased)", this);
} else {
println!("{}", this);
}
last = this;
}
println!("Increase count: {}", count);
}
Part 2
Most of what I mentioned for Part 1 will also apply here; however, the loop state is a bit more complex since you need to keep track of the previous length-3 window.
last = curr.to_vec();
This line makes a clone of curr
(note: to_vec()
on something that is already a Vec
is equivalent to clone()
), drops whatever Vec
was previously in last
and replaces it with the newly cloned one. This means you're deallocating and reallocating a length-3 vector every iteration, which is a lot of heap churn.
curr.push(line.parse().unwrap());
if curr.len() > 3 {
curr.remove(0);
}
Similarly, here you lengthen the vector to 4, then remove from the beginning, which shifts the three end elements backwards by 1. Increasing the size of the vector can also cause reallocation (it probably does not in this case, but mostly by luck).
There are a few ways to approach this problem.
You might have a buffer containing the previous 3 elements. At the beginning of each iteration, the buffer contains the last window; sum it up to get last_sum
. Then replace the oldest element with the newest one and rotate_left
by 1. Now the buffer contains the current window; sum it up to get curr_sum
. You don't need a second buffer to keep track of the other window. Note that you can initialize the window to [0; 3]
You could instead use a VecDeque
to store the buffer, combining push_back
with pop_front
(or vice versa). This means slightly less copying since the items do not need to be shifted, and it is flexible to runtime-determined window sizes. For a fixed window size of 3 it's probably overkill.
let curr_sum:u16 = curr.iter().sum();
let last_sum:u16 = last.iter().sum();
Calculating both the current and last sums each iteration means you're calculating each one (except the very first and very last sum) twice as often as necessary. You could make last_sum
an extra state variable and just assign it to the value of curr_sum
at the end of the loop.
A better algorithm?
In fact, even with that modification, you are still doing some extra work. Consider the example from the problem statement:
199 A
200 A B
208 A B C
210 B C D
Window A
and window B
both contain the term 200 + 208
, but you calculate that twice. You can calculate window B
from window A
by adding the new number (210) and subtracting the old one (199). This by itself does not win any performance (with windows of size 3) since you replace only two additions with one addition and one subtraction. However, note that if you only care about whether the sum is increasing or not from window A
to window B
, the center two numbers are completely irrelevant: all that matters is whether, for this slice of length 4, the last number is greater or less than the first. If you could loop over windows of length 4, you could replace all the addition with a single comparison. This strategy also works for solving Part 1 (with windows of size 2).
In the standard library, the way to iterate over windows is to collect
the iterator into a Vec
and use the windows
method. However, with the itertools
crate, you can iterate over windows of an iterator directly using the Itertools::tuple_windows
method. Either way is acceptable.
About mutability
Personally I find nothing bad about the use of mutability in your original code. Mutable state is neither good nor bad, but it is complex, and so should be used when it is useful and minimized otherwise. The amount of mutable state in these algorithms can't really be reduced (except by changing the algorithm itself, as I outlined in the previous section). It is possible to rewrite code like this to use scan
s and fold
s and for_each
es and eliminate (almost) all mut
s. But I don't find that useful. Iterator combinators can be overused, too.
That's not to say that mutable state isn't ever overused - just, I don't think this code is an example of such overuse.
Error handling
"How to handle errors better" is strongly dependent on context. As I mentioned earlier, expect
& panic!
are fine for coding challenges, prototypes, and tests; however, if you're writing a library you probably want to return errors with useful context that the caller can interpret, and if you're writing a binary you probably want to catch errors at some level and print nicely formatted messages. These desires can be at odds with each other, and there are other factors, which is why the Rust ecosystem has so many crates that help you deal with errors in one way or another.
A thing worth trying, if for no other reason than to become familiar with it, is to use the ?
operator to propagate errors up into main
instead of using unwrap
or expect
. main
may be defined as returning a Result
, so you can even use ?
inside main
itself (if you return an Err
from main
, the contents will be printed automatically, although maybe not in the most visually appealing way). Here's one possibility:
fn main() -> Result<(), Box<dyn std::error::Error>> {
let filename = env::args()
.nth(1)
.ok_or_else(|| "Please provide a file name")?;
let input = std::fs::read_to_string(filename)?;
Box<dyn Error>
is a type that can be easily converted from most other kinds of errors, so it's good for prototyping. Option::None
isn't an error, so I use ok_or_else
to convert it into something that can be bubbled up with ?
. But read_to_string
already returns a Result
of an appropriate type, so ?
works on that directly.
The next step up is to create your own error type and define conversions From
each of the error types you want to use with ?
. There are, as I mentioned, different ways to approach this problem space depending on your needs. Box<dyn Error>
, as above, is a starting point.