The Infection
Some days ago a friend of mine pointed me to the Project Euler site. It offers a lot of mathematical puzzles which can be solved either by mathematics or by writing a short computer program. And because I am not educated in mathematics well enough to solve the problems by pure mathematics the challenge for me is to find an elegant and efficient software solution.
When I started to solve my first problem I became immediately infected. The more familiar I got with the problem the more optimizations I did discover. And even so the web is yet full of information and discussions about published solutions (so far I resisted to read any solution up front because I fear to loss my interest in solving them) I still like to write about my way how I solved some of the problems and which kind of improvements I found.
Currently I do a lot of programming in Java and that's the reason why I will present my solutions in that language. Perhaps, if I find enough time to speed up learning Scala, I will present some of my solutions in Scala as well.
First Contact
The problem we start with is Problem No. 4:
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.
We will focus on finding an algorithm that reduces the number of required picks of products when searching the largest palindrome. We also strive to use not too much memory or processor time, calculating a product on the fly when making the decision to pick it.
Starting Very Simple (alpha)
The simplest way (I can imagine) to find the largest palindrome is to calculate the product of each possible pair (x, y) of two 3-digit numbers. We start with the largest x number (the upper bound) and pair it with each y number, beginning with the largest 
, and decrementing it after each pick, till we reach the smallest y number (the lower bound) 
. Than we decrement the x value and start over with the largest y value as before 
. For each pair we calculate the product and check if it is larger than the currently stored palindrome. If that is the case and the product is a palindrome as well 
, we store the new palindrome.
Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
for (int y = upperBound(); y >= lowerBound(); y--) {
long product = 1L * x * y;
if (palindrome.isLesser(product) && isPalindrome(product)) {
palindrome.setTo(product);
}
}
}
The type Palindrome does hold the current palindrome, in case we have found one, or the value 0 to indicate that we have not found one. The methods upperBound() and lowerBound() return the largest and smallest possible number for a given n-digit (3-digit in our case).The Palindrome.isLesser() method compares the value stored against the input parameter product. To calculate if a product is a palindrome is the responsibility of the method isPalindrome(). Finally when we find a greater palindrome than the one we do currently hold, we store it using the method Palindrome.setTo().
This algorithm requires 810.000 picks to find the largest 3-digit palindrome. We can do better!
Ignore Permutations (beta)
Approximately half of the pairs picked are permutations of the same x and y
numbers. This pairs do have the same product and therefore do not help in finding a larger
palindrome. This improvement can be achieved by choosing the x number as
starting value for y whenever decrementing x
.
Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
for (int y = x; y >= lowerBound(); y--) {
long product = 1L * x * y;
if (palindrome.isLesser(product) && isPalindrome(product)) {
palindrome.setTo(product);
}
}
}
We have reduced the required picks to find the largest 3-digit palindrome from 810.000 to 405.450. We still can do better!
Palindromes And Lesser Products (gamma)
While iterating down the y-axis each product we calculate is lesser than any product
of the same column calculated before. So when we find our first palindrome
we know that every pick on the same column can't be
larger than the palindrome just found. For the succeeding columns we can stop picking further
pairs when the first product calculated is lesser than or equal to the palindrome
.
Palindrome palindrome = Palindrome.createNullObject();
for (int x = upperBound(); x >= lowerBound(); x--) {
for (int y = x; y >= lowerBound(); y--) {
long product = 1L * x * y;
if (palindrome.isGreaterEqual(product)) {
break;
} else if (isPalindrome(product)) {
palindrome.setTo(product);
break;
}
}
}
We have added the method Palindrome.isGreaterEqual() to compare if the current palindrome is greater or equal than the input parameter product.
This is another huge improvement, reducing the required picks for finding the largest 3-digit palindrome from 405.450 to 7018. But we can do even better!
Think Diagonal (omega)
We discovered that large products do help in reducing the number of required picks. By iterating down the y-axis we decrease the product in each step by x. And because we start the algorithm with the largest x we decrease the product very fast. This can be improved by changing the iteration order from horizontal to diagonal. We just choose the two largest x and y numbers and increment x while decrement y till x is equal to the largest possible number (the upper bound) or y is equal to the smallest possible number (the lower bound). Than we decrement y if it is equal to x , otherwise we decrement x . This way the product decreases much slower.
Palindrome palindrome = Palindrome.createNullObject();
int startX = upperBound();
int startY = upperBound();
while (insideBoundaries(startX, startY)) {
for (int x = startX; int y = startY; insideBoundaries(x, y); x++, y--) {
long product = 1L * x * y;
if (palindrome.isGreaterEqual(product)) {
if (isDiagonalStart(x, y)) return;
else break;
} else if (isPalindrome(product)) {
palindrome = product;
break;
}
}
if (startX > startY) startX--;
else startY--;
}
The method insideBoundaries() returns true if both input parameter are neither less than the lowerBound() nor greater than the upperBound(), otherwise false. The method isDiagonalStart() returns true if the input parameter x is equal to startX and the input parameter y is equal to startY, otherwise false.
This change in the iteration order reduces the required picks for finding the largest 3-digit palindrome further from 7018 to 2251. But inspecting the Java program we notice that it starts to become more complex and harder to understand.
Some Analysis
Finally we can get an idea of how good the four different algorithms would scale relative to the total number of unique products for a given n-digit.
Finding the largest palindrome in the maximal matrix for a given n-digit is not only a matter of the used algorithm but also where the largest palindrome is found. To make the measurement more realistic we may try to calculate the average number of picks for a given n-digit as follows:
We execute one algorithm 9 times, reducing the upper bound of the matrix (the largest x and y values) by the lower bound after each execution. In each of this matrices we search for the largest palindrome. The sum of picks required in each run we divide by the number of total runs (9 in our case). This average number of required picks we divide by the number of available unique products for the given n-digit as a hint of the relative number of picks required to find the largest palindrome in an arbitrary matrix (we did not recalculated the available number of unique products for each reduced matrix because we are only interested in the growth and not exact graph).
As we can see algorithm gamma gave us the best improvement without making the algorithm to complex to understand or maintain. Algorithm omega still does much better compared to gamma but not compared to the total number of unique products. The average picks, given a 4-digit matrix, is 28626 for algorithm gamma and 5769 for algorithm omega. But the complexity of the program has grown as well.
That's it for now. For my next blog I am working on solving Problem No. 275
