QuestionQuestion

Transcribed TextTranscribed Text

Maximum Score: 388 Wordy's Search Game Current Score: 68 IN PLAY H P L x x T M A L F x Z U Y L L o E o N R W W A I A I U o o Z C H Z Y L o N U D L S R G C R E W C P G I L F H D D N B B C D T L U C A o G D V Z R T B F J N U S X U H E E J A C C Z D A B S U R D Z K E Figure 2: Some diagonal lines. Examples of ascending and descending diagonals are "HALT" and "DANCE", respectively. Classes to Implement In this assignment you must implement at least three classes (each in its own Java (.java) file): Word. java, HashChainDictionary. java, and WordSearchOperations. java. You may implement more classes if you need to. You must write all the code yourself. You cannot use code from the textbook, the Internet, or any other sources. You cannot use Java's Hashtable class or hashCode() method. Class Word This class stores the data that each entry of HashChainDictionary will contain. A Word object stores a String word, and its integer score, as explained above. Word objects represent the valid words that can be found in a given word search grid, and the score associated with the word would be the value to add to the total score if (newly) found. In a Word object, the String word and integer value score are the key and value, respectively. For this class, you must implement all and only the following public methods: public Word (String word, int score): A constructor which returns a new Word object with the specified word and its associated score. The String word will be used as the key attribute for every Word object, and integer value score is the value attribute. public String getKey (): Returns the word String stored in a Word object. public int getValue() : Returns the score stored in a Word object. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e., not accessible to other classes). Class lashChainDictionary This class implements a dictionary using a hash table with separate chaining. Important Specification: Recall that the load factor a = n/M where n is the number of elements stored in the hash table, and M is the size of the table. Your word dictionary will be 3 storing key-value records as given in words txt. Wordy requires fast operations for the program, select a prime number size for the hash table such that the load factor is very close to 0.75; a table size between 74,000 and 75,000 should work well. Use the information provided above about the number of records that will be stored in the word dictionary to determine this number. You must design your hash function SO that it produces few collisions. A bad hash function that causes many collisions will result in a lower mark. As mentioned above, you cannot use Java's hashCode() method in your hash function. For this class, you must implement all the public methods in the DictionaryADT interface: public interface DictionaryADT { public int put (Word word) throws DictionaryException public Word get (String inputWord) ; public Word remove (String inputWord) throws NoKeyException; public int size(); } Below is description of these methods. public int put (Word word) throws DictionaryException: Inserts the given Word object referenced by word into the dictionary. This method must throw a DictionaryExceptior (see Page 7) if the String stored in the Word object (its key) is already in the dictionary. You are required to implement the dictionary using a hash table with separate chaining. To determine how good your design is, we will count the number of collisions produced by your hash function. Method put must return 1 if the insertion of the Word object referenced by word produces a collision, and return 0 if no collision occurs. Recall that in separate chaining a collision occurs if T[h(k) already contains at least one element, where h(k) is your hash function with key k and the table is T; there is no collision if T[h(k) is null. public Word get (String inputWord): A method which returns the Word object with String inputWord as its key. It must return null if the word does not exist in the dictionary. public Word remove (String inputWord) throws NoKeyException: Removes the Word record with String inputWord as its key from the dictionary, and returns it. This method must throw the NoKeyException public int size( (): Returns the number of records stored in the hash table (not the size of the table). Since your lashChainDictionary class must implement all the methods of the DictionaryADT interface, the declaration of your class should be as follows: public class HashChainDictionary implements DictionaryADT You can download the file DictionaryADT java from the course website on OWL. The only other public method that you can implement in the HashChainDictionary is the constructor, which must be declared as follows public HashDictionary (int size) this initializes a dictionary with an empty hash table of the specified size. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e., not accessible to other classes). 4 Suggestion: You might want to implement a class Node storing an object of type Word and a Node reference that refers to the next node in a list, to construct the linked list associated with an entry of the hash table. You do not need to follow this suggestion. You can implement the lists associated with the entries of the table in any way you want. Class WordSearchOperations This class implements all the support methods needed by Wordy's Search Game to find new words, store the bank of words, and information about the game such as the grid of letters and the maximum score. The constructor for this class must be as follows: public VordSearchOperations (String fileName, String wordTextFile) throws IOException, DictionaryException 16 A de - X FELINE CANINE Maximum Score: 374 Wordy's Search Game 6 BFNYZW Current Score: 0 IN PLAY OOOCRE B F E L I N E NONEYZ ENTERE C A N I N E FELINE CANINE B F N Y Z W 10 BONE 6 11 LINE o o o C R E 12 NINE 13 NONE N o N E Y Z 14 FANCY 15 ENTER E N T E R E 16 Figure 3: How input file fileName relates to the wordsearch game. (A) indicates the dimension of the letter grid, (B) are the letters, and (C) is the word list of words that can be found in the game; your constructor must store the maximum score by summing the values of the scores for these words. For example, the maximum score for this list of hidden words (top to bottom) is 51 + 46 + 36+ 40+42+48+49+62= 3' The first parameter is the text file that stores the game data, and the second parameter is the text file storing all the potential words for the word bank and their scores. First, your constructor should create a dictionary, read each word and score per line from the text file wordTextFile and place these as Word objects into the dictionary. Next, read text file fileName and store the grid size gridSize, and the gridSize by gridSize grid {two-dimensional array) of letters, each letter is stored as a String. Before closing the second file, you must read a list of words that can be found in the game to compute the maximum score possible for the game; remember that your word dictionary should contain all these words. See Figure 3 for more details on the format of the input file fileName. You can assume the input file provided does not contain errors. Finally you should create a second dictionary to store the words found by the game SO far (you can decide the size of this hash table, the found words list is assumed to be small; a prime number between 70 to 100 should suffice). Notice that our constructor throws IOException and Dictionary Exception; you do not need to throw any exceptions in your method, any exceptions thrown by these two exceptions will be caught by the code provided to you. 5 The class WordSearchOperations should have (at minimum) instance variables for the grid of letters (a two-dimensional array letters), the grid size/dimension (an integer, gridSize), the maximum score possible (an integer, maxScore), and two dictionaries (the word dictionary, dict, found word dictionary, foundWords). You must also implement the following public methods for the WordSearchOperations class: public int getNumWordsFound (): Return the number of words found SO far during playtime. public int getSize() Return the grid size (dimension) of the letter grid (e.g. in Figure 3, this would return 6). public int getMaxScore(): Returns the maximum score for the game being played. This is used by the WordSearch class to determine if the game should finish or not. public String getLetter (int i, int j): Returns the letter on row i and column J in the grid, the String letters [i] [j]. In addition, there are three methods below. For the game to function properly, we need methods to check for if words are found in a String, to find words in a line, and to update the found word dictionary that should return the new words found. This involves manipulating many Strings, and lists of different lengths that are subject to frequent change. To make things less convoluted for you, we will make use of ArrayLists, an implementation of a resizable array in Java. In all three methods below, you will likely need at least one new ArrayList. Let us now describe each of the remaining methods. ArrayList<word> checkWords (String string) : Given a String string, you will return an ArrayList containing Word objects (in no particular order), each corresponding to valid words in the dictionary that are substrings of string. Remember that all valid words have at least four letters, but no more than seven letters. For example, if we were given the String "FISHBED", it should return an ArrayList containing the Word objects from the word dictionary for "FISH" and "FISHBED". You must check all possible substrings for valid words. FISHBED FISHBED FISHBED FISHBED FISHBED FISHBED FISHBED FISHBED FISHBED FISHBED ArrayList<word> findWords (String line) : Given a String line corresponding to a line of actively selected or currently used letters in the game grid, return the Array List of containing all words found within line (in no particular order). Inactive/unselected letters on a line are represented by blank spaces. To split a String on multiple blank spaces, use 6 </word></word>String wordStrings = line.split("\\s+"); This method should use checkWords as a subroutine. For example, if the String given is (periods indicating blank spaces) LNOMADIC, it should return an ArrayList of Word objects containing the the words "NOMAD" and "NOMADIC". Keep in mind that there might be multiple words separated by (possibly multiple) blank spaces, SO make sure you check each one. You can assume that a line of letters is given to you in the correct order. NOTE: This method only is executed by the main program when it detects a line of at least four letters. ArrayList<word> updateWordList (ArrayList<wor words)="" throws="" dictionaryl="" exception:<br="">Given an ArrayList of words, put all the newly found words (i.e. words not existing yet in the found words dictionary) from words into the found word dictionary, and return an ArrayList containing the Word objects for all the newly found words (in no particular order); keep in mind that the ArrayList words will often contain words already found during playtime. Do not handle the DictionaryException inside your method, you may assume the code pro- vided to you will handle the DictionaryException; your code should not actually throw the exception. Tip: When manipulating the word dictionary, you should only need to use put and get operations. For example, if words=CANDY, FISH but the found word dictionary already contains "CANDY", only put "FISH" into the found word dictionary, and the ArrayList returned by the method should only contain the Word object for "FISH". 7 </wor></word>

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/**
* LineData stores data for a line, this is used by the WordSearch class.
* @author
* @date
*/
public class LineData{
/**
* A String associated with a line.
*/
private String lineText;

/**
* The positions associated with a line in the grid/board.
*/
private GridPosition[] positions;

/**
* The number of positions in the row.
*/
private int size;

/**
* Constructor
* @param length - size of grid/board.
*/
public LineData(int length){
lineText=null;
positions = new GridPosition[length];
size=0;
}

/**
* To add a new position in the grid/board for a line.
* @param x - a row number
* @param y - a column number
*/
public void addPosition(int x, int y){
GridPosition pos = new GridPosition(x,y,"");
positions[size] = pos;
size++;
}

/**
* Same as addPosition, but adds them in reverse. Used by one of the line cases.
* @param x - a row number
* @param y - a column number
*/
public void addPositionRev(int x, int y){
GridPosition pos = new GridPosition(x,y,"");
size++;
positions[positions.length - size] = pos;
}

/**
* Get the number of elements so far in the line
* @return size
*/
public int getSize(){
return size;
}

/**
* Grab the GridPosition data
* @param pos - a position in the array storing the positions.
* @return a GridPosition object at position pos.
*/
public GridPosition getPosition(int pos){
return positions[pos];
}

/**
* Set the GridPosition object for position pos.
* @param pos - an integer
* @param gPos - a GridPosition object.
*/
public void setPosition(int pos...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$45.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats