Sunday, October 30, 2016

Next Largest Integer Palindrome

Language: C#
Problem: 
Given an inputted integer return the next largest value that is a palindrome.

///<title>NextPalindromeProgram</title> 
///<description>This program outputs the next largest integer palindrome given a 32 bit positive integer with two or more digits.</description>
///<copyright>Copyright(C) 2016</copyright>
///<author>Gabriel McFann</author>
///
/// <license>
///This program is free software: you can redistribute it and/or modify
///it under the terms of the GNU General Public License as published by
///the Free Software Foundation, either version 3 of the License, or
///(at your option) any later version.
///</license>
///<warranty>
///This program is distributed in the hope that it will be useful,
///but WITHOUT ANY WARRANTY; without even the implied warranty of
///MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
///GNU General Public License for more details.
///</warranty>
///You should have received a copy of the GNU General Public License
///along with this program.If not, see<http://www.gnu.org/licenses/>.
using System;
using System.Text;

namespace NextPalindromeNamespace
{
    public class NextPalindromeProgram
    {
        static void Main(string[] args)
        {
            new NextPalindromeProgram().run();
        }

        /// <summary>
        /// Non-static method to run the program.
        /// </summary>
        private void run()
        {
            int num = 0;
            char[] numCharArray = { };
            char[] originalFirstHalf = { };
            char[] originalSecondHalf = { };
            char[] newSecondHalf = { };
            int middleDigit = 0;
            int nextPalindrome = 0;

            string input = "";
            Console.WriteLine("NextPalindromeProgram  Copyright (C) 2016  Gabriel McFann");
            Console.Write(licensePrompt);
            Console.WriteLine("---------------------NEXT LARGEST PALINDROME---------------------");

            //Main loop to get User input
            do
            {
                //User Instructions
                Console.WriteLine("Input a positive 32 bit number with two or more digits.");
                Console.WriteLine("Type exit to exit.");
                Console.Write(": ");
                input = Console.ReadLine();
                int.TryParse(input, out num);

                if (input.Trim().ToLower() == "show w")
                {
                    Console.Write(warrantyInfo);
                }

                if (input.Trim().ToLower() == "show c")
                {
                    Console.Write(copyrightInfo);
                }

                if (num > 9)
                {
                    //Convert String to Char [] so as to deal with each digit individually.
                    numCharArray = num.ToString().ToCharArray();

                    //Create Halves of array
                    createArrayHalves(numCharArray, ref originalFirstHalf, ref newSecondHalf, ref originalSecondHalf);

                    //Check if we have an even number of digits.
                    //If we don't we'll have to deal with a middle digit.
                    if (numCharArray.Length % 2 == 0)
                    {
                        nextPalindrome = GetPalindromFromEvenNumOfChars(num, originalFirstHalf, newSecondHalf, originalFirstHalf.Length - 1);
                    }
                    else
                    {
                        middleDigit = int.Parse(numCharArray[numCharArray.Length / 2].ToString()); //Integer Division
                        nextPalindrome = GetPalindromFromOddNumOfChars(num, originalFirstHalf, newSecondHalf, middleDigit, originalFirstHalf.Length - 1);
                    }
                    //Check to see if the nextPalindrome is 0
                    //If the program has gotten this far this means that the number couldn't fit into a 32 bit number.
                    if (nextPalindrome == 0)
                    {
                        Console.WriteLine("Next largest Palindrome is too large to fit in a 32 bit number.");

                    }
                    else
                    {
                        Console.WriteLine("Next largest Palindrome: {0}", nextPalindrome);
                    }
                }
            } while (input.Trim().ToLower() != "exit");
        }

        /// <summary>
        /// Gets the Next Palindrome given an array with an even length.
        /// </summary>
        /// <param name="num" />The user inputted value.
        /// <param name="firstHalf" />First half of the array as an array
        /// <param name="newSecondHalf" />The new second half of the array as an array
        /// <param name="lastToFirstIndex" />The index of the last element in the firstHalf array
        /// <returns></returns>
        private int GetPalindromFromEvenNumOfChars(int num, char[] firstHalf, char[] newSecondHalf, int lastToFirstIndex)
        {
            int firstToLastIndex = 0;
            int nextPalindrome = 0;
            int.TryParse(GetStringFromCharArray(firstHalf) + GetStringFromCharArray(newSecondHalf), out nextPalindrome);
            while (nextPalindrome <= num)
            {
                calculateNextDigits(ref firstHalf, ref newSecondHalf, lastToFirstIndex, firstToLastIndex);
                firstToLastIndex++;
                lastToFirstIndex--;
                int.TryParse(GetStringFromCharArray(firstHalf) + GetStringFromCharArray(newSecondHalf), out nextPalindrome);
                if (lastToFirstIndex < 0) { break; }
            }
            return nextPalindrome;
        }

        /// <summary>
        /// Gets the Next Palindrome given an array with an odd length.
        /// </summary>
        /// <param name="num" />The user inputted value.
        /// <param name="firstHalf" />First half of the array as an array
        /// <param name="newSecondHalf" />The new second half of the array as an array
        /// <param name="middledigit" />The middle digit that would fit in between the even length arrays firstHalf and newSecondhalf.
        /// <param name="lastToFirstIndex" />The index of the last element in the firstHalf array
        /// <returns></returns>
        private int GetPalindromFromOddNumOfChars(int num, char[] firstHalf, char[] newSecondHalf, int middledigit, int lastToFirstIndex)
        {
            int firstToLastIndex = 0;
            bool incrementMidPoint = true;
            int nextPalindrome = 0;
            int.TryParse(GetStringFromCharArray(firstHalf) + middledigit + GetStringFromCharArray(newSecondHalf), out nextPalindrome);

            while (nextPalindrome <= num)
            {
                if (incrementMidPoint)
                {
                    middledigit = (middledigit + 1) % 10; //We only want to deal with the "1s" place. If the middelDigit is nine we want to wrap it back around to 0.
                    incrementMidPoint = false;

                }
                else
                {
                    calculateNextDigits(ref firstHalf, ref newSecondHalf, lastToFirstIndex, firstToLastIndex);
                    firstToLastIndex++;
                    lastToFirstIndex--;
                }
                int.TryParse(GetStringFromCharArray(firstHalf) + middledigit + GetStringFromCharArray(newSecondHalf), out nextPalindrome);
                if (lastToFirstIndex < 0) { break; }
            }
            return nextPalindrome;
        }

