2
\$\begingroup\$

I have made a simple C# script that will find the largest palindrome made by the product of two numbers. These numbers will be between a minimum and maximum value, inputted by int.Parse(Console.ReadLine()). Is there a way to make this better?

It is brute force, however I tried to make it use fewer numbers if one combination gives a smaller palindrome. The numbers are generated in a for loop.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

namespace ProjectEuler
{
    class Solution
    {
        static void Main( /*I am not sure what the point is for String args. If anybody can explain?*/ )
        {
            Console.Clear();
            Console.WriteLine("What would the maiximum value be for these numbers?");
            int max = int.Parse(Console.ReadLine());

            Console.WriteLine("\nWhat would the minimum value be for these numbers?");
            int min = int.Parse(Console.ReadLine());

            int largestNumb1 = 0;
            int largestNumb2 = 0;
            int generatedPalindrome = 0;

            for (int number1 = max; number1 >= min; number1--)
            {
                for (int number2 = max; number2 >= min; number2--)
                {
                    string generatedNumber = (number1 * number2).ToString();
                    if (IsPalindrome(generatedNumber))
                    {
                        if (int.Parse(generatedNumber) > generatedPalindrome)
                        {
                            generatedPalindrome = number1 * number2;
                            largestNumb1 = number1;
                            largestNumb2 = number2;
                            //This is mainly done to increase 'subtle' performance, by skipping numbers
                            //that will never give a larger number than the previous palindrome
                            number1--;
                            number2 = max;
                        }
                        else if (int.Parse(generatedNumber) < generatedPalindrome)
                        {
                            //This is mainly done to increase 'subtle' performance, by skipping numbers
                            //that will never give a larger number than the previous palindrome
                            number1--;
                            number2 = max;
                        }
                    }
                }
            }
            PrintAnswer(generatedPalindrome, largestNumb1, largestNumb2);
        }

        static bool IsPalindrome(string generatedNumber)
        {
            char[] answerChar = generatedNumber.ToCharArray();
            Array.Reverse(answerChar);
            string reversedString = new string(answerChar);

            if (generatedNumber == reversedString)
            {
                return true;
            }
            else
            {
                return false;
            }

        }

