This game is like the game scramble that you play on facebook. Also similar to boggle. Basically you input the dimension of the grid of letters that you want and the dictionary.txt file and it will print you all the words found. It's suppose
to find words in all directions as long as the letters are adjacent to each other.
My program below works, but It's extremely slow beyond a grid of 4x4. If I keep the word dictionary to 6 letter words max, it can do decent on time, I've solved a 32x32 in about 8 minutes if you just use a 6 letter dictionary. However Most dictionaries have large words and when I try to use a larger one, this program takes forever and I always have to kill it. How can I make this as efficient as possible? Where are the bottlenecks in this program? I plan to play with it some more myself when I have time but I don't for the next week or two. Can anyone help me out?
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;
import java.util.Scanner;
public class Scramble {
/*
* Defined fields and the constructor initializing them.
*/
int N; // Array size
int iterations; //number of iterations
int numwords; //number of words found
int maxlength; //biggest word in the dictionary
int dictionarySize; //total number of words in the dictionary
long beginTime; //Start time of search
long endTime; // End time of search
long totalTime; // The difference of start time and end time
long beginTimenano;
long endTimenano;
long totalTimenano;
Random random;
String[] randomLetter; //Array to hold 26 random generated letters
String [][] grid;
private Hashtable<String, Boolean> dictionary;
ArrayList<String> foundWords;
String[] newChars = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
"n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
};
public Scramble(int N)
{
this.N = N;
iterations = 0;
numwords = 0;
maxlength = 0;
dictionarySize = 0;
grid = new String[N][N];
randomLetter = new String[26];
random = new Random();
dictionary = new Hashtable<String, Boolean>();
foundWords = new ArrayList<String>();
loadDictionary();
randomize();
solve();
}
// Intializes the search method and displays the results
public void solve()
{
System.out.println("Size of dictionary: " + dictionarySize + " words");
System.out.println("Biggest word in dictionary: " + maxlength + " letters" +" \n");
System.out.print("Computing...." + "\n");
Search(this.foundWords);
System.out.println("Done!" + "\n");
System.out.println("Results: " + "\n");
System.out.println("Number of iterations : " + iterations);
System.out.println("Number of words found: " + numwords + "\n");
System.out.println("The words found are: " + "\n");
System.out.println(foundWords + "\n");
System.out.print("Search Time elapsed: " + totalTime + " miliseconds" + "\n");
System.out.print("Search Time elapsed in nanoseconds: " + totalTimenano + " nanoseconds" + "\n");
}
// Sets up a random array of letters.
public void randomize()
{
this.foundWords.clear();
// go through the array of newChars and populate grid with random letters
for (int row = 0; row < grid.length; row++)
{
for (int col = 0; col <grid[row].length; col++)
{
int r = random.nextInt(26);
grid[row][col] = newChars[r];
}
}
//print the array
System.out.println("Here's a randomly generated array ");
System.out.println(" ");
for(int row2 = 0; row2 < grid.length; row2++)
{
for(int col2 = 0; col2 < grid[row2].length; col2++)
{
System.out.print(grid[row2][col2]+ " ");
}
System.out.println();
}
System.out.println();
}
/*
* Searches the array by iterating through the letter grid using the SearchHelper function.
* Also measures the time.
*/
public void Search(ArrayList<String> list)
{
beginTime = System.currentTimeMillis();
beginTimenano = System.nanoTime();
for (int i = 0; i < this.N; i++)
{
for (int j = 0; j < this.N; j++)
{
SearchHelper(i, j, "", new boolean[this.N][this.N], list);
}
}
endTime = System.currentTimeMillis() ;
endTimenano = System.nanoTime();
totalTime = endTime - beginTime;
totalTimenano = endTimenano - beginTimenano;
}
/*
* The Search algorithm that recursively searches through the array.
* num1 and num2 correspond to i and j from the Search method.
* word is the string of letters to be searched in the dictionary.
* hasVisited keeps track of already visited indices
*
*/
public void SearchHelper(int num1, int num2, String word, boolean[][] hasVisited, ArrayList<String> list )
{
// Don't go past the bounds of the array
if((num1 < 0) || (num1 >= N))
{
return;
}
if ((num2 < 0) || (num2 >= N))
{
return;
}
// Change any upper case letters to lower case
word = word.toLowerCase();
// Don't bother with already covered indices
if(hasVisited[num1][num2] != false)
{
return;
}
// Append the letters
word = word + this.grid[num1][num2];
//If the word matches one found in the dictionary, add it to the list of words found.
if (checkWord(word, list))
{
numwords++;
list.add(word);
}
//At this point, mark that the index has been visited.
hasVisited[num1][num2] = true;
//Iterates through the grid of letters by visiting every adjacent letter.
for(int j = -1; j <= 1; j++)
{
for(int i = -1; i <= 1; i++)
{
if ((i == 0) && (j == 0))
{
continue;
}
//However, search for words only less than or equal to the biggest word in the dictionary.
if (word.length() <= maxlength )
{
SearchHelper(num1 + i, num2 + j, word, hasVisited, list );
}
}
}
//Mark the index as unvisited for the next word.
hasVisited[num1][num2] = false;
}
/*
* Compares the word from the letter grid to a word pulled from the dictionary.
*/
public boolean checkWord(String word, ArrayList<String> list)
{
iterations++;
//Don't bother checking words less than 3 letters long.
if(word.length() < 3)
{
return false;
}
//Set a boolean value to check if a word is null or it's not in the list since we're ignoring null words
//and those that are already in the list.
Boolean bool = (Boolean)this.dictionary.get(word);
return (bool != null) && (!list.contains(word));
}
/*
* Loads words from the dictionary text file entered onto the console. It puts the words into the dictionary
* Hashtable and throws an error if the dictionary file isn't found.
*/
public void loadDictionary()
{
String filename = new String();
try
{
Scanner in = new Scanner(System.in);
System.out.println("Enter the name of the txt file: ");
filename = in.next();
BufferedReader Dstream = new BufferedReader(new FileReader(filename));
while(Dstream.ready())
{
String str = Dstream.readLine();
//Ignores spaces and gaps in the file
if((str == null) || (str.length() <= 0))
{
continue;
}
this.dictionary.put(str, new Boolean(true));
//Adjusts max word length to the biggest word found in the dictionary.
if (str.length() > this.maxlength)
{
this.maxlength = str.length();
}
// Logs the number of words that were in the dictionary.
dictionarySize = dictionary.size();
}
}
catch (IOException localIOException)
{
System.out.println("Error: " + filename + " not loaded.");
}
}
//Sets up the program.
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n;
System.out.println("Enter the NxN dimension of the array: ");
n = in.nextInt();
Scramble test1 = new Scramble(n);
}
}