Project Euler 4: Largest palindrome product

Question

This solves Project Euler 4: Largest palindrome product using C# (specifically, using LINQPad). Any and all suggestions for improvements to either the C# code or the math/algorithm are very welcome.

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.

The code finds the answer to the 2-digit test case in about 3ms, and the 3-digit test case in about 250ms. The additional 4-digit test takes about 27 seconds so it is kind of slow.

I tried to find a mathematical solution to palindromes, but since the problem is lexical in nature, I had to resort to string manipulation. I wrote an extension method or two that I used in this problem...

IntUtils

public static class IntUtils
{ 
 // Equivalent to Math.Pow(long) for int type.
 public static int Pow(int baseNum, int exponent)
 {
 if (exponent == 0) { return 1; }
 else if (exponent == 1) { return baseNum; }
 else 
 {
 while (exponent > 1)
 {
 baseNum *= baseNum;
 exponent--;
 }
 }
 return baseNum;
 }
 // Check if a number is palindrome, i.e., reads the same backward or forward.
 public static bool IsPalindrome(int number)
 {
 string lexicalNumber = number.ToString();
 return lexicalNumber.Equals(StringUtils.Reverse(lexicalNumber)); 
}

StringUtils

public class StringUtils
{
 public static string Reverse(string s)
 {
 // Source: http://stackoverflow.com/a/228060/3626537
 char[] chars = s.ToCharArray();
 Array.Reverse(chars);
 return new string(chars);
 }
}

The solution code:

// ProjectEuler4: Largest palindrome product
// https://projecteuler.net/problem=4
void Main()
{
 Console.WriteLine("ProjectEuler4: Largest palindrome product");
 // this is the test case from the original statement/problem
 // it should return Palindrome: 9009 | firstFactor: 99 | secondFactor: 91
 int numDigits;
 numDigits = 2;
 ProjectEuler4 PE4_2dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_2dig.GetAnswer());
 // this is the challenge
 numDigits = 3;
 ProjectEuler4 PE4_3dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_3dig.GetAnswer());
 // another test with 4 digits, for performance
 numDigits = 4;
 ProjectEuler4 PE4_4dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_4dig.GetAnswer());
}
public class ProjectEuler4 
{
 private int numberOfDigits;
 // Constructor
 public ProjectEuler4(int numberOfDigits)
 {
 this.numberOfDigits = numberOfDigits;
 }
 // Get the minimum and maximum values of possible numbers considering the number of digits requested.
 private int[] GetMinAndMax()
 {
 int min = 1;
 int max = 1;
 int[] minAndMax = new int[2];
 for (int i = numberOfDigits; i > 1; i--)
 {
 min *= 10;
 }
 max = (min * 10) - 1;
 minAndMax[0] = min;
 minAndMax[1] = max;
 return minAndMax;
 }
 // Generate a list of all possible palindromes based on the array generated by PossibleFactors()
 private List<int> FindAllPalindromes(int[] minAndMax)
 {
 List<int> allPalindromes = new List<int>();
 for (int minNum = IntUtils.Pow(minAndMax[0], 2), maxNum = IntUtils.Pow(minAndMax[1], 2); 
 minNum <= maxNum; 
 minNum++)
 {
 if (IntUtils.IsPalindrome(minNum))
 {
 allPalindromes.Add(minNum);
 }
 }
 return allPalindromes;
 }
 // Iterate the list of allPalindromes starting with the largest, 
 // and returns the first instance of a palindrome number having both factors within the possibleFactors array.
 private int FindLargestPalindromeProduct(int[] minAndMax, List<int> allPalindromes)
 {
 int firstFactor = minAndMax[1];
 int secondFactor;
 int floor = minAndMax[0];
 int ceiling = minAndMax[1];
 int result = 0;
 //reverse the list to start with largest palindrome
 allPalindromes.Reverse();
 while (result == 0)
 {
 for (int ix = 0, n = allPalindromes[ix]; 
 ix < allPalindromes.Count;
 ix++, n = allPalindromes[ix])
 {
 for (int i = firstFactor; i > 0; i--)
 {
 if (n % i == 0)
 {
 secondFactor = n / i;
 if (secondFactor >= floor && secondFactor <= ceiling)
 {
 Console.WriteLine("Palindrome: {2} | firstFactor: {0} | secondFactor: {1}", i, secondFactor, n);
 result = n;
 return result;
 }
 }
 }
 }
 }
 return result;
 }
 // Get the answer to the problem.
 internal int GetAnswer()
 {
 int[] minAndMax = GetMinAndMax();
 List<int> allPalindromes = FindAllPalindromes(minAndMax);
 return FindLargestPalindromeProduct(minAndMax, allPalindromes);
 }
}

• t3chb0t: Could you also post the IntUtilis or at lest the function you use here and maybe the StringUtils too? ;-)
• Phrancis: @t3chb0t done and done
• psfinaki: Main is static, right?
• Phrancis: @psfinaki not in this case, it doesn't look like LINQPad needs a static Main method since the programs are all self-contained/single files.

Answer 1

CurrentCode

Ascertaining whether or not a number is a palindrome seems slow. The code

