0
\$\begingroup\$

I think this is a good solution to finding the largest numeric palindrome that can be formed from the product of two 3-digit numbers... But it seems like there are some improvements that we could make which I haven't thought of...

Given int inputs[899] which is initialized by: iota(begin(inputs), end(inputs), 100), Do you guys have any thoughts on this code:

for(auto it = crbegin(inputs); it != crend(inputs) && *it * *it > max_product; ++it) {
    const auto rhs = find_if(it, crend(inputs), [lhs = *it](const auto rhs){
        const auto input = to_string(lhs * rhs);

        return equal(cbegin(input), next(cbegin(input), size(input) / 2U), crbegin(input));
    });

    if(crend(inputs) != rhs) {
        const auto product = *it * *rhs;

        if(product > max_product) {
            max_product = product;
            max[0] = *it;
            max[1] = *rhs;
        }
    }
}

Live Example

This will correctly find 993 and 913 as the pair of 3-digit numbers that would form the largest numeric palindrome.

\$\endgroup\$
  • \$\begingroup\$ @πάνταῥεῖ So I assume that you're asking for like a tag: programming-challenge perhaps? Maybe performance? Sorry I'm just not familiar with posting here. I thought this was on topic. \$\endgroup\$ – Jonathan Mee Jun 22 '18 at 18:13
  • 1
    \$\begingroup\$ SE Code Review doesn't need a MCVE as it is usual at Stack Overflow, but you still have to provide enough context to make your code reviewable in a reasonable way. Show how your function is used in that context, make clear what the inputs are, etc. \$\endgroup\$ – πάντα ῥεῖ Jun 22 '18 at 18:29
1
\$\begingroup\$

The main thing I'd suggest is to use functions more to break up your code into more clearly defined subtasks - especially if those subtasks are reusable.

For example, the lambda in your find_if() is:

[lhs = *it](const auto rhs){
    const auto input = to_string(lhs * rhs);

    return equal(cbegin(input), next(cbegin(input), size(input) / 2U), crbegin(input));
}

That would be clearer - and more maintainable and reusable - as:

[lhs](auto rhs){ return is_numeric_palindrome(lhs * rhs); }

Where is_numeric_palindrome() could be defined as:

auto is_numeric_palindrome(int value)
{
    auto const s = std::to_string(value);

    return is_palindrome(s.begin(), s.end());
}

The way you do the test right now can be neither constexpr nor noexcept, because you use to_string(), but we'll fix that shortly.

is_palindrome() is also an operation that could be reusable, and can be defined as:

// Need C++20 for constexpr std::equal()
// could possibly be noexcept, if only conditionally
template <typename BiDiIterator>
constexpr auto is_palindrome(BiDiIterator first, BiDiIterator last)
{
    return std::equal(//...
}

Once you have these functions written you can optimize them at your leisure. For example, you could go back to is_numeric_palindrome() and rewrite it as:

auto is_numeric_palindrome(int value, int base = 10) noexcept
{
    constexpr auto MAX_SIZE = // determine the max buffer size you need

    auto buffer = std::array<char, MAX_SIZE>{};

    auto res = std::to_chars(buffer.data(), buffer.data() + buffer.size(), value, base);

    return is_palindrome(buffer.data(), res.ptr);
}

That should make the whole algorithm quite a bit faster. And as a free side-effect/benefit, you can now check for palindromes in bases other than 10. (Technically you could do that with to_string(), too, I believe.)

And then after that you could devise a way to test if a number is a palindrome in any base without converting it to a string. You'd just need to rewrite is_numeric_palindrome() again. That might make your code even faster; you'd have to profile to be sure.

Moving on....

I think it would make your code more clear to use some better-named variables in the mix. For example, obviously-named variables like lhs and it_end could be defined right at the top of the loop like:

for(auto it = crbegin(inputs); it != crend(inputs) && *it * *it > max_product; ++it) {
    const auto lhs = *it;
    const auto it_end = crend(inputs);

    const auto it2 = find_if(it, it_end, [lhs](auto rhs){ return is_numeric_palindrome(lhs * rhs); });

    if(it2 != it_end) {
        const auto rhs = *it2;
        const auto product = lhs * rhs;

        if(product > max_product) {
            max_product = product;
            max[0] = lhs;
            max[1] = rhs;
        }
    }
}

I think that's much easier to read and mentally parse.

Now onto some more technical concerns....

You never bother to check that your multiplication doesn't overflow... and in fact, in your demo code it does overflow the minimum size of an int. An int is only guaranteed to hold from -32,767 to 32,767 inclusive... your final palindrome is 906,609. Everything probably works on your system because your ints are 32 or 64 bits, but you really should check these things in general. One easy way to do that is just to get the max value from your inputs, and divide numeric_limits<int>::max() by that, and make sure the result is greater than the divisor.

If you want to generalize this algorithm into its own function - which is a good idea - be sure to check whether the input data is sorted, and be sure to handle the situation where the input data sequence is empty (maybe by returning optional<tuple<int, int>>. And do checks to make sure the data is what you expect it to be (for example, no negative values).

\$\endgroup\$

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.