Arrays, Strings, and Bits

Summary

You will write programs to compute the Scrabble score of a word, count the letters two strings have in common, and emit a UNIX-style permissions string.

Objectives

• Practice character string and array processing
• Reinforce bit-level data manipulation

Problem 1: Word Scoring

In word board games like Scrabble or Words with Friends, players place letters on a grid to form words. Rules of the games may vary, but a common thread among them is to score each word played as the sum of individual letter scores, with point values inversely proportional to the characters' frequencies.

Write a program wordscorer.c that features the function

int wordscore(const char *word)

which calculates the total score of the given word according to the following rules:

Your program should prompt the user to enter a word and report the word's score.

Programming Notes

• The program should verify the user input.
• The user should be able to enter a word of length at least 63
• The wordscore function should use assertto verify any preconditions.

• It is common for null-terminated strings (of indeterminate length) to be taken as arguments of type char *. However, in order to get memory in which to deposit a string entered by a user, you must declare an array of characters. Remember that an array variable holds the address of the first element of the array, so it can be passed as the pointer argument to wordscore.

  A functionally equivalent signature for the function would be

  int wordscore(const char word[])

  but this tells the programmer more that the input is an array, rather than a null-terminated string, so documentation would need to point out the precondition for null-termination.

Problem 2: Common Letters

Write a program common.c that reads two strings and counts how many letters the strings have in common. To determine common letters, each letter of one word should be matched with exactly one letter of the second word. The case of the letters (upper case versus lower case) should be ignored. For example:

• "room" and "tool" have two letters in common (each "o" in "room" is matched with a separate "o" in "tool").
• "red" and "fewer" have two letters in common (the "e" in "red" matches one of the "e"s in "fewer" and both words contain one "r").
• "Mississippi" and "Iowa" has just one letter in common (the "I" of Iowa matches one of the "i"s in "Mississippi").

To accomplish this, your program must make the calculation via the helper function

int common_chars(const char* word1, const char* word2)

Programming Notes

• The standard C header file <ctype.h> contains the definition of many useful character functions.
• The user should be able to enter words of length at least 63

Problem 3: Permission Bits

As you may recall from our earlier reading on Linux file permissions, three categories of permissions are granted to three categories of users. These nine bits are packed together into a single integer; the standard system header file <sys/stat.h> features bit masks allowing programmers to extract the individual bits, as shown in the following table.

For example, the bitmask S_IRUSR has the binary value (spaces inserted for readability) 100 000 000, that is a one in the leftmost of nine positions, while S_IWGRP would be 000 010 000.

Using these definitions, write the following procedure in a program called permissions.c that takes an integer and fills in the appropriate slots in a permissions array.

void get_permissions(unsigned short perms, char output[9])

Then use the procedure in a main program that tests your procedure by printing out the permissions in a form similar to ls -l.

get_permissions(S_IRUSR | S_IWUSR | S_IRGRP, ... );

rw-r-----

get_permissions(0755, ... );

rwxr-xr-x

get_permissions(0664, ... );

rw-rw-r--

get_permissions(256, ... );

r--------

Note: The parameter perms should have no bits to the left of position nine set. Your get_permissions procedure should verify this with an assertion.

Hint: Think about the numeric range of valid inputs.

Programming Notes

• The examples above include numbers represented in base 8 (called octal numbers), which are designated by a leading zero. The octal number 0755, which has a binary representation of 111 101 101. (shown with spaces added so you can see the significance of these numbers).

  If instead you type the number as 755 (without the leading zero), it is interpreted as a decimal number, which has the binary representation 1011110011—certainly not the value you wanted).

  Thus this problem is not about extracting the decimal columns (e.g., ones, tens, hundreds) from a number, but extracting the (nine) binary bits from a number, and using those bits to fill in the entries of your array.

• #include the requisite system header file
• Use C's ternary conditional expression for parsimony
• Mind the null terminator required for treating a character array as a string.

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 34 points.

• Comments on Program Format, Comments, Readability, etc.
  (Points not given, but points can be deducted.)
• [3 points] Programs verify user input and handle errors appropriately
• [11 points] Problem 1: Word Scoring
• [2 points] Program prompts and safely reads user input
• [1 point] Program prints final word score
• [1 point] Function concisely expresses algorithm
• [5 points] Function correctly tallies letter scores
• [2 points] Function verifies preconditions
• [8 points] Problem 2: Common Letters
• [2 points] Program prompts and safely reads user input
• [1 point] Program prints final count
• [5 points] Function correctly tallies common letters
• [5 points] Problem 3: Permission Bits
• [3 points] Function correctly fills permission string
• [1 points] Function verifies preconditions
• [1 point] Function concisely expresses algorithm
• [7 points] Tests demonstrate correctness
• [2 points] Test plan enumerates the range of problem circumstances
• [3 points] Test cases include specific inputs and expected outcome(s)
• [1 point] Transcripts demonstrate functionality with test runs
• [1 point] Statement argues why the program is correct

A five point penalty will apply to any submission that includes personally identifying information anywhere other than the references/honesty file.