DO NOT USE MAP, HASHMAP, HASHSET. TRY TO USE FILE READER or FILE IO ONLY PLEASE!
ID: 3817732 • Letter: D
Question
DO NOT USE MAP, HASHMAP, HASHSET. 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
package com.cheggtest;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
public class DictionaryEntryTest {
public int[] letters;
public int[] triplets;
}
class BoggleSolverTest {
final int ALPHABET_SIZE = 5; // up to 2^5 = 32 letters
final int BOARD_SIZE = 4; // 4x4 board
final int[] moves = { -BOARD_SIZE - 1, -BOARD_SIZE, -BOARD_SIZE + 1, -1,
+1, +BOARD_SIZE - 1, +BOARD_SIZE, +BOARD_SIZE + 1 };
DictionaryEntryTest[] dictionary; // Processed word list
int maxWordLength = 0;
int[] boardTripletIndices; // List of all 3-letter moves in board
// coordinates
DictionaryEntryTest[] buildDictionary(String fileName) throws IOException {
BufferedReader fileReader = new BufferedReader(new FileReader(fileName));
String word = fileReader.readLine();
ArrayList<DictionaryEntryTest> result = new ArrayList<DictionaryEntryTest>();
while (word != null) {
if (word.length() >= 3) {
word = word.toUpperCase();
if (word.length() > maxWordLength)
maxWordLength = word.length();
DictionaryEntryTest entry = new DictionaryEntryTest();
entry.letters = new int[word.length()];
entry.triplets = new int[word.length() - 2];
int i = 0;
for (char letter : word.toCharArray()) {
entry.letters[i] = (byte) letter - 65; // Convert ASCII to
// 0..25
if (i >= 2)
entry.triplets[i - 2] = (((entry.letters[i - 2] << ALPHABET_SIZE) + entry.letters[i - 1]) << ALPHABET_SIZE)
+ entry.letters[i];
i++;
}
result.add(entry);
}
word = fileReader.readLine();
}
return result.toArray(new DictionaryEntryTest[result.size()]);
}
boolean isWrap(int a, int b) { // Checks if move a->b wraps board edge (like
// 3->4)
return Math.abs(a % BOARD_SIZE - b % BOARD_SIZE) > 1;
}
int[] buildTripletIndices() {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int a = 0; a < BOARD_SIZE * BOARD_SIZE; a++)
for (int bm : moves) {
int b = a + bm;
if ((b >= 0) && (b < board.length) && !isWrap(a, b))
for (int cm : moves) {
int c = b + cm;
if ((c >= 0) && (c < board.length) && (c != a)
&& !isWrap(b, c)) {
result.add(a);
result.add(b);
result.add(c);
}
}
}
int[] result2 = new int[result.size()];
int i = 0;
for (Integer r : result)
result2[i++] = r;
return result2;
}
// Variables that depend on the actual game layout
int[] board = new int[BOARD_SIZE * BOARD_SIZE]; // Letters in board
boolean[] possibleTriplets = new boolean[1 << (ALPHABET_SIZE * 3)];
DictionaryEntryTest[] candidateWords;
int candidateCount;
int[] usedBoardPositions;
DictionaryEntryTest[] foundWords;
int foundCount;
void initializeBoard(String[] letters) {
for (int row = 0; row < BOARD_SIZE; row++)
for (int col = 0; col < BOARD_SIZE; col++)
board[row * BOARD_SIZE + col] = (byte) letters[row].charAt(col) - 65;
}
void setPossibleTriplets() {
Arrays.fill(possibleTriplets, false); // Reset list
int i = 0;
while (i < boardTripletIndices.length) {
int triplet = (((board[boardTripletIndices[i++]] << ALPHABET_SIZE) + board[boardTripletIndices[i++]]) << ALPHABET_SIZE)
+ board[boardTripletIndices[i++]];
possibleTriplets[triplet] = true;
}
}
void checkWordTriplets() {
candidateCount = 0;
for (DictionaryEntryTest entry : dictionary) {
boolean ok = true;
int len = entry.triplets.length;
for (int t = 0; (t < len) && ok; t++)
ok = possibleTriplets[entry.triplets[t]];
if (ok)
candidateWords[candidateCount++] = entry;
}
}
void checkWords() { // Can probably be optimized a lot
foundCount = 0;
for (int i = 0; i < candidateCount; i++) {
DictionaryEntryTest candidate = candidateWords[i];
for (int j = 0; j < board.length; j++)
if (board[j] == candidate.letters[0]) {
usedBoardPositions[0] = j;
if (checkNextLetters(candidate, 1, j)) {
foundWords[foundCount++] = candidate;
break;
}
}
}
}
boolean checkNextLetters(DictionaryEntryTest candidate, int letter, int pos) {
if (letter == candidate.letters.length)
return true;
int match = candidate.letters[letter];
for (int move : moves) {
int next = pos + move;
if ((next >= 0) && (next < board.length) && (board[next] == match)
&& !isWrap(pos, next)) {
boolean ok = true;
for (int i = 0; (i < letter) && ok; i++)
ok = usedBoardPositions[i] != next;
if (ok) {
usedBoardPositions[letter] = next;
if (checkNextLetters(candidate, letter + 1, next))
return true;
}
}
}
return false;
}
// Just some helper functions
String formatTime(long start, long end, long repetitions) {
long time = (end - start) / repetitions;
return time / 1000000 + "." + (time / 100000) % 10 + ""
+ (time / 10000) % 10 + "ms";
}
String getWord(DictionaryEntryTest entry) {
char[] result = new char[entry.letters.length];
int i = 0;
for (int letter : entry.letters)
result[i++] = (char) (letter + 97);
return new String(result);
}
void run() throws IOException {
long start = System.nanoTime();
// The following can be pre-computed and should be replaced by constants
dictionary = buildDictionary("C:/TWL06.txt");
boardTripletIndices = buildTripletIndices();
long precomputed = System.nanoTime();
// The following only needs to run once at the beginning of the program
candidateWords = new DictionaryEntryTest[dictionary.length]; // WAAAY
// too
// generous
foundWords = new DictionaryEntryTest[dictionary.length]; // WAAAY too
// generous
usedBoardPositions = new int[maxWordLength];
long initialized = System.nanoTime();
for (int n = 1; n <= 100; n++) {
// The following needs to run again for every new board
initializeBoard(new String[] { "DGHI", "KLPS", "YEUT", "EORN" });
setPossibleTriplets();
checkWordTriplets();
checkWords();
}
long solved = System.nanoTime();
// Print out result and statistics
System.out.println("Precomputation finished in "
+ formatTime(start, precomputed, 1) + ":");
System.out.println(" Words in the dictionary: " + dictionary.length);
System.out.println(" Longest word: " + maxWordLength
+ " letters");
System.out.println(" Number of triplet-moves: "
+ boardTripletIndices.length / 3);
System.out.println();
System.out.println("Initialization finished in "
+ formatTime(precomputed, initialized, 1));
System.out.println();
System.out.println("Board solved in "
+ formatTime(initialized, solved, 100) + ":");
System.out.println(" Number of candidates: " + candidateCount);
System.out.println(" Number of actual words: " + foundCount);
System.out.println();
System.out.println("Words found:");
int w = 0;
System.out.print(" ");
for (int i = 0; i < foundCount; i++) {
System.out.print(getWord(foundWords[i]));
w++;
if (w == 10) {
w = 0;
System.out.println();
System.out.print(" ");
} else if (i < foundCount - 1)
System.out.print(", ");
}
System.out.println();
}
public static void main(String[] args) throws IOException {
new BoggleSolverTest().run();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.