17
\$\begingroup\$

The problem is as follows:

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.

Using Project Euler to stretch my C# learning, I solved problem #4 with the code below. I ran this in a console app to get the answer. How can I improve my code?

class PalindromNumber
{
    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 >= 0; left--)
        {
            for(right=maxNumber; right >= 0; right--)
            {
                test = left * right;

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

                breakOut = (testNumberAsString == reverse && Convert.ToString(left).Length == 3 && Convert.ToString(right).Length == 3);

                if (breakOut )
                {
                    break;
                }
            }

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

        return returnString;
    }
}
\$\endgroup\$
33
\$\begingroup\$

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.

\$\endgroup\$
  • 12
    \$\begingroup\$ 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. That reasoning doesn't seem to make much sense to me. Why not use loops? They are common across almost any language and easily recognizable, not to mention the added performance benefits of looping over using LINQ or other abstracted enumerations. Why should it have a call to Max? Just like it didn't say "write a bunch of loops" it also did not say "Max a call to Max()". \$\endgroup\$ – Douglas Gaskell Apr 19 '17 at 17:12
  • 5
    \$\begingroup\$ @DouglasGaskell: computer programming is the art of building and composing abstractions. If you already have a debugged, tested abstraction for "compute the maximum of a set" and your job is to find the maximum of a set, then use the abstraction. \$\endgroup\$ – Eric Lippert Apr 19 '17 at 17:50
  • 11
    \$\begingroup\$ @DouglasGaskell: Now as for "performance benefits" -- those benefits have to be measured against many other competing optimization problems. The largest cost of software development is often the time it takes to write, test, debug, maintain and modify the code, so optimize for that. Once the code is correct, understandable and maintainable then you are starting from a position of strength when you do the empirical engineering work that is necessary to determine if performance is adequate. \$\endgroup\$ – Eric Lippert Apr 19 '17 at 17:52
  • 4
    \$\begingroup\$ @pgs: 78,526 μs is less than 1/10th of a second; is that not acceptable performance for a one-time solution? Project Euler (and this site) is mainly about helping beginners learn a new language. By far the most important thing for beginners to learn is how to write clean, readable code, not how to write fast code. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Apr 19 '17 at 21:52
  • 10
    \$\begingroup\$ @pgs: Absolutely: learning to approach performance as a customer-focussed engineering discipline is very important for beginners. That will prevent them from making the common beginner mistake of believing that expensive micro-scale optimizations that are invisible to users but make their code harder to write, read, and maintain, is a good idea. \$\endgroup\$ – Eric Lippert Apr 19 '17 at 22:40
10
\$\begingroup\$

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;
    }
}

@Divislor

[Benchmark]
public static string LargestPalindromeDavislor() => 
    LargestPalindromeDavislorImpl().First(HasFactors).ToString();
private static IEnumerable<Int32> LargestPalindromeDavislorImpl() {
    for (Int32 a = 9; a >= 1; --a)
        for (Int32 b = 9; b >= 0; --b)
            for (Int32 c = 9; c >= 0; --c)
                yield return a * 100001 + b * 10010 + c * 1100;
}
private static bool HasFactors(Int32 p) {
    Int32 lower1 = (p / 999 + 10) / 11,
        lower = Math.Max(10, lower1);
    Int32 upper1 = p / 1100,
          upper = Math.Min(90, upper1);
    Int32 count = Math.Max(upper - lower + 1, 0);
    return Enumerable.Range(lower, count).Any(x => p % x == 0);
}

@Divislor (Fastest)

[Benchmark]
public static string LargestPalindromeDavislor2() => 
    LargestPalindromeDavislorImpl().First(p => XCandidates(p).Any(x => p % x == 0)).ToString();

private static IEnumerable<int> XCandidates(int p) {
    int q = p / 11;
    int lower = Math.Max(10, (q + (999 - 1)) / 999);
    int upper = Math.Min(90, q / 100);
    int k = q % 6;

    if (k == 1 || k == 5) {
        int r = lower % 6;
        bool mod1 = r <= 1;
        int i = lower - r + (mod1 ? 1 : 5);

        while (i <= upper) {
            yield return i;
            i += mod1 ? 4 : 2;
            mod1 = !mod1;
        }
    } else if (k == 2 || k == 4) {
        int r = lower % 6;
        int m = (r == 3 || r == 0) ? r + 1 : r;
        int i = lower - r + m;
        while (i <= upper) {
            yield return i;
            if (m == 5) {
                i += 2;
                m = 1;
            } else if (m == 2) {
                i += 2;
                m = 4;
            } else {
                ++i;
                ++m;
            }
        }
    } else if (k == 3) {
        int i = lower + 1 - lower % 2;
        while (i <= upper) {
            yield return i;
            i += 2;
        }
    } else {
        for (int i = lower; i <= upper; ++i)
            yield return i;
    }
}

