Reorganised projects

6 files changed, 434 insertions, 0 deletions

diff --git a/Week6 Sliding game solver/src/Configuration.java b/Week6 Sliding game solver/src/Configuration.java
new file mode 100644
index 0000000..7264c5f
--- /dev/null
+++ b/Week6 Sliding game solver/src/Configuration.java
@@ -0,0 +1,21 @@
+import java.util.Collection;
+
+
+/**
+ * An interface for representing nodes in a state space.
+ * 
+ * @author Sjaak Smetsers
+ * @version 1.2
+ * @date 28-02-2015
+ */
+public interface Configuration extends Comparable<Configuration> {
+    /*
+     * To obtain the successors for a specific configuration
+     * @return a collection of configurations containing the successors
+     */
+	public Collection<Configuration> successors ();
+    /*
+     * For marking final / solution configurations.
+     */
+	public boolean isSolution ();
+}
diff --git a/Week6 Sliding game solver/src/Direction.java b/Week6 Sliding game solver/src/Direction.java
new file mode 100644
index 0000000..d4837b9
--- /dev/null
+++ b/Week6 Sliding game solver/src/Direction.java
@@ -0,0 +1,26 @@
+/**

+ * @author Sjaak Smetsers

+ * @version 1.2

+ * @date 28-02-2015

+ * An enumeration type for the 4 points of the compass 

+ * Each constant has 2 (final) int attributes indicating

+ * the displacement of each direction on a 2-dimensional grid 

+ * of which the origin is located in the upper left corner

+ */

+public enum Direction {

+    NORTH (0,-1), EAST (1,0), SOUTH(0,1), WEST(-1,0);

+    

+    private final int dx, dy;

+    private Direction (int dx, int dy) {

+        this.dx = dx;

+        this.dy = dy;

+    }

+    

+    public int GetDX () {

+        return dx;

+    }

+

+    public int GetDY () {

+        return dy;

+    }

+}

diff --git a/Week6 Sliding game solver/src/Main.java b/Week6 Sliding game solver/src/Main.java
new file mode 100644
index 0000000..4225013
--- /dev/null
+++ b/Week6 Sliding game solver/src/Main.java
@@ -0,0 +1,35 @@
+/**

+ * Solutions for the assignments of week 6.

+ * @author Camil Staps, s4498062

+ */

+public class Main

+{

+

+    /**

+     * Create a new sliding game, attempt to solve it and if it succeeds show a solution.

+     * @param args command-line arguments are ignored.

+     */

+    public static void main(String[] args) {

+        // Some examples:

+        // N = 5

+        //int[] x = {7,17,9,4,5,1,12,15,6,10,3,23,25,14,8,22,2,18,19,24,16,21,11,13,20};  // May take some time (that is, it did not find a solution after some hours here, I didn't check if there is one)

+        //int[] x = {2,4,6,8,10,1,3,5,7,9,12,14,16,18,20,11,13,15,17,19,21,22,23,24,25};  // Solution in 90

+        // N = 4

+        //int[] x = {2,3,10,11,14,1,13,15,5,4,8,7,6,12,9,16};     // Solution in 112

+        //int[] x = {10,8,16,7,6,13,15,3,14,1,4,2,5,9,12,11};     // Solution in 144

+        //int[] x = {9,12,5,4,2,16,7,11,3,6,10,13,14,1,8,15};     // Solution in 140

+        // N = 3

+        //int[] x = {8,7,6,5,4,3,1,2,9};                          // No solution (evaluates 292102 different boards before failing)

+        int[] x = {5,9,3,4,6,2,8,7,1};                          // Solution in 35

+        

+        SlidingGame sg = new SlidingGame(x);

+        System.out.println("Solving:\n" + sg);

+        Solver s = new Solver(sg);

+        if (s.solve()) {

+            System.out.println("Success!");

+            System.out.println(s.getWinner());

+        } else {

+            System.out.println("Failure...");

+        }

+    }

+}

diff --git a/Week6 Sliding game solver/src/Node.java b/Week6 Sliding game solver/src/Node.java
new file mode 100644
index 0000000..cb5c900
--- /dev/null
+++ b/Week6 Sliding game solver/src/Node.java
@@ -0,0 +1,92 @@
+import java.util.ArrayList;

+

