Programming Assignment 7

Due April 26, before midnight

Program Description
For instant messaging on a cellphone, the digit keys {2,3,4,5,6,7,8,9} are pressed to spell a word.  Each digit corresponds to a subset of letters as shown in the photo below

phone keypad
As can be seen, the digits "1" and "0" are not associated with letters.  The other digits are assigned the following possible letters

2 = {a,b,c} 3={d,e,f}
4={g,h,i}
 5={j,k,l}
 6={m,n,o}
7={p,q,r,s}
 8={t,u,v}
 9={w,x,y,z}

Here are two example digit sequences, and possible words they spell:

"229" can spell the words "bay" or "caw"

"269" can spell "amy", "any", "bmw", "bow", "box", "boy", "cow", "cox", or "coy"

In this assignment, you will implement methods that given a sequence of digits, will find all possible matching words in a dictionary.   The dictionary class is provided, and a text file containing words for the dictionary class is provided.

What You Do
It is assumed that you are using NetBeans to develop your code for this assignment.  Create a new NetBeans project that is a "General" "Java Application". Name your NetBeans project program7.

Download the source for the Main.java, Dictionary.java, and PhoneSpeller.java classes, and store these in the program7/src/program7 directory.  Also download the file words, and store this in the same directory.   Note: Be sure to modify the source of PhoneSpeller.java to specify the correct file location for you copy of the file words.

Using NetBeans, you are to implement a recursive static method for the class PhoneSpeller:
  1. public static Vector<String> findAllCombos(String digits)
This recursive method finds all the possible combinations of letters that are valid for an input sequence of digits, returned as a vector of strings.  If the string contains a 1 or 0, then there are no combinations of letters possible, and this method must return a Vector which is empty.  This method must be implemented using recursion.

You can assume that the input String digits contains only digits.
  1. public static Vector<String> findAllWords(String digits)
This method finds all the possible words in the dictionary that could possibly be spelled using all possible combinations of letters for each digit.

Use the static method Dictionary.findWord(String s) to determine what words are listed in the dictionary.

Recursive Algorithm

There are many ways to implement the recursive algorithm for findAllCombos.  It is suggested that the base case is used when a number string is only 1 digit long, and the recursive case is used when the length of the number string is greater than 1. 

For example, given the digit string "234":
findAllCombos("34")   -->
findAllCombos("4")   -->
{"g","h","i"}
{"dg","dh","di","eg","eh","ei","fg",fh","fi"}

Hint

You may want to implement a helper method private static String digitToCharacters(char digit) that takes a digit as input and produces a string of possible letters as output.  For instance, if digit = '2' then the method returns the string "abc".   This is only a suggestion.

Programming Style

You are expected to follow the CS111 / CS112 Java Coding Standard.  You will be graded on programming style. Each student must schedule two meetings with course staff to review a submitted program's style.   Two lab times will be set aside for this (refer to course schedule).  You can also arrange to have tutors review your program style during scheduled tutoring hours.   This is meant to allow students to get guidance and feedback on style, and the grading of style is separate from the grading of Program Assignment 7.

Testing

You are responsible for testing your method.  To help you in testing, a few example tests are provided in the file Main.java.  Other tests will be conducted in grading -- so test your methods carefully before submitting your code. 

Caution and Commentary

Note that the recursive algorithm used here for spelling with digits gets incredibly slow for longer sequences of digits.  Why?  Obviously cellphones use a faster, better method! Can you imagine a faster algorithm for solving the problem given here? 
     

What You Submit
Submit your  file called PhoneSpeller.java in a directory named 07 via gsubmit .

Under no circumstances will late assignments be accepted.

Grading Criteria

20% Submitted code compiles without errors
20% findAllCombos returns the correct values for the cases given in Main.java
20% findAllCombos returns the correct values for the cases given at testing time
20% findAllWords returns the correct values for the cases given in Main.java
20% findAllWords returns the correct values for the cases given at testing time