CIT 591 Assignment 4: Numeric spell checker
Fall 2004, David Matuszek

Purposes of this assignment:

General idea of the assignment:

A spell checker reads your document and compares the words in it to a dictionary. If it doesn't find a word in the dictionary, it suggests a replacement word (typically, more than one).

In this assignment you will write a NumericSpellChecker class whose "dictionary" is a list of numbers. Your spell checker will return the single best match. (If there is more than one equally good "best" match, your spell checker will return all of them.)

We will use the random number generator to create the dictionary. Numbers to be searched for will be entered by the user. Except as noted, you should thoroughly test all methods with JUnit.

Details:

JUnit

Name your class NumericSpellChecker. Name your JUnit class NumericSpellCheckerTest (BlueJ will do this automatically if you right-click on the NumericSpellChecker class and select Create Test Class). You should have a test method for every method except the main method and the supplied getNumber method.

Please follow the sequence recommended in class. That is, write the test methods first, along with stubs; then run the tests; then start filling in the stubs with the actual code, testing frequently. I can't watch over your shoulder to make sure you do things this way, but please give it a try.

Methods

Write (at least) the following methods:

public static int[] generateRandomArray(int size)
Creates and returns an array of size random integers (see below).

public void createDictionary(int[] numbers)
Creates a "dictionary" int array of the same size as the numbers array, and copies the values from numbers into it. Does not simply make another reference to the input array. This dictionary will be an instance variable of NumericSpellChecker.

public void createRandomDictionary(int size)
Creates a dictionary of size random numbers by using the above two methods.

public boolean exactMatch(int inputNumber)
Returns true if and only if the dictionary contains exactly the number given.

public static int countDifferences(int a, int b)
Counts how many digits are different in the two integers a and b. Digits may be changed, but no digits will be deleted or inserted, so you need only compare digits in the same positions. Count a difference in sign (+ or -) as just one additional difference. Examples and hints are given below.

public int[] findBestMatches(int inputNumber)
Searches the dictionary and returns the numbers that most closely match the inputNumber, that is, have the fewest differences from the input number. There may be ties for the best match, so return an array of results. This method should, of course, use the countDifferences method.

public static void main(String[] args)
Uses createRandomDictionary to create a random dictionary of 100 integers, then repeatedly gets a number from the user and searches the dictionary for the best match or matches. If there is an exact match, it reports this fact to the user; otherwise, it prints out all the best matches (there may be more than one). Quit the program when the user enters a zero.

You do not need to write a unit test for the main method; but you should write it last, after all the other methods have been completed.

If you write additional methods, you should either write JUnit tests for them, or you should declare them private (rather than public). Private methods can only be tested indirectly, by testing the public methods that use them.

Hints

Testing

Test for extreme cases, as well as typical ones. For example, check the first and last locations of an array. Check that it is possible to find negative numbers as well as positive ones. Check that you can find a zero, if the dictionary contains one.

Check that createDictionary really does create a duplicate of the array given to it, not just another reference to the same array.

You probably don't want to do all your testing with a random dictionary. The above methods allow you to create a dictionary containing numbers that you choose.

You should write at least one test method for each method to be tested, and you should try to write a test that uses only the method being tested. If you can't avoid using the other methods, that's okay, but don't use them more than you must.

You can use the setUp method to create a dictionary for use by some of the test methods; this is a bit hazardous, because creating a dictionary might not work. Remember, too, that you can write helper methods in your JUnit test class--don't begin the method name with "test", and JUnit won't try to call it automatically.

Counting differences

For positive integers, number % 10 will give you the last digit, and number / 10 will give you the number with the last digit removed. If number is negative, number % 10 will also be negative (or zero).

The best way to count is by repeatedly comparing and removing the last digit until both numbers are zero.

Examples:

77777777
37777477
difference = 2
12345678
  345007
difference = 5
-112233445500
 112200005500
difference = 5
-100200300
  -1234500
difference = 6

"Random" numbers

Computers don't really work with random numbers. In reality, each "random" number is computed from the one before it by applying a fairly simple formula. (Hence, these are called pseudo-random numbers, meaning "false" random.) In order to get the exact same sequence of "random" numbers every time, all you need to do is start with the same number. This can be a big help in testing programs that use "random" numbers!

To get the same sequence of random numbers every time, import java.util.Random, and provide an int or long seed when you create the Random object.Like this:

Random random = new Random(12345);

If you leave out the argument to the constructor, Random will use the number of milliseconds since January 1, 1970, as its seed.

Getting user input

You can use the following method (written by me but debugged by Mirko) to get numbers from the user. As we have not yet discussed how to test a method that does input and/or output, you do not need to write a unit test for it.

import java.util.Scanner;

Scanner scanner = new Scanner(System.in);

public int getNumber() {
    System.out.print("Enter an integer: ");
    while(true){
        if (scanner.hasNextInt()) {
            int result = scanner.nextInt();
            scanner.nextLine();
            return result;
        }
        else {
            System.out.print("\"" + scanner.nextLine() +
                             "\" is not an integer. Try again: ");
        }
    }
}

Grading:

In addition to program correctness and good unit tests, we will check for the following style points: correct indentation, correct spacing, correct capitalization, and reasonable variable names.

Due date:

Thursday, October 6, before midnight. Zip up all your files and turn in one copy for your team, via Blackboard.