Project Euler 30 - Digit fifth powers in Rust I am trying to move from Python to a systems programming language so this is a bit of a challenge for me.

fn main() {
    let mut total_pow = 0;
    for x in 2..360000 { 
        let values: Vec&lt;char&gt; = x.to_string().chars().collect();
        let mut total = 0;
        for i in values {
            let value = i.to_digit(10).unwrap();
            total += value.pow(5);
        }
        if total == x {
            total_pow += x
        }
    }
    println!("Numbers {}", total_pow);
}


It runs in just under 1 second, which I think is slow:




$ time cargo run
Total: 443839
real  0m0.894s
user  0m0.888s
sys   0m0.012s



After building with the --release flag the time has greatly improved:


$ time cargo run --release
Numbers 443839

real  0m0.083s
user  0m0.072s
sys   0m0.012s



Some of my concerns are:


Converting x, the loop value, to a char array and then converting each char back into a digit to perform pow on. Is there an easier way? In Python it is really simple (list(str(x))).
I feel the speed of this is really slow.
Best practices for rust/systems level code. I realize this is a fairly simple program but I want to make sure that I learn the good habits early.
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&lt;char&gt; = 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) -&gt; Vec&lt;u32&gt; {
    if n == 0 {
        vec![0]
    } else {
        let mut digits = Vec::new();
        while n &gt; 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(|&amp;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) -&gt; Vec&lt;u32&gt; {
    if n == 0 {
        vec![0]
    } else {
        let mut digits = Vec::new();
        while n &gt; 0 {
            digits.push(n % 10);
            n /= 10;
        }

        digits
    }
}

fn main() {
    let total_pow: u32 = (2..360000).filter(|&amp;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.