Project Euler - Problem 4: Largest Palindrome Product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

---

Explanation:

Loop over all numbers in the range of 100-999 twice to get a product that will then be checked to see if it is a palindrome.

Solution #1:

My initial solution was the conversion of the explanation to code (using the explanation as pseudo code - brilliant!). I came up with something like this:

public static void Main(string[] args)
{
 long startTimeTicks = DateTime.Now.Ticks;

 int maxProduct = 0;
 for(int i = 999; i > 100; i--)
 {
  for(int j = 999; j > 100; j--)
  {
   int product = i * j;
 
   if(IsPalindrome(product) && product > maxProduct)
   {
    maxProduct = product;
   }
  }
 }
 Console.WriteLine(maxProduct);

 long endTimeTicks = DateTime.Now.Ticks;
 Console.WriteLine("Took {0} ticks", endTimeTicks - startTimeTicks);
}

private static bool IsPalindrome(int product)
{
 return int.Parse(new string(product.ToString().Reverse().ToArray())) == product;
}

A online sample of which can be found here.

I am not too fond how this one requires a linq command - as they are not very efficient. It also is bad that we are taking the int converting it to a string, reversing it - which returns an Enumeration of char so we convert it to a char array and then put it back in a string and parse it back to an int. Talk about a highly inefficient process - not to mention the readability is lost. This may explain the high 500000 to mid 600000 ticks I was getting. We are also repeating products a lot since the loops overlap quite a bit - but probably not noticeable. Let's see if we can improve this.

A more inefficient way to do this would be to separate the product.ToString().ToCharArray() into a variable and then use the Array.Reverse() on that variable before casting it back to a string. This is the worst kind of boxing/unboxing (converting between types) possible and I saw entries in the millions of ticks. But it does technically get the job done.

Solution #2:

The second solution will remove the number of products we generate. We can assign j to the value of i in the loop because we will have already generated the product for those numbers when i was a greater number. We can also break out of the j for loop when the product is less than the maxProduct we currently have because any numbers generated after this number will only get lower and lower. It ends up looking something like this:

public static void Main(string[] args)
{
 long startTimeTicks = DateTime.Now.Ticks;

 int maxProduct = 0;
 for(int i = 999; i > 100; i--)
 {
  for(int j = i; j > 100; j--)
  {
   int product = i * j;

   if(product < maxProduct)
   {
    break;
   }
 
   if(IsPalindrome(product) && product > maxProduct)
   {
    maxProduct = product;
   }
  }
 }
 Console.WriteLine(maxProduct);

 long endTimeTicks = DateTime.Now.Ticks;
 Console.WriteLine("Took {0} ticks", endTimeTicks - startTimeTicks);
}

private static bool IsPalindrome(int product)
{
 return int.Parse(new string(product.ToString().Reverse().ToArray())) == product;
}

A online sample of which can be found here.

Surprisingly, this gives us quite a bit of an improvement. My average runs were now typically less than 500000 ticks! I would not have normally expected that. Now let's see if we can improve our integer reversing and bring this home!

Solution #3:

The last way we care going to improve this is to create a reverse function to return an integer instead of unboxing all over the place that the current linq method requires. I think this will give us the most noticeable improvement. We are going to do this by some clever math. We can reverse an integer by taking the product modulus ten and adding it to our new reversed integer. This will give us the value in the new tens place. We then divide the product by 10 to move the pointer over a spot - and since it is an integer everything after the pointer (decimal in this case) gets dropped. While this product number is greater than 0 we will move our new integer up a pointer position (or moving the decimal the other way) by multiplying it by ten. Since integers are copied by value to new methods we don't have to worry about creating a new placeholder, although they could. It eventually works out to something like this:

public static void Main(string[] args)
{
 long startTimeTicks = DateTime.Now.Ticks;

 int maxProduct = 0;
 for(int i = 999; i > 100; i--)
 {
  for(int j = i; j > 100; j--)
  {
   int product = i * j;

   if(product < maxProduct)
   {
    break;
   }
 
   if(IsPalindrome(product) && product > maxProduct)
   {
    maxProduct = product;
   }
  }
 }
 Console.WriteLine(maxProduct);

 long endTimeTicks = DateTime.Now.Ticks;
 Console.WriteLine("Took {0} ticks", endTimeTicks - startTimeTicks);
}

private static bool IsPalindrome(int product)
{
 return ReverseInt(product) == product;
}

private static int ReverseInt(int toReverse)
{
 int reverse = 0;
 while(toReverse > 0)
 {
  reverse = reverse * 10 + (toReverse % 10);
  toReverse /= 10;
 }
 return reverse;
}

A sample of which can be found here.

I was surprised that this did not give as much of a performance gain if any at all! Perhaps there are some compiler optimizations done that make the linq method form just as good if not better. I was averaging ticks in the low 400000.

Conclusion:

Surprisingly, the best performance increase seen came from changing the loops and breaking out as soon as possible so less comparisons were done. I wonder what the impact would be if we were to remove that change and keep the integer magic - would it be comparable to the initial method? Granted there are other factors that must be considered when looking at ticks, such as how busy the CPU on the machine is, whether it's remote, what the specs of that machine are. I still like to use them to get a general idea of the improvements that are made.

Let me know your thoughts in the comments!