3
\$\begingroup\$

My word search goes through and searches for the first letter in the word slowly. I am looking for a way to optimize the program to search faster and efficiently. I want to find a way to search faster by using a single loop instead of nested loops in my findWords method. I think it would be better to use the appropriate ArrayList from the Hashtable to go only to the row, col coordinates that contain the first letter of the word.

public class WordSearch {

    VJFrame F;
    int dx = 30;
    int dy = 30;
    int timing = 10;

    ArrayList < String > word;

    private class Coordinate {
        Integer r;
        Integer c;

        private Coordinate(Integer row, Integer col) {
            this.r = row;
            this.c = col;
        }

    }

    Hashtable < String, ArrayList < Coordinate >> H = new Hashtable < String, ArrayList < Coordinate >> ();

    public WordSearch(VJFrame F) {
        this.F = F;
    }

    public void initialize(String[][] mat, int rows, int cols, String fileName) throws IOException {
        BufferedReader buffer = new BufferedReader(new FileReader(fileName));
        String s;
        for (int i = 0; i < rows; i++) {
            s = buffer.readLine();
            for (int j = 0; j < cols; j++) {
                mat[i][j] = s.substring(j, j + 1);
                if (!H.containsKey(mat[i][j])) {
                    H.put(mat[i][j], new ArrayList < Coordinate > ());
                }
                H.get(mat[i][j]).add(new Coordinate(i, j));
            }
        }
    }

