import java.util.Set;
import java.util.TreeSet;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

/**
 * Class that represents a Boggle board and enables an exhaustive search
 * of that board.
 *   @author Dave Reed
 *   @version 10/27/13
 */
public class BoggleBoard {
    private final static int SIZE = 4;
    
    private char[][] board;
    private Trie dictionary;
    private Set<String> words;
            
    /**
     * Constructs a Boggle board with random letters in each spot.
     *   @param filename the name of the dictionary file
     */
    public BoggleBoard(String filename) {
        board = new char[BoggleBoard.SIZE][BoggleBoard.SIZE];
        for (int r = 0; r < this.board.length; r++) {
            for (int c = 0; c < this.board.length; c++) {
                this.board[r][c] = (char)('a' + (int)(Math.random()*26));
            }
        }
        
        this.dictionary = new Trie();
        try {
            Scanner dictFile = new Scanner(new File(filename));
            while (dictFile.hasNext()) {
                this.dictionary.add(dictFile.next());
            }
        }
        catch (FileNotFoundException e) {
            System.out.println("DICTIONARY FILE NOT FOUND");
        } 
        
        this.words = new TreeSet<String>();
        this.findAllWords();
    }
    
    /**
     * Determines whether the word can be found on the board.
     *   @param word the word to be searched for
     *   @return true if the word is on the board, else false
     */
    public boolean contains(String word) {
        return this.words.contains(word);
    }
    
    /**
     * Generates a set of all the words found on the board.
     *   @return the set of words
     */
    public Set<String> allWords() {
        return words;
    }
    
    /**
     * Converts the board to a String (with line breaks after each row)
     *   @return the string version of the board
     */
    public String toString() {
        String str = "";
        for (int r = 0; r < board.length; r++) {
            for (char ch : board[r]) {
                str += ch + " ";
            }
            if (r < board.length-1) { 
                str += "\n"; 
            }
        }
        return str;
    }
    
    ///////////////////////////////////////////////////////////////////
    
    /**
     * Private method for searching the board and placing all found 
     * words in this.words
     */
    private void findAllWords() {
        for (int r = 0; r < this.board.length; r++) {
            for (int c = 0; c < this.board.length; c++) {
                this.findAllWords("", r, c);
            }
        }        
    }
    
    /**
     * Private helper method for recursively searching the board
     * and placing all found words in this.words
     *   @param sofar the sequence of characters traversed so far
     *   @param row the row to continue searching from
     *   @param col the column to continue searching from
     */
    private void findAllWords(String sofar, int row, int col) {
        if (row >= 0 && row < this.board.length && 
                col >= 0 && col < this.board.length && 
                this.board[row][col] != '*') {
            sofar += this.board[row][col];

            if (this.dictionary.containsPrefix(sofar)) {
                if (this.dictionary.containsWord(sofar)) {
                    this.words.add(sofar);
                }
                
                char saved = this.board[row][col];
                this.board[row][col] = '*';
                this.findAllWords(sofar, row-1, col-1);
                this.findAllWords(sofar, row-1, col);
                this.findAllWords(sofar, row-1, col+1);
                this.findAllWords(sofar, row, col-1);
                this.findAllWords(sofar, row, col+1);
                this.findAllWords(sofar, row+1, col-1);
                this.findAllWords(sofar, row+1, col);
                this.findAllWords(sofar, row+1, col+1);
                this.board[row][col] = saved;
            }
        }
    } 
}