Project Euler Problem #4 - Palindromic number

The other answers are all giving you different ways to reorganize your loops. They're all not bad in their own way, but the better solution in C# is to not write any loops in the first place.

Your program could be written like this:

static void Main()
{
    var query = from first in ThreeDigitNumbers()
                from second in ThreeDigitNumbers()
                let product = first * second
                where IsPalindromicNumber(product)
                select product;
    Console.WriteLine(query.Max());
}

Notice how every part of this program reads like the specification of the problem. The problem is "give the maximum of the palindromic numbers that are formed as the product of two three-digit numbers", and clearly that's what this program does.

Writing helper methods IsPalindromicNumber and ThreeDigitNumbers is left as an exercise.

Now, once that program is written and correct, then is the time to start asking questions about whether it is sufficiently fast, and so on. We could notice for instance that we check both 113 x 115 and 115 x 113, even though they obviously have the same result. So we could then modify the query to

from second in ThreeDigitNumbersGreaterThan(first)

and then write that helper method. And so on.

(Exercise: Notice how introducing an optimization can introduce a bug if you're not careful. What bug did I just suggest that you write?)

But the takeaway here is write your program so that it looks like the specification. The specification does not say "write a bunch of loops". It says "find the maximum..." so there should be a call to Max in there somewhere. Write small methods that each do one thing well, and do exactly what they say on the tin.

The desire polyndromic number should be 6-digit number. We can show that this number is divisible on \$11\$ and use this fact to improve performance. \$P=100000x+10000y+1000z+100z+10y+x = 11(9091x+910y+100z)\$

This version is working in about 1000X faster than original one (measured by BenchmarkDotNet).

//Thanks to @Velial and @Denis
private static bool IsPalindromicNumber(int i) {
    string testNumber = Convert.ToString(i);
    for (int j = testNumber.Length / 2; j >= 0; j--) {
        if (testNumber[j] != testNumber[testNumber.Length - 1 - j]) {
            return false;
        }
    }
    return true;
}

[Benchmark]
public static string LargestPalindromeOriginal() {
    int test = 0;
    int left = 0;
    int right = 0;
    int biggestNumber = 0;
    int maxNumber = 999;
    for (left = maxNumber; left >= 99; left--) {
        for (right = maxNumber; right >= 99; right--) {
            test = left * right;
            if (IsPalindromicNumber(test)) {
                break;
            }
        }
        if (test <= biggestNumber) continue;
        biggestNumber = test;
    }
    return biggestNumber.ToString();
}

Almost every task in Euler project can be solved by slight-soft-brute-force. And this task is not an exception.

BTW I have completed this task long time ago without presented optimization. I found out it in the problem post-overview document.

I also made comparative analysis of all provided unique solutions.

@IvenBach (original)

[Benchmark]
public static string LargestPalindromeOriginal() {
    int test = 0;
    int left = 0;
    int right = 0;
    int biggestNumber = 0;
    int maxNumber = 999;
    for (left = maxNumber; left >= 99; left--) {
        for (right = maxNumber; right >= 99; right--) {
            test = left * right;
            if (IsPalindromicNumber(test)) {
                break;
            }
        }
        if (test <= biggestNumber) continue;
        biggestNumber = test;
    }
    return biggestNumber.ToString();
}

@Denis

[Benchmark]
public static string LargestPalindromeDenis() {
    int max = 0;
    for (int i = 100; i < 1000; i++) {
        for (int j = i + 1; j < 1000; j++) {
            int ij = i * j;
            if (max < ij && IsPalindromicNumber(ij)) {
                max = ij;
            }
        }
    }
    return max.ToString();
}

@Eric

[Benchmark]
public static string LargestPalindromeEric() {
    var query = from first in ThreeDigitNumbers()
                from second in ThreeDigitNumbers()
                let product = first * second
                where IsPalindromicNumber(product)
                select product;
    return query.Max().ToString();
}

private static IEnumerable<int> ThreeDigitNumbers() {
    for (int i = 100; i < 999; i++) {
        yield return i;
    }
}

And here are the results

                    Method |           Mean |        StdDev |         Median |
-------------------------- |--------------- |-------------- |--------------- |
 LargestPalindromeOriginal | 34,142.4309 us |   140.0219 us | 34,137.4766 us |
    LargestPalindromeDenis |  3,477.5650 us |    25.3361 us |  3,472.7747 us |
     LargestPalindromeEric | 79,561.3217 us | 2,772.4105 us | 78,526.1813 us |
      LargestPalindromePgs |     36.0029 us |     0.1324 us |     36.0501 us |

Log file can be found here

I'm going to guess that you're a C programmer by background, because of the way you've declared all of the variables at the top of the method. That's considered bad practice in most modern languages, because it obscures the scope of the variables. So the first refactor I would recommend is to declare the variables where they're first used, or in the enclosing scope if the first use is in too narrow a scope:

        int biggestNumber = 0;
        string returnString=string.Empty;
        for (int left=maxNumber; left >= 0; left--)
        {
            for(int right=maxNumber; right >= 0; right--)
            {
                int test = left * right;
                ...

There's a lot of unnecessary searching. Consider the additional constraints we can impose without affecting correctness*:

• left >= 100 and right >= 100 (as suggested in Velial's answer)
• right >= left (since multiplication is symmetric)
• right >= biggestNumber / left (since otherwise test < biggestNumber)

* Well, see next point

Ok, there is one issue with respect to affecting correctness.

            for(right=maxNumber; right >= 0; right--)
            {
                test = left * right;
                ...
                breakOut = ...;

                if (breakOut )
                {
                    break;
                }
            }

            if (test>biggestNumber)
            {
                biggestNumber = test;
                returnString = $"Palindrome: {test}, Left: {left}, Right: {right}";
            }

The correctness currently relies on the fact that if we don't break then when we hit the if (test>biggestNumber) we have test == 0 because of the loop termination condition. That's rather convoluted.

The logic for breaking out of the loop, which should really be explained in a comment somewhere, is that the largest palindrome over all (left, right) is at least as large as the largest palindrome for a given left, so having found that largest palindrome we don't need to consider the rest. So a better name (maybe not the best name) for breakOut would be testIsPalindrome, and then it becomes obvious that the if (test>biggestNumber) block should be inside the if (testIsPalindrome) block.

                string testNumberAsString = Convert.ToString(test);
                string reverse = string.Empty;
                for (int index = testNumberAsString.Length; index > 0; index--)
                {
                    reverse += testNumberAsString[index-1];
                }

It's debatable whether you should convert to a string to test for being a palindrome or just to a list of digits, but that's a minor issue. The bigger issue is that in C# strings are immutable, which means that += really allocates a new block of memory, copies across the lval's characters, and then copies across the rval. Rule of thumb: never use string + anything in a loop. Instead use the mutable string class System.Text.StringBuilder.

Incidentally, reversing a string is a lot more subtle than most people realise.

I'd like to suggest an alternative solution as your's looks over-complicated and it's hard to follow your logic.

My solution offers better performance, better readability and more OO look better code structure.

We can start by defining a function that determines whether a number is a palindrome or not:

public static bool IsPalindrome(string input)
{
    for (int i = 0; i <= input.Length / 2; i++)
    {
        if (input[i] != input[input.Length - 1 - i])
        {
            return false;
        }
    }
    return true;
}

With this our main logic becomes trivial:

private static void Main()
{
    int max = 0;
    for (int i = 100; i < 1000; i++)
    {
        for (int j = i + 1; j < 1000; j++)
        {
            if (max < i * j && IsPalindrome((i * j).ToString()))
            {
                max = i * j;
            }
        }
    }
    Console.WriteLine(max);
}

Your method can be improved at several points.

1. You can set a lower limit to 100 instead of 0 in for loops for left and right. In this way you can skip the check for length == 3 in breakOut.

2. Instead of creating a new string you can make a loop and check the char symmetrically in testNumberAsString. Also you need to process only half of the length of the string.

   public string GetPalindromeNumber(int maxNumber = 999)
   {
       bool breakOut = false;
       int test = 0;
       int left = 0;
       int right = 0;
       int biggestNumber = 0;
       string returnString = string.Empty;
   
       for (left = maxNumber; left >= 100; --left)
       {
           for (right = left; right >= 100; --right)
           {
               test = left * right;
   
               string testNumberAsString = Convert.ToString(test);
   
               breakOut = true;
   
               for (int index = testNumberAsString.Length - 1; index >= testNumberAsString.Length / 2; index--)
               {
                   if (testNumberAsString[index] != testNumberAsString[testNumberAsString.Length - 1 - index])
                   {
                       breakOut = false;
                       break;
                   }
               }
   
               if (breakOut)
               {
                   break;
               }
           }
   
           if (test > biggestNumber)
           {
               biggestNumber = test;
               returnString = $"Palindrome: {test}, Left: {left}, Right: {right}";
           }
       }
   
       return returnString;
   }
   

   }

Building on the point of limiting left and right to >=100, you could also try skipping all numbers which end in a zero. Unless you're defining numbers to have leading zeros, then 100 is a palindrome -> 00100.

Building on Eric's answer, the other question you will need to be asking when you get further with Project Euler is what is the best search strategy to minimize cost.

So while filtering the products of all three digits numbers by palindromes, then calculating the maximum of those values gives the correct result, exhaustive search isn't a principle that will scale. There are 900 three digit numbers, 810000 (non-distinct) products, but only 900 palindromes between 100001 and 999999.

So rather than changing the question to the one Eric answered ("From all the products of two 3-digit numbers, take all which are palindromes and find the largest") write code which answers the question "find the largest palindrome made from the product of two 3-digit numbers."

To do this, create a sequence of palindromes in descending magnitude and test whether each one is a product of two three digit numbers. It's easier to make a palindrome than test for one, and not excessively complex to test whether a six digit number is the product of two three digit numbers.

result = SixDigitPalindromes().Where(IsProductOfTwoThreeDigitNumbers).First();

You can create the palindromes easily using the yield operator and nested loops for the three digits. As you generate the palindromes in descending order, don't need to generate all the values, as the maximum will be first one found which satisfies the requirements.

It isn't easily obvious that this is a better search order - to test for a palindrome takes only a dozen arithmetic operations, to discover a pair of three digit factors could take hundreds - but as the search space is reduced by a factor of a thousand or so you end up with a better result ( or rather the same result in a fraction of the time ).

I posted a solution in C a few years ago here that uses a few more optimizations than pgs’. (I could rewrite it in C# as an exercise and make it more elegant.) You can read the source if you like, but here’s a description of the algorithm.

We’re looking for a six-digit number, because a product of two three-digit numbers must be less than 1,000×1,000 = 1,000,000. The basic approach is to generate the 900 six-digit palindromes, from 999,999 to 100,001, in descending order, and test whether each is a solution by attempting a factorization. Because we generate all palindromes in descending order, the first solution we find is the greatest. There is no need to search any further; that is our answer.

We can optimize the factorization by noticing that a six-digit palindrome abccba = 100001 a + 10010 b + 1100 c = 11 (9091 a + 910 b + 100 c). So if we have a six-digit palindrome p = xy, 11 is a prime factor of p, so 11 must be a factor of x or y. We can pick either to be the multiple of 11, so let’s choose x. The smallest three-digit multiple of 11 is 110 and the greatest is 990. The other factor y = p/x is between 100 and 999, so x = p/y is between p/999 and p/100. That gives us the following restrictions on x:

• 11|x
• 110 ≤ x ≤ 990
• p/999 ≤ x ≤ p/100

There are other conditions we can put on our values (for example, no prime greater than 999 can be a factor of p), but those are the ones that let us write a fast inner loop.

If there are integers x and y = p/x that meet these conditions, p = xy is our solution. I expressed this as a set of four nested loops: the three initial digits of the palindrome, plus the possible values of x. There are 900 possible palindromes and, for each one, fewer than 81 multiples of 11 in range to be candidates for x, making the search space tiny.