SHARE
TWEET

Untitled

a guest Aug 18th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.datastructures.problems;
  2.  
  3. import java.util.*;
  4. import java.util.stream.Stream;
  5.  
  6. /**
  7.  * Dictionary = [ CAT, DOG, BYTE, TUBE, CAN, ANT, CAR, TANK ]
  8.  * Boggle = {
  9.  *     C    J   Z   E
  10.  *     V    A   X   B
  11.  *     X    N   T   U
  12.  *     I    A   N   K
  13.  * }
  14.  *
  15.  * Dictionary = [ APPLE, PICKLE, SIDE, KICK, SICK, MOOD, CAT, CATS, MAN, SUPER, ANTMAN, GODZILLA,
  16.  * DOG, DOT, SINE, COS, SIGNAL, BITCOIN, COOL, ZAPPER ]
  17.  *
  18.  * Boggle = {
  19.  *     C  N  T  S  S
  20.  *     D  A  T  I  N
  21.  *     O  O  M  E  L
  22.  *     S  I  K  N  D
  23.  *     P  I  C  L  E
  24.  * }
  25.  *
  26.  * Approach:
  27.  * Solve it using Graph (DFS) and Trie
  28.  */
  29. public class BoggleGameSolver {
  30.  
  31.     private static int[][] DELTAS = new int[][] {
  32.             { -1, -1 },
  33.             { -1, 1 },
  34.             { 1, 1 },
  35.             { 1, -1 },
  36.             { 1, 0 },
  37.             { 0, 1 },
  38.             { -1, 0 },
  39.             { 0, -1 },
  40.     };
  41.  
  42.     public static void main(String[] args) {
  43.         String[] dict = new String[] { "CAT", "DOG", "BYTE", "TUBE", "CAN", "ANT", "CAR", "TANK" };
  44.         char[][] boggle = new char[][] {
  45.                 { 'C', 'J', 'Z', 'E' },
  46.                 { 'V', 'A', 'X', 'B' },
  47.                 { 'X', 'N', 'T', 'U' },
  48.                 { 'I', 'A', 'N', 'K' }
  49.         };
  50.         solveBoggle(dict, boggle, 4, 4);
  51.     }
  52.  
  53.     /**
  54.      *
  55.      * @param dict - dictionary of words
  56.      * @param boggle - matrix of m x n
  57.      * @param m - rows
  58.      * @param n - columns
  59.      * @return
  60.      */
  61.     private static void solveBoggle(String[] dict, char[][] boggle, int m, int n) {
  62.         Trie trie = new Trie(dict);
  63.         Set<String> results = new HashSet<>();
  64.         for(int i=0; i<m; i++) {
  65.             for(int j=0; j<n; j++) {
  66.                 StringBuilder w = new StringBuilder();
  67.                 w.append(boggle[i][j]);
  68.                 solveBoggleHelper(new Cell(i, j), w, boggle, new HashSet<>(), results, trie, m, n);
  69.                 w.deleteCharAt(w.length()-1);
  70.             }
  71.         }
  72.         System.out.println("Found words: " + results);
  73.     }
  74.  
  75.     private static void solveBoggleHelper(Cell cell, StringBuilder w, char[][] boggle, Set<Cell> visited, Set<String> results, Trie trie, int maxRows, int maxCols) {
  76.         visited.add(cell);
  77.         Trie.Node node = trie.searchNode(w.toString());
  78.         if(node != null) {
  79.             if(node.leaf) {
  80.                 results.add(w.toString());
  81.             }
  82.             List<Cell> neighbours = getNeighbours(cell, visited, maxRows, maxCols);
  83.             if(neighbours != null) {
  84.                 for(Cell c: neighbours) {
  85.                     w.append(boggle[c.r][c.c]);
  86.                     solveBoggleHelper(c, w, boggle, new HashSet<>(), results, trie, maxRows, maxCols);
  87.                     w.deleteCharAt(w.length()-1);
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.     private static List<Cell> getNeighbours(Cell cell, Set<Cell> visited, int maxRows, int maxCols) {
  94.         List<Cell> cells = new ArrayList<>();
  95.         for(int i = 0; i< DELTAS.length; i++) {
  96.             Cell nextCell = new Cell(cell.r + DELTAS[i][0], cell.c + DELTAS[i][1]);
  97.             if(valid(nextCell, maxRows, maxCols) && !visited.contains(nextCell)) {
  98.                 cells.add(nextCell);
  99.             }
  100.         }
  101.         return cells;
  102.     }
  103.  
  104.     private static boolean valid(Cell cell, int maxRow, int maxCol) {
  105.         return cell.r >= 0 && cell.r < maxRow && cell.c >= 0 && cell.c < maxCol;
  106.     }
  107.  
  108.     private static class Cell {
  109.         private int r;
  110.         private int c;
  111.  
  112.         public Cell(int r, int c) {
  113.             this.r = r;
  114.             this.c = c;
  115.         }
  116.  
  117.         @Override
  118.         public boolean equals(Object o) {
  119.             if (this == o) return true;
  120.             if (o == null || getClass() != o.getClass()) return false;
  121.             Cell cell = (Cell) o;
  122.             return r == cell.r &&
  123.                     c == cell.c;
  124.         }
  125.  
  126.         @Override
  127.         public int hashCode() {
  128.             return Objects.hash(r, c);
  129.         }
  130.  
  131.         @Override
  132.         public String toString() {
  133.             return String.format("[%s, %s]", r, c);
  134.         }
  135.     }
  136.  
  137.     private static class Trie {
  138.  
  139.         private Node root;
  140.  
  141.         public Trie() {
  142.             root = new Node(' ');
  143.         }
  144.  
  145.         public Trie(String[] words) {
  146.             this();
  147.             build(words);
  148.         }
  149.  
  150.         @Override
  151.         public String toString() {
  152.             return String.format("[%s]", root);
  153.         }
  154.  
  155.         public void build(String[] words) {
  156.             Stream.of(words).forEach(w -> add(w));
  157.         }
  158.  
  159.         public boolean containsWord(String w) {
  160.             Node node = searchNode(w);
  161.             return node != null && node.leaf;
  162.         }
  163.  
  164.         private Node searchNode(String w) {
  165.             if(root.children == null) return null;
  166.             Node node = root;
  167.             for(int i=0; i<w.length(); i++) {
  168.                 char ch = w.charAt(i);
  169.                 int j = ch - 'A';
  170.                 if(node.children == null || node.children[j] == null) return null;
  171.                 node = node.children[j];
  172.             }
  173.             return node;
  174.         }
  175.  
  176.         public void add(String w) {
  177.             Node node = root;
  178.             for(int i=0; i<w.length(); i++) {
  179.                 char ch = w.charAt(i);
  180.                 node = add(node, ch, i == w.length()-1);
  181.             }
  182.         }
  183.  
  184.         private Node add(Node node, char ch, boolean leaf) {
  185.             if(node.children == null) node.children = new Node[26];
  186.             int i = ch - 'A';
  187.             if(node.children[i] == null) {
  188.                 Node newNode = new Node(ch, leaf);
  189.                 node.children[i] = newNode;
  190.                 return newNode;
  191.             } else {
  192.                 node.children[i].leaf = leaf;
  193.                 return node.children[i];
  194.             }
  195.         }
  196.  
  197.         private static class Node {
  198.             private char ch;
  199.             private boolean leaf;
  200.             private Node[] children;
  201.  
  202.             public Node(char ch) {
  203.                 this.ch = ch;
  204.             }
  205.  
  206.             public Node(char ch, boolean leaf) {
  207.                 this.ch = ch;
  208.                 this.leaf = leaf;
  209.             }
  210.  
  211.             @Override
  212.             public String toString() {
  213.                 return String.format("[%s, %s, %s]", ch, leaf, Arrays.toString(children));
  214.             }
  215.         }
  216.     }
  217. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top