4
\$\begingroup\$

I am new to rust and this is a program that finds out the palindromes between a range. All tests have been passed but this program is really slow in finding the 4 digits Palindromes.

This is an exercism exercise and Palindrome struct and struct methods new, value, and insert must be used in the final solution.

I need your help to review this code.

use std::cmp::Ordering;

#[macro_use]
extern crate itertools;

#[derive(Debug, Eq)]
pub struct Palindrome {
    factors: (u64, u64)

}


impl PartialOrd for Palindrome {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Palindrome {
    fn cmp(&self, other: &Self) -> Ordering {
        // self.height.cmp(&other.height)
        (self.value()).cmp(&other.value()) 

    }
}


impl PartialEq for Palindrome {
    fn eq(&self, other: &Self) -> bool {
        // self.height == other.height
        self.value() == other.value() 


    }
}

impl Palindrome {
    pub fn new(a: u64, b: u64) -> Palindrome {
        Palindrome{
            factors: (b, a)
        }


    }

    pub fn value(&self) ->  u64 {
        self.factors.0*self.factors.1
    }

    pub fn insert(&mut self, a: u64, b: u64) {
            self.factors.0 = a;
            self.factors.1 = b;

    }
}


fn reverse_number(mut n: u64) -> u64{
    let radix = 10;
    let mut reversed = 0;

    while n != 0 {
        reversed = reversed * radix + n % radix;
        n /= radix;
    }

    reversed

}


fn is_palindrome(palindrome: &Palindrome) -> bool{
    if palindrome.value() == reverse_number(palindrome.value()){
        return true;
    }
    false
}

pub fn palindrome_products(min: u64, max: u64)-> Option<(Palindrome, Palindrome)>{
    if max <= min {
        return None;
    }

    let products = iproduct!(min..=max, min..=max)
        .map(|(i, j)| Palindrome::new(i, j))
        .filter(|palindrome| is_palindrome(palindrome));

        Some((products.clone().min()?, products.clone().max()?))


    }

Here is the full the test Suit

//! This test suite was generated by the rust exercise tool, which can be found at
//! https://github.com/exercism/rust/tree/master/util/exercise

use palindrome_products::{palindrome_products, Palindrome};

/// Process a single test case for the property `smallest`
///
/// All cases for the `smallest` property are implemented
/// in terms of this function.
fn process_smallest_case(input: (u64, u64), expected: Option<Palindrome>) {
    let min = palindrome_products(input.0, input.1).map(|(min, _)| min);
    assert_eq!(min, expected);
}

/// Process a single test case for the property `largest`
///
/// All cases for the `largest` property are implemented
/// in terms of this function.
/// 
fn process_largest_case(input: (u64, u64), expected: Option<Palindrome>) {
    let max = palindrome_products(input.0, input.1).map(|(_, max)| max);
    assert_eq!(max, expected);
}

#[test]
/// finds the smallest palindrome from single digit factors
fn test_finds_the_smallest_palindrome_from_single_digit_factors() {
    process_smallest_case((1, 9), Some(Palindrome::new(1, 1)));
}

#[test]
#[ignore]
/// finds the largest palindrome from single digit factors
fn test_finds_the_largest_palindrome_from_single_digit_factors() {
    let mut expect = Palindrome::new(1, 9);
    expect.insert(3, 3);
    process_largest_case((1, 9), Some(expect));
}

#[test]
#[ignore]
/// find the smallest palindrome from double digit factors
fn test_find_the_smallest_palindrome_from_double_digit_factors() {
    process_smallest_case((10, 99), Some(Palindrome::new(11, 11)));
}

#[test]
#[ignore]
/// find the largest palindrome from double digit factors
fn test_find_the_largest_palindrome_from_double_digit_factors() {
    process_largest_case((10, 99), Some(Palindrome::new(91, 99)));
}

#[test]
#[ignore]
/// find smallest palindrome from triple digit factors
fn test_find_smallest_palindrome_from_triple_digit_factors() {
    process_smallest_case((100, 999), Some(Palindrome::new(101, 101)));
}

#[test]
#[ignore]
/// find the largest palindrome from triple digit factors
fn test_find_the_largest_palindrome_from_triple_digit_factors() {
    process_largest_case((100, 999), Some(Palindrome::new(913, 993)));
}

#[test]
#[ignore]
/// find smallest palindrome from four digit factors
fn test_find_smallest_palindrome_from_four_digit_factors() {
    process_smallest_case((1000, 9999), Some(Palindrome::new(1001, 1001)));
}

#[test]
#[ignore]
/// find the largest palindrome from four digit factors
fn test_find_the_largest_palindrome_from_four_digit_factors() {
    process_largest_case((1000, 9999), Some(Palindrome::new(9901, 9999)));
}

#[test]
#[ignore]
/// empty result for smallest if no palindrome in the range
fn test_empty_result_for_smallest_if_no_palindrome_in_the_range() {
    process_smallest_case((1002, 1003), None);
}

#[test]
#[ignore]
/// empty result for largest if no palindrome in the range
fn test_empty_result_for_largest_if_no_palindrome_in_the_range() {
    process_largest_case((15, 15), None);
}

#[test]
#[ignore]
/// error result for smallest if min is more than max
fn test_error_result_for_smallest_if_min_is_more_than_max() {
    process_smallest_case((10000, 1), None);
}

#[test]
#[ignore]
/// error result for largest if min is more than max
fn test_error_result_for_largest_if_min_is_more_than_max() {
    process_largest_case((2, 1), None);
}


```
\$\endgroup\$
4
\$\begingroup\$

Run rustfmt

You have some inconsistent formatting. Just run cargo fmt and your code will be automatically formatted to best practices.

Make Palindrome a tuple struct

Instead of

#[derive(Debug, Eq)]
pub struct Palindrome {
    factors: (u64, u64),
}

Use

#[derive(Debug, Eq)]
pub struct Palindrome(u64, u64);

Derive PartialOrd

Instead of

impl PartialOrd for Palindrome {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

Just use #[derive(Debug, Eq, PartialOrd)] instead, like what you already do for Eq.

Rename Palindrome

It should be called something like Pair instead, unless required by your course—an instance of a Palindrome can actually not be a palindrome.

Don't explicitly return

fn is_palindrome(palindrome: &Palindrome) -> bool {
    if palindrome.value() == reverse_number(palindrome.value()) {
        return true;
    }
    false
}

You're comparing a boolean, then returning based on that. Just return the boolean directly:

fn is_palindrome(palindrome: &Palindrome) -> bool {
    palindrome.value() == reverse_number(palindrome.value())
}

However, that function should probably be a method of Palindrome unless it's required to be separate by the course.

Accept a range instead of (min, max)

Instead of

pub fn palindrome_products(min: u64, max: u64) -> Option<(Palindrome, Palindrome)> {
    if max <= min {
        return None;
    }

    let products = iproduct!(min..=max, min..=max)
        .map(|(i, j)| Palindrome::new(i, j))
        .filter(|palindrome| palindrome.is_palindrome());

    Some((products.clone().min()?, products.clone().max()?))
}

fn process_smallest_case(input: (u64, u64), expected: Option<Palindrome>) {
    let min = palindrome_products(input.0, input.1).map(|(min, _)| min);
    assert_eq!(min, expected);
}

How about

pub fn palindrome_products(range: RangeInclusive<u64>) -> Option<(Palindrome, Palindrome)> {
    let products = iproduct!(range.clone(), range)
        .map(|(i, j)| Palindrome::new(i, j))
        .filter(|palindrome| palindrome.is_palindrome());

    Some((products.clone().min()?, products.clone().max()?))
}

fn process_smallest_case(input: RangeInclusive<u64>, expected: Option<Palindrome>) {
    let min = palindrome_products(input).map(|(min, _)| min);
    assert_eq!(min, expected);
}

Performance: use Itertools::minmax

Currently, you check if every number is a palindrome twice:

pub fn palindrome_products(range: RangeInclusive<u64>) -> Option<(Palindrome, Palindrome)> {
    let products = iproduct!(range.clone(), range)
        .map(|(i, j)| Palindrome::new(i, j))
        .filter(|palindrome| palindrome.is_palindrome());

    Some((products.clone().min()?, products.clone().max()?))
}

Instead, use:

pub fn palindrome_products(range: RangeInclusive<u64>) -> Option<(Palindrome, Palindrome)> {
    let products = iproduct!(range.clone(), range)
        .map(|(i, j)| Palindrome::new(i, j))
        .filter(|palindrome| palindrome.is_palindrome());
    match products.minmax() {
        MinMaxResult::NoElements => None,
        // You'll need to #[derive(Copy, Clone)] on Palindrome
        MinMaxResult::OneElement(p) => Some((p, p)),
        MinMaxResult::MinMax(min, max) => Some((min, max)),
    }
}

Alternatively, you could return a impl Iterator<Item = Palindrome> from palindrome_products and call .min() or .max() from process_smallest_case and process_largest_case respectively.

Embed tests

Put your tests in the same file, then gate them behind a

#[cfg(test)]
mod tests {
    // tests
}

Add benchmarks

I don't know how you're testing speed, but Rust doesn't optimize your code by default when running tests. Either use the unstable #[bench] attribute or my personal favorite Criterion. Both will automatically compile for optimization.

Final code

use std::cmp::Ordering;
use std::ops::RangeInclusive;

use itertools::iproduct;
use itertools::{Itertools, MinMaxResult};

#[derive(Copy, Clone, Debug, Eq, PartialOrd)]
pub struct Pair(u64, u64);

impl Ord for Pair {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value().cmp(&other.value())
    }
}

impl PartialEq for Pair {
    fn eq(&self, other: &Self) -> bool {
        self.value() == other.value()
    }
}

impl Pair {
    pub fn new(a: u64, b: u64) -> Pair {
        Pair(b, a)
    }

    pub fn value(&self) -> u64 {
        self.0 * self.1
    }

    pub fn insert(&mut self, a: u64, b: u64) {
        self.0 = a;
        self.1 = b;
    }

    pub fn is_palindrome(&self) -> bool {
        self.value() == reverse_number(self.value())
    }
}

fn reverse_number(mut n: u64) -> u64 {
    let radix = 10;
    let mut reversed = 0;

    while n != 0 {
        reversed = reversed * radix + n % radix;
        n /= radix;
    }

    reversed
}

pub fn palindrome_products(range: RangeInclusive<u64>) -> Option<(Pair, Pair)> {
    let products = iproduct!(range.clone(), range)
        .map(|(i, j)| Pair::new(i, j))
        .filter(Pair::is_palindrome);
    match products.minmax() {
        MinMaxResult::NoElements => None,
        MinMaxResult::OneElement(p) => Some((p, p)),
        MinMaxResult::MinMax(min, max) => Some((min, max)),
    }
}

#[cfg(test)]
mod tests {
    use std::ops::RangeInclusive;

    use super::{palindrome_products, Pair};

    fn process_smallest_case(input: RangeInclusive<u64>, expected: Option<Pair>) {
        let min = palindrome_products(input).map(|(min, _)| min);
        assert_eq!(min, expected);
    }

    /// Process a single test case for the property `largest`
    ///
    /// All cases for the `largest` property are implemented in terms of this function.
    ///
    fn process_largest_case(input: RangeInclusive<u64>, expected: Option<Pair>) {
        let max = palindrome_products(input).map(|(_, max)| max);
        assert_eq!(max, expected);
    }

    #[test]
    /// finds the smallest palindrome from single digit factors
    fn test_finds_the_smallest_palindrome_from_single_digit_factors() {
        process_smallest_case(1..=9, Some(Pair::new(1, 1)));
    }

    #[test]
    #[ignore]
    /// finds the largest palindrome from single digit factors
    fn test_finds_the_largest_palindrome_from_single_digit_factors() {
        let mut expect = Pair::new(1, 9);
        expect.insert(3, 3);
        process_largest_case(1..=9, Some(expect));
    }

    #[test]
    #[ignore]
    /// find the smallest palindrome from double digit factors
    fn test_find_the_smallest_palindrome_from_double_digit_factors() {
        process_smallest_case(10..=99, Some(Pair::new(11, 11)));
    }

    #[test]
    #[ignore]
    /// find the largest palindrome from double digit factors
    fn test_find_the_largest_palindrome_from_double_digit_factors() {
        process_largest_case(10..=99, Some(Pair::new(91, 99)));
    }

    #[test]
    #[ignore]
    /// find smallest palindrome from triple digit factors
    fn test_find_smallest_palindrome_from_triple_digit_factors() {
        process_smallest_case(100..=999, Some(Pair::new(101, 101)));
    }

    #[test]
    #[ignore]
    /// find the largest palindrome from triple digit factors
    fn test_find_the_largest_palindrome_from_triple_digit_factors() {
        process_largest_case(100..=999, Some(Pair::new(913, 993)));
    }

    #[test]
    #[ignore]
    /// find smallest palindrome from four digit factors
    fn test_find_smallest_palindrome_from_four_digit_factors() {
        process_smallest_case(1000..=9999, Some(Pair::new(1001, 1001)));
    }

    #[test]
    #[ignore]
    /// find the largest palindrome from four digit factors
    fn test_find_the_largest_palindrome_from_four_digit_factors() {
        process_largest_case(1000..=9999, Some(Pair::new(9901, 9999)));
    }

    #[test]
    #[ignore]
    /// empty result for smallest if no palindrome in the range
    fn test_empty_result_for_smallest_if_no_palindrome_in_the_range() {
        process_smallest_case(1002..=1003, None);
    }

    #[test]
    #[ignore]
    /// empty result for largest if no palindrome in the range
    fn test_empty_result_for_largest_if_no_palindrome_in_the_range() {
        process_largest_case(15..=15, None);
    }

    #[test]
    #[ignore]
    /// error result for smallest if min is more than max
    fn test_error_result_for_smallest_if_min_is_more_than_max() {
        process_smallest_case(10000..=1, None);
    }

    #[test]
    #[ignore]
    /// error result for largest if min is more than max
    fn test_error_result_for_largest_if_min_is_more_than_max() {
        process_largest_case(2..=1, None);
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Couldn't figure out where I am testing for palindrome twice? \$\endgroup\$ – GraphicalDot May 30 at 7:24
  • \$\begingroup\$ ''' filter(|palindrome| palindrome.is_palindrome());''' should be '''.filter(palindrome.is_palindrome);''' \$\endgroup\$ – GraphicalDot May 30 at 7:30
  • 1
    \$\begingroup\$ @GraphicalDot you were testing for palindromes twice because you were cloning the iterator and using it in min and max. Iterators are lazy, so they're evaluated when used—there's no temporary array created. So min would run through the entire iterator and find minimums, and max would run through it again (calling is_palindrome on every number a second time). As for filter, you can either use filter(|palindrome| palindrome.is_palindrome()) or filter(Pair::is_palindrome). filter(palindrome.is_palindrome) is not valid Rust (nor is it valid Java, JS, or C++, but it is in Go). \$\endgroup\$ – lights0123 May 30 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.