import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

import edu.princeton.cs.algs4.TrieSET;
public class BoggleWordFinder {

    // some useful constants
    public static final String WORD_LIST = "src/words";
    public static final int ROWS = 5;
    public static final int COLUMNS = 5;
    public static final int SEED = 137;

    public BoggleWordFinder(String filename) throws Exception {
        TrieSET trie = new TrieSET();
        ArrayList<String> answers = new ArrayList<String>();
        initDictionary(filename, trie);
        BoggleBoard board = new BoggleBoard();
        System.out.println(board);

        for (int i = 0; i < board.getColumns()-1; i++) {
            for (int j = 0; j < board.getRows()-1; j++) {
                dfs(i, j, new String(), answers, board, trie);
                board = clearVisited(board);
            }
        }
        //System.out.println(answers);
    }

    private static BoggleBoard clearVisited(BoggleBoard board) {
        for (int i = 0; i < board.getColumns()-1; i++) {
            for (int j = 0; j < board.getRows()-1; j++) {
                board.setUnvisited(i,j);
            }
        }
        return board;
    }

    public static void initDictionary(String filename, TrieSET trie) throws FileNotFoundException {
        File file = new File(filename);
        Scanner sc = new Scanner(file);
        while(sc.hasNextLine()) {
            if(Character.isLowerCase(sc.nextLine().charAt(0))) {
                trie.add(sc.nextLine());
            }
        }
    }

    private static ArrayList<String> checkDictionary(String str, BoggleBoard board, TrieSET trie, ArrayList<String> answers) {
        for(String word : trie) {
            if(word.equals(str)) {
                System.out.println(str);
                answers.add(str);
            }
        }
        return answers;
    }

    private static boolean isNull(TrieSET trie, String word) {
        int i = 0;
        for (String str: trie.keysWithPrefix(word)) {
            i++;
        }
        return i == 0 ? true : false;
    }

    public static void dfs(int i, int j, String str, ArrayList<String> answers, BoggleBoard board, TrieSET trie) {
        if (i < 0 || j < 0 || i > board.getColumns()-1 || j > board.getRows()-1 || board.isVisited(i, j)) return;
        str += board.getCharAt(i,j);
        if(isNull(trie, str)) return;
        //System.out.println(str);
        //System.out.println(trie.keysWithPrefix(str));
        board.setVisited(i,j);

        answers = checkDictionary(str, board, trie, answers);
        //north
        dfs(i, j+1, str, answers, board, trie);
        //NW
        dfs(i-1, j+1, str, answers, board, trie);
        //west
        dfs(i-1, j, str, answers, board, trie);
        //SW
        dfs(i-1, j-1, str, answers, board, trie);
        //south
        dfs(i, j-1, str, answers, board, trie);
        //SE
        dfs(i+1, j-1, str, answers, board, trie);
        //east
        dfs(i+1, j, str, answers, board, trie);
        //NE
        dfs(i+1, j+1, str, answers, board, trie);

        board.setUnvisited(i,j);
    }


    public static void main(String[] args) throws Exception {
        System.out.println(new File("words").getAbsolutePath());
        BoggleWordFinder bwf = new BoggleWordFinder("D:\\Desktop\\Fall 2021\\CIS27 D&S\\Boggle Solver\\src\\words");
    }

}