Project Euler - Rust Problem 1

https://projecteuler.net/problem=1

 Project Euler is a site with challenges that people solve with programs and then submit that code to be commented on.  Normally, there's not a lot of comments unless you have a unique approach.  That's fine.

I've solved many of them in python but I'm going to go through them with Rust.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The problem is asking that we find all of the natural numbers that are below 1000 that are multiples of 3 or 5. When we find them, add them together and then give the sum.

Natural Numbers are integers that are positive. So any whole number below 1000.

first we have to go through all those numbers.

for n in 0..1000 {}

A for loop will do the trick just fine.  0..1000 runs through all the numbers up to but not including 1000.  I could start at 3 instead of 0, 3..1000.  That would be fine as well since I know that 0, 1, and 2 aren't multiples of 3 or 5.

In the loop, we need to determine if the number (n) is divisible by 3 or 5.  One at a time, we can use simple if and else if statements.

if n%3 == 0{}

else if n%5 == 0{}

n % 3 == 0  

If we take n, the given number as we loop through, and divide it by 3, will it do so evenly or will there be a remainder?  If there's no remainder, we get 0.  The % used here will give us this answer.  The statement n%3 == 0 will result in a true or false.

The same is true of the else if statement.

Great! We have the logic for going through every number, 0 to 1000 and then figuring out if it's a multiple of 3 or 5.

We don't need an else statement.  If the given number (n) is not divisible by 3 or 5, then we will do nothing with it and can continue on.

Lastly, we need something to hold the sum of the values as we go through.

let mut sum: i32 = 0;

The variable sum is declared as mutable as we will need to change the value every time we find a multiple.

Finally, we need some way to see what the final value is.  We'll use the print to console macro for this.

The final code might look like this.

let mut sum: i32 = 0;

for n in 0..1000{

    if n%3 == 0{

        sum += n;

    }

    else if n%5 == 0{

        sum += n;

    }

}

println!("{}", sum);

 

Now I freely admit that this is not an inspired solution.  It doesn't take into account any kind of performance.  It's pretty brute force as it is but it's a beginner problem to highlight beginner problems in code.

This solution comes in at 1.29 seconds.

A more elegant approach

my friend showed me a way to make this a little more compact.

    let x = (0..1000).collect::<Vec<i32>>();

    let x: i32 = x.iter().filter(|&n| n%3 == 0 || n%5 == 0).sum();

    dbg!(x);

First, he declared a variable x as a vector collecting all the values from 0 to 1000.

Then he declared x as a number using shadowing.  Shadowing is convenient because it allows you to not only change the value of a variable but the type.  You're basically forcing the variable x as it exists to leave scope and release it's name and then assign it's name to a new value.  In this case, he used shadowing to iterate (iter()) through all the values in the vector and then filter out only the values that are divisble by 3 and 5 evenly.  Finally we added them altogether.

He did this in one line using what's called a Closure.  It's similar to a lambda in python.  
https://doc.rust-lang.org/rust-by-example/fn/closures.html

The dbg! macro is a debug macro that prints things to the console.  The rust documentation recommends that using this feature not be used, recommending the debug! macro from the log crate.  However, this is not a final release of a program and is simply a learning tool.

The logic is very elegant and works just the same as my code but it is smaller.  On Rust Playground it ran in 0.91 seconds versus the 1.3 seconds that my original code did.  It's not surprising really.  

Other solutions from other users -

Another user (forrin ) using Rust, posted this solution.

fn main() { println!("Result: {}", basic_solution(999)); } fn basic_solution(target: i32) -> i32 { let mut sum = 0; for n in 1..=target { if n % 3 == 0 || n % 5 == 0 { sum+= n; } } return sum; }

This solution is fine. It does basically what mine does except he isolated it into a function and filtered out the if/else if to a if this or that.

Runs 1.25seconds on Rust playground.

Another solution, similar to my friend's.

fn main() {

    let bound : i32 = 1000;

    println!("out {}", (1..bound).filter(|&n| n % 3 == 0 || n % 5 == 0).sum::<i32>().to_string())

}

This one filters the same but does all in the same line.  While I do like this solution and it runs at a 0.89 seconds on rust playground, it's hard to read and hard to understand at a glance what is going on.

Finally, another user (DMDM2 ) posted this solution, similar to my original answer.

let mut sum = 0; for x in 0..1000 { if (x % 3 == 0) | (x % 5 == 0) { sum += x; } } println!("Sum is: {}", sum);

This answer runs at 1.03 seconds. Faster than above, I assumed it's because the above user called another function.  However, if you remove the function call and put everything in the main scope, it still runs at 1.39, slower than above and slower than here.

let's compare the two answers from forrin and DMDM2 side by side.

Overall time is 1.25 seconds (forrin)  versus  1.03 seconds (DMDM2)

Before I continue, I'm not trying to call either of them out.  My solution for this wasn't exactly inspired.  I'm simply trying to delve into the workings of our answers and account for the performance differences.

We've already discussed that removing the function call actually makes it slower.

So let's compare the logic after the function call.

let mut sum = 0;

That's the same.  We all have to have a container to put the answer.

for n in 1..=target  vs for x in 0..1000

If we run 0..=999 on the right, we actually add some time on.  This makes sense, given that instead of stopping at a limit, we're evaluating if the number is = to 999 and only stopping after that.  

other than the left side looking for a variable and then referencing that value every time it evaluates (if it is running how I think it is and correct me if I'm wrong), the for loop is the same.

Once the for loop is concluded, the function on the left then passes the value back to the main function and prints it.  The one on the right just prints the variable.

I'm going to assume that the extra step of passing through a function call makes up some of that time.  I would love to know exactly what the differences here are.  Let me know if you have any thoughts about this below.