Palindromes

A palindrome is a word or sentence (or several sentences) that is spelled the same way forwards and backwards. "Rotor" and "racecar" are (word) palindromes. Non-letters aren't included and cases can be upper or lower so "A man, a plan, a canal: Panama!" is also a palindrome.

You can find lots of palindrome lists on the Internet. One good source is http://www.palindromelist.net

This lab has two parts.

Part 1: A Palindromic Word Tester

The algorithm to detect palindromes is simple: Start indices i and j at the first and last letters of the word and compare the two letters. If they are different (allowing for upper/lower case), you can stop right there: The word is not a palindrome. Otherwise, increment i and decrement j. If you get as far as "i >= j", the word is a palindrome.

In the first part of this lab, you will prompt the user to enter a word, test to see if it's a palindrome, and print the result.

Follow these steps:

1. Download the file palindrome_tester_tplt.c to your lab directory.

2. Rename it:

   $ mv palindrome_tester_tplt.c palindrome_tester.c
   

   Here's what it looks like:

   #include <stdio.h>   // for standard I/O functions
   #include <string.h>  // for strlen()
   #include <ctype.h>   // for tolower()
   
   #define MAX_LINE_LENGTH 1024 // assume no lines longer than this
   
   
   int isAPalindrome(char line[])
   {
       /*
        * ASSIGNMENT
        *
        * declare ints `i` and `j`
        * declare a MAX_LINE_LENGTH char array `buf`
        * copy `line` to `buf` using the `strcpy()` function
        * set `i` to 0
        * set `j` to be the length of `buf` (use `strlen()` for this) - 1
        * as long as `i` is less than `j`,
        *     if the lower case `buf[i]` is not equal to the lower case
        *      `buf[j]`, (use `tolower()` to convert both chars to lower
        *      case)
        *         return 0 (`line` is not a palindrome)
        *     increment `i`
        *     decrement `j`
        * return 1 (`line` is a palindrome)
        */
   }
   
   int main(void)
   {
       char word[MAX_LINE_LENGTH];
   
       // Prompt for a single word to test and print success or
       // failure.
       printf("Enter a word: ");
       fgets(word, MAX_LINE_LENGTH, stdin);
       /*
        * ASSIGNMENT
        *
        * `word` ends in a newline, which you should remove.
        * if `word` is a palindrome (hint: use `isAPalindrome()`)
        *     print a message that includes `word` saying that it is a
        *      palindrome
        * otherwise
        *     print a message that includes `word` saying that it is not
        *      a palindrome
        */
   
       return 0;
   }
   
   

3. Follow the instructions in the comments marked ASSIGNMENT to complete the source file.

4. Compile your code as usual:

   $ gcc -Wall palindrome_tester.c -o palindrome_tester.exe
   

5. When you run it, your result should look like this:

   $ ./palindrome_tester
   Enter a word: aword
   "aword" is not a palindrome.
   $ ./palindrome_tester
   Enter a word: rotor
   "rotor" is a palindrome.
   $ ./palindrome_tester
   Enter a word: Rotor
   "Rotor" is a palindrome.
   

Part 2: A Palindromic Filter

In the second part of this lab, you will create a palindromic "filter": A program that reads a series of lines on standard input (which defaults to your terminal emulator) and prints only those who are palindromes to standard output (which, again, defaults to your terminal emulator).

Follow these steps:

1. Download the file palindrome_filter_tplt.c to your lab directory.

2. Rename it:

   $ mv palindrome_filter_tplt.c palindrome_filter.c
   

   Here's what it looks like:

   #include <stdio.h>   // for standard I/O functions
   #include <string.h>  // for strlen()
   #include <ctype.h>   // for tolower()
   
   #define MAX_LINE_LENGTH 1024 // assume no lines longer than this
   
   
   // remove everything that isn't a letter from `buf`, shortening it as
   // necessary
   void removeNonLetters(char buf[])
   {
       /*
        * ASSIGNMENT
        *
        * declare ints `i` and `j` and initialize them both to 0
        * as long as `buf[j]` is not NUL (the character '\0'),
        *     if `buf[j]` is a letter (use the `isletter()` function)
        *         assign `buf[j]` to `buf[i]`
        *         increment `i`
        *     increment `j`
        * set `buf[i]` to NUL
        */
   }
   
   
   int isAPalindrome(char line[])
   {
       /*
        * ASSIGNMENT
        *
        * Modify your previous code as follows: After copying `line` to
        *  `buf`, add a call to `removeNonLetters()` to remove all
        *  non-letters from `buf`. (This can take the place of your
        *  newline removal in Part 1.)
        */
   }
   
   int main(void)
   {
       char line[MAX_LINE_LENGTH];
   
       /*
        * The `fgets()` call below reads a line of text from the console.
        * You don't need to modify it: Just complete the assignment below.
        */
       while (fgets(line, MAX_LINE_LENGTH, stdin) != NULL)
       {
           /*
            * (`line` contains a line of text to test for palindromicity.
            *  It ends in a newline, but leave it alone: It will be
            *  removed in `isAPalindrome()`.)
            *
            * ASSIGNMENT
            *
            * If the length of `line` (including the newline) is greater
            *  than or equal to 4 and it is a palindrome, print it (hint:
            *  use `strlen()` and `isAPalindrome()`).
            */
       }
   
       return 0;
   }
   
   

3. Follow the instructions in the comments marked ASSIGNMENT to complete the source file. Note that

   1. There's a new function, removeNonLetters(), to write that removes all non-letters from a string.
   2. isAPalindrome() needs to be modified to call removeNonLetters().
   3. main() needs to be modified to reject words two or fewer characters in length.

4. Compile your code as usual:

   $ gcc -Wall palindrome_filter.c -o palindrome_filter.exe
   

5. When you run it, your result should look like this:

   $ ./palindrome_filter
   aword (enter this)
   rotor (enter this)
   rotor (this is output)
   Rotor (enter this)
   Rotor (this is output)
   A man, a plan, a canal: Panama! (enter this)
   A man, a plan, a canal: Panama! (this is output)
   

   The parenthetical remarks are comments: Do not enter them. Notice that only the palindrome lines are duplicated: The filter ignored the non-palindromic first line. Also, filters never prompt the user for input: They assume the user knows what data to input.

6. Download the file words to your lab directory. This file contains 99,171 common English words. You can use palindrome_filter to detect which of them are palindromes by "redirecting" standard input to come from this file instead of the terminal emulator. You do that with the "<" character as follows:

   $ ./palindrome_filter <words
   

   This will produce a list of all the words in words that are palindromes.