    public void display(String[][] mat) {
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                System.out.print(mat[i][j] + " ");
                F.add(new JRectangle(dx * j, dy * i, dx, dy, Color.black, Color.white), timing);
                F.add(new JString(dx * j + 5, dy * i + 25, mat[i][j], Color.black), timing);
            }
            System.out.println();
            F.add(new JString(dx * mat[i].length + 5, dy * i + 25, Integer.toString(i), Color.white), timing);
        }
        for (int j = 0; j < mat[0].length; j++) {
            F.add(new JString(dx * j + 5, dy * mat.length + 25, Integer.toString(j), Color.white), timing);
        }
    }

    public boolean match(String[][] matrix, int row, int col, String word, Direction d) {

        String check = word.substring(0, 1);
        int index = 1;
        while (index < word.length()) {
            if (matrix[row + d.deltaRow][col + d.deltaCol].equals(word.substring(index, index + 1))) {
                index++;
                check = check + matrix[row + d.deltaRow][col + d.deltaCol];
                row = row + d.deltaRow;
                col = col + d.deltaCol;
            } else {
                return false;
            };
        }
        if (check.equalsIgnoreCase(word)) {
            return true;
        } else {
            return false;
        }
    }

    public void displayWord(String[][] matrix, int row, int col, String word, Direction d) {

        for (int index = 0; index < word.length(); index++) {
            int drow = index * d.getDeltaRow();
            int dcol = index * d.getDeltaCol();
            F.add(new JRectangle(dx * (col + dcol), dy * (row + drow), dx, dy, Color.black, Color.green), timing);
            F.add(new JString(dx * (col + dcol) + 5, dy * (row + drow) + 25, matrix[row + drow][col + dcol], Color.black), 500);
        }

        try {
            Thread.sleep(2000);
        } catch (Exception e) {}

        for (int index = 0; index < word.length(); index++) {
            int drow = index * d.getDeltaRow();
            int dcol = index * d.getDeltaCol();
            F.add(new JRectangle(dx * (col + dcol), dy * (row + drow), dx, dy, Color.black, Color.white), timing);
            F.add(new JString(dx * (col + dcol) + 5, dy * (row + drow) + 25, matrix[row + drow][col + dcol], Color.black), 500);
        }

    }

    public void findWords(String[][] matrix, String fileName) throws IOException {
        BufferedReader buf = new BufferedReader(new FileReader(fileName));
        int wrdCnt = 0;
        int row = 1;
        int deltaX = this.dx * (3 + matrix.length);
        while (buf.ready()) {
            boolean found = false;
            Direction d;
            String word = buf.readLine();

            F.add(new JString(deltaX, dy * row, word, Color.yellow), timing);
            wrdCnt++;
            if (wrdCnt % 2 == 0) {
                deltaX = this.dx * (3 + matrix.length);
                row++;
            } else {
                deltaX += 150;
            }

            for (Integer i = 1;
            (i < matrix.length - 1) && (!found); i++) {
                for (Integer j = 1;
                (j < matrix[i].length - 1) && (!found); j++) {
                    F.add(new JRectangle(dx * j, dy * i, dx, dy, Color.black, Color.yellow), 20);
                    F.add(new JString(dx * j + 5, dy * i + 25, matrix[i][j], Color.black), 20);
                    if (matrix[i][j].equals(word.substring(0, 1))) {
                        for (Directions Dir = new Directions();
                        (!found) && (Dir.hasNext());) {
                            d = (Direction) Dir.next();
                            found = match(matrix, i, j, word, d);
                            if (found) {
                                displayWord(matrix, i, j, word, d);
                                System.out.println(word + " found at (" + i + "," + j + ") heading " + d.getName());
                            }
                        }
                    }
                    F.add(new JRectangle(dx * j, dy * i, dx, dy, Color.black, Color.white), 20);
                    F.add(new JString(dx * j + 5, dy * i + 25, matrix[i][j], Color.black), 20);
                }
            }
            if (!found) System.out.println(word + " not found");
        }
    }

}

    public class Directions implements Iterator{
    Direction[] D = new Direction[8];
    Integer index;

    public Directions(){
        this.D[0] = new Direction("north"    , -1, 0);
        this.D[1] = new Direction("northeast", -1, 1);
        this.D[2] = new Direction("east"     , 0, 1);
        this.D[3] = new Direction("southeast", 1, 1);
        this.D[4] = new Direction("south"    , 1, 0);
        this.D[5] = new Direction("southwest", 1, -1);
        this.D[6] = new Direction("west"     , 0, -1);
        this.D[7] = new Direction("northwest", -1, -1);
        this.index = 0;
    }

    public Object next(){
        assert this.index<8: "Iteration error";
        return D[this.index++];
    }

    public boolean hasNext(){
        return this.index<8;
    }

    public void remove(){

    }

}


      public class Direction {
      public String name;
      public Integer deltaRow;
      public Integer deltaCol;

       public Direction (String name, Integer dRow, Integer dCol){
         this.name = name;
         this.deltaRow = dRow;
         this.deltaCol = dCol;
      }

       public Integer getDeltaRow(){
         return this.deltaRow;}

       public Integer getDeltaCol(){
         return this.deltaCol;}

       public String getName(){
         return this.name;}

       public String toString(){
         return this.name+"\t"+this.deltaRow+"\t"+this.deltaCol;
      }
   }


       public class WordSearchMain{

      public static void main(String [] argv) throws IOException {
         int rows = 17;
         int cols = 17;
         String [][] matrix = new String[rows][cols];
            VJFrame VWS = new VJFrame("Word Search");
         WordSearch W = new WordSearch(VWS);

         W.initialize(matrix, rows, cols, "matrixB.txt");

         W.display(matrix);

         W.findWords(matrix, "words.txt");
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ I added more classes that are included in my program if it makes more sense. My code works fine and I was just looking for ways to change my findWords method to find the word faster. \$\endgroup\$ – Eagles11 Nov 30 '15 at 1:47
  • 1
    \$\begingroup\$ Oh, I see. I misread your question -- I thought you were asking how to make the code work, not how to make it better. You might want to rephrase that \$\endgroup\$ – Nic Hartley Nov 30 '15 at 2:37
  • \$\begingroup\$ Can you explain some more context here? It looks like you're searching a 2-dimensional array. Is this like a word search game where there are multiple words hidden in a 2D array of what appear to be random letters? Or is this something different? \$\endgroup\$ – user1118321 Nov 30 '15 at 3:05
  • \$\begingroup\$ It makes a hashtable of arraylists. The keys for the table are the letters in the matrix. Associated to each key is an ArrayList of the (row, col) Coodinate pairs for all the coordinates where the letter resides. \$\endgroup\$ – Eagles11 Nov 30 '15 at 3:16
  • 1
    \$\begingroup\$ Sorry, I wasn't asking how it's implemented. My question is what is the point of the code? What purpose does it serve to a user of the code? \$\endgroup\$ – user1118321 Nov 30 '15 at 4:24
3
\$\begingroup\$

You've asked about how to improve performance, but I would advise you to improve the code organization first. It's rather difficult to do a good job of optimizing the performance with the code in its current form.

Specifically, your code violates the Single-Responsibility Principle, as exemplified in findWords(), which does…

  • Read a file containing a list of words.
  • For each word, display it in yellow, while worrying about laying out that list in a two-column format.
  • Search for the word in the matrix.
  • Highlight rectangles to display the progress as the search progresses.
  • Call displayWord() when the word is found — which sleeps (making benchmarking difficult).

I suggest that you start by ripping out the graphical UI so that you can focus on the algorithm. The algorithm should have a findWord(String word) function that returns a search result in the form of a row coordinate, column coordinate, and a direction.

Once you have that working, then you can go about implementing the UI as a separate class.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I am only looking to cut my nested for loops in the findWords() method down. I feel like it is overkill to search through every letter. \$\endgroup\$ – Eagles11 Nov 30 '15 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.