Solutions w6

1 files changed, 129 insertions, 18 deletions

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<Configuration> successors () {

-         throw new UnsupportedOperationException("successors : not supported yet.");        

+        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 g) {

-        throw new UnsupportedOperationException("compareTo : not supported yet.");        

-     }

+    public int compareTo(Configuration t) {

+        SlidingGame tsg = (SlidingGame) t;

+        return manhattan - tsg.getManhattan();

+    }

 

 }