DO NOT USE MAP, HASHMAP, HASHSET, BUFFERED READER, OR ANY PACKAGES. TRY TO USE F
ID: 3817778 • Letter: D
Question
DO NOT USE MAP, HASHMAP, HASHSET, BUFFERED READER, OR ANY PACKAGES. TRY TO USE FILE READER or FILE IO ONLY PLEASE!
Objective:
Write a java program that takes a 5x5 array of characters and detects how many words, 2 to 5 letters in length, can be found. From each letter it is possible to reach every other neighboring letter, but each letter at a given location can only be used once. Check each combination of letters against this simple dictionary file. Use depth first search.
dictionary file:
https://cse.sc.edu/~shephejj/csce146/Homework/WordFindingGame_files/dict.txt
Example:
Example Dialog:
Your Code's Output Should Look Identical:
R A H J M
Y U W W K
R X N F M
Q G E E B
E O A P E
Starting 0 0
Found Word: RAY
Found Word: RAW
Found Word: RUN
Found Word: RUNWAY
Found Word: RUNG
Found Word: RUNGE
Found Word: RUNGE
Found Word: RUNE
Found Word: RUNE
Starting 0 1
Found Word: AR
Found Word: AH
Found Word: AWN
Starting 0 2
Found Word: HA
Found Word: HAY
Found Word: HAW
Found Word: HUN
Found Word: HUNG
Found Word: HUNGRY
Starting 0 3
Starting 0 4
Starting 1 0
Found Word: YAH
Found Word: YAW
Found Word: YAWN
Found Word: YUH
Starting 1 1
Found Word: URGE
Found Word: URGE
Found Word: UN
Starting 1 2
Found Word: WA
Found Word: WAR
Found Word: WARY
Found Word: WAH
Found Word: WAY
Found Word: WU
Starting 1 3
Starting 1 4
Starting 2 0
Found Word: RUN
Found Word: RUNWAY
Found Word: RUNG
Found Word: RUNGE
Found Word: RUNGE
Found Word: RUNE
Found Word: RUNE
Starting 2 1
Starting 2 2
Found Word: NU
Found Word: NW
Found Word: NW
Found Word: NE
Found Word: NEE
Found Word: NEAP
Found Word: NE
Found Word: NEE
Found Word: NEAP
Found Word: NEE
Starting 2 3
Found Word: FM
Found Word: FE
Found Word: FEE
Found Word: FE
Found Word: FEE
Found Word: FEB
Found Word: FEE
Starting 2 4
Found Word: ME
Found Word: MEN
Found Word: MENU
Starting 3 0
Starting 3 1
Found Word: GNU
Found Word: GE
Found Word: GENE
Found Word: GEE
Found Word: GE
Found Word: GO
Found Word: GOA
Found Word: GA
Found Word: GAO
Found Word: GAP
Found Word: GAPE
Found Word: GAPE
Found Word: GAPE
Starting 3 2
Found Word: EX
Found Word: EN
Found Word: ENG
Found Word: EGO
Found Word: EPA
Starting 3 3
Found Word: EN
Found Word: ENG
Found Word: EM
Found Word: EPA
Starting 3 4
Found Word: BMW
Found Word: BE
Found Word: BEN
Found Word: BEE
Found Word: BEEN
Found Word: BEEF
Found Word: BEEP
Found Word: BEE
Found Word: BEEP
Found Word: BP
Found Word: BE
Found Word: BEE
Found Word: BEEN
Found Word: BEEF
Found Word: BEEP
Starting 4 0
Found Word: EGO
Starting 4 1
Starting 4 2
Found Word: AGE
Found Word: AGEE
Found Word: AGE
Found Word: AGO
Found Word: APE
Found Word: APEX
Found Word: APE
Found Word: APE
Starting 4 3
Found Word: PEN
Found Word: PENURY
Found Word: PENURY
Found Word: PEG
Found Word: PEE
Found Word: PEA
Found Word: PEN
Found Word: PENURY
Found Word: PENURY
Found Word: PEE
Found Word: PEA
Found Word: PEE
Found Word: PA
Found Word: PAGE
Found Word: PAGE
Found Word: PEE
Starting 4 4
Found Word: EBEN
Found Word: EPA
RI, H J M YUWWK RXNFM QGEEB EOAPE RAHJM WWK XNFM QG'EEB EOAPE MKMBE RYRQE QEExplanation / Answer
WordFinder.java
// please make sure you have dict.txt containing mentioned dict in the same directory from where you are executing code
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class WordFinder {
private static Map<String, Integer> dict = new HashMap<>();
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() >=2 && dict.containsKey(word.toLowerCase());
}
// A recursive function to print all words present on boggle
public static void findWordsUtil(char board[][], boolean visited[][], int i,
int j, String str)
{
// Mark current cell as visited and append current character
// to str
visited[i][j] = true;
if (str.length() == 5)
{
return;
}
str = str + board[i][j];
// If str is present in dictionary, then print it
if (isWord(str))
System.out.println("Found Word: " + 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(char 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++)
{
System.out.println("Starting " + i + " " + j);
findWordsUtil(board, visited, i, j, str);
}
}
}
// Driver program to test above function
public static void main(String[] args) throws FileNotFoundException
{
readDict("dict.txt");
char board[][] = {{'R','A','H', 'J', 'M'},
{'Y','U','W', 'W', 'K'},
{'R','X','N', 'F', 'M'},
{'Q','G','E', 'E', 'B'},
{'E','O','A', 'P', 'E'}};
findWords(board);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.