Problem Description: In this assignment, you will implement a version of a word
ID: 3739636 • Letter: P
Question
Problem Description:
In this assignment, you will implement a version of a word search game much like Boggle1 and other popular word games. The approach you take to finding words on the board will be a direct application of depth-first search with backtracking. The version of the game that you will implement is played on a square board according to the following rules. 1. Each position on the board contains one or more uppercase letters. 2. Words are formed by joining the contents of adjacent positions on the board. 3. Positions may be joined horizontally, vertically, or diagonally, and the board does not wrap around. 4. No position on the board may be used more than once within any one word. 5. A specified minimum word length (number of letters) is required for all valid words. 6. A specified lexicon is used to define the set of all legal words.
Implementation Details:
Your must implement your solution to the assignment in terms of two provided files: WordSearchGame.java and WordSearchGameFactory.java, plus one class that you create from scratch all on your own. The interface WordSearchGame describes all the behavior that is necessary to play the game. So, we can think of this interface as the specification for a game engine. You must develop your own game engine that meets this specification; that is, you must write a class that implements the WordSearchGame interface. You can name this class anything you want and you can add as many additional methods as you like. The WordSearchGameFactory is a class with a single factory method for creating game engines. You must modify the createGame method to return an instance of your class that implements the WordSearchGame interface. Factory classes like this are convenient ways of completely separating an implementation (your class) from a specification (the provided interface). So, the test suite used for grading can be written completely in terms of the interface and without any knowledge of the specific classes used in the implementation. A brief example client along with the corresponding output are given below. Although the class that implements the WordSearchGame interface must be in the same directory, the ExampleGameClient code is independent of its name or any other details of the class.
Given Code for WordSearchGame.java
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
/**
* Defines the methods needed to play a word search game.
*
* @author Dean Hendrix (dh@auburn.edu)
* @version 2018-03-22
*
*/
public interface WordSearchGame {
/**
* Loads the lexicon into a data structure for later use.
*
* @param fileName A string containing the name of the file to be opened.
* @throws IllegalArgumentException if fileName is null
* @throws IllegalArgumentException if fileName cannot be opened.
*/
void loadLexicon(String fileName);
/**
* Stores the incoming array of Strings in a data structure that will make
* it convenient to find words.
*
* @param letterArray This array of length N^2 stores the contents of the
* game board in row-major order. Thus, index 0 stores the contents of board
* position (0,0) and index length-1 stores the contents of board position
* (N-1,N-1). Note that the board must be square and that the strings inside
* may be longer than one character.
* @throws IllegalArgumentException if letterArray is null, or is not
* square.
*/
void setBoard(String[] letterArray);
/**
* Creates a String representation of the board, suitable for printing to
* standard out. Note that this method can always be called since
* implementing classes should have a default board.
*/
String getBoard();
/**
* Retrieves all valid words on the game board, according to the stated game
* rules.
*
* @param minimumWordLength The minimum allowed length (i.e., number of
* characters) for any word found on the board.
* @return java.util.SortedSet which contains all the words of minimum length
* found on the game board and in the lexicon.
* @throws IllegalArgumentException if minimumWordLength < 1
* @throws IllegalStateException if loadLexicon has not been called.
*/
SortedSet<String> getAllValidWords(int minimumWordLength);
/**
* Computes the cummulative score for the scorable words in the given set.
* To be scorable, a word must (1) have at least the minimum number of characters,
* (2) be in the lexicon, and (3) be on the board. Each scorable word is
* awarded one point for the minimum number of characters, and one point for
* each character beyond the minimum number.
*
* @param words The set of words that are to be scored.
* @param minimumWordLength The minimum number of characters required per word
* @return the cummulative score of all scorable words in the set
* @throws IllegalArgumentException if minimumWordLength < 1
* @throws IllegalStateException if loadLexicon has not been called.
*/
int getScoreForWords(SortedSet<String> words, int minimumWordLength);
/**
* Determines if the given word is in the lexicon.
*
* @param wordToCheck The word to validate
* @return true if wordToCheck appears in lexicon, false otherwise.
* @throws IllegalArgumentException if wordToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
boolean isValidWord(String wordToCheck);
/**
* Determines if there is at least one word in the lexicon with the
* given prefix.
*
* @param prefixToCheck The prefix to validate
* @return true if prefixToCheck appears in lexicon, false otherwise.
* @throws IllegalArgumentException if prefixToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
boolean isValidPrefix(String prefixToCheck);
/**
* Determines if the given word is in on the game board. If so, it returns
* the path that makes up the word.
* @param wordToCheck The word to validate
* @return java.util.List containing java.lang.Integer objects with the path
* that makes up the word on the game board. If word is not on the game
* board, return an empty list. Positions on the board are numbered from zero
* top to bottom, left to right (i.e., in row-major order). Thus, on an NxN
* board, the upper left position is numbered 0 and the lower right position
* is numbered N^2 - 1.
* @throws IllegalArgumentException if wordToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
List<Integer> isOnBoard(String wordToCheck);
}
Explanation / Answer
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
WordSearchGame game = WordSearchGameFactory.createGame();
System.out.println(game.getBoard());
game.loadLexicon("words.txt");
TreeSet<String> list = new TreeSet<String>(game.getAllValidWords(3));
System.out.println(list.size() + "");
}
}
-----------------------------------------------------------------------------------------------------
public class WordSearchGameFactory {
public static WordSearchGame createGame() {
// change this to return an instance of your game engine
return new WordSearchEngine();
}
}
--------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Scanner;
import java.util.ArrayList;
public class WordSearchEngine implements WordSearchGame{
//String fileName = null;
private TreeSet<String> lexicon = new TreeSet<String>();
private String[][] board = new String[][] {
{"E", "E", "C", "A"},
{"A", "L", "E", "P"},
{"H","N", "B", "O"},
{"Q", "T", "T", "Y"}
};
private int squareSize = 4;
private boolean lexiconCalled = false;
@Override
public void loadLexicon(String fileName) {
if(fileName == null) {
throw new IllegalArgumentException();
}
File file = new File(fileName);
Scanner s = null;
try {
s = new Scanner(file);
while(s.hasNext()) {
lexicon.add(s.next().toLowerCase());
}
} catch (FileNotFoundException e) {
throw new IllegalArgumentException();
} finally {
if(s != null) {
s.close();
}
}
//System.out.println(lexicon.size());
lexiconCalled = true;
}
@Override
public void setBoard(String[] letterArray) {
if(letterArray == null) {
throw new IllegalArgumentException();
}
double n = Math.sqrt((double) letterArray.length);
if(n == Math.round(n)) {
int n2 = (int) n;
board = new String[n2][n2];
for(int i = 0; i < n2; i++) {
for(int x = 0; x < n2; x++) {
board[i][x] = letterArray[(i*n2 + x)];
}
}
//board = Arrays.copyOf(letterArray, letterArray.length);
squareSize = n2;
}
else throw new IllegalArgumentException();
}
@Override
public String getBoard() {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < squareSize; i++) {
for(int x = 0; x < squareSize; x++) {
sb.append(board[i][x] + " ");
if(x == squareSize - 1) {
sb.append("br ");
}
}
}
String s = sb.toString();
return s;
}
@Override
public SortedSet<String> getAllValidWords(int minimumWordLength) {
if(!lexiconCalled) {
throw new IllegalStateException();
}
if(minimumWordLength < 1) {
throw new IllegalArgumentException();
}
boolean[][] visited = new boolean[squareSize][squareSize];
TreeSet<String> words = new TreeSet<String>();
for(int a = 0; a < squareSize; a++) {
for(int b = 0; b < squareSize; b++) {
getWords(minimumWordLength,a,b,"",visited,words);
}
}
return words;
}
private void getWords(int minLength, int i, int x, String str, boolean[][] vis, TreeSet<String> word) {
vis[i][x] = true;
str = str + board[i][x];
System.out.println("Current str: " + str);
System.out.println(str + "");
if(isValidWord(str) && str.length() >= minLength) {
word.add(str);
}
if(isValidPrefix(str)) {
for (int row = i-1; row <= i+1 && row < squareSize; row++) {
for (int col = x-1; col <= x+1 && col < squareSize; col++) {
if (row >= 0 && col >= 0 && !vis[row][col]) {
System.out.println("Valid Prefix");
getWords(minLength, row, col, str, vis, word);
System.out.println("Should come after valid run");
}
}
}
}
// Erase current character from string and mark visited
// of current cell as false
str = str.substring(0, str.length()-1);
vis[i][x] = false;
System.out.println("this thing got run");
}
@Override
public int getScoreForWords(SortedSet<String> words, int minimumWordLength) {
if(!lexiconCalled) {
throw new IllegalStateException();
}
if(minimumWordLength < 1) {
throw new IllegalArgumentException();
}
Iterator<String> iter = words.iterator();
int total = 0;
while(iter.hasNext()) {
String s = iter.next();
if(s.length() >= minimumWordLength && isValidWord(s) && !isOnBoard(s).isEmpty()) {
total += 1;
if(s.length() > minimumWordLength) {
total += s.length() - minimumWordLength;
}
}
}
return total;
}
@Override
public boolean isValidWord(String wordToCheck) {
wordToCheck = wordToCheck.toLowerCase();
if(wordToCheck == null) {
throw new IllegalArgumentException();
}
else if(!lexiconCalled) {
throw new IllegalStateException();
}
else if(lexicon.contains(wordToCheck)) {
return true;
}
else return false;
}
@Override
public boolean isValidPrefix(String prefixToCheck) {
prefixToCheck = prefixToCheck.toLowerCase();
System.out.println("falsefalse");
if(prefixToCheck.equals(null)) {
throw new IllegalArgumentException();
}
if(!lexiconCalled) {
throw new IllegalStateException();
}
//TreeSet<String> l = new TreeSet<String>(lexicon.tailSet(prefixToCheck));
String s = lexicon.ceiling(prefixToCheck);
System.out.println("s = " + s);
if(s.equals(null) || !s.startsWith(prefixToCheck)) {
return false;
}
else if(s.startsWith(prefixToCheck) || s.equals(prefixToCheck)) {
System.out.println("THis is working lol");
return true;
}
return false;
}
@Override
public List<Integer> isOnBoard(String wordToCheck) {
if(wordToCheck.equals(null)) {
throw new IllegalArgumentException();
}
if(!lexiconCalled) {
throw new IllegalStateException();
}
boolean[][] visited = new boolean[squareSize][squareSize];
ArrayList<Integer> list = new ArrayList<Integer>();
for(int a = 0; a < squareSize; a++) {
for(int b = 0; b < squareSize; b++) {
wordOnBoard(a,b,"",wordToCheck,visited,list);
}
}
//wordOnBoard(0,0,"",wordToCheck,visited,list);
return list;
}
private void wordOnBoard(int i, int x, String str, String found, boolean[][] vis, ArrayList<Integer> word) {
vis[i][x] = true;
str = str + board[i][x];
if(str.equals(found)) {
for(int j = 0; j < squareSize; j++) {
for(int k = 0; k < squareSize; k++) {
if(vis[j][k] == true) {
word.add(j * squareSize + k);
}
}
}
}
if(found.startsWith(str)) {
for (int row = i-1; row <= i+1 && row < squareSize; row++) {
for (int col = x-1; col <= x+1 && col < squareSize; col++) {
if (row >= 0 && col >= 0 && !vis[row][col]) {
wordOnBoard(row, col, str, found, vis, word);
}
}
}
}
// Erase current character from string and mark visited
// of current cell as false
str = str.substring(0, str.length()-1);
vis[i][x] = false;
}
private class ComparePrefix implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return 0;
}
}
}
-----------------------------------------------------------------------------------------
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
public interface WordSearchGame {
/**
* Loads the lexicon into a data structure for later use.
*
* @param fileName A string containing the name of the file to be opened.
* @throws IllegalArgumentException if fileName is null
* @throws IllegalArgumentException if fileName cannot be opened.
*/
void loadLexicon(String fileName);
/**
* Stores the incoming array of Strings in a data structure that will
* make it convenient to find words.
*
* @param letterArray This array of length N^2 stores the contents of the
* game board in row-major order. Thus, index 0 stores the contents
* of board position (0,0) and index length-1 stores the contents
* of board position (N-1,N-1). Note that the board must be square
* and that the strings inside may be longer than one character.
* @throws IllegalArgumentException if letterArray is null, or is
* not square.
*/
void setBoard(String[] letterArray);
/**
* Creates a String representation of the board, suitable for
* printing to standard out. Note that this method can always be
* called since implementing classes should have a default board.
*/
String getBoard();
/**
* Retrieves all valid words on the game board, according to the
* stated game rules.
*
* @param minimumWordLength The minimum allowed length (i.e., number
* of characters) for any word found on the board.
* @return java.util.SortedSet which contains all the words of minimum
* length found on the game board and in the lexicon.
* @throws IllegalArgumentException if minimumWordLength < 1
* @throws IllegalStateException if loadLexicon has not been called.
*/
SortedSet<String> getAllValidWords(int minimumWordLength);
/**
* Computes the cummulative score for the scorable words in the given set.
* To be scorable, a word must (1) have at least the minimum number of characters,
* (2) be in the lexicon, and (3) be on the board. Each scorable word is
* awarded one point for the minimum number of characters, and one point for
* each character beyond the minimum number.
*
* @param words The set of words that are to be scored.
* @param minimumWordLength The minimum number of characters required per word
* @return the cummulative score of all scorable words in the set
* @throws IllegalArgumentException if minimumWordLength < 1
* @throws IllegalStateException if loadLexicon has not been called.
*/
int getScoreForWords(SortedSet<String> words, int minimumWordLength);
/**
* Determines if the given word is in the lexicon.
*
* @param wordToCheck The word to validate
* @return true if wordToCheck appears in lexicon, false otherwise.
* @throws IllegalArgumentException if wordToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
boolean isValidWord(String wordToCheck);
/**
* Determines if there is at least one word in the lexicon with the
* given prefix.
*
* @param prefixToCheck The prefix to validate
* @return true if prefixToCheck appears in lexicon, false otherwise.
* @throws IllegalArgumentException if prefixToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
boolean isValidPrefix(String prefixToCheck);
/**
* Determines if the given word is in on the game board. If so,
* it returns the path that makes up the word.
*
* @param wordToCheck The word to validate
* @return java.util.List containing java.lang.Integer objects with
* the path that makes up the word on the game board. If word
* is not on the game board, return an empty list. Positions on the board are
* numbered from zero top to bottom, left to right (i.e., in row-major
* order). Thus, on an NxN board, the upper left position is numbered
* 0 and the lower right position is numbered N^2 - 1.
* @throws IllegalArgumentException if wordToCheck is null.
* @throws IllegalStateException if loadLexicon has not been called.
*/
List<Integer> isOnBoard(String wordToCheck);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.