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 Sliding game solver/src/SlidingGame.java | 205 +++++++++++++++++++++++++ 1 file changed, 205 insertions(+) create mode 100644 Week6 Sliding game solver/src/SlidingGame.java (limited to 'Week6 Sliding game solver/src/SlidingGame.java') diff --git a/Week6 Sliding game solver/src/SlidingGame.java b/Week6 Sliding game solver/src/SlidingGame.java new file mode 100644 index 0000000..0e80797 --- /dev/null +++ b/Week6 Sliding game solver/src/SlidingGame.java @@ -0,0 +1,205 @@ +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