+/**

+ * For maintaining lists of T-elements enabling

+ * a structure suited for backwards traversal

+ * 

+ * @author Pieter Koopman, Sjaak Smetsers

+ * @author Camil Staps, s4498062

+ * 

+ * @param <T> The element this node is based on

+ */

+@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.

+public class Node<T extends Comparable> implements Comparable<Node<T>>

+{

+    // the data field

+    private final T item;

+    // a reference to the predecessor

+    private final Node<T> previous;

+

+    /* A constructor that initializes each node

+     * with the specified values

+     * @param from the node preceding the current node

+     * @param item the initial data item

+     */

+    public Node (Node<T> from, T item) {

+        this.previous    = from;

+        this.item        = item;

+    }

+

+    /* a getter for the item

+     * @return item

+     */

+    public T getItem() {

+        return item;

+    }

+

+    /*

+     * a getter for the predecessor

+     * @return previous

+     */

+    public Node<T> getPrevious() {

+        return previous;

+    }

+

+    /*

+     * determines the length of the current list

+     * @return the length as an integer

+     */

+    public int length () {

+        int length = 1;

+        Node<T> prev = previous;

+        while ( prev != null ) {

+            prev = prev.previous;

+            length++;

+        }

+        return length;

+    }

+    

+    @Override

+    public String toString() {

+        StringBuilder result = new StringBuilder();

+        

+        ArrayList<Node<T>> path;

+        path = new ArrayList<Node<T>>();

+        Node<T> prev = this;

+        while ( prev != null ) {

+            path.add(prev);

+            prev = prev.previous;

+        }

+        

+        for (int i = path.size() - 1; i >= 0; i--)

+            result.append(path.size() - i - 1).append(":\n").append(path.get(i).getItem().toString());

+        

+        return result.toString();

+    }

+    

+    /**

+     * Just comparing the items isn't very clever. The Manhattan distance is a fairly small number.

+     * With large queues, many nodes will then have the same priority. It's much better to select

+     * on both Manhattan distance and path length. That way, we will find shorter paths.

+     * Note though that since we're prioritizing on Manhattan distance primarily, this does not 

+     * mean that we necessarily find the shortest path.

+     * @param t

+     * @return 

+     */

+    @Override

+    public int compareTo(Node<T> t) {

+        if (this.item.compareTo(t.item) == 0)

+            return Integer.compare(length(), t.length());

+        return this.item.compareTo(t.item);

+    }

+}

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<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();

+    }

+

+}

diff --git a/Week6 Sliding game solver/src/Solver.java b/Week6 Sliding game solver/src/Solver.java
new file mode 100644
index 0000000..9b78f27
--- /dev/null
+++ b/Week6 Sliding game solver/src/Solver.java
@@ -0,0 +1,55 @@
+import java.util.HashSet;

+import java.util.PriorityQueue;

+import java.util.Queue;

+

+/**

+ * A class that implements a breadth-first search algorithm

+ * for finding the Configurations for which the isSolution predicate holds

+ * 

+ * @author Pieter Koopman, Sjaak Smetsers

+ * @author Camil Staps, s4498062

+ */

+@SuppressWarnings("Convert2Diamond")    // We disable these warnings for Java <=1.7 compatibility.

+public class Solver

+{

+    // A queue for maintaining graphs that are not visited yet.

+    private final Queue<Node<Configuration>> toExamine = new PriorityQueue<Node<Configuration>>();

+    private final HashSet<Configuration> examined = new HashSet<Configuration>();

+    

+    private Node winner = null;

+

+    public Solver(Configuration g) {

+        toExamine.add(new Node(null, g));

+    }

+    

+    /* A skeleton implementation of the solver

+     * @return a string representation of the solution

+     */

+    public boolean solve () {

+        while (!toExamine.isEmpty()) {

+            Node next = toExamine.remove();

+            Configuration nextConfiguration = (Configuration) next.getItem();

+            examined.add(nextConfiguration);

+            if (nextConfiguration.isSolution()) {

+                winner = next;

+                return true;

+            } else {

+                for (Configuration succ: nextConfiguration.successors()) {

+                    if (!examined.contains(succ)) {

+                        toExamine.add(new Node(next, succ));

+                    }

+                }

+            }

+        }

+        return false;

+    }

+    

+    /**

+     * Return the winning Node (from which the path can be reconstructed)

+     * @return the node in which we found a solution

+     */

+    public Node getWinner() {

+        return winner;

+    }

+    

+}