The Objective

The purpose of this assignment is to give you practice with recursion, using command line arguments, changing numbers to strings, writing error messages to stderr and to do some more file handling and dynamic memory allocation. As always, you should continue to practice using top-down design and good implementation techniques.

The Background

A palindromic number is an integer whose digits are the same whether read forward or backward. Its first digit and last digit are the same, and if long enough, its second and next-to-last digits are the same, etc. Here are some examples of palindromic numbers: 121, 93439, 6, 22, 887020788

It is interesting that if an integer is not a palindromic number, if its digits are reversed and then that new number is added to the original number, a palindromic number is often produced,
i.e. 123 + 321 = 444
If that sum is not a palindromic number reversing its digits and adding that to the sum will often produce a palindromic number,
i.e. 964 + 469 = 1433      1433 + 3341 = 4774

Although most numbers produce a palindromic number with just one or two reverse and add iterations, some take longer. The number 89 takes 24 iterations of the reverse and add algorithm before a palindromic number is produced.

Some numbers are being tested that appear to never form a palindromic number regardless of the number of reverse and add iterations that have been performed. The definition of a lychrel (pronounced la-shrel) is a number that has been proven to never form a palindrome even after repeated reversal and addition. Wade VanLandingham is credited for the term lychrel.

Although proof has been found that some numbers in other bases are lychrels, proof has not been found that any number in base 10 is a lychrel. So numbers in base 10 that appear to be lychrels can technically only be called candidate lychrels. Several candidate lychrels are known. The first candidate lychrel is 196. It hasn't yet produced a palindrome even after over a million iterations of reverse and add. The first million non-palindromic digits were discovered by John Walker.

If you're interested, here's more information about lychrels.

The Task

Since we don't want your project to run infinitely, you'll need to check to see if the random number generated is a candidate lychrel first. If it is, don't attempt to do the reversal and adds, just print a message and get another random number to test. See the sample output.

If the number is not a candidate lychrel, you should check to see if it is a palindrome. If it's not a palindrome, perform as many reverse and adds as necessary in a recursive function until a palindrome is formed, printing the numbers used and the sum at each step. After the palindrome has been formed you must state the number of reverse and adds that were necessary.

Your program is to use command line arguments to accept a seed for the random number generator, the number of random numbers to check, and the name of the data file containing a list of candidate lychrels.

Since one of the objectives of this project is to give you practice working with characters, in this case the characters that represent digits, you will be working not only with numbers, but also digit characters that are stored in strings.

Other Facts

• Repeated reverse and add operations create large integers quickly. The 24 iterations necessary for the number 89, overflows the size of an int, as well as many other numbers that require even fewer iterations. Therefore, we will have to work with the integer type, long long, for the sums and the numeric versions of the reversed sums.
• The conversion string for printf() for a long long is "%lld"
• Although you can make use of the function atoi() found in the stdlib library to convert the strings of the command line arguments into ints, when converting a string to a long long, you are required to use a function that I'm providing called StringToLongLong() whose object code is found in the file stringtoll.o and whose interface is the file stringtoll.h, both in my pub directory.
• You will need to copy these files from my pub directory into your proj4 directory.
  cp /afs/umbc.edu/users/b/o/bogar/pub/stringtoll.*  .
  where the space and the dot at the end of the command are necessary and a part of the command, meaning into my current directory with the same name as the source file.
• The functions atoll(), atoq, and strtoll() that were in the stdlib at one time seem to no longer be there. Trying to use them will result in Implicit Declaration warnings when trying to compile.
• You will also need to copy the file called lychrels.dat from my pub directory into your proj4 directory.

Program Requirements

• Your program must use command line arguments. At the command line the user must enter (in this order):
  • the name of the executable file,
  • an integer to be used as the seed for the random number generator,
  • an integer which is the number of values to be tested,
  • and the name of the input file that contains the list of candidate lychrels.

• If the user doesn't enter the correct number of command line arguments you should provide a detailed explanation of what should be typed at the command line and exit() the program.

• HINT : Working with the lychrels data file
  Since there is no indication at the top of the file about how many items are in the file, you'll need to do the following:
  • Open the file and read integers from it counting them until you reach the end of the file.
  • Dynamically allocate the space needed for an array of the candidate lychrels.
  • Rewind the file.
  • Read the integers from the file into the array of lychrels.
  • Close the file.

• For the reverse and add algorithm, you must use a recursive function with the following required prototype, without modification :
  void ReverseAndAdd(long long num, int* timesPtr);

• You must also use a recursive predicate function to determine whether a string is a palindrome, returning TRUE if the string is a palindrome and FALSE if not. TRUE and FALSE need to be #defined. You must use the following prototype, without modification :
  int IsPalindrome (char* string, int left, int right);
  Note: For modularity the function IsPalindrome() is designed to take a string, not a long long. This function would be a great module to keep in a util.c file.

• You are required to write a function that changes a long long into a string.
  HINT: Since you'll be doing this just to check to see if it is a palindrome, it is okay, actually preferred, if the string has the digits reversed. I called my function NumToReversedString(). This task can be accomplished by stripping the digits from a number, changing them into their character versions, and adding them to the end of a string. Don't forget that when building a string a character at a time, you will have to place the null terminator onto the string manually as well.

• You MUST close any files that you have opened and also free any memory that you have dynamically allocated as soon as you have finished using them.

• You must use separate compilation for this project.

Sample Run

Here is a link to the sample output of this program.

Please note that the sample output only shows what is expected from your program if the user is actually entering everything as instructed. This is not a test of the program at all, but just a sample for your clarification.

Since we are all using the same random number generator, for the same exact command line arguments, your output should match mine precisely.

Submitting the Program

To submit your program, type the following command at the Unix prompt

submit cs201 Proj4 followed by all of your .c and .h files necessary for compilation

DO NOT submit the stringtoll.o and stringtoll.h files that I provided.
We'll be using my copies of those files during grading.

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj4