Creative Scratchpad

It's a new day and that means it's time for another problem to solve; lo and behold, problem No. 4 is here:

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.

How do we identify a palindrome? The first thing that comes in mind is to reverse the number, for example by converting it to string first and reversing that, and check if is the same as before. The usual way of doing it is to iterate the string backwards and add the individual letters to an empty string.

fn reverseStr str =
(
    local reversed = ""
    for i in str.count to 1 by -1 do
        reversed += str[i]
    reversed
)

As stated in the helpfile, this creates intermediate strings in the process and if we compare heapFree before and after running it we can confirm that using append is a little bit better in this regard.

fn reverseStr str =
(
    local reversed = ""
    for i in str.count to 1 by -1 do
        append reversed str[i]
    reversed
)

Switching to a stringStream method is on par with the string method both in regards of speed and memory.

fn reverseStr str =
(
    local reversed = stringStream ""
    for i in str.count to 1 by -1 do
        format str[i] to:reversed
    reversed as string
)

But what if we operated on the string in place instead of using a new variable, be it a stringStream or a string? We can try that, by iterating over half of the string (for odd numbers the middle component will stay the same so we can safely do an integer division here) and checking the values to corresponding values counted from the end. The expression for that, str.count-(i-1) is here written in its expanded form, str.count-i+1. Note that the cost of declaring a new variable to hold the str.count value would beat the possible speed gain by not accessing the property in every iteration (mind you, there will be only three iterations) so we're just accessing it directly.

fn reverseStr str =
(
    for i = 1 to (str.count/2) do
        swap str[i] str[str.count-i+1]
    str
)

That's cool and all but do we really need to do the double type-casting, something along the lines of (i as string) == reverseStr (i as string) to check if the number is a palindrome? Why not just do the comparison in place as well and stop comparing when the two chars differ?

fn isPalindrome str =
(
    local palindromic = true
    for i = 1 to (str.count/2) while palindromic do
        palindromic = str[i] == str[str.count-i+1]
    palindromic
)

Okay, this looks promising; let's try to make another function to make use of this one and see if we can improve it further on. Even though it's not the task here, let's make it reusable again, just for the fun of it. First, we need a list of n-digit numbers. That's easy enough, for three digits it would be 100..999 or 10^2..10^3-1. In general it's #{10^(digits-1)..(10^digits-1)}. The maximum product possible is then obtained by multiplying the maximum values, hence list.count^2 and the smallest possible palindrome from the range by multiplying the minimum range values, i.e. 10^(digits-1)*10^(digits-1) or in short 10^(digits+digits-2).

Now we have the boundaries and we can start iterating over the range. As we look for the largest one, we iterate from the biggest values down, checking if the value is a palindrome and, if so, taking the vaues from list and trying to identify if it could be divided by any of them without remainder. Then if all these conditions are met we check if the result of the division can be found in the range we work with. If that's the case we're done.

fn largestPalindromeProduct digits =
(
    local list = #{10^(digits-1)..(10^digits-1)}
    local maximum = list.count^2
    local minimum = 10^(digits+digits-2) + 1

    for i = maximum to minimum by -1
        where isPalindrome (i as string) do
            for item in list
                where mod i item == 0 AND
                list[i/item] do
                    return i
)

It might seem that the line for item in list could be better done iterating backwards as well. However, before reaching the right solution we would be testing the others for all the values in the list anyway in search for all the proper divisors so the difference in execution time is minuscule.

Yet it's slow and sluggish. There must be a way to improve it, palindrome numbers sure have some properties that we can use, right? Yes, they do, it turns out that all palindromes with an even number of digits are divisible by 11. With the premise that there'll be at least one 2n-digit palindrome evenly divisible by two n-digit numbers we can implement it in our function. The only change is that the maximum range value gets corrected by substracting the remainder after division by 11 and the step is now 11.

fn isPalindrome str =
(
    local palindromic = true
    for i = 1 to (str.count/2) while palindromic do
        palindromic = str[i] == str[str.count-i+1]
    palindromic
)

fn largestPalindromeProduct digits =
(
    local list = #{10^(digits-1)..(10^digits-1)}
    local maximum = list.count^2
    maximum -= int(mod maximum 11)
    local minimum = 10^(digits+digits-2) + 1

    for i = maximum to minimum by -11
        where isPalindrome (i as string) do
            for item in list
                where mod i item == 0 AND
                list[i/item] do
                    return i
)

largestPalindromeProduct 3

And that's it, we're done for today.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.