Finding all possibilities in word search game

Question

i have this boggle-type game that I've written in Java. It works fine, there isn't anything wrong, but i would like to add a feature that when the game ends (by the timer reaching 0, or user entering 0 to exit to main menu) the system will calculate all the possible words that you could have found. I have a method here, which is what is used to search the 10x10 grid of letters to find a match to what the user enters.

   public class FinalProjectBogel {

 static private BufferedReader br = new BufferedReader (newInputStreamReader(System.in),1);
boolean timeUp = true;
boolean notValid = true;

Toolkit toolkit;
Timer timer;
sortLib sl = new sortLib();

public FinalProjectBogel() throws IOException
{
    toolkit = Toolkit.getDefaultToolkit();
    timer = new Timer();     //Creates new timer       

   // CREDITS
   System.out.println("");
   System.out.println("BOGEL ®");
   System.out.println("Created by George Ondi and Kirkland Clive Douglas");
   //Edited by Alan Kwok
   System.out.println("");
//________________________________________________________________________________________
// MAIN MENU
//________________________________________________________________________________________
   for (int ctrloop = 0; 0 < 1; ctrloop--)//Endless loop for main menu
   {
        System.out.println("");
        System.out.println("Enter one of the following numeric options to initiate the corresponding command.");
        System.out.println("");
        System.out.println("1  Commence Game");
        System.out.println("2  Rules");
        System.out.println("3  View Highscores");
        System.out.println("4  Exit");
        System.out.println("");
//________________________________________________________________________________________
// TIMER / GAMEBOARD
//________________________________________________________________________________________
        int userCmd = Keyboard.readInt();//Gets input from user for the main menu
        System.out.println("");

        if (userCmd==1)//Runs the game it self
        {
                timer.schedule(new RemindTask(),0,1*1000);  // start timer

                int score = 0;//Where your points are scored

                char table[][] = new char[10][10]; //Creates the array for the 10x10 grid
                int ctr = 0;
                char c;
                Random r = new Random();//for the random characters

                for (int x = 0; x < 10; x++)
                {
                    for (int y = 0; y < 10; y++)
                    {
                         table[x][y] = (char)(r.nextInt(26) + 'a');//creates random characters
                    }
                }   
                for (int x = 0; x < 10; x++)
                {
                    for (int y = 0; y < 10; y++)
                    {
                        System.out.print("|" + table[x][y] + "|");//creats the grid and the lines between the letters
                    }
                    System.out.println("");
                }
                System.out.println("Enter words that appear horizontally, vertically.");
                System.out.println("- Enter 0 to return to main menu.");
                String userInput = Keyboard.readString();//User input for the word search
               // System.out.println(userInput);
                String[] wordStorage = new String[50];//creats array for words you enter. this is where they are stored then later compared with.
                int size = 0;//for keeping track of array size
                boolean Flag = false;
//________________________________________________________________________________________
//  EXITING TO MAIN MENU OPTION / BUFF.READER / WORDSEARCH
//________________________________________________________________________________________
                while (Flag != true )
                {
                    if (userInput.equals("0"))//The following is initiated if userin. = 0
                    {
                        timer.cancel();//Cancels timer
                        timer = new Timer();//Makes or schedules a new timer
                        //HIGHSCORE FILES
                        notValid = false;
                        System.out.println("");
                        System.out.println("");
                        int[] numbers = new int[11];//creates array for storing highscore
                        BufferedReader lineIn2 = new BufferedReader(new FileReader("Highscore.txt"));//reads highscore file
                        String line2 = "";
                        //load array with file (for loop)
                        for (int ctr5 = 0; ctr5 < 11; ctr5++)
                        {
                            line2 = lineIn2.readLine();
                            numbers[ctr5] = Integer.parseInt(line2);
                        }
                        System.out.println("");
                        System.out.println("");
                        System.out.println("");
                        System.out.println("");
                        System.out.println("");
                        System.out.println("The previous highscore is: " + numbers[10]);
                        System.out.println("");
                        System.out.println("Your highscore is: " + score);

                        lineIn2.close();//closes file
                        PrintWriter lineOut2 = new PrintWriter(new FileWriter("Highscore.txt"));//writes to file
                        int Highscore = score;

                        numbers[0] = Highscore;
                        sl.quickSort(numbers, 0,10); //Sorts the high scores
                        System.out.println("");                         
                        System.out.println("The high scores are:");
                        for (int index = numbers.length-1; index >= 1; index--)
                        {
                            System.out.print (numbers[index] + " ");//Displays array of numbers. Not neccessry for game
                        }
                        for (int ctr99 = 0; ctr99 < 11; ctr99++)
                        {
                            lineOut2.println(numbers[ctr99]);//writes scores back to file
                        }
                        System.out.println("");
                        System.out.println();
                        lineOut2.close();//closes file one last time
                        System.out.println("The words you entered are:");

                        for (int disp = size-1; disp >= 0; disp--)
                        {
                            System.out.print(wordStorage[disp] + " ");
                        }
                        System.out.println("");

                        //notValid = true;
                        timeUp = false;
                        //Breaks back to main menu
                        break;//breaks back to main menu
                    }
                    else if (!userInput.equals("0") && !timeUp)//If userin. doesn't equal 0, following error is displayed
                    {
                            System.out.println("");
                            System.out.println("-------------------------Not a valid input----------------------------");
                            System.out.println("");
                    }
                    ctr = 0;
                    boolean answer = wordSearch(table, userInput);
                    //link the two together
                    BufferedReader lineIn = new BufferedReader(new FileReader("allWordsEn.txt"));//opens dictionary
                    int ctr2 = 0;
                    String line = lineIn.readLine();//reads dictionary
                    boolean match = false;
//________________________________________________________________________________________
//  SCORE SYSTEM / ERROR MESSAGES
//________________________________________________________________________________________
                        while(line != null && answer)
                        {
                            StringTokenizer words = new StringTokenizer(line);
                            String temp = words.nextToken();

                            if (userInput.equalsIgnoreCase(temp))//the following compares userinput with array of 
                                                                 //stored words, to see if they already exist or not
                            {
                                boolean ifwordexist = false;

                                for (int ctr9 = 0; ctr9 <= size; ctr9++)
                                {
                                    if (userInput.equals(wordStorage[ctr9]))
                                    {
                                        ifwordexist = true;
                                        System.out.println("You entered the word aleady");
                                        match = true;
                                        break;
                                    }
                                     //check if word is in the array.. if yes, ifwordexist= true
                                }

                                if (!ifwordexist)
                                {
                                    wordStorage[size] = userInput;  // store name into the array
                                    int temp999 = userInput.length();
                                    size++;     // keep track of logical size of the array
                                    score+=temp999; //Adds points to total score equal to length of word
                                    System.out.println("Match Dictionary! +" + temp999  + " Total Score: " + score); //displays current score
                                    match = true;
                                    break;
                                }
                            }
                            line = lineIn.readLine();
                            ctr2++;
                        }
                        lineIn.close(); //closes dictionary
                    //If word doesn't match the grid or dictionary, displays the following error message
                    if (timeUp)
                    {
                        if (!match)
                        {
                            System.out.println("Word not found in database. No point scored, try Again.");
                        }
                        //Displays the gird once again
                        for (int x = 0; x < 10; x++)
                        {
                            for (int y = 0; y < 10; y++)
                            {
                                System.out.print("|" + table[x][y] + "|");
                            }
                            System.out.println("");
                        }
                        System.out.println("Next word");
                    }

                    System.out.println("- Enter \"0\" to return to main menu.");
                    userInput = Keyboard.readString();
                }
           }
//________________________________________________________________________________________
// RULES
//________________________________________________________________________________________
        else if (userCmd==2)//displayes rules
        {
            System.out.println("Rules:");
            System.out.println("");
            System.out.println("- Search the 10 x 10 grid for words that are formed vertically and horizontally (left to right, top to bottom)");
            System.out.println("- When you have found a word (minimum 2 letter word), type the word into the program.");
            System.out.println("- The amount of points you score is determined by the length of the word you entered.");
            System.out.println("- The goal of the game is to score as many points before the time runs out.");
            System.out.println("- While playing the game you can enter \"0\" to return to the main menu.");
            System.out.println("- Good Luck and have fun!");
            System.out.println("");
        }
        else if (userCmd==3)//displayes high scores
        {
            int[] numbers = new int[11];
            BufferedReader lineIn2 = new BufferedReader(new FileReader("Highscore.txt"));
            String line2 = "";
            //load array with file (for loop)
            for (int ctr5 = 0; ctr5 < 11; ctr5++)
            {
                line2 = lineIn2.readLine();
                numbers[ctr5] = Integer.parseInt(line2);
            }
            System.out.println("");
            System.out.println("");
            System.out.println("The previous highscore is: " + numbers[10]);
            System.out.println("");
            lineIn2.close();
            PrintWriter lineOut2 = new PrintWriter(new FileWriter("Highscore.txt"));
            sl.quickSort(numbers, 0,10); //Sorts the high scores
            System.out.println("The high scores are:");
            for (int index = numbers.length-1; index >= 1; index--)
            {
                System.out.print (numbers[index] + " ");//Displays array of numbers. Not neccessry for game
            }

            for (int ctr99 = 0; ctr99 < 11; ctr99++)
            {
                lineOut2.println(numbers[ctr99]);
            }
            System.out.println("");
            System.out.println();
            lineOut2.close();
        }
        else if (userCmd==4)//ends the process
        {
            System.out.println("Bye!");
            System.exit(0);
        }
            else//displayes error message if input doesn't match 1,2,3, or 4.
            {
                System.out.println("");
                System.out.println("-------------------------Not a valid input----------------------------");
                System.out.println("");
                System.out.println("");
            }
   }
}
//________________________________________________________________________________________
// COUNTDOWN TIMER / ADJUST TIMER HERE
//________________________________________________________________________________________
class RemindTask extends TimerTask
{
    int numWarningBeeps = 59;//Set timer here (seconds)

        public void run() 
        {
            if (numWarningBeeps > 0) 
            {
                toolkit.beep();//Creats beeping noises
                numWarningBeeps--;
                timeUp = true;
            } 
            else 
            {
                toolkit.beep(); 
                timer.cancel();//cancels timer when it reaches 0
                System.out.println("");
                System.out.println("Time's up!");
                System.out.println("");
                System.out.println("- Enter \"0\" to continue.");
                timeUp = false;
                notValid = false;
                timer = new Timer();//creats or schedules new timer
                //System.exit(0);   //Stops the AWT thread (and everything else)
            }
        }
}    


   //____________________________________________________________________________
          // MAIN METHOD / RELATED TO TIMER
   //__________________________________________________________________________
 public static void main(String[] args) throws IOException
{
 new FinalProjectBogel();
}





        //____________________________________________________________________________
       // WORDSEARCH METHOD (Searches grid for words you enter to see if they match)
      //_______________________________________________________________________________

     public static boolean wordSearch (char[][] table, String search)
       {
           int  ctr = search.length();
           String temp = ""; 
           String hcraes = (search); // copy search into hcraes

           //Right to left, bottom to top
           int ls = search.length();  // length of initial string
            StringBuilder sb = new StringBuilder(); // temporary place to store growing string
            for(int ii=ls-1;ii>=0; ii--) {
                    sb.append(search.charAt(ii)); // build the string one character at a time
                }
            hcraes = sb.toString(); // convert to "regular" string

           // LEFT TO RIGHT / X-AXIS
           for (int row = 0; row < 10; row++) //Checks each row (x) one by one
           {
                   for (int a = 0; a <= (10 - ctr); a++)
                   {
                    StringBuilder s = new StringBuilder(10-ctr);//Does... something
                        for (int x = a; x <= (a+ctr-1); x++) //Checks every possibility in the row
                         {
                            s.append(table[row][x]);
                            temp = s.toString();
                            if (temp.equals(search) || temp.equals(hcraes))
                            {
                                return true;
                            }
                         }
                   }
           }
           // TOP TO BOTTOM / Y-AXIS
           for (int column = 0; column < 10; column++)
           {
                   for (int b = 0; b <= (10 - ctr); b++)
                   {
                    StringBuilder v = new StringBuilder(10-ctr);
                        for (int y = b; y <= (b+ctr-1); y++)//checks every possibility in grid
                         {
                            v.append(table[y][column]);
                            temp = v.toString();
                            if (temp.equals(search) || temp.equals(hcraes))
                            {
                                return true;
                            }
                         }
                   }
           }
            return false;//if word isn't in grid it returns as false, which then displays an error message
      }

All i would like to know is what the code for this is. When user enters 0 i would like it to display all the possible words. Keep in mind, i have an external .txt file which basically is the dictionary which words are compared with.

Answer 1

As an alternative to the above approach, here is code that will perform the exhaustive search in Java. It is not quite as efficient - but it has the advantage of being OS-independent.

There are three conceptual blocks here: First, I create a 10x10 grid (using code from your application above... I needed to get a table[][] somehow). I added a little "trick" here - instead of picking letters randomly from the alphabet, I pick them randomly from a string with "approximate" English letter frequencies. We should get more "English sounding" word combinations in the resulting grid.

Next, I read the grid left to right, right to left, top to bottom, and bottom to top. This creates a total of 40 strings to search.

Third, I open the input file and look at one string at a time; I attempt to match this against the 40 strings in turn, and as soon as I find a match I stop looking (in other words, it doesn't matter if there is more than one match).

I ran this with a very small input file, and it seemed to work. When you run it against a full dictionary it may be quite slow - but note that I do attempt to break out of the search loops as soon as I -know I have a match, or -know I don't have a match.

There are no doubt ways this could be further optimized.

import java.util.Random;
import java.io.*;

public class myGrep {

public static void main(String[] args){
char t40[][] = new char[40][10];
char table[][] = new char[10][10]; //Creates the array for the 10x10 grid
int ii=0, jj=0;
char c;

int ctr = 0;
char m;

Random r = new Random();//for the random characters

// First, I create a random table of 10x10 characters to work with
// To make it more interesting, I use a string with approximate frequencies
// for characters in the English language - this should yield more, and longer
// "findable" words in the grid
// source: http://www.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html
String cfreq = "eeeeeeeeeeeetttttttttaaaaaaaaoooooooo" +
               "iiiiiiinnnnnnnssssssrrrrrrhhhhhhddddl" +
               "llluuucccmmmffyywwggppbbvkxqjz";

for (int x = 0; x < 10; x++)
{
  for (int y = 0; y < 10; y++)
  {
    table[x][y] = cfreq.charAt(r.nextInt(cfreq.length()));
   }
}   

// Now, make a second table of 40 lines; this speeds up the search
// since I won't have to think about "direction" any more ... just search L to R
for (int x = 0; x < 10; x++)
{
   for (int y = 0; y < 10; y++)
   {
      m = table[x][y];
      t40[x][y]=m;       // L to R
      t40[x+10][9-y]=m;  // R to L
      t40[y+20][x]=m;    // T to B
      t40[y+30][9-x]=m;  // B to T
   }
}

// confirm that we now have 40 rows of strings:
System.out.println("The following 40 strings represent searching the 10x10 grid in all directions:");
for( ii = 0; ii<40; ii++) {
  System.out.println(t40[ii]);
}

// Now starts the fun... for each word in the input file, look for a match
  try {
    FileInputStream fstream = new FileInputStream("textfile.txt");
    DataInputStream in = new DataInputStream(fstream);
    BufferedReader br = new BufferedReader(new InputStreamReader(in));
    String strLine;

    //Read File Line By Line
    while ((strLine = br.readLine()) != null)   {
      if(canFind(strLine, t40)) 
      {
        System.out.println (strLine);
      }
    }

    //Close the input stream
    in.close();
  } catch (Exception e) { //Catch exception if any
    System.err.println("Error: " + e.getMessage());
  }

} // end of main()

private static boolean canFind(String findme, char[][] searchme) {
  boolean isfound = false;
  int li = 0;

  // loop over all lines in the searchme table: we know there are 40
  while (li < 40 && !isfound) {
    // look for a match of the first character:
    for(int ii = 0; ii<11-findme.length(); ii++) {
      if(searchme[li][ii] == findme.charAt(0)) {
        isfound = true;
        for(int jj = 1; (jj < findme.length()) && isfound; jj++) {
          // **** this line could probably be optimized more: ****
          isfound = (isfound && (findme.charAt(jj) == searchme[li][ii+jj]));
        }
      ii = 10; // exit for(int ii = 0;..) loop...
      }
    }
    li++;
  }
  return isfound;

}
}

Answer 2

The searching you are trying to do now really becomes "heavy duty" - it's no longer a single word. I recommend you use grep., rather than making your own code. I am going to assume you can do this on a linux (Mac OS) type machine ... not too familiar with Windows, sorry.

The basic approach is this: Your grid of 10x10 can be turned into a total of 40 strings (10 each horizontal and vertical) x 2 [ because you can read backwards ]. Put those 40 strings, one line at a time, into a file we call file.txt

Now comes the magic. There is a very fast version of grep that looks for an "exact match" of the key, using the -F option. Assume your "valid words" are in a second file named valid.txt. From the directory where both these files are located, execute the following command:

grep -oF valid.txt file.txt > words.txt

Here is the explanation:

-o        : output the matched string, not the line found
-F        : do not do pattern matching; look for an exact match 
            (much, much faster - not available in all versions of grep. 
            If you don't have it, use -f instead)
valid.txt : file with the 'keys' (good words)
file.txt  : file to be searched for the keys
>         : send the output of the command...
words.txt : ... to this file

You could call this command from inside your java program (see for example this link), and read the file back in. It will save you some programming, and it will quite likely be much faster than anything you can code yourself.