        static void PrintAnswer(int generatedPalindrome, int largestNumb1, int largestNumb2)
        {
            Console.Clear();
            if (generatedPalindrome != 0)
            {
                Console.WriteLine("Largest possible palindrome given limit: {0}\nNumbers used: {1} & {2}", generatedPalindrome, largestNumb1, largestNumb2);
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("Sorry, but no valid palindrome was generated given your values.\nWould you like to try again? (y)");
                if (Console.ReadLine() == "y")
                {
                    Main();
                }
                else
                {
                    return;
                }
            }
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

For getting integers (or any other data that needs to be validated) from the user, sometimes it's best to create a separate function that you can call. For example:

static int GetIntFromUser(string prompt)
{
    int input;

    while (true)
    {
        if (prompt != null) Console.Write(prompt);
        if (int.TryParse(Console.ReadLine(), out input)) break;
        Console.WriteLine("Sorry, {0} is not a valid integer. Please try again.", input);
    }

    return input;
}

Then you can use it like:

int max = GetIntFromUser("Enter the maximum value for these numbers: ");
int min = GetIntFromUser("Enter the minimum value for these numbers: "); 
\$\endgroup\$
4
  • \$\begingroup\$ Ah, Ok. But isn't this a bit more complicated then Int.TryParse ? \$\endgroup\$ Jan 14 '15 at 10:20
  • \$\begingroup\$ Complicated? Not to me. This is how I use int.TryParse (note the second if statement). What less complicated thing will you do if int.TryParse fails? The nice thing here is, you only have to write this code once. Then you can call it any time you need an int from the user, and you know the result will be an int. \$\endgroup\$
    – Rufus L
    Jan 14 '15 at 10:36
  • \$\begingroup\$ Ahh, I didn't know this loops until you give a valid integer. Thank you (I was wondering what the while loop was for ;) ). May i ask one more thing (please)? I need the user to give a min and max value. How do I make a function return two values like the function your provided? \$\endgroup\$ Jan 14 '15 at 10:38
  • \$\begingroup\$ Just call it a second time with something like: int min = GetIntFromUser("Enter the minimum value for these numbers: "); It's very similar to what you have already, but adds the error handling if the user doesn't enter a valid int. \$\endgroup\$
    – Rufus L
    Jan 14 '15 at 10:40
3
\$\begingroup\$

Your IsPalindrome method is inefficient. It's unnecessary to reverse the char array and compare with the origin. You need one pointer starting from the head and another pointer going from the tail of the array, when arr[head] doesn't equal to arr[tail], you breaks the loop and return false, which means the number is not a palindrome.

And some more polishing things:

  1. The code will not check the input of the user, "abc" will make the application crash because int.Parse throws an exception.

  2. It confuses a lot if you change the value of the looping variables (number1 & number2) inside the loop. Since a * b = b * a, you can make number2 loops from number1 ~ min.

\$\endgroup\$
4
  • \$\begingroup\$ How would I check if int.Parse throws an exception? \$\endgroup\$ Jan 14 '15 at 8:56
  • \$\begingroup\$ If the parse can fail, use int.TryParse(string, out int) \$\endgroup\$
    – RobH
    Jan 14 '15 at 9:29
  • \$\begingroup\$ Ahh, K. Lastly, could you explain on your step 2, on how a *b == b * a? \$\endgroup\$ Jan 14 '15 at 11:06
  • \$\begingroup\$ @AhkamNihardeen: "a *b=b *a" means if you tried 5*2 in the loop, it's unnecessary to try 2*5 again in the loop. So you can loop number2 from min to number1, so number2 is always less than number1. \$\endgroup\$
    – Cheng Chen
    Jan 15 '15 at 2:54
2
\$\begingroup\$

One improvement, the inner loop doesn't need to check with values already used(10 * 3 == 3 * 10). Start the inner loop from number1-1:

for (int number2 = number1 - 1; number2 >= min; number2--)

Checking for largest palindrome can be much simpler using a temporary variable. And as was mentioned reversing a char array is less efficient than checking the digits from each end:

static long largestPalindrome(int max, int min, out int num1, out int num2)
{
    int i = max;
    int j = 0;
    min--;
    long largestPalindrome = 0;
    long result = 0;
    num1 = 0;
    num2 = 0;
    //If you look at the inner loop, j starts at i-1. This way the inner loop doesn't look
    // at combinations that have already been looked at. By declaring the loop variable 
    //outside the loop you can use the variable after the loop is finished, if necessary.
    // This also means that you don't need to declare it inside the loop and that portion
    // can stay empty.
    for (; i > min; i--)
    {
        for (j = i - 1; j > min; j--)
        {
            result = j * i;
            if (result < largestPalindrome)
            {
                break;
            }
            if (isPalindrome(result) && result > largestPalindrome)
            {
                largestPalindrome = result;
                num1 = i;
                num2 = j;
            }
        }
    }

    return largestPalindrome;
}
static bool isPalindrome(long num)
{
    //This function will loop through half the string comparing each digit in the front 
    //half with the corresponding digit in the back half, and exit if they're not equal.
    //Since this loops through only half the digits, this is more efficient than 
    //`Array.Reverse`, since that loops through all the digits.
    //Side note:  Even or odd number of digits is handled correctly.
    var temp = num.ToString();
    int limit = temp.Length / 2;
    int lastIndex = temp.Length-1;
    for(int i = 0; i < limit;i++)
    {
        if(temp[i] != temp[lastIndex - i])
        {
            return false;
        }
    }
    return true;
}

I am not sure what the point is for String args. If anybody can explain?

Those are to accept command line arguments.

\$\endgroup\$
4
  • \$\begingroup\$ It would be smarter to extract temp.Length-1 to a variable inside isPalindrome() \$\endgroup\$
    – Heslacher
    Jan 14 '15 at 7:37
  • \$\begingroup\$ SO looking through each letter in the string and see if it is the same is quicker than reversing and checking that way? \$\endgroup\$ Jan 14 '15 at 8:49
  • \$\begingroup\$ I understand the idea that 10*3 == 3*10, but I don't understand how you did it. I am confused to what you did, could you explain in a bit more detail, like why you didn't put some stuff before the ; tag? Also, wouldn't it just be simpler to divide the max + min input by 2? Then, you could make number one start on max, and stop when it reaches that value? Similarly, make number 2 start on that number, and keep going down until it reaches the min? \$\endgroup\$ Jan 14 '15 at 8:54
  • \$\begingroup\$ @AhkamNihardeen - I added more explanation. \$\endgroup\$
    – user33306
    Jan 14 '15 at 16:33

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.