Algorithms-II : 4-Boggle add prototypes and data

1 files changed, 217 insertions, 0 deletions

diff --git a/Algorithms/Part-II/4-Boggle/BoggleBoard.java b/Algorithms/Part-II/4-Boggle/BoggleBoard.java
new file mode 100644
index 0000000..ec7ba38
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/BoggleBoard.java
@@ -0,0 +1,217 @@
+/*************************************************************************
+ *  Compilation:  javac BoggleBoard.java
+ *  Execution:    java  BoggleBoard
+ *  Dependencies: StdRandom.java In.java StdOut.java
+ *
+ *  A data type for Boggle boards.
+ *
+ *************************************************************************/
+
+public class BoggleBoard {
+    private final int M;        // number of rows
+    private final int N;        // number of columns
+    private char[][] board;     // the M-by-N array of characters
+
+    // the 16 Boggle dice (1992 version)
+    private static final String[] boggle1992 = {
+        "LRYTTE", "VTHRWE", "EGHWNE", "SEOTIS",
+        "ANAEEG", "IDSYTT", "OATTOW", "MTOICU",
+        "AFPKFS", "XLDERI", "HCPOAS", "ENSIEU",
+        "YLDEVR", "ZNRNHL", "NMIQHU", "OBBAOJ"
+    };
+
+    // the 16 Boggle dice (1983 version)
+    private static final String[] boggle1983 = {
+        "AACIOT", "ABILTY", "ABJMOQ", "ACDEMP",
+        "ACELRS", "ADENVZ", "AHMORS", "BIFORX",
+        "DENOSW", "DKNOTU", "EEFHIY", "EGINTV",
+        "EGKLUY", "EHINPS", "ELPSTU", "GILRUW",
+    };
+
+    // the 25 Boggle Master / Boggle Deluxe dice
+    private static final String[] boggleMaster = {
+        "AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM",
+        "AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCNSTW",
+        "CEIILT", "CEILPT", "CEIPST", "DDLNOR", "DHHLOR",
+        "DHHNOT", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU",
+        "FIPRSY", "GORRVW", "HIPRRY", "NOOTUW", "OOOTTU"
+    };
+
+    // the 25 Big Boggle dice
+    private static final String[] boggleBig = {
+        "AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM",
+        "AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCENST",
+        "CEIILT", "CEILPT", "CEIPST", "DDHNOT", "DHHLOR",
+        "DHLNOR", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU",
+        "FIPRSY", "GORRVW", "IPRRRY", "NOOTUW", "OOOTTU"
+    };
+
+
+    // letters and frequencies of letters in the English alphabet
+    private static final String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+    private static final double[] frequencies = {
+        0.08167, 0.01492, 0.02782, 0.04253, 0.12703, 0.02228,
+        0.02015, 0.06094, 0.06966, 0.00153, 0.00772, 0.04025,
+        0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987,
+        0.06327, 0.09056, 0.02758, 0.00978, 0.02360, 0.00150,
+        0.01974, 0.00074
+    };
+
+    /**
+     * Initializes a random 4-by-4 board, by rolling the Hasbro dice.
+     */
+    public BoggleBoard() {
+        M = 4;
+        N = 4;
+        StdRandom.shuffle(boggle1992);
+        board = new char[M][N];
+        for (int i = 0; i < M; i++) {
+            for (int j = 0; j < N; j++) {
+                String letters = boggle1992[N*i+j];
+                int r = StdRandom.uniform(letters.length());
+                board[i][j] = letters.charAt(r);
+            }
+        }
+    }
+
+    /**
+     * Initializes a board from the given filename.
+     * @param filename the name of the file containing the Boggle board
+     */
+    public BoggleBoard(String filename) {
+        In in = new In(filename);
+        M = in.readInt();
+        N = in.readInt();
+        board = new char[M][N];
+        for (int i = 0; i < M; i++) {
+            for (int j = 0; j < N; j++) {
+                String letter = in.readString().toUpperCase();
+                if (letter.equals("QU"))
+                    board[i][j] = 'Q';
+                else if (letter.length() != 1)
+                    throw new IllegalArgumentException("invalid character: " + letter);
+                else if (alphabet.indexOf(letter) == -1)
+                    throw new IllegalArgumentException("invalid character: " + letter);
+                else 
+                    board[i][j] = letter.charAt(0);
+            }
+        }
+    }
+
+    /**
+     * Initializes a random M-by-N board, according to the frequency
+     * of letters in the English language.
+     * @param M the number of rows
+     * @param N the number of columns
+     */
+    public BoggleBoard(int M, int N) {
+        this.M = M;
+        this.N = N;
+        board = new char[M][N];
+        for (int i = 0; i < M; i++) {
+            for (int j = 0; j < N; j++) {
+                int r = StdRandom.discrete(frequencies);
+                board[i][j] = alphabet.charAt(r);
+            }
+        }
+    }
+
+    /**
+     * Initializes a board from the given 2d character array,
+     * with 'Q' representing the two-letter sequence "Qu".
+     * @param a the 2d character array
+     */
+    public BoggleBoard(char[][] a) {
+        this.M = a.length;
+        this.N = a[0].length;
+        board = new char[M][N];
+        for (int i = 0; i < M; i++) {
+            if (a[i].length != N)
+                throw new IllegalArgumentException("char[][] array is ragged");
+            for (int j = 0; j < N; j++) {
+                if (alphabet.indexOf(a[i][j]) == -1)
+                    throw new IllegalArgumentException("invalid character: " + a[i][j]);
+                board[i][j] = a[i][j];
+            }
+        }
+    }
+
+    /**
+     * Returns the number of rows.
+     * @return number of rows
+     */
+    public int rows() { return M; }
+
+    /**
+     * Returns the number of columns.
+     * @return number of columns
+     */
+    public int cols() { return N; }
+
+    /**
+     * Returns the letter in row i and column j,
+     * with 'Q' representing the two-letter sequence "Qu".
+     * @param i the row
+     * @param j the column
+     * @return the letter in row i and column j
+     *    with 'Q' representing the two-letter sequence "Qu".
+     */
+    public char getLetter(int i, int j) {
+        return board[i][j];
+    }
+
+    /**
+     * Returns a string representation of the board, replacing 'Q' with "Qu".
+     * @return a string representation of the board, replacing 'Q' with "Qu"
+     */
+    public String toString() {
+        StringBuilder sb = new StringBuilder(M + " " + N + "\n");
+        for (int i = 0; i < M; i++) {
+            for (int j = 0; j < N; j++) {
+                sb.append(board[i][j]);
+                if (board[i][j] == 'Q') sb.append("u ");
+                else sb.append("  ");
+            }
+            sb.append("\n");
+        }
+        return sb.toString().trim();
+    }
+
+    /**
+     * Unit tests the BoggleBoard data type.
+     */
+    public static void main(String[] args) {
+
+        // initialize a 4-by-4 board using Hasbro dice
+        StdOut.println("Hasbro board:");
+        BoggleBoard board1 = new BoggleBoard();
+        StdOut.println(board1);
+        StdOut.println();
+
+        // initialize a 4-by-4 board using letter frequencies in English language
+        StdOut.println("Random 4-by-4 board:");
+        BoggleBoard board2 = new BoggleBoard(4, 4);
+        StdOut.println(board2);
+        StdOut.println();
+
+        // initialize a 4-by-4 board from a 2d char array
+        StdOut.println("4-by-4 board from 2D character array:");
+        char[][] a =  {
+            { 'D', 'O', 'T', 'Y' },
+            { 'T', 'R', 'S', 'F' },
+            { 'M', 'X', 'M', 'O' },
+            { 'Z', 'A', 'B', 'W' }
+        };
+        BoggleBoard board3 = new BoggleBoard(a);
+        StdOut.println(board3);
+        StdOut.println();
+
+        // initialize a 4-by-4 board from a file
+        String filename = "board-quinquevalencies.txt";
+        StdOut.println("4-by-4 board from file " + filename + ":");
+        BoggleBoard board4 = new BoggleBoard(filename);
+        StdOut.println(board4);
+        StdOut.println();
+    }
+
+}