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);



	}



	
}

Don't have time to give it a really going-over right now, but I do see some nested loops. That's always a good place to look for time sinks - but don't just start optimizing them, check them out first.
You can make some simple profile scaffolding by declaring a counter for each of those loops and incrementing it each time you enter. That'll tell you at least how many times each executes, which is a start.

If you want to examine the time spent, use the system time to total time spent in each loop (check system time at the start and at the end of the loop, and keep a tally of the total).

If your program is spending the bulk of its time in one or two of these inner loops, that'll be a good place to look for optimizing.

Jon Bentley has a nice article on profiling in his second volume of Programming Pearls - it's all about C and awk, but it's pretty timeless stuff.

Edited 5 Years Ago by jon.kiparsky: n/a

You may also want to turn verbose garbage collection on and see how much time the program is spending collecting garbage. If it's a lot, it could indicate that your java heap is too low. (It's adjustable, just google java garbage collection and heap size adjustment).

If you are using Eclipse for your IDE, there are a number of profiler plug-ins available (some free, some not so free) that can help you find where the program is spending its time, memory usage, etc. I'm sure the same is true for NetBeans and IntelliJ, but I'm not positive about that.

Profiling wouldn't help on a bad algorithm, and this is the case here I am afraid. The code tries pretty much all chains on a grid, to match each against every dictionary word. Obviously most of the efforts is wasted.
My recommendation is to turn the table around, and instead try to fit dictionary words into the grid. This way you will prune the barren chains early. Most important is to preprocess the dictionary into a proper structure - take look at PATRICIA tree for example.

Could you show me what you mean by turning the table around? I think I understand what your saying, just not sure how to go about doing it.

Assuming that the dictionary is preprocessed into a tree, do something like this:

do_square(square, node):
    if node is null,
        return success, dictionary word found
    if letter in the square exist at the current node,
        select subtree corresponding to the letter
        for all neighbours
            do_square(neighbour, subtree)
    else
        return failure

I skipped a lot, especially bookkeeping, tracing the path, etc, etc, but you should get the basic idea.

Edited 5 Years Ago by nezachem: n/a

In the program, I had all the words loaded into a hash table, I think that should be efficient enough for now unless that is causing this problem. It's the traversing the matrix part efficiently that's got me confused when thinking of how I should implement it. I'll take a look at what you mentioned but I guess I'll have to think for a while and draw it on paper.

I guess what I'm trying to sort out first is, basically how efficient can I get it with what I have now using a hash table? I'm pretty sure it's not the hash table that's causing this, it's the worthless checks for all possible words in the grid that are not dictionary words.

Once I get it to an acceptable efficiency then I'll experiment using different data structure like a trie or search tree ect. I think the hash table or a trie are my best bets though.

I just need a better recursive function that checks the adjacent squares (and marks ones already checked to prevent looping ect.)

Edited 5 Years Ago by charchar88: n/a

> it's the worthless checks for all possible words in the grid that are not dictionary words

Correct. That's why I suggest to let the dictionary drive the search.

This article has been dead for over six months. Start a new discussion instead.