///<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