From 3f702ed231134d224ee5fd5525f627a8058909a1 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Fri, 13 Mar 2015 19:34:04 +0100 Subject: Solutions w6 --- Week6/src/SlidingGame.java | 147 +++++++++++++++++++++++++++++++++++++++------ 1 file changed, 129 insertions(+), 18 deletions(-) (limited to 'Week6/src/SlidingGame.java') diff --git a/Week6/src/SlidingGame.java b/Week6/src/SlidingGame.java index 29e76fc..0e80797 100644 --- a/Week6/src/SlidingGame.java +++ b/Week6/src/SlidingGame.java @@ -1,21 +1,26 @@ +import java.util.ArrayList; import java.util.Collection; /** * @author Pieter Koopman, Sjaak Smetsers - * @version 1.2 - * @date 28-02-2015 + * @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 + * 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 int [][] board; + private final int [][] board; private int holeX, holeY; + private final int manhattan; /* * A constructor that initializes the board with the specified array @@ -25,7 +30,7 @@ public class SlidingGame implements Configuration public SlidingGame (int [] start) { board = new int[N][N]; - assert start.length == N*N: "Length of specified board incorrect"; + assert start.length == SIZE: "Length of specified board incorrect"; for( int p = 0; p < start.length; p++) { board[p % N][p / N] = start[p]; @@ -34,11 +39,72 @@ public class SlidingGame implements Configuration 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 + * The hole is displayed as a space. * @return the string representation */ @Override @@ -47,7 +113,8 @@ public class SlidingGame implements Configuration for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { int puzzel = board[col][row]; - buf.append(puzzel == HOLE ? " " : puzzel + " "); + // 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"); } @@ -55,11 +122,11 @@ public class SlidingGame implements Configuration } /* - * a standard implementation of equals checking - * whether 2 boards are filled in exactly the same way - * @return a boolean indicating equality + * 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 + @Override public boolean equals(Object o) { if (o == null || o.getClass() != getClass()) { return false; @@ -78,17 +145,61 @@ public class SlidingGame implements Configuration @Override public boolean isSolution () { - throw new UnsupportedOperationException("isGoal : not supported yet."); - } + for( int p = 0; p < SIZE; p++) { + if (board[p % N][p / N] != p + 1) { + return false; + } + } + return true; + } @Override public Collection successors () { - throw new UnsupportedOperationException("successors : not supported yet."); + 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 g) { - throw new UnsupportedOperationException("compareTo : not supported yet."); - } + public int compareTo(Configuration t) { + SlidingGame tsg = (SlidingGame) t; + return manhattan - tsg.getManhattan(); + } } -- cgit v1.2.3