Thursday, December 29, 2011

Program to Make the Plural of a Word

Problem:

Write a method regularPluralForm(word) that returns the plural of word formed by following these standard English rules:

a) If the word ends in s, x, z, ch, or sh, add es to the word. 
b) If the word ends in y and the y is preceded by a consonant, change the y to ies. 
c) In all other cases, add just an s.
Write a test program and design a set of test cases to verify that your program works.

(Roberts ch 10, problem 7).

What it looks like:

/*File: MakePlural.java
 * ---------------------
 * This program lets the user enter in any word and it will print out the plural form according to the basic,
 * not totally comprehensive rules outlined in the problem from ch. 10. It makes use of the private methods
 * makePlural (which take in a string and returns another string, the plural form of the word).
 */
import acm.program.ConsoleProgram;
public class MakePlural extends ConsoleProgram {
    public void run() {
       while (true){
           String word = readLine("Enter word and we'll make it plural. Enter '0' to stop: ");
           if (word.equals("0")){
               break;
           }
       print(makePlural(word) + " ");
       }
    }
    
    //Takes the submitted string, inspects the last letter (or last 2 letters in case of "ch" and "sh"),
    //and returns the appropriate plural form.
    private String makePlural (String singularWord){
        String pluralWord = "";
        String strippedWord = singularWord.substring(0, singularWord.length()-1);
        char lastLetter = singularWord.charAt(singularWord.length()-1);
        switch (lastLetter){
            case 's':
            case 'x':
            case 'z':
                pluralWord = singularWord + "es";
                break;
            case 'h': // checking for if the word ends with "ch" or "sh"
                if ((singularWord.charAt(singularWord.length()-2)== 'c') || (singularWord.charAt(singularWord.length()-2)== 's')) {
                    pluralWord = singularWord + "es";
                    break;
                } 
            case 'y':
                if (isEnglishConsonant(singularWord.charAt(singularWord.length()-2))) {
                    pluralWord = strippedWord + "ies";
                    break;
                }
            default: pluralWord = singularWord + "s";
            break;
        }
        return pluralWord;
    }
    private boolean isEnglishConsonant(char ch) {
        switch (Character.toLowerCase(ch)) {
            case 'a': case 'e': case 'i': case 'o': case 'u': 
                return false;
            default: 
                return true;
        }
    }
}





What made it tricky:


The program is structured to work well as a "switch" statement, and I had wanted to create a neat table that took a substring "lastLetter" (last 2 letters in the case of "ch" and "sh") and neatly return the proper plural form.  However you can't switch on a string as I learned-- damn! So had to use the character only and switch on that, which made checking for "ch" and "sh" slightly less convenient.


Come to think of it, why *can't* you switch on a string? You'd think that it's a similar situation to comparing strings via "if (s1 == s2)", namely that it would often give you the wrong answer since they're comparing actual objects, not values. However I got an error when I attempted...anyone know why?


Another bug I ran into came from attempting to inspect the last letter and second-to-last-letter by doing charAt(-1) or charAt(-2) and making a substring of all but the last letter of the original word by doing "singularWord.substring(0, -1)". Those were throwing out-of-bounds errors. Oops-- sure would have been convenient.


The main bug I got stuck on before it worked is that it kept giving me the default case. So "sky" gave me "skys", "box" gave me "boxs" etc. I didn't know why and whether the non-default case was even getting run so I added debugging lines to print out the plural form as soon as it gets run.






It appeared that the special cases were getting run, but the default was getting run every time. Why?


I suppose I needed to add "break" statements to my special cases in the "switch" statement. I looked up confirmation for this in the text and this is what it said:


"Java is defined so that if the break statement is missing, the program starts executing statements from the next clause after it finishes the selected one. While this design can be useful in some cases, it tends to cause more problems than it solves. To reinforce the importance of remembering to include the break statement, every case clause in this text ends with an explicit break statement (or sometimes with a return statement, as discussed in Chapter 5)."


That kind of makes sense... depending on what the syntax means when it checks for "default," it's posible that "default" means every single case *in addition to* the special cases that do apply. So yes, once I did add a "break" statement to each case, the problem worked correctly.


It's weird though because one example in the book does a simple switch statement with a default, but does not have a break statement after the special cases:

private boolean isEnglishVowel(char ch) {
     switch (Character.toLowerCase(ch)) {
         case 'a': case 'e': case 'i': case 'o': case 'u':
            return true;
         default: 
            return false;
    }
}   
I can confirm that this private method works correctly since I used it in my own program. So I'm not quite sure when a break statement is required. I do realize that the author may not have meant to include a confusing example in the final version of the book, so I'll check this PDF against my hard copy when I'm back home. Any ideas on this switch statement conundrum however?

Wednesday, December 28, 2011

Program to Determine the Ordinal Value of a Number

Problem:
Like most other languages, English include two types of numbers: cardinal numbers (such as one, two, three, and four) that are used in counting, and ordinal numbers (such as first, second, third, and fourth) that are used to indicate a position in a sequence. In numeric form, ordinals are usually indicated by writing the digits in the number, followed by the last two letters of the English word that names the corresponding ordinal. Thus, the ordinal numbers first, second, third, and fourth often appear in print as 1st, 2nd, 3rd, and 4th.
The general rule for determining the suffix of an ordinal can be defined as follows:
Numbers ending in the digit 1, 2, and 3, take the suffixes "st", "nd", and "rd", respectively, unless the number ends with the two- digit combination 11, 12, or 13. Those numbers, and any numbers not ending with a 1, 2, or 3, take the suffix "th".
Your task in this problem is to write a function ordinalForm(n) that takes an integer n and returns a string indicating the corresponding ordinal number.  (Roberts ch 10, problem 9).


What it looks like:

/* File: ordinalForm.java
 * -----------------
 *This console program lets the user enter in any integer and will print out the ordinal form of that number. For example
 *the ordinal form of 1 is "1st," 2 is "2nd" etc. The user enters the sentinel value "-1" to stop running the program.
 *
 *The program and the method of the same name takes an integer as the entered value and returns a string. We use the ACM library's (?)
 *built-in Integer class and its toString method. Because the suffix of an ordinal value depends on the last digit
 *of a number our program has to strip out and inspect the last digit of the supplied integer so we use the method 
 *"getLastDigit" to inspect the last digit. In the case of numbers ending with "11", "12" and "13" we need to see the last
 **two* digits so we also use a similiarly-constructed getSecondToLastDigit.
 */
import acm.program.ConsoleProgram;
public class ordinalForm extends ConsoleProgram {
    public void run() {
       while (true){
       int cardinal = readInt("Enter number and we'll give you the ordinal form: ");
       if (cardinal == -1){
           break;
       }
       print(makeOrdinal(cardinal));
       }
    }
    private String makeOrdinal(int n) {
        String ordinal = "";
        int lastDigit = getLastDigit(n);
        int secondToLastDigit = getSecondToLastDigit(n);
        if ((lastDigit == 1) && secondToLastDigit !=(1)){
            ordinal = Integer.toString(n) + "st"; //Not sure why it's "Integer.toString(n)" instead of "n.toString" or "toString(n)"
        }
        else if (lastDigit ==2 && secondToLastDigit !=(1)) {
            ordinal = Integer.toString(n) + "nd"; 
        }
        else if (lastDigit == 3 && secondToLastDigit !=(1)) {
            ordinal = Integer.toString(n) + "rd";
        }
        else ordinal = Integer.toString(n) + "th";
        return ordinal;
    }
    private int getLastDigit(int n) {
        int remainder = n % 10;
        return remainder;
    }
    
    private int getSecondToLastDigit(int n) {
        int remainder = 0;
        for (int i = 0; i < 2; i++){
            remainder = n % 10;
            n /= 10;
        }
        return remainder;
    }
}
}








What made it tricky:


My first version of this was running just fine....it just kept returning the wrong answer. Have a look at this sample run when the bug existed and guess what the problem was:



Here's a clue: this is what my private methods getSecondToLastDigit(n) and getLastDigit(n) looked like:

    private int getLastDigit(int n) {
        int remainder = 0;
        while (n > 0) {
            remainder = n % 10;
            n /= 10;
        }
        return remainder;
    }

    private int getSecondToLastDigit(int n) {
        int remainder = 0;
        while (n > 10) {
            remainder = n % 10;
            n /= 10;
        }
        return remainder;
    }
So while getLastDigit(n) should have just divided by n *once* and returned the remainder, instead it kept dividing by n until there was nothing left. So it was really stripping off and returning the *first* digit, not the last! getSecondToLastDigit(n) was behaving the same way, except it stopped one iteration sooner so it returned the second digit, not the second-to-last. Ugh, so embarrassing, blame it on the Christmas food abundance.

I didn't see the pattern or understand what was wrong for a while so I made this quick debugging program that printed out the results of just getLastDigit(n):

import acm.program.ConsoleProgram;
public class testLastDigit extends ConsoleProgram {
    public void run() {
       int n = readInt("Enter an int and we'll give you the last digit");
       print (getLastDigit(n));
    }
    private int getLastDigit(int n) {
        int remainder = 0;
        while (n > 0) {
            remainder = n % 10;
            n /= 10;
        }
        return remainder;

    }
}
I ran it a bunch of times and saw that indeed, testLastDigit  was giving me the wrong answer. Once I saw that it was wrong and predictably wrong, the fix was easy.


Saturday, December 17, 2011

Program to Search for a Substring inside a String

Problem: If the designers of the String class had not defined the version of indexOf that takes a string argument, you could implement it using the other methods available in the library. Without calling indexOf directly, implement a method myIndexOf that behaves in exactly the same way.


What it looks like:




/* File: myIndexOfTester.java
 * ---------------
 * This program has a run method that lets the user enter in a (supposed to be) big string and a
 * little string. Then it uses the private method myIndexOf to see whether the little string exists
 * inside the big string and if so, return the index within the big string that the little string
 * exists at.
 * 
 * There is already an indexOf method in Java's standard String class, but the Stanford folks 
 * thought it would be good for us to try implementing it ourselves with other methods in the
 * String class.
 */
import acm.program.*;
public class myIndexOfTester extends ConsoleProgram {
    public void run() {
       String enteredString = readLine("Enter a string: ");
       String searchedForString = readLine("Enter the string you're searching for inside it: ");
       print(myIndexOf(searchedForString, enteredString));
    }
    private int myIndexOf(String littleString, String bigString) {
//"Real" program would check that littleString is longer than bigString & raise and exception of it weren't

//For every letter in bigString MINUS the length of littleString (to guard against out-of-bounds
//errors), check if littleString equals the segment of bigString that starts at that index.
        for (int i = 0; i < bigString.length()-1-littleString.length()-1; i++) {      
            if (littleString.equals(bigString.substring(i, i+littleString.length() ))) {
                return i;
            }           
        }
        return -1; //Signifies that littleString doesn't exist inside bigString         
    }
}




The basic gist of this problem, or at least my approach to it, is you want to take your little string and compare it to substrings inside the big string. In particular, you want to iterate through each letter of the big string and carve out a substring starting at that index and of an equal length to the little string. If they are equivalent, then return the index. If you never get an equivalency, then return -1 (as is the existing convention).


What made it tricky: Two things! 1) Off-by-one errors, and 2) Out-of-bounds errors.


** Off-by-one Errors **


Let's say your big string is "HELLO WORLD". This string has 11 characters, including the space, so the method bigString.length() would return 11. If you iterated from 0 to 11, however, your last iteration would be looking at nothing since there's no character at space "11"! Therefore, you have to make the outer bound of your loop is the length of the big string minus one.




** Out-of-bounds Errors **


Let's say your big string is "HELLO", and the little string you're inspecting "HELLO" for is "HI." You go thru every letter in "HELLO," seeing if the 2-letter substring at that letter is equivalent to "HI".


However, what happens on the last couple of iterations of your loop? If your index is the letter "O" in "HELLO", you're comparing "HI" with "O" and then nothing! To keep this from happening, you need to stop your comparisons so that all the letters in "HI" have something in the string "HELLO" to get compared to.






