Project Euler - Rust problem 12

 On the Project Euler site, which I highly recommend, they don't want anyone sharing answers over 100.  I'm cool with that.  Once I get there, I'll share other things.  I'm getting more comfortable with Rust so we'll see where that goes.

Problem 12 - Project Euler

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1

 3: 1,2,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

There's a few ways to approach this.  I chose to go into this brute force style.  

[dependencies]

divisors = "0.2.1"

Here's my single dependency and the code.

use std::time::{Instant};

fn main() {

    let start_time = Instant::now();

    let mut final_num: u32 = 0;

    let mut divisor_count: u32 = 0;

    let mut count: u32 = 1;

    while divisor_count < 498{

        let triangle = get_tri(count);

        let divisors = divisors::get_divisors(triangle);

        divisor_count = divisors.len() as u32;

        final_num = triangle;

        count += 1;

    }

println!("time = {:?}, final number = {:?}", start_time.elapsed(), final_num);

}

fn get_tri(x: u32) -> u32 {

    let mut count = x;

    let mut sum = 0;

    while count > 0{

        sum += count;

        count -= 1;

    }

    sum

}

Here we go. Declaring the final_num, the divisor count, and the count.  Then the loop. While the divisor count is less than 498 the loop will run.

Why 498?  I used 498 as the threshold because it would return on divisor length being 499 and this particular crate doesn't count 1 as a divisor where most of the problems do consider it. So I always have to take that into consideration when I use this crate.

In the loop, we define the triangle based on the current count.  That count is incremented by 1 at the end of the loop.  We get the number of divisors for the triangle. Assign final number to the triangle and increment the count.

Once it reaches 499, it breaks the while and prints the answer.  

I included the time thing just for fun.  I did go back and change the let triangle = get_tri(count) to final_num = get_tri(count).  It works. It's not as efficient as some of the other answers in other languages but it does get the job done. 1.5 seconds.

Project Euler - Rust Problem 11

 Problem 11 

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

After all this time, I still haven't figured out a good way to import information from txt files.

So I hard coded it... as an array, a multidimensional array, a constant multidimensional array

const DATA: [[u32;20]; 20] = [

    [08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08], ...

[01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]];

So that worked out.  Obviously I cut the center out for this post but it is in the code. 

Once that was out of the way, I was able to focus on the logic.  Now, I separated much of the logic into different functions.  While I could pass the values through to them, since I'm not editing the grid, I decided to keep it immutable and as a constant. It honestly makes reading the code easier (for me) but I'm not sure if that's really the best way to go about it.  In this instance though, I think it's the best way.

Here's my main function:

fn main(){

    let mut max_sum: u32 = 0;

    for x in 0..DATA.len(){

        for y in 0..DATA[x].len(){

            let sum = eval(x as u32, y as u32);

            if sum > max_sum{max_sum = sum};

        }

    }

    println!("{}", max_sum);

}

I tried to keep my main function as brief as possible.  so the loop is pretty straight forward.

Loop through each line, then loop through each number.  I declared a sum and if that sum is greater than the max, it replaces it. If not continue to the next.  The sum is equal to the return of a function eval that passes in the x and y numbers (numerical locations in the grid).

So what does eval do?

fn eval(x: u32, y: u32) -> u32 {

    let data_vec: Vec<u32> = vec![eval_vertical(x,y), eval_right(x,y),

        eval_diag_r(x,y), eval_diag_l(x,y)];

    let ans = data_vec.iter().fold(std::u32::MIN, |a,b| a.max(*b));

    ans

}

As you can see it does a few things.  First, it creates a vector.  Then it sorts that vector and sets ans to the max value in that vector and returns that from the function.

The vector itself is set to the values of all these functions.  Each function does basically the same thing.  It multiplies the values of the number and then the 3 down for vertical, the 3 right for right and then the diags right and left. I even put in a requirement for x and y positions so it didn't error out by going over the index.

fn eval_vertical(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y] * DATA[x+2][y] * DATA[x+3][y]

}

fn eval_right(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y > 16{

        return 0;

    }

    DATA[x][y] * DATA[x][y+1] * DATA[x][y+2] * DATA[x][y+3]

}

fn eval_diag_r(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y > 16 || x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y+1] * DATA[x+2][y+2] * DATA[x+3][y+3]

}

