If you want to measure the execution time of your program, run it directly, rather than going through Cargo, which adds some overhead of its own.
$ time cargo run --release
Running `target/release/pe30`
Numbers 443839
real 0m0.111s
user 0m0.087s
sys 0m0.027s
$ time ./target/release/pe30
Numbers 443839
real 0m0.045s
user 0m0.040s
sys 0m0.003s
(Cargo's overhead was much worse in the 0.2.0 nightly I first tried this with...)
The Rust compiler generates quite suboptimal code in debug builds, so don't worry too much about it.
Now for the code review proper:
let values: Vec<char> = x.to_string().chars().collect();
There is no need to collect() if all you're going to do is iterate on the collection. chars() returns a struct that implements Iterator, so you can use directly in a for loop.
let values = x.to_string().chars();
Oops, that doesn't compile:
src/main.rs:4:22: 4:35 error: borrowed value does not live long enough
src/main.rs:4 let values = x.to_string().chars();
^~~~~~~~~~~~~
We need to keep the value of x.to_string() alive, since the value of x.to_string().chars() refers to it. (You can discover that from the fact that Chars has a lifetime parameter ('a).) Let's split up the expression:
let x_str = x.to_string();
let values = x_str.chars();
But rather than using the builtin to_string(), we can generate the digits of a number arithmetically:
fn digits(mut n: u32) -> Vec<u32> {
if n == 0 {
vec![0]
} else {
let mut digits = Vec::new();
while n > 0 {
digits.push(n % 10);
n /= 10;
}
digits
}
}
fn main() {
let mut total_pow = 0;
for x in 2..360000 {
let digits = digits(x);
let mut total = 0;
for digit in digits {
total += digit.pow(5);
}
if total == x {
total_pow += x
}
}
println!("Numbers {}", total_pow);
}
(digits produces the digits from least-significant to most-significant; the order isn't important in this algorithm.)
At this point, I think the code is pretty optimal. However, Rust also encourages functional-style programming. Why not take a look?
First, let's change this loop:
let mut total = 0;
for digit in digits {
total += digit.pow(5);
}
into a fold:
let total = digits.iter().fold(0, |sum, digit| sum + digit.pow(5));
fold lets you produce a single value from an Iterator. You specify the initial value, then a function to call on each item that returns the accumulator to pass to the next item, or to return if the end is reached. When you compile with --release, fold is often inlined.
We can do the same again with the outer loop:
let total_pow = (2..360000).fold(0, |total_pow, x| {
let digits = digits(x);
let total = digits.iter().fold(0, |sum, digit| sum + digit.pow(5));
if total == x {
total_pow + x
} else {
total_pow
}
});
This big closure looks a bit messy, though. Let's break up the problem further. First, we want to obtain the list of numbers that can be written as the sum of fifth powers of their digits. Then, we want to sum that list.
For the first task, we need to eliminate numbers that don't apply. To keep only some items from a list, we can use filter. filter returns a new Iterator, on which we can apply fold to get the sum.
fn main() {
let total_pow = (2..360000).filter(|&x| {
x == digits(x).iter().fold(0, |sum, digit| sum + digit.pow(5))
}).fold(0, |total_pow, x| {
total_pow + x
});
println!("Numbers {}", total_pow);
}
If you're using a nightly compiler, you can also use sum (unstable at the time of writing). For the outer fold, we can use sum directly. For the inner fold, we could first use map to turn the sequence of digits into a sequence of their fifth powers, then sum them up. (I had to add a type annotation on total_pow, for some reason.)
#![feature(iter_arith)] // for Iterator::sum()
fn digits(mut n: u32) -> Vec<u32> {
if n == 0 {
vec![0]
} else {
let mut digits = Vec::new();
while n > 0 {
digits.push(n % 10);
n /= 10;
}
digits
}
}
fn main() {
let total_pow: u32 = (2..360000).filter(|&x| {
x == digits(x).iter().map(|digit| digit.pow(5)).sum()
}).sum();
println!("Numbers {}", total_pow);
}
Functional style can make program quite shorter, but also somewhat hard to read when you're not used to it. I encourage you to get used to it, because you're likely to encounter this style again when reading other people's Rust code.