1. Converts from number to string
2. Reverses the string
3. Creates a new string
4. Compares the two strings

Once the we have converted the number to a string we can just use an Is the string a Palindrome routine to check. In some quick tests it took about 2/3 of the time.

private static bool IsPalindrome(int number)
{
 string lexicalNumber = number.ToString();
 int start = 0;
 int end = lexicalNumber.Length-1;
 while(start < end)
 {
 if(lexicalNumber[start++] != lexicalNumber[end--])
 {
 return false;
 }
 }
 return true;
}

IntUtils.Pow seems like overkill.

for (int minNum = (minAndMax[0] * minAndMax[0]), maxNum = (minAndMax[1] * minAndMax[1]); minNum <= maxNum; minNum++)

does the same job with a lot less clutter.

We wish to examine the palindromes in descending order and stop when we reach the first with valid factors. By returning the values in a List<int> we are checking all the numbers in the range and adding them to the list before we do the first test. This is where yield comes in:

private static IEnumerable<int> GetPalindromes(int min, int max)
{
 for(var value = (max * max); value >=(min*min); value--)
 {
 if (IsPalindrome(value))
 {
 yield return value;
 }
 }
}

By using yield and by not having to reverse the list we get an order of magnitude (13 ms vs 150 ms in my tests) improvement in time. The processing is now

FOR EACH NUMBER IN THE RANGE (DESCENDING)
- Check to see if the number is a palindrome
- Check to set if it has valid factors
- Stop if success
END

rather than

FOR EACH NUMBER IN THE RANGE (DESCENDING)
- Check to see if the number is a palindrome
END

FOR EACH NUMBER IN THE RANGE (DESCENDING)
- Check to set if has valid factors
- Stop if success
END

NOTE: Having to use Reverse() kills any benefits from yield as the whole Enumerable needs to be evaluated before we can start using it, so changing the generation order is very important.

Performance

With these changes I am getting the following timings

Found 9999, 9901 => 99000099 in 182 ms 
Found 993, 913 => 906609 in 13 ms

Approach

Instead of

1. Testing all numbers in the allowed range to see if they are palindromes
2. Finding the factors for each of these

We might approach it by generating the palindromes in each

e.g.

If we are trying the 3 digit version, we can generate the possible palindromes and test each

999 => 999999
998 => 998899
...

We can check the factors for each of these, starting at maxValue (999) and stopping at the square root of the plaindrome - because once we pass this point, we should have already found the pair of factors (We imply the square root by checking if factor2> factor1 because I believe this to be faster but it may not be)

private static int[] FindPalindromeFactors(int min, int max)
{
 int lhs = max;
 while (lhs> 0)
 {
 var palindrome = BuildPalindrome(lhs--);
 for (int factor1 = max; factor1 >= min; factor1--)
 {
 var factor2 = palindrome / factor1;
 if (factor2 > max || (factor2 > factor1) )
 {
 break;
 }
 if ((palindrome % factor1) == 0)
 {
 return new int []{ factor1, factor2 };
 }
 }
 }
 return null;
}
private static int BuildPalindrome(int lhs)
{
 var str = lhs.ToString(CultureInfo.InvariantCulture);
 return Convert.ToInt32(str + new string(str.Reverse().ToArray()));
}

Performance

With this approach I am getting the following timings

Found 993, 913 => 906609 in 2 ms
Found 9999, 9901 => 99000099 in 0 ms

Presumable, the 4 digit version is so fast because it only needs to check 100 possibilities 9999 -> 9000 and only needs to find the factors for these 100 numbers where

Answer 2

@AlanT mentioned really good points. The change of the algorithm should drastically increase the performance.

However, the Main function is left alone, let's try to improve it.

Add some space

 public static void Main()
 {
 Console.WriteLine("ProjectEuler4: Largest palindrome product");
 // this is the test case from the original statement/problem
 // it should return Palindrome: 9009 | firstFactor: 99 | secondFactor: 91
 int numDigits;
 numDigits = 2;
 ProjectEuler4 PE4_2dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_2dig.GetAnswer());
 // this is the challenge
 numDigits = 3;
 ProjectEuler4 PE4_3dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_3dig.GetAnswer());
 // another test with 4 digits, for performance
 numDigits = 4;
 ProjectEuler4 PE4_4dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_4dig.GetAnswer());
 }

Init vars together with declaring

 public static void Main()
 {
 Console.WriteLine("ProjectEuler4: Largest palindrome product");
 // this is the test case from the original statement/problem
 // it should return Palindrome: 9009 | firstFactor: 99 | secondFactor: 91
 int numDigits = 2;
 ProjectEuler4 PE4_2dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_2dig.GetAnswer());
 // this is the challenge
 numDigits = 3;
 ProjectEuler4 PE4_3dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_3dig.GetAnswer());
 // another test with 4 digits, for performance
 numDigits = 4;
 ProjectEuler4 PE4_4dig = new ProjectEuler4(numDigits);
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, PE4_4dig.GetAnswer());
 }

