Reorganised projects

6 files changed, 0 insertions, 434 deletions

diff --git a/Week6/src/Configuration.java b/Week6/src/Configuration.java
deleted file mode 100644
index 7264c5f..0000000
--- a/Week6/src/Configuration.java
+++ /dev/null
@@ -1,21 +0,0 @@
-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/src/Direction.java b/Week6/src/Direction.java
deleted file mode 100644
index d4837b9..0000000
--- a/Week6/src/Direction.java
+++ /dev/null
@@ -1,26 +0,0 @@
-/**

- * @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/src/Main.java b/Week6/src/Main.java
deleted file mode 100644
index 4225013..0000000
--- a/Week6/src/Main.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/**

- * 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/src/Node.java b/Week6/src/Node.java
deleted file mode 100644
index cb5c900..0000000
--- a/Week6/src/Node.java
+++ /dev/null
@@ -1,92 +0,0 @@
-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/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();

-    }

-

-}

diff --git a/Week6/src/Solver.java b/Week6/src/Solver.java
deleted file mode 100644
index 9b78f27..0000000
--- a/Week6/src/Solver.java
+++ /dev/null
@@ -1,55 +0,0 @@
-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;

-    }

-    

-}