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);
}
}
IntUtilis
or at lest the function you use here and maybe theStringUtils
too? ;-) \$\endgroup\$Main
method since the programs are all self-contained/single files. \$\endgroup\$