fn eval_diag_l(x: u32, y: u32) -> u32{

    let x: usize = x as usize;

    let y: usize = y as usize;

    if y < 3 || x > 16 {

        return 0;

    }

    DATA[x][y] * DATA[x+1][y-1] * DATA[x+2][y-2] * DATA[x+3][y-3]

}

As you can see, they're closely repetitive and could merit a rewrite using recursion and even a direction argument with a match case... shrug. But that's not what I did.

It could cut the code size in half though.

Anyways, that's the code.  

I didn't see any other rust answer.  To the next problem.

Project Euler - Rust Problem 10

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

I've been doing a lot of exploring through the crate.io website.  I've found much like the old apple istore catch phrase, there's a crate for that.

I utilized a library called prime_tools.  The library has a function that literally finds all prime numbers less than a given number.  It returns a vector as 32bit unsigned integers.  From there we could loop through using vector.init().sum() however, sum() isn't a function of u64 and the answer here exceeds the max of a u32. So I went with a for loop.  Someday I hope to learn a better way

Tmol file - 

[dependencies]

prime_tools = "0.3.4"

main.rs

fn main(){

let my_vec = prime_tools::get_primes_less_than_x(2000000);

let mut my_sum: u64 = 0;

for i in my_vec{

my_sum = my_sum + i as u64;

}

println!("{}", my_sum);

}

Now, this is kind of a cop out in someways but it gets the job done.  The alternative is to go through and brute force it. Alternatively, you could use a sieve until you got to or exceeded 2000000.  This was my go to.

There was another user that used rust and went with the sieve method. I won't go into that here as I've already covered it with a previous problem that addressed prime numbers.

User Hegemon8 used an interesting brute force method.

Slick. 0.64s fn main() { let mut vector:Vec<bool> = vec![false; 2_000_000]; for i in 2..1415 { if vector[i] == false { let mut j = i * i; while j < vector.len() { vector[j] = true; j = j + i; } } } let mut sum = 0; for (index, i) in vector.iter().enumerate() { if i == &false { sum = sum + index; } } println!("{}", sum - 1); }

He created a vector of 2000000 values of bools all set to false.  They he looped through all the values from 2 to 1415.  Then if the value of the loop in the vector was false, he multiplied it by itself and set it to true if that index existed.  The significance of 1415 is that squared it exceeds 20000000 and 1414 falls a little short.  If you square a number the resulting number can't be prime.  This is a clever sieve method that's more compact than other's I've seen.  He then sums up all the false indexes and returns the sum.

I was curious if we could clean this up.

Maybe?

Here's my rewrite for the for loop at the bottom

let sum: u64 = vector.into_iter().enumerate().fold(0, |s, (i, j)| s + eval(i as u64, j));    

println!("{}", sum);

Then I had to add a function.

fn eval(x: u64, y: bool) -> u64{

    match y { true => 0, false => x as u64}

}

Now. It seems that the reason I had to use u64 is cause the answer is soooo big.

I learned a lot about the fold method doing this (4 hours of head to desk before it worked).  I also learned that in a fold, you can't (or I couldn't find how) to use a filter/match/ifelse statement.  I tried but match wouldn't work....

