Get position of word in Boggle

Question

I'm solving 4 *4 boggle in Android using this piece of code. It's working well but I'm trying to get position of found word in it.

| A | C | E | X |
-----------------
| X | X | X | X |
-----------------
| X | X | X | X |
-----------------
| X | B | A | R |

Lets say I'm trying to find ACE's position based on 0 index. It is [0, 1, 2].

Or BAR, it's [13, 14, 15]

How can I achieve this? I tried a few implementation but it messed so I'm posting code without them.

public class Boggle {

    private NavigableSet<String> dict___ = new TreeSet<>();
    ArrayList<Word> foundWords = new ArrayList<>();

    /* helpers */
    int N = 4;
    char[][] board = new char[N][N];


    /* context obj*/
    private final Context ctx;

    public Boggle(Context ctx) {
        this.ctx = ctx;
        initFile();
    }


    public ArrayList<Word> startSolving(String str) {
        initPuzzle(str);

        Stack<Point> visitedLetters = new Stack<>();


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                findWordRecursive(i, j, new Word("", null), visitedLetters);
            }
        }

        Log("foundWords = " + foundWords.size());
        Log("=============================");

        return foundWords;
    }

    private void findWordRecursive(int i, int j, Word prefix, Stack<Point> visitedLetters) {

        Point currentLocation = new Point(i, j);
        visitedLetters.push(currentLocation);

        String possibleWord = prefix.getWord() + this.board[i][j];

        if (dict___.contains(possibleWord)) {
            if(!isFoundWordsContains(possibleWord)) {
                foundWords.add(
                        new Word(
                                possibleWord,
                                null)
                );
            }
        }

        NavigableSet<String> child__ = findChildWords(possibleWord);

        if (!child__.isEmpty()) {
            for (int x = Math.max(0, i - 1); x < Math.min(i + 2, 4); x++) {
                for (int y = Math.max(0, j - 1); y < Math.min(j + 2, 4); y++) {
                    if (!visitedLetters.contains(new Point(x,y))) {
                        findWordRecursive(x, y, new Word(possibleWord, null), visitedLetters);
                    }
                }
            }
        }

        visitedLetters.pop();
    }

    private void initFile() {

        Log("=============================");
        Log("init starting");

        //fill dict___ array with words from a TXT file.

        Log("init finished")

    }


    void initPuzzle(String letters) {
        letters = letters.toLowerCase(new Locale("tr", "TR"));
        int in = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {

                board[i][j] = letters.charAt(in);
                in++;
            }
        }
        Log("board letters inited");
    }

    void Log(String e){
         Log.wtf("___Boggle___", e);
    }

    NavigableSet<String> findChildWords(String prefix){
        prefix = prefix.toLowerCase(new Locale("tr", "TR"));
        return dict___.subSet(prefix, false, prefix+"zzzzzzzzzzzzzzz", false);
    }

    boolean isFoundWordsContains(String word) {
        boolean yeah = false;

        for (int i = 0; i < foundWords.size(); i++) {
            if(word.equals(foundWords.get(i).getWord())) {
                yeah = true;
                break;
            }
        }

        return yeah;
    }
}

---

Word class:

public class Word {

    private String word;
    private ArrayList<Integer> position;

    public Word(String word, ArrayList<Integer> position) {
        this.word = word;
        this.position = position;
    }

    public String getWord() {
        return word;
    }

}

Answer 1

I think your issue is because of prefix = prefix.toLowerCase(new Locale("tr", "TR"));

So to make your code works, you may need to check these step:

• all of String in dict___ must be lowerCase.
• dict___ must contain the word subset (for "ace", must have at least "a", "ac", "ace")

• in findWordRecursive replace String possibleWord = prefix.getWord() + this.board[i][j]; by
  String possibleWord = prefix.getWord() + this.board[i][j]; possibleWord = possibleWord.toLowerCase();
  Update
  To find position, you could try this:

• in startSolving, use findWordRecursive(i, j, new Word("", new ArrayList<Integer>()), visitedLetters);

• in findWordRecursive, add pass currentPosition
  

      int curPos = i * N + j;
      if (dict___.contains(possibleWord)) {
          if(!isFoundWordsContains(possibleWord)) {
              // add current position to the word
              ArrayList<Integer> posList = new ArrayList<Integer>();
              posList.addAll(prefix.position);
              posList.add(curPos);
              foundWords.add(
                      new Word(
                              possibleWord,
                              posList)
              );
          }
      }
  
      NavigableSet<String> child__ = findChildWords(possibleWord);
  
      if (!child__.isEmpty()) {
          for (int x = Math.max(0, i - 1); x < Math.min(i + 2, 4); x++) {
              for (int y = Math.max(0, j - 1); y < Math.min(j + 2, 4); y++) {
                  if (!visitedLetters.contains(new Point(x,y))) {
                      // add current before find new word
                      ArrayList<Integer> posList = new ArrayList<Integer>(prefix.position);
                      posList.addAll(prefix.position);
                      posList.add(curPos);
  
                      findWordRecursive(x, y, new Word(possibleWord, posList), visitedLetters);
                  }
              }
          }
      }