Functional Practice: Euler Problem #4 in F# - Palindromes

In continuing to practice my F#, I'm moving forward with the problems from Project Euler. Last time, I took on Euler Problem #3 which involved calculating prime factors. This time, we'll look at Euler Problem #4 which involves palindromes.

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.

As before, we'll try to replicate the sample solution and then apply it to the target.

[Update: Collected articles for the first 10 Euler Problems in F# are available here: Jeremy Explores Functional Programming.]

Finding Palindromes the Hard Way
I figured that a good first step would be to try to identify palindrome numbers: numbers that are the same both forward and backward.

I seriously overthought this. I was thinking about how I would handle it imperatively. I would convert the number to a string and then compare the first character to the last character, and then figure out how to do the math to compare the other characters heading toward the middle of the string.

The Easy Way
Then I had a thought that made things blindingly obvious. If you take the reverse of the string, it will be the same as the original. So rather than comparing individual characters, we could just compare the whole string.

It seems so obvious now, but it took my brain a bit of mulling before it settled on it.

Here's the function to check if a number is a palindrome (this shows the code from the script file and the output from the F# Interactive window):

This first converts the integer to a string by using the sprintf function. Since a string is a sequence (which we can think of as IEnumerable from the C# world), we can convert this to a list with the toList function.

And the reason why we want a list is because list has a "rev" function that reverses the elements. The last line compares the original list to the reversed list. If they are the same, then we have a palindrome number.

Let's check some values:

And we can see that the true/false values come back as expected: "9009" is true, "17" is false, and "202" is true.

Brute Force Again
To replicate the sample, I decided to take the brute force approach (again). The set of 2 digit numbers is not too large -- just the values between 10 and 99. I decided to come up with a way to multiply all the possible combinations.

This is a bit of a kludge, but it works. (And as they say, if it's stupid and it works, then it ain't stupid.)

This takes a list of numbers (from 10 to 99) and then maps a function across them. This does another map with the same numbers (from 10 to 99) and outputs the product of 2 values.

The result is a list of lists.

As an example, let's say that our list is [1..3] (the values 1, 2, and 3). If we run this function, then we would get 3 lists: [1*1, 1*2, 1*3], [2*1, 2*2, 2*3], and [3*1, 3*2, 3*3]. This ends up looking like this: [[1, 2, 3][2, 4, 6][3, 6, 9]]

When we use our full set [10..99], we end up with 90 lists all with 90 elements each. This holds all the possible values of multiplying two 2-digit numbers together.

Flattening the Lists
We really only want to deal with one list, so we'll combine these together. This is as simple as using the "concat" function:

Now, we have a single list with all 810 of the values.

Getting the Palindromes
Now we can filter the list using the "isPalindrome" function that we created above:

No we can see that all of the values read the same forward and backward: 121, 242, 363, etc.

Largest Palindrome
The last step is to get the largest value from our filtered list. We can just use "max" for that:

This gives us our sample number of 9009. Success!

Getting the Solution
Now we can take our code that works with 2-digit numbers and try it with 3-digit numbers:

This gives us the solution of 906609. We can verify this is the correct answer by checking other solutions online.

Creating a Function
So let's put our code together to create a function called "maxPalindrome":

This creates "isPalindrome" as a local function. The rest of the code is the same, and our solution is still accurate.

Which 3-Digit Numbers?
This gives us the answer of what the largest palindrome is based on the multiplication of two 3-digit numbers. But it doesn't tell us which two numbers will produce the product. How can we find that?

It turns out that we have all of the information in our original method, we just don't hang onto it. Instead of returning an integer with the multiplication result, we'll return a tuple that contains the result and both operands.

Tuple in the Map
Let's start wit the "map" functions. instead of returning just "x * y", we'll return that, plus the values "x" and "y":

Now we have the result (such as "124000") and the operands that make up that number ("100" and "124").

Tuple in the Filter
We'll have to update the filter as well. For this we'll use a bit of pattern matching:

Notice that the function inside our filter now takes a tuple with three elements: a, b, and c. We just care about the "a" value here (the result), and that's the value we pass to "isPalindrome".

And when we look at the output, we see that the results are all palindromes: 10201, 11211, 12221, etc.).

Tuple in the Max
We'll also need to use the tuple when we look for the maximum value. For this, we'll swap out "max" for "maxBy":

We can't simply use "max" because our tuple doesn't have a clearly defined way to compare it to other tuples. If we use "maxBy", we pass in a function for calculating the maximum value. In this case, we use pattern matching on our tuple and pick out the "a" value (our multiplication result).

Since the entire tuple is returned, we can see all of the values in the output. Our palindrome result is "906609" and we get this by multiplying "913" and "993". (Feel free to verify the multiplication if you don't trust me.)

If we check the timing, this takes a little over 1 second to complete. I'm okay with that performance in this case. There is probably a way to get it to run faster by using some math tricks.

Combining Two Functions
This looks like quite a few steps. I did a bit of exploration of the "List" functions to see if there was some way to combine these steps.

In doing so, I ran across the "collect" function. Let's compare the old and new function calls:

The "collect" function lets us apply a function (just like "map") and then concatenates the results (just like "concat").

I didn't make up this code myself (with the "for..in" code). Instead, I took this from an example that showed how to get a Cartesian result from multiplying two sets (which is exactly what we want here). I modified the code a little so that it would return our tuple.

Here's our final method:

This gives us the solution to Euler Problem #4: the largest palindrome from multiplying two 3-digit numbers is "906609". And we get that by multiplying "913" and "993".

Wrap Up
I've done a little searching online, and I've found a different way of reversing the string. But I think that this code is more readable.

In addition, I found a way to get the Cartesian product of our two sets. Instead of using a "collect", it uses a recursive function and peels off the head of each list. I need to get more comfortable with that type of code, so I'll be investigating that a bit more.

I'll keep practicing with F#. With each new exercise, I'm learning something new. This is definitely helping me get more comfortable with the language.

Happy Coding!