As I write this, I had a facepalm moment.  Yup learning in real time now. :(

I went back and tried something. It worked.

let sum: u64 = vector.into_iter()

    .enumerate()

    .fold(0, |s, (i, j)| s + match j { true => 0, false => i as u64});

Yup, so the match did work. I realized when I tried earlier I didn't add to the s value which is the total sum.

Correct me if I'm wrong (please).
fold (starting value, |return value, value_i'm evaluating in the iter| formula evaluated and added to the return value)

That's my understanding anyways.

Project Euler - Rust Problem 9

Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Pythagorean triplets are whole numbers that work with the right triangle formula.  They also increase in value so none of them are the same. 

There's a whole system of mathematics that deals with equations like this where there are multiple unknowns and various answers that once known will solve all equations present.  These equations are known as Diophantine equations.  

Thanks wikipedia... but that doesn't help me.  However, there's some juicy information on PT's.

Here are some properties that must be satisfied that we can use.

a^2 + b^2 = c^2
a < b < c
((c * a)(c*b))/2 is always a square
(3,4,5) is the smallest known PT
At most only one of a,b,c is a square (more than 1 square they're not a set)
a or b is divisible by 3
a or b is divisible by 4
a or b or c is divisible by 5
the largest number that always divides abc is 60

Ok, so there's a few things that we can increment by and check by. as well as a starting point.

We could always do the brute force method.

for i in 1..1000, for j in 2..1000, for k in 3..1000 if i+j+k = 1000, check if i^2 + j^2 = k^2, if true return i,j,k

Psudo code but that's the basic brute force. I mean if only one of them is equal to 1000 and satisfies the formula then great. 

However, I wanted to try a different approach.  There's a relation to PT's and Fibonacci sequences that is pretty interesting.  The downside to our current problem is that while the Fib numbers do follow a predictive pattern, they do not encompass all the PT's in that range.  They skip quite a few.

Kind of a "all buicks are cars but not all cars are buicks".

Project Euler - Rust Problem 8

Problem 8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Well then.  Yeah, that's a thing.

Logically speaking... you would loop through the numbers starting with 0-3 and then ending -4:-1.  So... With Rust, it doesn't index the same way as python.  We should still be able to loop through it just fine.  The bigger issue, for me, is how do you get the input into the program.

You can hard code it.  Just put in the string of numbers manually into the code.  Sure why not? I would pull it in from a text file but... I'm still trying to figure that out. meh.

So I loaded the number string into a vector as integers. 

My code

fn main(){

        let mut my_vec = vec![7,3,(all the numbers from above),5,0];

let mut largest_multi = 0;

let mut first: u64 = my_vec.pop().unwrap();

let mut second: u64 = my_vec.pop().unwrap();

let mut third: u64 = my_vec.pop().unwrap();

let mut fourth: u64 = my_vec.pop().unwrap();

let mut fifth: u64 = my_vec.pop().unwrap();

let mut sixth: u64 = my_vec.pop().unwrap();

let mut seventh: u64 = my_vec.pop().unwrap();

let mut eighth: u64 = my_vec.pop().unwrap();

let mut ninth: u64 = my_vec.pop().unwrap();

let mut tenth: u64 = my_vec.pop().unwrap();

let mut eleventh: u64 = my_vec.pop().unwrap();

let mut twelvth: u64 = my_vec.pop().unwrap();

let mut thirteenth: u64 = my_vec.pop().unwrap();

while my_vec.len() > 0{

let mut x = first * second * third * fourth * fifth * sixth * seventh * eighth * ninth * tenth * eleventh * twelvth * thirteenth;

if x > largest_multi{

largest_multi = x;

}

println!("{}", my_vec.len());

first = second;

second = third;

third = fourth;

fourth = fifth;

fifth = sixth;

sixth = seventh;

seventh = eighth;

eighth = ninth;

ninth = tenth;

tenth = eleventh;

eleventh = twelvth;

twelvth = thirteenth;

thirteenth = my_vec.pop().unwrap();

}

println!("{:?}", largest_multi);

}

So after I hard coded the number string, I defined 13 variables.  Then I filled those with the first 13 popped values from the vector.  Then I created the loop based on the length of the vec.  If the vec is greater than 0 then there's still values in them.  So every loop, all 13 variables are multiplied together.

if the multiple is greater than the largest recorded value, it records the new value.  After all the values have been popped, the largest multiple is printed.

There's obviously ways to improve this.  filter out any iteration if 0 is in the variables. you know skip those.  Change how the slices of the vec are accessed.

I doubt this is the most effective method.

Other Guys Code

Minacode wrote:

The main idea is to not calculate the whole window at every step. Thus, we have to divide through the leftmost number we are "leaving" while moving the window to the next position, and then multiply with the new number on the right. Because there are zeros, we have to be careful. At the start and after every zero, we have to incrementally multiply enough numbers to make up a whole window of 13 numbers. This is why we keep track of a scope count which measures the current size of the window. Until we did not reach 13 elements, we do not update the max value. fn main() { let series = [ 7,3,(all the numbers in the list),5,0 ]; let length = series.len(); let scope = 13; let mut product: u64 = series[0]; let mut max = product; let mut i = 0; let mut scope_count = 1; while i < length-scope { let new = series[i + scope_count]; if new == 0 { i += scope_count; scope_count = 1; while i < length && series[i] == 0 { i += 1; } if i == length { break; } product = series[i]; } else { if scope_count == scope { let last = series[i]; product /= last; product *= new; if product > max { max = product; } i += 1; } else { scope_count += 1; product *= new; } } } println!("{}", max); }

So basically this code improves in all the ways that I had mentioned. It cycles through the list 13 at a time and multiplies them together. If it == 0 then it moves the cycle. He also uses an array instead of a vec. I will be looking into the benefits of using one over the other.

Project Euler - Rust Problem 7

 Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Now this is interesting. Because we dealt with primes in an earlier problem.  There we cheaped out a little... and so why should this be any different.

This is literally an example in the primal crate documentation. add "primal = "0.2"" " to the tmol

// (.nth is zero indexed.)
let p = primal::Primes::all().nth(10001 - 1).unwrap();
println!("The 10001st prime is {}", p); // 104743

Boom prints the answer. No fuss no muss. 

Alternativly, there's some of the other approaches.

The other guys code

First answer comes from BitRake who is quickly becoming my favorite person on the answer forums.

He points out, look we have this website with all known primes on it. Prime pages.

Another user Frinzie did it manually.  Kudos to him for tackling this challenge in a more robust approach.

fn is_prime(num: i32) -> bool { // works for odd numbers in range [3, +inf) let ceil = (num as f64).sqrt() as i32; for i in (3..=ceil).step_by(2) { if num % i == 0 { return false; } } true } fn main() { let mut primes = vec![2]; let mut num = 3; while primes.len() < 10001 { if is_prime(num) { primes.push(num); } num += 2; } println!("{}", primes[10000]) }

First he creates a vector primes.  Got to have a place to store the answers.  Then a num variable starting at 3.  Primes after 2 can't be even by definition so he's only going to check odd numbers.  Start at 3 and add 2 with every iteration.

He sets the limit in the while loop, while the primes vector length is less than 10001 the loop will check all odd numbers and add them to the primes list until it has 10001.  Finally it prints out the 10000 index of the primes vector.  

Great approach using solid logic.

One last user did it the same way Frinzie approached it but without putting the function logic in the function.

Special note: 1 apparently isn't prime. shrug so I guess I'll take that into account when using the these libraries.

Project Euler - Rust Problem 6

 Problem 6

The sum of the squares of the first ten natural numbers is,

    1^2 + 2^2...+10^2 = 385

The square of the sum of the first ten natural numbers is,

    (1+2+...+10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is .

    3025 - 385 = 2640

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This seems pretty straight forward.

we need a sum of squares function and a square of sums function and then subtract the two.

Sounds easy...

My approach

fn main() {

let test_u_limit = 100;

let x = square_of_sums(test_u_limit) - sum_of_squares(test_u_limit);

println!("{}", x);

}

Here's my main function. Straight forward.  Subtract the returns of two functions.

Let's tackle the sum of squares function. 

fn sum_of_squares(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans = ans + (x^2);

}

println!("Sum of squares is {}", ans);

return ans

}

I went with i64 on the off chance that the value might exceed 2147483647.  It doesn't but I didn't know that.  I guess, I could refactor it to i32 since I have to refactor it to get it to work. 

Oh yeah, this doesn't work.  Fun fact... the ^ symbol doesn't raise to a power.  Nope.  It's a bitwise operator.  This doesn't work.

According to stack overflow, to raise to a power it should read x.pow(2).  pow takes an unsigned 32 bit int and returns a signed 32 bit int.

so the refined code reads...

fn sum_of_squares(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans = ans + x.pow(2);

}

return ans

}

not a huge change but it works.  Unfortunately, I did the same thing with the square of sums function but I fixed it at the same time I did the previous refactor.

fn square_of_sums(u_limit: i64) -> i64{

let mut ans = 0;

for x in 1..=u_limit{

ans += x;

}

ans = ans.pow(2);

return ans

}

This works fine.  I learned how to raise things to a power.

what's interesting is this can work with raw numbers if you type them. I played around on the playground and found this works.

fn main(){

    let x: i32 = 7;

    println!("x to the 2 power is {}", x.pow(2));

    println!("5 to the 2 power is {}", 5i32.pow(2));

   

}

Other guys code

eathren had almost the same idea. except he approached the power issue manually.

doing i*i instead of i.pow(2)  

Still works but I wonder if he ran into the same issue I did with the ^ symbol.
He also opted for 1..n+1 instead of 1..=n  I wonder if there's a performance advantage to that.

Final thoughts

I'm discovering that there aren't alot of answers in Rust on these problem sites.  Most of the answers I'm seeing are from the last 4 months.  It seems like it's picking up steam.  I'm getting more comfortable with it.  I thought it would be a lot harder.  Not that it's easy just... it's easier than I had anticipated.  Till next time.