diff options
Diffstat (limited to 'Week6/src/SlidingGame.java')
| -rw-r--r-- | Week6/src/SlidingGame.java | 205 |
1 files changed, 0 insertions, 205 deletions
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<Configuration> successors () {
- Collection<Configuration> successors = new ArrayList<Configuration>();
- 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();
- }
-
-}
|