From 6a44b074f0169a1b0f9e92347af929c5e471746e Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Sat, 18 Apr 2015 13:44:44 +0200 Subject: Reorganised projects --- Week6/src/SlidingGame.java | 205 --------------------------------------------- 1 file changed, 205 deletions(-) delete mode 100644 Week6/src/SlidingGame.java (limited to 'Week6/src/SlidingGame.java') diff --git a/Week6/src/SlidingGame.java b/Week6/src/SlidingGame.java deleted file mode 100644 index 0e80797..0000000 --- a/Week6/src/SlidingGame.java +++ /dev/null @@ -1,205 +0,0 @@ -import java.util.ArrayList; -import java.util.Collection; - -/** - * @author Pieter Koopman, Sjaak Smetsers - * @author Camil Staps, s4498062 - * - * A template implementation of a sliding game also - * implementing the Graph interface - */ -@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility. -public class SlidingGame implements Configuration -{ - public static final int N = 3, SIZE = N * N, HOLE = SIZE; - - /* - * The board is represented by a 2-dimensional array; - * The position of the hole is kept in 2 variables holeX and holeY - * We store the summed manhattan of all tiles and the hole in manhattan - */ - private final int [][] board; - private int holeX, holeY; - private final int manhattan; - - /* - * A constructor that initializes the board with the specified array - * @param start: a one dimensional array containing the initial board. - * The elements of start are stored row-wise. - */ - public SlidingGame (int [] start) { - board = new int[N][N]; - - assert start.length == SIZE: "Length of specified board incorrect"; - - for( int p = 0; p < start.length; p++) { - board[p % N][p / N] = start[p]; - if ( start[p] == HOLE ) { - holeX = p % N; - holeY = p / N; - } - } - - manhattan = calculateManhattan(); - } - - /** - * A constructor that initialises the board with a specified 2D array - * @param board a 2D array containing the initial board - */ - public SlidingGame (int[][] board) { - this.board = new int[N][N]; - - assert board.length == N: "Length of specified board incorrect"; - - for (int a = 0; a < N; a++) { - assert board[a].length == N: "Length of specified board incorrect"; - for (int b = 0; b < N; b++) { - this.board[a][b] = board[a][b]; - if (board[a][b] == HOLE) { - holeX = a; - holeY = b; - } - } - } - - manhattan = calculateManhattan(); - } - - /** - * Calculate the summed Manhattan distance for all tiles and the hole - * @return the Manhattan distance - */ - private int calculateManhattan() { - int result = 0; - for (int x = 0; x < N; x++) { - for (int y = 0; y < N; y++) { - int this_x = (board[x][y] - 1) % N; - int this_y = (board[x][y] - 1) / N; - result += Math.abs(this_x - x) + Math.abs(this_y - y); - } - } - return result; - } - - public int getManhattan() { - return manhattan; - } - - /** - * Attempt to move the hole in a specified direction - * @param d the direction in which to move - * @return A new instance of this class where the hole has moved - * @throws ArrayIndexOutOfBoundsException If the hole cannot be moved - */ - private SlidingGame move(Direction d) throws ArrayIndexOutOfBoundsException { - int[][] newboard = new int[N][N]; - for (int a = 0; a < N; a++) - System.arraycopy(board[a], 0, newboard[a], 0, N); - - newboard[holeX][holeY] = newboard[holeX + d.GetDX()][holeY + d.GetDY()]; - newboard[holeX + d.GetDX()][holeY + d.GetDY()] = HOLE; - return new SlidingGame(newboard); - } - - /* - * Converts a board into a printable representation. - * The hole is displayed as a space. - * @return the string representation - */ - @Override - public String toString() { - StringBuilder buf = new StringBuilder(); - for (int row = 0; row < N; row++) { - for (int col = 0; col < N; col++) { - int puzzel = board[col][row]; - // Using String.format to pad left as in http://stackoverflow.com/a/391978/1544337; provides better formatting for puzzles with N > 3 - buf.append(String.format("%1$" + ((int) Math.log10(SIZE - 1) + 2) + "s", puzzel == HOLE ? " " : puzzel + " ")); - } - buf.append("\n"); - } - return buf.toString(); - } - - /* - * A standard implementation of equals checking whether 2 boards are filled - * in exactly the same way. - * @return true iff this object and o are equal - */ - @Override - public boolean equals(Object o) { - if (o == null || o.getClass() != getClass()) { - return false; - } else { - SlidingGame other_puzzle = (SlidingGame) o; - for (int row = 0; row < N; row++) { - for (int col = 0; col < N; col++) { - if (board[col][row] != other_puzzle.board[col][row]) { - return false; - } - } - } - return true; - } - } - - @Override - public boolean isSolution () { - for( int p = 0; p < SIZE; p++) { - if (board[p % N][p / N] != p + 1) { - return false; - } - } - return true; - } - - @Override - public Collection successors () { - Collection successors = new ArrayList(); - try { - successors.add(move(Direction.EAST)); - } catch (ArrayIndexOutOfBoundsException e) {} - try { - successors.add(move(Direction.SOUTH)); - } catch (ArrayIndexOutOfBoundsException e) {} - try { - successors.add(move(Direction.WEST)); - } catch (ArrayIndexOutOfBoundsException e) {} - try { - successors.add(move(Direction.NORTH)); - } catch (ArrayIndexOutOfBoundsException e) {} - return successors; - } - - /** - * According to the assignment we should use: - * result += board[x][y] * Math.pow(31, x + N*y); - * However, this results for even small boards in INT_MAX, so this is not very useful. - * - * Giving every board a unique hash would be: - * result += board[x][y] * Math.pow(SIZE, x + N*y); - * However, already with N=4 that results in INT_MAX as well. - * - * The current implementation uses SIZE as base and subtracts n(n-1) from the exponent. - * This results in values well below INT_MAX for N up to 5 (and possibly higher). - * Of course, it also means that different puzzles may have the same value. - * For N>3 this is unavoidable since 16! > INT_MAX. For N <= 3 we are not too concerned - * since the program is fast enough for small programs for us to accept this imperfectness. - */ - @Override - public int hashCode() { - int result = 0; - for (int x = 0; x < N; x++) - for (int y = 0; y < N; y++) - result += board[x][y] * Math.pow(SIZE, x + N*y - (N-1)*N); - - return result; - } - - @Override - public int compareTo(Configuration t) { - SlidingGame tsg = (SlidingGame) t; - return manhattan - tsg.getManhattan(); - } - -} -- cgit v1.2.3