3

What kind of approch could be an easy way to find the given words on a puzzle like this? I'm using Java. Thanks for help.

enter image description here

Improve this question
2
  • 1
    Did you already try something? Is this homework? More info, please! Commented May 10, 2011 at 19:12
  • This is not homework, I'm just practicing. The data is not coming. I tried something with many for loops which are comparising characters but I think there must be an easier way. I'm searching words vertical and horizontal and also diagonal. Commented May 10, 2011 at 19:16

4 Answers 4

Reset to default
3

Interesting question. I would solve this by first building a list of "possible word holders" (sequences of characters which can possibly hold one of the given words) by traversing the puzzle horizontally, vertically and diagonally (in both directions). I would then see if the given words (or their reverse) are present (using contains() method in Java) in each of the obtained "possible word holders". Here is the code I wrote in Java. I haven't tested it properly, but I guess it works!

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class WordPuzzle {

    public Set<String> findWords(char[][] puzzle, Set<String> words) {
        Set<String> foundWords = new HashSet<String>();
        int minimumWordLength = findMinimumWordLength(words);
        Set<String> possibleWords = findPossibleWords(puzzle, minimumWordLength);
        for(String word : words) {
            for(String possibleWord : possibleWords) {
                if(possibleWord.contains(word) || possibleWord.contains(new StringBuffer(word).reverse())) {
                    foundWords.add(word);
                    break;
                }
            }
        }       
        return foundWords;
    }

    private int findMinimumWordLength(Set<String> words) {
        int minimumLength = Integer.MAX_VALUE;
        for(String word : words) {
            if(word.length() < minimumLength)
                minimumLength = word.length();
        }
        return minimumLength;
    }

    private Set<String> findPossibleWords(char[][] puzzle, int minimumWordLength) {
        Set<String> possibleWords = new LinkedHashSet<String>();
        int dimension = puzzle.length; //Assuming puzzle is square
        if(dimension >= minimumWordLength) {
            /* Every row in the puzzle is added as a possible word holder */
            for(int i = 0; i < dimension; i++) {
                if(puzzle[i].length >= minimumWordLength) {
                    possibleWords.add(new String(puzzle[i]));
                }
            }
            /* Every column in the puzzle is added as a possible word holder */
            for(int i = 0; i < dimension; i++) {
                StringBuffer temp = new StringBuffer();
                for(int j = 0; j < dimension; j++) {
                    temp = temp.append(puzzle[j][i]);
                }
                possibleWords.add(new String(temp));
            }
            /* Adding principle diagonal word holders */
            StringBuffer temp1 = new StringBuffer();
            StringBuffer temp2 = new StringBuffer();
            for(int i = 0; i < dimension; i++) {
                temp1 = temp1.append(puzzle[i][i]);
                temp2 = temp2.append(puzzle[i][dimension - i - 1]);
            }
            possibleWords.add(new String(temp1));
            possibleWords.add(new String(temp2));
            /* Adding non-principle diagonal word holders */
            for(int i = 1; i < dimension - minimumWordLength; i++) {
                temp1 = new StringBuffer();
                temp2 = new StringBuffer();
                StringBuffer temp3 = new StringBuffer();
                StringBuffer temp4 = new StringBuffer();
                for(int j = i, k = 0; j < dimension && k < dimension; j++, k++) {
                    temp1 = temp1.append(puzzle[j][k]);
                    temp2 = temp2.append(puzzle[k][j]);
                    temp3 = temp3.append(puzzle[dimension - j - 1][k]);
                    temp4 = temp4.append(puzzle[dimension - k - 1][j]);
                }
                possibleWords.add(new String(temp1));
                possibleWords.add(new String(temp2));
                possibleWords.add(new String(temp3));
                possibleWords.add(new String(temp4));
            }
        }
        return possibleWords;
    }

    public static void main(String args[]) {
        WordPuzzle program = new WordPuzzle();
        char[][] puzzle = { 
                            {'F','Y','Y','H','N','R','D'},
                            {'R','L','J','C','I','N','U'},
                            {'A','A','W','A','A','H','R'},
                            {'N','T','K','L','P','N','E'},
                            {'C','I','L','F','S','A','P'},
                            {'E','O','G','O','T','P','N'},
                            {'H','P','O','L','A','N','D'}
                          };
        Set<String> words = new HashSet<String>();
        words.add("FRANCE");
        words.add("POLAND");
        words.add("INDIA");
        words.add("JAPAN");
        words.add("USA");
        words.add("HOLLAND");
        Set<String> wordsFound = program.findWords(puzzle, words);
        for(String word : wordsFound) {
            System.out.println(word);
        }
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I think you are considering only the principal diagonal, what about the rest?
I considered all the diagonals. However I might have over-complicated traversing the diagonals. I will update the solution with a more elegant one shortly. Still, the given solution seemed to work for all diagonals. Or have I not tested enough?
Yup. It seemed to work for all cases. Haven't tested it thoroughly though.
I just corrected a mistake in the previous code. The updated code seems to work AFAIK.
Thanks Vithun. Is there any way to contact directly with you?
1

In general, I say use the most naive approach unless your puzzles are going to be large. I wouldn't optimize anything that takes less than 0.1s, but thats just me. 

foreach box
    for all directions
        grab the string of characters in that direction
        lookup a dictionary

I think the smarts can be in how you design your dictionary. In this case, I would do a multi-level hash table where characters pick which hash table to look at the next level.

Improve this answer

2 Comments

To me the for loop is the most intuitive way to loop over it. Less thinking and debugging in that code.
The mutli-level hash is an optimization to speed up lookup the dictionary, if thats what you are referring to. You may have to do it if the dictionary is large.
0

I would put the word list into a Trie, then do a search from all squares in all directions.

Improve this answer

Comments

0

The easiest approach (conceptualy) is to simply enumerate all possible words in your array and check all of then in a dictionnary. A dictionnary behing a map, an array of string... or a real dictionnary downloaded from the internet.

As an exemple here is the code to find all possible word horizontally... Adding other direction is just more work :

import java.util.HashSet;
import java.util.Set;

public class WordFinder {

  public static void main(String[] args) {

    String[][] words = { { "F", "Y", "Y", "H", "N", "R", "D" }, 
                         { "R", "L", "J", "C", "I", "N", "U" },
                         ...};
    Set<String> dictionnary = new HashSet<String>();
    dictionnary.add(...);

    Set<String> wordsFound = findWords(words, dictionnary);
    ...
  }

  /**
   * Find all words in the specified array present in the dictionnary.
   * 
   */
  private static Set<String> findWords(String[][] words, Set<String> dictionnary) {
    Set<String> wordsFound = new HashSet<String>();

    // Find all possible words horizontally :
    int nbrRows = words.length;
    int nbrCol = words[0].length; // We suppose we have at least one row and all row have same lengh

    // Iterate through all rows
    for (int currentRow = 0; currentRow < nbrRows; currentRow++) {
      // Iterate through all possible starting position in the current row.
      for (int beginWordIndex = 0; beginWordIndex < nbrCol; beginWordIndex++) {
        // Iterate then through all possible ending positions in the current row, so to deal with word of any lengh.
        for (int endWordIndex = beginWordIndex; endWordIndex < nbrCol; endWordIndex++) {
          // Construct a word from the begin/end indexes :
          String currentWord = getWordInRow(words, currentRow, beginWordIndex, endWordIndex);

          // Check if the word candidate really exist, if yes, store it in the wordsFound variable.
          if (dictionnary.contains(currentWord)) {
            wordsFound.add(currentWord);
          }

          // The reverse
          String reverseWord = reverseString(currentWord);
          // Check if the reverse word really exist, if yes, store it in the wordsFound variable.
          if (dictionnary.contains(reverseWord)) {
            wordsFound.add(currentWord);
          }

        }
      }
    }

    // Don't forget vertically and in diagonals too... Same principe.

    return wordsFound;
  }

  /**
   * Return a word "candidate" in the specified row, starting at beginIndex and finishing at endIndex.
   */
  private static String getWordInRow(String[][] words, int row, int beginIndex, int endIndex) {
    String currentWord = "";
    int currentPosition = beginIndex;
    while (currentPosition <= endIndex) {
      currentWord += words[row][currentPosition];
    }
    return currentWord;
  }

  /**
   * Return the reverse of a String
   */
  private static String reverseString(String string) {
    String result = "";
    for (int i = string.length()-1; i >=0;i++) {
      result+= string.charAt(i);
    }
    return result;
  }

}

This is not the best, most effective solution. But it is conceptually simple.

EDIT :

reverse order: see edited code. Just write a function that can reverse a word. Because we already have all posible word in normal order, reversing them is enough to have words in reverse order.

Diagonals : I'am sure you can do it if you have understood the code I have already put. I will not do your homework or do your testing in place of you. Try to figure how you would do it with a paper and a pen. How would you do it if you had to do it by hand. Then from that, write your solution ;)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.