diff options
Diffstat (limited to 'Algorithms/Part-II/4-Boggle/BoggleBoard.java')
| -rw-r--r-- | Algorithms/Part-II/4-Boggle/BoggleBoard.java | 217 |
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(); + } + +} |