Log file can be found here

                     Method |           Mean |        StdDev |         Median |
--------------------------- |--------------- |-------------- |--------------- |
  LargestPalindromeOriginal | 33,322.0311 us |   271.1871 us | 33,298.1558 us |
     LargestPalindromeDenis |  3,547.6625 us |    59.1731 us |  3,538.8128 us |
      LargestPalindromeEric | 79,636.8086 us | 1,029.9705 us | 79,615.3664 us |
       LargestPalindromePgs |     34.9557 us |     0.6435 us |     34.8254 us |
  LargestPalindromeDavislor |      7.3468 us |     0.1378 us |      7.3217 us |
 LargestPalindromeDavislor2 |      5.2548 us |     0.0622 us |      5.2729 us |
\$\endgroup\$
  • 1
    \$\begingroup\$ How does mine stack up? \$\endgroup\$ – Davislor Apr 20 '17 at 6:34
  • \$\begingroup\$ @Davislor: I included your solution. Up to now it's the best one. Good idea, I should accept. \$\endgroup\$ – pgs Apr 20 '17 at 9:42
  • 1
    \$\begingroup\$ Added a more-optimized solution to my post. \$\endgroup\$ – Davislor Apr 21 '17 at 5:19
  • \$\begingroup\$ @t3chb0t: On my computer (8threads are 100% busy) it takes 4 times more time than Eric' solution. \$\endgroup\$ – pgs Apr 21 '17 at 20:31
  • 1
    \$\begingroup\$ @pgs: you can find it here. \$\endgroup\$ – pgs Apr 21 '17 at 20:47
8
\$\begingroup\$

Edit: There are two solutions in C# below, a short one in the middle and a more-optimized one at the end.

