Project Euler - Rust Problem 4

Project Euler

Problem 4 - in Rust

A palindromic number reads the same both ways. 

The largest palindrome made from the product 

of two 2-digit numbers is 9009 = 91 × 99. 

 

Find the largest palindrome made from the 

product of two 3-digit numbers.

Fun times.  Love palindromes.  Taco Cat... anyone? :)

What isn't fun? Strings in Rust.

They are the bane of my existence in programing with Rust. I don't know why they're so hard to mess with but they are.  So we can approach this just straight numbers or ... we can convert them to strings and compare...

Numbers. for sure.

Breakdown

I'm starting to get into a groove with analyzing these problems and my approach. I realize my approach might be complete crap but it works and it's mine so :P.

Seriously thought, first rule of fight clu... of answering these things.  <whistles innocently> First thing is breaking it down into managable pieces. 

So, what is it asking?

Find - we're looking for something
the largest - biggest number (quantifier)
Palindrome - something the same forward and backwards.
made from the product of 2 (3) digit numbers -... ok

so we're taking two 3 digit numbers, I assume they are both different, and we are multiplying them together.  If the answer is a palindrome and there's no other palindrome answer above it, then that's the answer...

Sure.

So what's the first question?

Can we narrow down the pool of numbers we're using? Get a range?

We can take the two smallest 3 digit numbers and multiply those for the low.  Then take the two largest 3 digit number and multiply those for the high.

100 * 101 = 10,100   This is not a palindrome but it is the lowest product of two 3 digit numbers.

999 * 998 = 997,002 this is also not a palindrome but is the highest product of two 3 digit numbers.

Now we have a range. [10,100..997,002].  The number we seek is in there.

so if we use the variable ans then the following is true:

10100 < ans < 997002

This gives us the starting point. 986902 different possibilities for a product

Recognize 

As the great Warren G once said, Recognize.  That's what we have to teach the computer to do. 

If we have a number, say 4516.  We can mod by 10 and get 6.  if we take the number and divide by 10, we get 451.6 (rounded down, aka flat) 451.  mod 10 = 1, divide by 10 = 45, mod 10 = 5, ... and if we add these mod's to a vec we now have the reverse value divided by each digit and in reverse order.

Also, if you have an even numbered value with a zero in the one's place, it will never by a palendrom.  143580 reversed is 085341.  The computer will drop the 0 and honestly, it would never add a leading 0 in the first place.  So this can be the first step in the logic of determining if it's a palendrome.

psuedo code

for loop - 

num = a*b

If num % 10 == 0 {

continue

}

function call to pal_check(num)

We will save a lot of time skipping over the values evenly divisible by 10.

pal_check function - pseduo code

pass in the value we're checking
declare two Vec's, one for forwards, one for back
for loop - break apart the number and add it to the array, one push and one insert to 0
then return true if both vecs match
else return false

rinse repeat

Implimentation 

So there we have it. The basic logic of what we're looking at.

So what does that look like in code?

My Code:

// range [10100..997002] of possible products 

// 10100 < ans < 997002

fn main() {

let mut h_num: u32 = 999;

let mut ans: u32 = 10100;

while h_num > 100{

let l_num = h_num -1;

for x in 100..l_num{

let num = h_num * x;

if num % 10 == 0{

continue;

}

if pal_chk(num) == true {

if ans < num{

ans = num;

}

}

}

h_num -= 1;

}

println!("Ans is {}", ans);

}

fn pal_chk(x: u32) -> bool{

if x % 10 == 0{

return false

}

let num = x.clone();

let mut numbi = num.clone();

let mut vec1 = Vec::new();

let mut vec2 = Vec::new();

while numbi > 0{

let a = numbi % 10;

vec1.push(a);

vec2.insert(0, a);

numbi = numbi/10;

}

return vec1 == vec2

}

Now, I realize that my naming convention probably sucks. I'm still trying to learn the syntax and honestly, I'm not too worried about that at the moment.  This code worked and that's what's important at this moment.

Let's look at what some of the other guy's code looks like.

Other Guy's Code

So here we have Frinzie.

fn largest_palindrome() -> i32 {

    let mut largest = 0;

    for i in (101..1000).rev() {

        for j in (101..1000).rev() {

            let num = i*j;

            if num > largest && is_palindrome(num) {

                largest = num;

            }

        }

    }

    largest

}

fn is_palindrome(num: i32) -> bool {

    let snum = num.to_string();

    let reverse_snum: String = snum.chars().rev().collect();

    reverse_snum == snum

}

fn main() {

    println!("{}", largest_palindrome());

}

Something that's always bothered me is the idiomatic rust convention of not labeling the return as return.  Instead we just toss whatever we're returning at the end of the function and we don't end it with a semi-colon (;). Personally, I use return.   I do that because it improves readability.

That's not a dig at F here just a personal pet peeve as it were.

What's going on here.

Main prints the result of the function largest_palindrome.  That function hardcodes the range of all values less than 1000.  and uses two for loops inside each other.  Far more efficient, I'm sure than how I hobbled the same functional result together.  I'm doing this while working 3rd... and I need more practice with the for loop syntax in Rust.  Hats off to F here for reminding me.

Then he submits the two loop values as a product and evaluates it as both larger than the largest value on record and if it's a palindrome. if it is both then it replaces largest and moves on.  After all the values have been ran through, it returns largest and prints it.

So, this is the basic logic that I used to approach the problem but a much smoother execution.

Conclusion

Most of the submissions I saw involved converting the int to a string and then slicing it up and so on.  Mine did not.  That and a dollar will get me a sweet tea at McDonald's.  I still have a lot to learn.