package com.datastructures.problems;

import java.util.*;
import java.util.stream.Stream;

/**
 * Dictionary = [ CAT, DOG, BYTE, TUBE, CAN, ANT, CAR, TANK ]
 * Boggle = {
 *     C    J   Z   E
 *     V    A   X   B
 *     X    N   T   U
 *     I    A   N   K
 * }
 *
 * Dictionary = [ APPLE, PICKLE, SIDE, KICK, SICK, MOOD, CAT, CATS, MAN, SUPER, ANTMAN, GODZILLA,
 * DOG, DOT, SINE, COS, SIGNAL, BITCOIN, COOL, ZAPPER ]
 *
 * Boggle = {
 *     C  N  T  S  S
 *     D  A  T  I  N
 *     O  O  M  E  L
 *     S  I  K  N  D
 *     P  I  C  L  E
 * }
 *
 * Approach:
 * Solve it using Graph (DFS) and Trie
 */
public class BoggleGameSolver {

    private static int[][] DELTAS = new int[][] {
            { -1, -1 },
            { -1, 1 },
            { 1, 1 },
            { 1, -1 },
            { 1, 0 },
            { 0, 1 },
            { -1, 0 },
            { 0, -1 },
    };

    public static void main(String[] args) {
        String[] dict = new String[] { "CAT", "DOG", "BYTE", "TUBE", "CAN", "ANT", "CAR", "TANK" };
        char[][] boggle = new char[][] {
                { 'C', 'J', 'Z', 'E' },
                { 'V', 'A', 'X', 'B' },
                { 'X', 'N', 'T', 'U' },
                { 'I', 'A', 'N', 'K' }
        };
        solveBoggle(dict, boggle, 4, 4);
    }

    /**
     *
     * @param dict - dictionary of words
     * @param boggle - matrix of m x n
     * @param m - rows
     * @param n - columns
     * @return
     */
    private static void solveBoggle(String[] dict, char[][] boggle, int m, int n) {
        Trie trie = new Trie(dict);
        Set<String> results = new HashSet<>();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                StringBuilder w = new StringBuilder();
                w.append(boggle[i][j]);
                solveBoggleHelper(new Cell(i, j), w, boggle, new HashSet<>(), results, trie, m, n);
                w.deleteCharAt(w.length()-1);
            }
        }
        System.out.println("Found words: " + results);
    }

    private static void solveBoggleHelper(Cell cell, StringBuilder w, char[][] boggle, Set<Cell> visited, Set<String> results, Trie trie, int maxRows, int maxCols) {
        visited.add(cell);
        Trie.Node node = trie.searchNode(w.toString());
        if(node != null) {
            if(node.leaf) {
                results.add(w.toString());
            }
            List<Cell> neighbours = getNeighbours(cell, visited, maxRows, maxCols);
            if(neighbours != null) {
                for(Cell c: neighbours) {
                    w.append(boggle[c.r][c.c]);
                    solveBoggleHelper(c, w, boggle, new HashSet<>(), results, trie, maxRows, maxCols);
                    w.deleteCharAt(w.length()-1);
                }
            }
        }
    }

    private static List<Cell> getNeighbours(Cell cell, Set<Cell> visited, int maxRows, int maxCols) {
        List<Cell> cells = new ArrayList<>();
        for(int i = 0; i< DELTAS.length; i++) {
            Cell nextCell = new Cell(cell.r + DELTAS[i][0], cell.c + DELTAS[i][1]);
            if(valid(nextCell, maxRows, maxCols) && !visited.contains(nextCell)) {
                cells.add(nextCell);
            }
        }
        return cells;
    }

    private static boolean valid(Cell cell, int maxRow, int maxCol) {
        return cell.r >= 0 && cell.r < maxRow && cell.c >= 0 && cell.c < maxCol;
    }

    private static class Cell {
        private int r;
        private int c;

        public Cell(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Cell cell = (Cell) o;
            return r == cell.r &&
                    c == cell.c;
        }

        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }

        @Override
        public String toString() {
            return String.format("[%s, %s]", r, c);
        }
    }

    private static class Trie {

        private Node root;

        public Trie() {
            root = new Node(' ');
        }

        public Trie(String[] words) {
            this();
            build(words);
        }

        @Override
        public String toString() {
            return String.format("[%s]", root);
        }

        public void build(String[] words) {
            Stream.of(words).forEach(w -> add(w));
        }

        public boolean containsWord(String w) {
            Node node = searchNode(w);
            return node != null && node.leaf;
        }

        private Node searchNode(String w) {
            if(root.children == null) return null;
            Node node = root;
            for(int i=0; i<w.length(); i++) {
                char ch = w.charAt(i);
                int j = ch - 'A';
                if(node.children == null || node.children[j] == null) return null;
                node = node.children[j];
            }
            return node;
        }

        public void add(String w) {
            Node node = root;
            for(int i=0; i<w.length(); i++) {
                char ch = w.charAt(i);
                node = add(node, ch, i == w.length()-1);
            }
        }

        private Node add(Node node, char ch, boolean leaf) {
            if(node.children == null) node.children = new Node[26];
            int i = ch - 'A';
            if(node.children[i] == null) {
                Node newNode = new Node(ch, leaf);
                node.children[i] = newNode;
                return newNode;
            } else {
                node.children[i].leaf = leaf;
                return node.children[i];
            }
        }

        private static class Node {
            private char ch;
            private boolean leaf;
            private Node[] children;

            public Node(char ch) {
                this.ch = ch;
            }

            public Node(char ch, boolean leaf) {
                this.ch = ch;
                this.leaf = leaf;
            }

            @Override
            public String toString() {
                return String.format("[%s, %s, %s]", ch, leaf, Arrays.toString(children));
            }
        }
    }
}