Palindrome products description mentions factors

Programming Rust
1

The description for palindrome products mentions (emphasis mine):

Your solution should return the largest and smallest palindromes, along with the factors of each within the range. If the largest or smallest palindrome has more than one pair of factors within the range, then return all the pairs.

However, the function signature is:

pub fn palindrome_products(min: u64, max: u64) -> Option<(Palindrome, Palindrome)>

The exercise does not require returning factors.

I’ll see if I can make a PR for it.

2

Many language tracks do require the factors be returned. For example, see F# or Ruby.

The exercise descriptions are shared across languages - see problem-specifications. We don’t make track-specific edits.

Some tracks append to the shared instructions. For example, see Python. It might make sense to create an instructions.append.md for Rust. (I am not a Rust maintainer.)

3

That’s fair enough. I’m not sure an append would be appropriate, and it would be possible to change the exercise to require factors, but that might be a very breaking change.

I’m starting to see why this wasn’t changed before…

I’ll wait for the Rust maintainer, and see what they recommend. In the meantime please ignore the PR.

4

The exercise was added 6 years ago and the description was synced with problem-specifictions 4 years ago, so the discrepancy has existed for a while. I think two options make sense:

  • bring the exercise in line with the description (breaking change)
  • instructions.append.md to explain the discrepancy as mentioned above

The main downside of breaking an exercise is that the community solutions for that exercise are invalidated and won’t be shown to users anymore. @ellnix would you like to check the community solutions if there are any that are interesting? (Just the top results for relevant sorting mechanisms, the ones people are likely to see.) If there aren’t any particularly interesting solutions, we might as well do a breaking change I think.

5

I’m not sure this would be a great idea, it doesn’t feel very professional.

I think this is the most interesting solution: flsilves's solution for Palindrome Products in Rust on Exercism. A similar one is here: textyash's solution for Palindrome Products in Rust on Exercism.

They operate on ranges of the smallest (min * min) and largest (max * max) possible product and find the first and last numbers that are palindromes with multiples inside the range. It’s similar to looping through a 2D array without nested loops.

I’m not aware of a more creative solution to this exercise, I racked my brains for quite a bit today trying to see if I could get the test suite to complete in less than 10s (on my admittedly bad laptop) since I felt like I was missing something.

There are some features of interest in the conventional solutions:

  • This loop to determine if a number is a palindrome:

        let mut reverse = 0;
    let mut r = value;
    while r > 0 {
        reverse = reverse * 10 + r % 10;
        r /= 10;
    }
    value == reverse

    which can also be found elsewhere, such as this geeksforgeeks c++ example.

  • The observation that multiples of 10 cannot be palindromes
    The top two community solutions both use this, either in their palindrome checking logic

        if value % 10 == 0 { return false };

    or more prematurely in the nested loop

    if i % 10 == 0 {
    continue;
}
// ...
     if j % 10 == 0 {
         continue;
     }

    However, this doesn’t really change the big O profile of the solution.

  • Keeping track of min and max outside of the loop, preferably using Option, this means avoiding the allocation of every palindrome in a vector and also the linear search in an unsorted vector. The space complexity is good but it doesn’t do anything for the time complexity.

6

I think published community solutions continue to appear even if they no longer pass the new tests.

Rust has roughly 1,200 completed solutions.

7

I’m not sure this would be a great idea, it doesn’t feel very professional.

More professional than just having incorrect instructions. Sometimes you gotta be pragmatic.

But I think we can do a breaking change here. The interesting solutions don’t do anything someone else isn’t gonna come up with for the new design.

I think published community solutions continue to appear even if they no longer pass the new tests.

Huh, that seems to be the case. I remember that solutions with failing tests would be hidden by default but there was a toggle to show them. I can’t find the toggle anymore and I can see failing solutions in the default view, so apparatly that got changed. Even more reason to do a breaking change.

@ellnix do you want to bring the exercise design in line with the instructions?

8

Sure, do you have any particular design considerations? It seems to be normal for returned collections in the Rust track to be Vecs, and I’m not sure they should be shoved inside the Palindrome struct since that would no longer conform to the newtype pattern (which this exercise seems to want to teach).

Perhaps a return type of Option<((Palindrome, Vec<u64>), (Palindrome, Vec<u64>))>? Looks a little bit silly.

In go it seems to be a lot more minimal:

package palindrome

// Define Product type here.

func Products(fmin, fmax int) (Product, Product, error) {
	panic("Please implement the Products function")
}

Swift has two different functions, I would prefer to keep only one to keep more of a challenge:

class PalindromeProducts {
  // Write your code for the 'PalindromeProducts' exercise in this file.

  static func largest(from: Int, to: Int) throws -> (value: Int?, factors: Set<[Int]>) {
  }

  static func smallest(from: Int, to: Int) throws -> (value: Int?, factors: Set<[Int]>) {
  }
}

C# is the same as Swift.

I think the best thing to do would be to forget about the newtype pattern and just shove a Vec inside Palindrome.

9

Yeah I’m fine with dropping the newtype from the design.

What about something like this:

struct Palindrome { /* todo students */ }

impl Palindrome {
    fn vaule() -> u64;
    fn factors() -> Vec<(u64, u64)>;
}

This would let students decide if they want to store the palindrome’s vaule explictly or compute it on-demand based on its factors.

10

I like it :+1:

I’ll make a PR when I get time.

11

PR is up:

Probably did stupid stuff, I’ll be around to implement feedback.

2 Likes