2018-1-31

# Finding the largest palindrome product with Rust

An easy way to check whether a number is a palindrome is to convert the number to a string, reverse it and check for equality. Neither string conversions or pure brute-force will lead to an optimal solution.

The fourth Project Euler problem - Largest Palindrome Product - is stated as follows.

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.

## Pure brute-force with string conversions

``````fn is_palindrome(product: u32) -> bool {
let str = product.to_string();
let rev_str = str.chars().rev().collect::<String>();
str == rev_str
}

fn get_largest_palindrome(n: u32) -> u32 {
let start = 1 * u32::pow(10, n - 1);
let end = start * 10;

(start..end)
.flat_map(|x| (x..end).map(move |y| x * y))
.filter(|&p| is_palindrome(p))
.max()
.unwrap()
}

fn main() {
println!(
"Largest palindrome n=3: {}",
get_largest_palindrome(3)
);
}
``````
N Execution Time Improvement
2 9.8 ms Baseline
3 933.5 ms Baseline
4 103286.6 ms Baseline

## Pure brute-force with modulo operation

``````fn is_palindrome(n: u32, num: u32) -> bool {
!(0..n).any(|a| (num / 10u32.pow(2 * n - 1 - a)) % 10 != (num / 10u32.pow(a)) % 10)
}

fn get_largest_palindrome(n: u32) -> u32 {
let start = 1 * u32::pow(10, n - 1);
let end = start * 10;

(start..end)
.flat_map(|x| (x..end).map(move |y| x * y))
.filter(|&p| is_palindrome(n, p))
.max()
.unwrap()
}

fn main() {
println!(
"Largest palindrome n=3: {}",
get_largest_palindrome(3)
);
}
``````
N Execution Time Improvement
2 1.4 ms 7X
3 104.8 ms 9X
4 10568.0 ms 10X

## More efficient algorithm with string conversions

``````fn is_palindrome(product: u32) -> bool {
let str = product.to_string();
let rev_str = str.chars().rev().collect::<String>();
str == rev_str
}

fn get_largest_palindrome(n: u32) -> u32 {
let a_start = 10u32.pow(n - 1) / 11 + 1;
let a_end = 10u32.pow(n) / 11 + 1;
let b_start = 10u32.pow(n - 1);
let b_end = 10u32.pow(n);

(a_start..a_end)
.flat_map(|x| (b_start..b_end).map(move |y| 11 * x * y))
.filter(|&prod| prod > 10u32.pow(2 * n - 1) && is_palindrome(prod))
.max()
.unwrap()
}

fn main() {
println!(
"Largest palindrome n=3: {}",
get_largest_palindrome(3)
);
}
``````
N Execution Time Improvement
2 1.3 ms 8X
3 125.8 ms 7X
4 14348.6 ms 7X

## More efficient algorithm with modulo operation

``````fn is_palindrome(n: u32, num: u32) -> bool {
!(0..n).any(|a| (num / 10u32.pow(2 * n - 1 - a)) % 10 != (num / 10u32.pow(a)) % 10)
}

fn get_largest_palindrome(n: u32) -> u32 {
let a_start = 10u32.pow(n - 1) / 11 + 1;
let a_end = 10u32.pow(n) / 11 + 1;
let b_start = 10u32.pow(n - 1);
let b_end = 10u32.pow(n);

(a_start..a_end)
.flat_map(|x| (b_start..b_end).map(move |y| 11 * x * y))
.filter(|&prod| prod > 10u32.pow(2 * n - 1) && is_palindrome(n, prod))
.max()
.unwrap()
}

fn main() {
println!(
"Largest palindrome n=3: {}",
get_largest_palindrome(3)
);
}
``````
N Execution Time Improvement
2 0.3 ms 30X
3 20.0 ms 47X
4 2149.2 ms 48X

The optimized versions of my pure brute-force algorithm is more or less a product of the friendly community over at the Rust Discrord. If you need help with the programming language Rust, I couldn't recommend the Discord channel enough.

Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.