The last tricky thing is, the problem specified that the method has to behave the *same* way as the existing indexOf. That takes in just one argument (the little string) and you apply it to the big string. My implementation takes in both the big string and the little string as arguments, so I had been worried that I hadn't actually solved the requirement. 


However, how is it possible to write your own implementation as a method by itself without "knowing" the length of the big string? Not sure whether this is do-able.... I checked the textbook to see whether the authors printed this problem. (I have to confess that I've been studying with a PDF of the pre-print copy of the textbook since it's easier to have on hand, and I leave the heavy text at home). I saw that the printed version omitted this problem, so I'm assuming that the editors decided that it wasn't quite a perfectly designed problem because of that mismatch. Thoughts?

Monday, December 12, 2011

Program to Calculate the Scrabble Score of a Word

Problem:
In most word games, each letter in a word is scored according to its point value, which is inversely proportional to its frequency in English words. In ScrabbleTM, the points are allocated as follows:

For example, the Scrabble word "FARM" is worth 9 points: 4 for the F, 1 each for the A and the R, and 3 for the M. Write a ConsoleProgram that reads in words and prints out their score in Scrabble, not counting any of the other bonuses that occur in the game. You should ignore any characters other than uppercase letters in computing the score. In particular, lowercase letters are assumed to represent blank tiles, which can stand for any letter but which have a score of 0. (Robers ch 9, problem 5)

What it looks like:


/* File: ScrabbleCalc
 * -----------------
 * This program takes in an arbitrary word from the end-user and calculates its value according to the points alloted
 * to each letter by the game Scrabble. Characters must be upper-case; lowercase letters are ignored.
 * 
 * The program makes use of the private method 'scabbleScore' that takes in the input string and iterates through
 * each charcter. The method also establishes the integer 'score,' an instance variable that keeps track of the
 * accumulating points for the word. In each loop, it asses character via a switch statement and adds the appropriate 
 * points value for the character to 'score.'
 */
import acm.program.*;
public class ScrabbleCalc extends ConsoleProgram {
    public void run() {
       String word = readLine("Enter Scrabble word (all in uppercase) and we'll calculate your score: ");
       print(scrabbleScore(word));
    }
    private int scrabbleScore(String scrabbleWord) {
        int score = 0;
        for (int i = 0; i < scrabbleWord.length(); i++){
            char calculatedLetter = scrabbleWord.charAt(i);
            switch (calculatedLetter) {
                case 'A':
                case 'E':
                case 'I':
                case 'L':
                case 'N':
                case 'O':
                case 'R':
                case 'S':
                case 'T':
                case 'U': //Jesus this is fugly
                    score +=1; break;
                case 'D':
                case 'G':
                    score +=2; break;
                case 'B':
                case 'C':
                case 'M':
                case 'P':
                    score +=3; break;
                case 'F':
                case 'H':
                case 'V':
                case 'W':
                case 'Y':
                    score +=4; break;
                case 'K':
                    score +=5; break;
                case 'J':
                case 'X':
                    score +=8; break;
                case 'Q':
                case 'Z':
                    score +=10; break;
                default: break;
            }
        }
        return score;
    }
}

What made it tricky:

Whenever I tell other programmers I'm learning programming with Java, they express much exasperation about the language, and I begin to see why. The statement that I had wanted to express was,  "If the letter at increment "i" is A, E, I, L, etc, then add 1 to the instance variable "score." I was looking for the switch statement to support an "or" statement (ie "case 'A' || 'E' || 'I' || 'L' ") but alas, the syntax isn't that neat. I had to list all the separate cases individually, though fortunately I didn't have to do the action block repeatedly for cases with identical points! I don't exactly know how you'd handle this in Python or Ruby but I expect it would be more succinct.
I think if building a Scrabble calculator in the "real world," you'd want to use a hash table  to easily turn the letter:points match into key:value pairs. We haven't gotten to hashes and arrays yet, so the tools for this problem were either a) switch statements or b) cascading "if" statements.