Cross Word Solver

You are to implement a method to assist with solving word puzzles, e.g. crossword puzzles. If a user knows the length of the word and some of the letters, your method should return should return a list of the matching words in a dictionary (i.e. a list of words, which I have supplied). For example, if they are looking for a word of 6 letters, with the first being 'b', the second 'i' and the fifth 'r', they would input bi..r. (with dots standing for unknown letters) and your method would return the strings

bikers
binary
bistro

We would like to do this efficiently, i.e. examining as few of the words in the dictionary as possible (because the dictionary might be very large). If the user doesn't know the first letter, we have no choice but to go through the whole dictionary checking each word. But if they know some letters at the start, we can do much better, because the dictionary is guaranteed to be in alphabetical order.

Thus, for example, all the words starting with 'bi' will be together in the dictionary. We can use the variant binary search algorithm (AltBinarySearch) from the week 4 notes to find the position of the start of this group and then search sequentially from there, checking the rest of the word against the given clue, until either the initial letters no longer match or we reach the end of the dictionary.

Dictionary

I have supplied a bundle of Java files FindWords.java into which you should add your work. One of these is a class Dictionary, which provides access to the dictionary. You don't need to change this class, and shouldn't submit it: your code needs to work with my version.

The class contains two methods:

public int size()
returns the number of words in the dictionary.
public char[] getWord(int i)
Returns the word in the dictionary at position i, a number that must be greater than or equal to zero and less than size().

Note that arrays like the one returned by getWord() include a field length that gives the number of elements in the array. The first position in an array has index 0.

You may assume that words in the dictionary consist of lowercase letters, and that they are in order.

Do not access the dictionary in any other way (I might test with a different one).

The task

Your task is to fill in the implementation of four methods in the class MySearcher. (Currently they either throw exceptions or do little.) This will be the only file you submit. Do not rename it or change the names or signatures of the methods in it. (You may add more methods if you like, but shouldn't need any fields.) The class implements the interface Searcher, which you should not alter or submit. (This is to ensure you haven't changed the signatures of the methods.)

The required methods are:

boolean equal(char[] s, char[] t, int n)
[10%] This method should return true if the first n elements of the two arrays are equal, or, if either is shorter than n, if both have the same length and the same characters.
boolean lessThan(char[] s, char[] t, int n)
[20%] This method should return true if the first n elements of the array s come before the first n elements of the array t in dictionary order. For example, if n is 4:

binary is less than bind
binder is not less than binding
binding is not less than binder
bin is less then binary
bit is not less then binary

int findPrefix(Dictionary d, char[] w, int n)
[30%] This method should return the first position p in the dictionary such that for all i less than p, lessThan(d.getWord(i), w, n) is true. It should use a Java version of the variant binary search algorithm (AltBinarySearch) from the week 4 notes to minimize the number of words in the dictionary that are examined.
ArrayList< char[] > findMatches(Dictionary d, char[] clue)
[40%] This method should return the words from the dictionary that match the clue, which consists of letters and dots. A word matches the clue if it has the same number of characters, and matches each letter present in the clue. Where possible, this method should minimize the number of words in the dictionary that are examined, by calling your findPrefix() method. The words should be in dictionary order. Note that you can use the ArrayList method add to add a character array to the end of the list.

Other points:

• For each loop that you write, you should attach an invariant in a comment. This need not be in any particular programming language, but should be precise and unambiguous.
• Your code should be as clear as possible. Ideally it should be so clear that the invariants are the only comments required.
• A normal Java program would use String rather than arrays of characters, but the aim of this coursework is to practice with arrays and algorithms. Thus you should not use String methods or the Java binarySearch method.
• My test framework will be counting uses of getWord to check that your algorithms are using it efficiently. (So don't copy the whole dictionary!) For this purpose, multiple successive accesses to the same word will count as one access (so don't mess up your code to avoid that).