        /// <summary>
        /// Increments the value in the char arrays at the given indecies.
        /// </summary>
        /// <param name="firstHalf" />The reference to the firstHalf char array.
        /// <param name="newSecondHalf" />The reference to the newSecondHalf char array.
        /// <param name="lastToFirstIndex" />The index that is used in the firstHalf array.
        /// <param name="firstToLastIndex" />The index that is used in the newSecondHalf array.
        private void calculateNextDigits(ref char[] firstHalf, ref char[] newSecondHalf, int lastToFirstIndex, int firstToLastIndex)
        {
            if (lastToFirstIndex == 0 && firstHalf[lastToFirstIndex] == '9' && newSecondHalf[firstToLastIndex] == '9')
            {
                firstHalf[lastToFirstIndex] = ((int.Parse(firstHalf[lastToFirstIndex].ToString()) + 1) % 10).ToString().ToCharArray()[0];
                firstHalf = Insert(firstHalf, 0, '1');
                newSecondHalf[firstToLastIndex] = '1';
            }
            else
            {
                newSecondHalf[firstToLastIndex] = ((int.Parse(newSecondHalf[firstToLastIndex].ToString()) + 1) % 10).ToString().ToCharArray()[0];
                firstHalf[lastToFirstIndex] = ((int.Parse(firstHalf[lastToFirstIndex].ToString()) + 1) % 10).ToString().ToCharArray()[0];
            }
        }

        /// <summary>
        /// Create 3 arrays that represent the first half, the second half and the first half reversed as the new second half. 
        /// </summary>
        /// <param name="numCharArray" />The char array to half.
        /// <param name="originalFirstHalf" /> The reference to the array that will represent the first half of numCharArray.
        /// <param name="newSecondHalf" />The reference to the array that will represent the reverse first half (the new second half) of numCharArray.
        /// <param name="originalSecondHalf" />The reference to the array that will represent the original second half of numCharArray.
        private void createArrayHalves(char[] numCharArray, ref char[] originalFirstHalf, ref char[] newSecondHalf, ref char[] originalSecondHalf)
        {
            originalFirstHalf = new char[numCharArray.Length / 2];
            newSecondHalf = new char[numCharArray.Length / 2];
            originalSecondHalf = new char[numCharArray.Length / 2];

            for (int i = 0, j = (numCharArray.Length / 2) - 1; i < numCharArray.Length / 2; i++, j--)
            {
                originalFirstHalf[i] = numCharArray[i];
                newSecondHalf[j] = numCharArray[i];
            }

            //Take into account that the array length could be even or odd
            for (int i = numCharArray.Length % 2 == 0 ? (numCharArray.Length / 2) : (numCharArray.Length / 2) + 1, j = 0; i < numCharArray.Length; i++, j++)
            {
                originalSecondHalf[j] = numCharArray[i];
            }
        }

        /// <summary>
        /// Transforms char [] back into string.
        /// </summary>
        /// <param name="array" /> the char [] to be made into a string.
        /// <returns></returns>
        public string GetStringFromCharArray(char[] array)
        {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < array.Length; i++)
            {
                builder.Append(array[i]);
            }
            return builder.ToString() == null ? "" : builder.ToString();
        }

        /// <summary>
        /// Inserts a char value at the given index of a char [].
        /// </summary>
        /// <param name="array" />The array to insert into.
        /// <param name="index" />The index at which to insert the value.
        /// <param name="value" />The value to insert.
        /// <returns></returns>
        public char[] Insert(char[] array, int index, char value)
        {

            char[] tempArray = new char[array.Length + 1];
            if (index > array.Length + 1)
            {
                index = tempArray.Length - 1;
            }
            if (index < 0)
            {
                index = 0;
            }
            for (int i = 0, j = 0; i < tempArray.Length; i++, j++)
            {
                if (i == index)
                {
                    tempArray[index] = value;
                    j--;
                }
                else
                {
                    tempArray[i] = array[j];
                }
            }
            return tempArray;

        }

        private const string licensePrompt = "This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'.\n" +
                          "This is free software, and you are welcome to redistribute it\n" +
                          "under certain conditions; type `show c' for details.\n";

        private const string warrantyInfo = "This program is distributed in the hope that it will be useful,\n" +
                                          "but WITHOUT ANY WARRANTY; without even the implied warranty of\n" +
                                          "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the\n" +
                                          "GNU General Public License for more details.\n";

        private const string copyrightInfo = "This program is free software: you can redistribute it and / or modify\n" +
                                          "it under the terms of the GNU General Public License as published by\n" +
                                          "the Free Software Foundation, either version 3 of the License, or\n" +
                                          "(at your option) any later version.\n";
    }
}
Here is the solution/project file for running in visual studio.

Note: If the code isn't formatted and doesn't have syntax highlighting, try changing the URL of this page to be http instead of https.

No comments :

Post a Comment