I posted a solution in C a few years ago here that uses a few more optimizations than pgs’. (Now rewritten in C# below, in a more functional style.) 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 ≤ xp/100

If an x meets all of these conditions, our p is the product of two three-digit numbers. 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.

The Code

I’m new to C#, so I’d appreciate a code review myself.

using System;
using System.Collections.Generic;
using System.Linq;

static class Euler4 {
  static public bool hasFactors(Int32 p)
  {
    // Find candidates for x such that p = 11*x*y, where x is an integer
    // between 10 and 90, and y is an integer between 100 and 999.  Any
    // pair of three-digit factors will decompose into 11*x and y.

    // Use the greater lower bound that makes y <= 999 and 11*x >= 100.
    Int32 lower = Math.Max((p/11+998)/999, 10);
    // Use the lesser upper bound that makes y >= 100 and 11*x <= 999.
    Int32 upper = Math.Min(p/(100*11), 90);
    // Calculate the extent of the range:
    Int32 count = Math.Max(upper-lower+1, 0);

    return Enumerable.Range(lower, count).Any(x => p%x == 0);
  } 


  static public IEnumerable<Int32> listPalindromes()
  // Generates a lazily-evaluated list of palindromes in descending order.
  {
    for (Int32 a = 9; a >= 1; --a )
      for (Int32 b = 9; b >= 0; --b )
        for (Int32 c = 9; c >= 0; --c )
          yield return a*100001 + b*10010 + c*1100;
  }

  // The solution to Euler problem 4:
  static public readonly Int32 answer = listPalindromes().First(hasFactors);

  static public void Main()
  {
    Console.WriteLine(answer);
  }
};

Generalizing the Problem

Peter Taylor mentioned he was benchmarking my algorithm for finding eight-digit and ten-digit palindromic numbers. It would therefore be polite for me to prove that it actually works: that is, that any palindromic number whose length is even is a multiple of 11. (It does not work for odd lengths: all palindromes 101, 10001, 1000001, ... are congruent to 2, mod 11.) I’m sure I’m not the first person to do this and that he already knew it was valid.

Theorem: Any palindrome whose length n is even is a multiple of 11.

Basis case: Any two-digit palindrome (00, 11, 22, ...) is a digit times 11.

Inductive step: Suppose any palindrome of length n-2 is a multiple of 11.

Any palindrome of length n consists of a palindrome of length n-2 enclosed by a pair of identical digits. (For example, 1221 is 22 surrounded by 1s.) This can be written as (1+10ⁿ⁻¹) a + 10 b, where a is a digit and b is a palindrome of length n-2. For example, 321123 = (1+10⁶⁻¹)·3 + 10·2112.

Because n is even, n-1 is odd. We know 10 ≡ -1 (mod 11), so 1+10ⁿ⁻¹ ≡ 1+(-1)ⁿ⁻¹ ≡ 1-1 ≡ 0 (mod 11). Our inductive hypothesis tells us that b is also a multiple of 11, and therefore so is 10·b. Our n-digit palindrome is the sum of two multiples of 11, so it is a multiple of 11 itself. ∎

Other Optimizations

There is some more low-hanging fruit that could be picked here.

The best one is that it’s easy to test whether our palindrome p is odd or even. Any product of an even number is even, so if p is odd, both of its factors must be odd too. Dividing by another prime like 11 keeps the parity, and therefore, when p is odd, we only need to check the odd candidates for x. That cuts the search space in half, half the time, for a savings of 25%.

This generalizes to other primes than 2: p = xy is divisible by some prime q if and only if x or y are divisible by q. We could use the Chinese Remainder Theorem to test several prime factors at once: a number is divisible by 2 if and only if it is congruent to 0, 2 or 4 mod 6, and divisible by 3 if and only if it is congruent to 0 or 3 mod 6, so we can take r = p mod 6. If r is 1 or 5, then x mod 6 must be 1 or 5 as well. If r is 2 or 4, then x mod 6 cannot be 0 or 3. If r is 3, x mod 6 cannot be 0, 2 or 4. That reduces the search space by two-thirds one-third of the time, one-third another third of the time and one-half another sixth of the time, pruning the search space by a total of 5/12, or 41.6%. We could extend this to 2, 3, and 5 by going modulo 30, with severely increasing complexity and diminishing returns.

Second Solution

This solution uses the optimization from the previous section. It might not actually be faster. For example, on some machines, the work to skip checking some values of x might take longer than just doing the trial divisions.

using System;
using System.Collections.Generic;
using System.Linq;

static class Euler4 {
  static public bool hasFactors(int p)
  {
    return xCandidates(p).Any(x => p%x == 0);
  }

  static public IEnumerable<int> listPalindromes()
  // Generates a lazily-evaluated list of palindromes in descending order.
  {
    for (int a = 9; a >= 1; --a )
      for (int b = 9; b >= 0; --b )
        for (int c = 9; c >= 0; --c )
          yield return a*100001 + b*10010 + c*1100;
  }

  static public IEnumerable<int> xCandidates(int p)
  // Generate a lazily-evaluated list of potential values of x such that
  // p == 11*x*y, and both 11*x and y are between 100 and 999.
  {
    int q = p/11; // All palindromes of even length are multiples of 11.
    // The greatest lower bound on x such that 11*x >= 100 and y <= 999.
    int lower = Math.Max(10, (q+(999-1))/999);
    // The least upper bound on x such that 11*x <= 999 and y >= 100.
    int upper = Math.Min(90, q/100);
    int k = q%6;

    if (k == 1 || k == 5) {
      // Neither 2 nor 3 is a factor of z.
      // The possible values of x%6 are 1 and 5.
      int r = lower%6;
      bool mod1 = r <= 1;
      int i = lower - r + (mod1 ? 1 : 5);

      while (i <= upper) {
        yield return i;
        i += mod1 ? 4 : 2;
        mod1 = !mod1;
      } // end while
    } else if (k == 2 || k == 4) {
      // 3 cannot be a factor of x.
      // The possible values of x%6 are 1, 2, 4 and 5.
      int r = lower%6;
      int m = (r == 3 || r == 0) ? r+1 : r;
      int i = lower - r + m;

      while (i <= upper) {
        yield return i;
        if (m == 5) {
          i += 2;
          m = 1;
        } else if ( m == 2) {
          i += 2;
          m = 4;
        } else { // m == 1 || m == 4
          ++i;
          ++m;
        } // end if
      } // end while
    } else if (k == 3) {
      // 2 cannot be a factor of x.
      // The possible values of x%6 are 1, 3 and 5.
      int i = lower + 1 - lower%2;

      while (i <= upper) {
        yield return i;
        i += 2;
      } // end while
    } else { // k == 0.  Because y%6 could be 0, x%6 can be anything.
      for ( int i = lower; i <= upper; ++i )
        yield return i;
    } // end if
  }

  // The solution to Euler problem 4:
  static public readonly int answer = listPalindromes().First(hasFactors);

  static public void Main()
  {
    Console.WriteLine(answer);
  }
};
\$\endgroup\$
  • \$\begingroup\$ And, wrote that code sample now. \$\endgroup\$ – Davislor Apr 20 '17 at 6:25
  • \$\begingroup\$ Last(hasFactors) doesn't search from the end: it searches from the start, discarding the previous solution when it finds a later one. You want Reverse().First(hasFactors). \$\endgroup\$ – Peter Taylor Apr 20 '17 at 7:25
  • 1
    \$\begingroup\$ @RobH, you're looking at the wrong Last. It's line 986 and it has no special cases. Davislor, calling ToArray effectively removes the laziness, but so does Reverse(); however, since Last with predicate doesn't have any special casing for arrays there's no benefit. If you want efficiency then the way to do it is to write your own Range which supports counting down. \$\endgroup\$ – Peter Taylor Apr 20 '17 at 8:15
  • 1
    \$\begingroup\$ Added a more-optimized solution. \$\endgroup\$ – Davislor Apr 21 '17 at 5:18
  • 2
    \$\begingroup\$ @PeteKirkham This was my first post to Code Review, so I don’t know the community well. I think writing that was a great learning exercise for myself, and I hope it illustrates some useful approaches to problems, but if people here aren’t looking for posts like this, there are other sites. \$\endgroup\$ – Davislor Apr 21 '17 at 17:11
6
\$\begingroup\$

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.


Since everyone's posting competing versions of the final code, after refactoring I end up with

    public static int GreatestPalindrome(int minNumber, int maxNumber)
    {
        long biggestNumber = 0;
        for (int left = maxNumber; left >= minNumber; left--)
        {
            for (int right = maxNumber; right >= left; right--)
            {
                var test = left * right;
                if (test < biggestNumber) break;
                if (IsPalindrome(test)) biggestNumber = test;
            }
        }

        return biggestNumber;
    }

called as GreatestPalindrome(100, 999). The body of the if (IsPalindrome(test)) block could break;, but the next iteration of the loop will do that anyway. If I were really interested in microoptimising I'd expland the scope of test and replace the multiplication with a subtraction, but pace the impression some people seem to have, microoptimising wasn't the goal of my review.

\$\endgroup\$
  • \$\begingroup\$ I think variables at the start of a method is a Pascal thing. I vaguely remember long methods with thirty variables of which less than half were actually used :( \$\endgroup\$ – JollyJoker Apr 19 '17 at 13:01
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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 ).

\$\endgroup\$
5
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Just wait... you're the next one who'll receive comments about how much your solution sucks and how slow it is etc even though there is no performance tag :-P \$\endgroup\$ – t3chb0t Apr 19 '17 at 14:30
  • \$\begingroup\$ @t3chb0t It should be a lot faster than OP solution :( \$\endgroup\$ – Denis Apr 19 '17 at 14:34
  • \$\begingroup\$ It doesn't matter, mine was too ;-] \$\endgroup\$ – t3chb0t Apr 19 '17 at 14:36
  • 2
    \$\begingroup\$ @t3chb0t, I didn't say that your solution sucked, just that it was slow, and the reason I said that was that you claimed it was fast. Similarly this one: it claims to have better performance but throws away the sensible optimisations in OP's code. What's the point in optimising the palindrome check if you make the code perform thousands of additional palindrome checks? As for "more OO look"... \$\endgroup\$ – Peter Taylor Apr 19 '17 at 14:49
  • 1
    \$\begingroup\$ @PeterTaylor Thanks for your comment, for such a simple task where there are no classes or any hierarchy involved the only thing I can think of that can make the code more OO is dividing the code into smaller methods by following the SRP. As for performance I claimed that mine is faster because that's what my result show. \$\endgroup\$ – Denis Apr 19 '17 at 14:56
3
\$\begingroup\$

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;
    }
    

    }

\$\endgroup\$
  • 1
    \$\begingroup\$ You can also avoid testing about half the products as a * b == b * a, so count right down from left instead of maxNumber. \$\endgroup\$ – Pete Kirkham Apr 19 '17 at 15:06
  • \$\begingroup\$ You are right. I have been updated my answer. \$\endgroup\$ – Velial Apr 19 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.