jules0707

Board.java

Dec 2nd, 2020
451
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import edu.princeton.cs.algs4.Stack;
  3. import edu.princeton.cs.algs4.StdRandom;
  4.  
  5.  
  6. public class Board {
  7.     private final int dimension; // the dimension of the board
  8.     private final int[][] tiles;
  9.     private int manhattan = -1;
  10.     private int hamming = -1;
  11.     private byte blankTile_i;
  12.     private byte blankTile_j;
  13.     private byte swapTwinTile1;
  14.     private byte swapTwinTile2;
  15.     private boolean foundBlankTile;
  16.  
  17.  
  18.     // create a board from an n-by-n array of tiles,
  19.     // where tiles[row][col] = tile at (row, col)
  20.     public Board(int[][] initials) {
  21.         // we have to do a double nested loop to copy the entries in a two-dimensional array as Arrays,copyOf or
  22.         // clone only deep-copy one dimensional array
  23.         int length = initials.length;
  24.         assert 2 <= length;
  25.         assert length < 128;
  26.         this.tiles = initials;
  27.         this.dimension = length;
  28.         this.hamming = hamming();
  29.         this.manhattan = manhattan();
  30.         findBlankTile(initials);
  31.     }
  32.  
  33.     // defensive copy of input to ensure immutability
  34.     private void findBlankTile(int[][] tiles) {
  35.         int N = tiles.length;
  36.         for (byte i = 0; i < N; i++) {
  37.             for (byte j = 0; j < N; j++) {
  38.                 // search for blank tile position as we touch on the array for the first time
  39.                 if (!foundBlankTile) {
  40.                     if (tiles[i][j] == 0) {
  41.                         foundBlankTile = true;
  42.                         blankTile_i = i;
  43.                         blankTile_j = j;
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49.  
  50.     // string representation of this board
  51.     public String toString() {
  52.         StringBuilder s = new StringBuilder();
  53.         s.append(dimension + "\n");
  54.         for (byte i = 0; i < dimension; i++) {
  55.             for (byte j = 0; j < dimension; j++) {
  56.                 s.append(String.format("%2d ", tiles[i][j]));
  57.             }
  58.             s.append("\n");
  59.         }
  60.         return s.toString();
  61.     }
  62.  
  63.     // board dimension n * n
  64.     public int dimension() {
  65.         return tiles.length;
  66.     }
  67.  
  68.     // sum of Manhattan distances between tiles and goal
  69.     public int manhattan() {
  70.         int manhattanValue;
  71.         // has manhattan already been computed?
  72.         if (manhattan >= 0) return manhattan;
  73.         else {
  74.             manhattanValue = 0;
  75.             for (byte i = 0; i < dimension; i++) {
  76.                 for (byte j = 0; j < dimension; j++) {
  77.                     int tileFound = tiles[i][j];
  78.                     int tileExpected = tile(i, j); // the expected number at position (i,j)
  79.                     if (tileFound != 0) {  // we ignore the blank tile
  80.                         if (tileFound != tileExpected) {
  81.                             int i_expected = index_i_of(tileFound);
  82.                             int j_expected = index_j_of(tileFound);
  83.                             manhattanValue += Math.abs(i - i_expected) + Math.abs(j - j_expected);
  84.                         }
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.         manhattan = manhattanValue;
  90.         return manhattan;
  91.     }
  92.  
  93.     // number of tiles out of place
  94.     public int hamming() {
  95.         int hammingValue;
  96.         if (hamming >= 0) return hamming;
  97.         else {
  98.             hammingValue = 0;
  99.             for (byte i = 0; i < dimension; i++) {
  100.                 for (byte j = 0; j < dimension; j++) {
  101.                     int tileFound = tiles[i][j];
  102.                     if (tileFound != 0) { // we ignore the blank tile
  103.                         if (tileFound != tile(i, j)) {
  104.                             hammingValue++;
  105.                         } // tileFound is not at its sequential place
  106.                     }
  107.                 }
  108.             }
  109.             hamming = hammingValue; // we set the hamming value to avoid recomputation
  110.         }
  111.         return hamming;
  112.     }
  113.  
  114.     // is this board the goal board?
  115.     public boolean isGoal() {
  116.         return hamming == 0;
  117.     }
  118.  
  119.     private int index_j_of(int tile) {
  120.         return tile - (index_i_of(tile) * dimension + 1);
  121.     }
  122.  
  123.     private int index_i_of(int tile) {
  124.         return (tile - 1) / dimension;
  125.     }
  126.  
  127.     private int tile(int i, int j) {
  128.         return i * dimension + j + 1;
  129.     }
  130.  
  131.  
  132.     // does this board equal y?
  133.     @Override
  134.     public boolean equals(Object y) {
  135.         // taken from  p. 103 of Algorithms, 4th edition.
  136.         if (this == y) return true;
  137.         if (y == null) return false;
  138.         if (this.getClass() != y.getClass()) return false;
  139.         Board that = (Board) y;
  140.  
  141.         // test the values of each instance variables of the two boards
  142.         if (this.dimension != that.dimension) return false;
  143.         if (this.hamming != that.hamming) return false;
  144.         if (this.manhattan != that.manhattan) return false;
  145.  
  146.         // we assume the two boards are equals until found different
  147.         int false_count = 0;
  148.  
  149.         // we compare the values of each tiles of the two puzzles one at a time and stop as soon as an inequality is found
  150.         for (byte i = 0; i < dimension; i++) {
  151.             for (byte j = 0; j < dimension; j++) {
  152.                 if (this.tiles[i][j] != that.tiles[i][j]) {
  153.                     false_count++;
  154.                 }
  155.             }
  156.         }
  157.         return false_count == 0;
  158.     }
  159.  
  160.  
  161.     private static int[][] hardCopy(int[][] initial, int blank_i, int blank_j, int swap_i, int swap_j) {
  162.         int N = initial[0].length;
  163.         int[][] hardCopy = new int[N][N];
  164.  
  165.         // we do an independent copy of initial
  166.         for (byte i = 0; i < N; i++) {
  167.             for (byte j = 0; j < N; j++) {
  168.                 // we found the blank tile
  169.                 if (i == blank_i && j == blank_j) {
  170.                     // we copy it to the swaped location
  171.                     hardCopy[i][j] = initial[swap_i][swap_j];
  172.                 }
  173.                 // we found the tile to swap
  174.                 else if (i == swap_i && j == swap_j) {
  175.                     // we copy it to the blank tile location
  176.                     hardCopy[swap_i][swap_j] = initial[blank_i][blank_j];
  177.                 } else {
  178.                     // we copy all the  other tiles
  179.                     hardCopy[i][j] = initial[i][j];
  180.                 }
  181.             }
  182.         }
  183.         return hardCopy;
  184.     }
  185.  
  186.  
  187.     // all neighboring boards
  188.     public Iterable<Board> neighbors() {
  189.         Board neighbour;
  190.         Stack<Board> neighbours = new Stack<>();
  191.  
  192.         // we have a top neighbour
  193.         if (blankTile_i - 1 >= 0) {
  194.             int[][] tilesCopy = hardCopy(tiles, blankTile_i, blankTile_j, blankTile_i - 1, blankTile_j);
  195.             neighbour = new Board(tilesCopy);
  196.             neighbours.push(neighbour);
  197.         }
  198.  
  199.         // bottom neighbour
  200.         if (blankTile_i + 1 < dimension) {
  201.             int[][] tilesCopy = hardCopy(tiles, blankTile_i, blankTile_j, blankTile_i + 1, blankTile_j);
  202.             neighbour = new Board(tilesCopy);
  203.             neighbours.push(neighbour);
  204.         }
  205.  
  206.         // right neighbour
  207.         if (blankTile_j + 1 < dimension) {
  208.             int[][] tilesCopy = hardCopy(tiles, blankTile_i, blankTile_j, blankTile_i, blankTile_j + 1);
  209.             neighbour = new Board(tilesCopy);
  210.             neighbours.push(neighbour);
  211.         }
  212.  
  213.         // left neighbour
  214.         if (blankTile_j - 1 >= 0) {
  215.             int[][] tilesCopy = hardCopy(tiles, blankTile_i, blankTile_j, blankTile_i, blankTile_j - 1);
  216.             neighbour = new Board(tilesCopy);
  217.             neighbours.push(neighbour);
  218.         }
  219.         return neighbours;
  220.     }
  221.  
  222.  
  223.     private static int[][] hardCopy2(int[][] initial, int i_1, int j_1, int i_2, int j_2) {
  224.         int N = initial[0].length;
  225.         int[][] hardCopy2 = new int[N][N];
  226.  
  227.         // we do an independent copy of initial
  228.         for (byte i = 0; i < N; i++) {
  229.             for (byte j = 0; j < N; j++) {
  230.                 // we found the tile 1 to swap
  231.                 if (i == i_1 && j == j_1) {
  232.                     // we copy it to the swaped location
  233.                     hardCopy2[i][j] = initial[i_2][j_2];
  234.                 }
  235.                 // we found the tile 2 to swap
  236.                 else if (i == i_2 && j == j_2) {
  237.                     // we copy it to the blank tile location
  238.                     hardCopy2[i][j] = initial[i_1][j_1];
  239.                 } else {
  240.                     // we copy all the  other tiles
  241.                     hardCopy2[i][j] = initial[i][j];
  242.                 }
  243.             }
  244.         }
  245.         return hardCopy2;
  246.     }
  247.  
  248.  
  249.     // a board that is obtained by exchanging any pair of tiles except the blank square that is not a tile
  250.     public Board twin() {
  251.         if (swapTwinTile1 == 0 && swapTwinTile2 == 0) {
  252.             do {
  253.                 // we pick two random non nul distinct integer that are less than the dimension of the number of tiles in the board
  254.                 swapTwinTile1 = (byte) StdRandom.uniform(1, dimension * dimension);
  255.                 swapTwinTile2 = (byte) StdRandom.uniform(1, dimension * dimension);
  256.             } while (swapTwinTile1 == swapTwinTile2);
  257.         }
  258.  
  259.         // find location of tile1 & tile2
  260.         int[] tile1Coordinates = findCoordinates(swapTwinTile1);
  261.         int[] tiles2Coordinates = findCoordinates(swapTwinTile2);
  262.  
  263.         int i1 = tile1Coordinates[0];
  264.         int j1 = tile1Coordinates[1];
  265.         int i2 = tiles2Coordinates[0];
  266.         int j2 = tiles2Coordinates[1];
  267.  
  268.         // we reference the copy of tiles
  269.         int[][] twin = hardCopy2(tiles, i1, j1, i2, j2);
  270.  
  271.         return new Board(twin);
  272.     }
  273.  
  274.     private int[] findCoordinates(int tile) {
  275.         int coordinate_i = -1;
  276.         int coordinate_j = -1;
  277.         for (byte i = 0; i < dimension; i++) {
  278.             for (byte j = 0; j < dimension; j++) {
  279.                 if (tiles[i][j] == tile) {
  280.                     coordinate_i = i;
  281.                     coordinate_j = j;
  282.                     break;
  283.                 }
  284.             }
  285.         }
  286.         // TODO try catch here for corner cases of NaN and others like not found -1??
  287.         return new int[]{coordinate_i, coordinate_j};
  288.     }
  289.  
  290.     // unit testing (not graded)
  291. /*    public static void main(String[] args) {
  292.  
  293.         for (String filename : args) {
  294.             In in = new In(filename);
  295.             int n = in.readInt();
  296.             int[][] tiles = new int[n][n];
  297.             for (int i = 0; i < n; i++) {
  298.                 for (int j = 0; j < n; j++) {
  299.                     tiles[i][j] = in.readInt();
  300.                 }
  301.             }
  302.             Board b = new Board(tiles);
  303.  
  304.             StdOut.println("The board: " + b.toString());
  305.             StdOut.println("The neighbours: " + b.neighbors());
  306.             StdOut.println("manhattan of board: " + b.manhattan);
  307.             StdOut.println("hamming of board: " + b.hamming);
  308. */
  309.  
  310. //            StdOut.println("A twin 1st time : " + b.twin().toString());
  311. //            StdOut.println("twin equals twin : " + b.twin().equals(b.twin()));
  312. //
  313. //            b.neighbors();
  314. //
  315. //            StdOut.println("A twin 2nd time : " + b.twin().toString());
  316. //            b.neighbors();
  317. //
  318. //            StdOut.println("A twin 3rd time : " + b.twin().toString());
  319. //            b.neighbors();
  320. //
  321. //            StdOut.println("A twin 4th time : " + b.twin().toString());
  322. //            b.neighbors();
  323. //
  324. //
  325. //            StdOut.println("twin equals twin once : " + b.twin().equals(b.twin()));
  326. //            StdOut.println("twin equals twin twice : " + b.twin().equals(b.twin()));
  327. //            StdOut.println("twin equals twin three times : " + b.twin().equals(b.twin()));
  328. //
  329. //            StdOut.println("list of neighbours : " + " \n " + b.neighbors().toString());
  330. //            StdOut.println("A list of neighbours 5th time : " + b.neighbors().toString());
  331. //
  332. //            int[][] tiles1 = {{8, 5, 4}, {7, 0, 6}, {3, 1, 2}};
  333. //            int[][] tiles2 = {{8, 5, 4}, {7, 0, 6}, {3, 2, 1}};
  334. //
  335. //            Board board1 = new Board(tiles1);
  336. //            Board board2 = new Board(tiles2);
  337. //
  338. //            StdOut.println(board1.equals(board2));
  339. //
  340. //
  341. //        }
  342. //    } // end of main()
  343. } // end
RAW Paste Data