Notice repeating code & extract it

 public static void Main()
 {
 Console.WriteLine("ProjectEuler4: Largest palindrome product");
 // this is the test case from the original statement/problem
 // it should return Palindrome: 9009 | firstFactor: 99 | secondFactor: 91
 var numDigits = 2;
 var answer = GetPESolution(numDigits);
 WriteResult(numDigits, answer);
 // this is the challenge
 numDigits = 3;
 answer = GetPESolution(numDigits);
 WriteResult(numDigits, answer);
 // another test with 4 digits, for performance
 numDigits = 4;
 answer = GetPESolution(numDigits);
 WriteResult(numDigits, answer);
 }
 private static int GetPESolution(int numDigits)
 {
 var pe = new ProjectEuler4(numDigits);
 var answer = pe.GetAnswer();
 return answer;
 }
 private static void WriteResult(int numDigits, int answer)
 {
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, answer);
 }

At this stage the code is readable. Along the way, we got rid of the ugly var names like PE4_3dig.

Now, we can further refactor it to have something like...

 // ProjectEuler4: Largest palindrome product
 // https://projecteuler.net/problem=4
 public static void Main()
 {
 Console.WriteLine("ProjectEuler4: Largest palindrome product");
 // this is the test case from the original statement/problem
 // it should return Palindrome: 9009 | firstFactor: 99 | secondFactor: 91
 TestPE(2);
 // this is the challenge
 TestPE(3);
 // another test with 4 digits, for performance
 TestPE(4);
 }
 private static void TestPE(int numDigits)
 {
 var answer = GetPESolution(numDigits);
 WriteResult(numDigits, answer);
 }
 private static int GetPESolution(int numDigits)
 {
 var pe = new ProjectEuler4(numDigits);
 var answer = pe.GetAnswer();
 return answer;
 }
 private static void WriteResult(int numDigits, int answer)
 {
 Console.WriteLine("The largest palindrome product of {0}-digit numbers is: {1}", numDigits, answer);
 }

But I insist on...

Transform it to tests

You yourself call it test case in a comment. You should end up with methods like

 [TestMethod]
 public void OriginalProblem()
 {
 var numDigits = 2;
 var expected = 9009;
 var actual = PE4.GetPESolution(numDigits);
 Assert.AreEqual(expected, actual);
 }

---

Side notes

1. If you still want to have console output, you should have it in one place, as now it is scattered.

2. You do not need to add a comment above every function. I.e.

    // Get the minimum and maximum values of possible numbers considering the number of digits requested.
    private int[] GetMinAndMax()
   

   Here, the method name is good enough. Notice, however, that the comment is misleading a bit, the method does not really request any number of digits (as it has no parameters), it somehow has it already. Also, would you remember to modify the comment if you modify the method, e.g. start returning only max here?

3. And you definetely do not need this comment:

   // Constructor
   public ProjectEuler4(int numberOfDigits)
   

   Well, everybody should understand this is a constuctor.

   Actually, of all your comments I would at best leave only comments in the Main method and a SO link. Really, the names you have given to the methods are fine, good job.

4. Consider using this keyword whenever applicable, it usually increases readability.

• t3chb0t: 4. I strongly discourage the usage of this. I has the exact opposite effect.

Answer 3

I'm finding your code very hard to follow. Let me describe to you how I'd solve this problem.

First, state the problem. We want the largest of all products of two 3-digit numbers that are palindromes.

Let's start with all products of two 3-digit numbers:

static IEnumerable<int> Products()
{
 for (int i = 100; i < 1000; ++i)
 for (int j = i; j < 1000; ++j)
 yield return i * j;
}

Now we have all the products. But we want only the products that are palindromes:

var palindromes = Products().Where(p => IsPalindrome(p));

Exercise: implement IsPalindrome efficiently.

We want the biggest of them:

var answer = palindromes.Max();

And we're done. Not only is this solution about ten total lines of code, each line is obviously correct.

My advice to you is: raise the level of abstraction of your code. If you want to get the largest of a set of things, there should be a line of code in there that says largest = things.Max();. Is there a concept mentioned in the problem statement? Then find or make a function that implements that concept. Your code will get a lot easier to follow.

In fact we can even eliminate the initial loops and reduce the whole thing to just one query:

 var palindromes = from i in Enumerable.Range(100, 900)
 from j in Enumerable.Range(i, 900 - i) 
 let p = i * j
 where IsPalindrome(p)
 select p;
 Console.WriteLine(palindromes.Max());

Notice how compact and how plainly correct this code is.

• t3chb0t: Unfortunately this solution is incomplete because you also need to know which two numbers build the palindrome ;-) instead of a simple int you could return a struct or an anonyous object containing i and j there is also no room for optimizations (if there are mathematically any).
• Eric Lippert: @t3chb0t: the problem statement is "Find the largest palindrome made from the product of two 3-digit numbers." Where in there does it say that you need the factors?
• Eric Lippert: @t3chb0t: Of course there is room for optimizations! Let's start with: no numbers which end in a zero are palindromes: from i in Enumerable.Range(100, 900) where i % 10 != 0 from j in Enumerable.Range(i, 900 - i) where j % 10 != 0 let p = i * j where p % 10 != 0 ..., BOOM, optimization. There is plenty of room for optimizations here.