THE DICTIONARY HAS TO BE HARD CODED INTO THE PROGRAM, YOU CANNOT INPUT THE .TXT
ID: 3825651 • Letter: T
Question
THE DICTIONARY HAS TO BE HARD CODED INTO THE PROGRAM, YOU CANNOT INPUT THE .TXT FILE
PROGRAM NEEDS TO USE A HUERISTIC BY FIRST ADDING DICTIONARY INTO A TREEMAP
ONLY WORDS OF LENGTH 3 or MORE ARE TO BE OUTPUTTED
Solving the game of Boggle can be done elegantly with recursion and backtracking. Backtracking is a technique whereby an algorithm recognizes it is impossible or unnecessary to search any deeper into the search space from a given point. An example of this is finding your way through a maze. When you hit a dead end you mark that last step as a dead end and avoid going down that path. A fast and efficient solution to Boggle requires a hueristic that helps you recognize a dead end and save vast amounts of wasted searches (and thus vast amounts of time).
Boggle is a board game that uses 16 dice arranged in a 4 x 4 grid. There is also a 5x5 version. Each die has 6 faces with a letter of the alphabet on it. Occasionally the string "Qu" will appear on a dice face. A typical board might look like this.
The Assignment
Your program MUST produce exactly the same output my solution produces on each boggle input file. You are to hard code the dictionary.txt filename somewhere inside your program and always load that file as your dictionary of legal words. For this assignment there is only one dictionary file we will ever use. So, go ahead and hard code the "dictionary.txt" filename in your code. Your program should be executed as follows:
The only output is to be the real dictionary words you found in the grid. One word per line. No other output of any kind. The words must be unique, no duplicates and they must appear in sorted order ascending from top to bottom. Please see my correct output files below and make sure your solution has the same exact words as mine.
dictionary.txt 172822 words. Your reference dictionary
INPUT FILES TO RUN YOUR SOLUTION ON
A good solution will find all the dictionary words in the grid in under 1/4 of a second from the time the program started running till it printed out the last valid word to the screen.
4x4-board.txt:
all real dictionary words you should find -> 4x4-board-output.txt
http://people.cs.pitt.edu/~hoffmant/S17-401/project-10/4x4-board-output.txt
5x5-board.txt:
all real dictionary words you should find -> 5x5-board-output.txt:
http://people.cs.pitt.edu/~hoffmant/S17-401/project-10/5x5-board-output.txt
10x10-board.txt:
all real dictionary words you should find -> 10x10-board-output.txt
http://people.cs.pitt.edu/~hoffmant/S17-401/project-10/10x10-board-output.txt
HERE IS A GOOD PSEUDO CODE OUTLINE:
The links will take you to the outputs that have to match the code that is ran. It would have been to long to post all the words. A regular dictionary is to be hard coded into the program that contains every word in a reference dictionary that will be used to find all the words that are in each boggle game.
Explanation / Answer
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
//please make sure you have dict.txt containing mentioned dict in the same directory from where you are executing code
public class WordFinder2 {
private static Map<String, Integer> dict = new TreeMap<>();
public static void readDict(String filename) throws FileNotFoundException
{
FileReader fr = new FileReader(filename);
Scanner sc = new Scanner(fr);
while(sc.hasNext())
{
dict.put(sc.next().toLowerCase(), 1);
}
sc.close();
}
// A given function to check if a given string is present in
// dictionary.
public static boolean isWord(String word)
{
return word.length() >=3 && dict.containsKey(word.toLowerCase());
}
public static List<String> foundWordList = new ArrayList<>();
// A recursive function to print all words present on boggle
public static void findWordsUtil(String board[][], boolean visited[][], int i,
int j, String str)
{
// Mark current cell as visited and append current character
// to str
if (visited[i][j])
return;
if(str.length() >= 10)
return;
visited[i][j] = true;
str = str + board[i][j];
// If str is present in dictionary, then print it
if (isWord(str))
{
if (!foundWordList.contains(str))
foundWordList.add(str);
//System.out.println(str);
}
int M = board.length;
int N = board[0].length;
// Traverse 8 adjacent cells of boggle[i][j]
for (int row=i-1; row<=i+1 && row<M; row++)
{
for (int col=j-1; col<=j+1 && col<N; col++)
{
if (row>=0 && col>=0 && !visited[row][col])
findWordsUtil(board,visited, row, col, str);
}
}
// Erase current character from string and mark visited
// of current cell as false
if (str != null && str.length() > 0 ) {
str = str.substring(0, str.length()-1);
}
visited[i][j] = false;
}
// Prints all words present in dictionary.
public static void findWords(String board[][])
{
int M = board.length;
int N = board[0].length;
// Mark all characters as not visited
boolean visited[][] = new boolean[M][N];
// Initialize current string
String str = "";
// Consider every character and look for all words
// starting with this character
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
{
findWordsUtil(board, visited, i, j, str);
}
}
}
// Driver program to test above function
public static void main(String[] args) throws FileNotFoundException
{
readDict("dictionary.txt");
FileReader fr = new FileReader(args[0]);
Scanner sc = new Scanner(fr);
int n = Integer.parseInt(sc.nextLine());
String board[][] = new String[n][n];
int i = 0;
while(sc.hasNextLine())
{
String[] parts = sc.nextLine().split("\s+");
board[i++] = parts;
}
sc.close();
findWords(board);
Collections.sort(foundWordList);
for(String word : foundWordList)
System.out.println(word);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.