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/src/Configuration.java | 21 ----- Week6/src/Direction.java | 26 ------ Week6/src/Main.java | 35 -------- Week6/src/Node.java | 92 ------------------- Week6/src/SlidingGame.java | 205 ------------------------------------------- Week6/src/Solver.java | 55 ------------ 6 files changed, 434 deletions(-) delete mode 100644 Week6/src/Configuration.java delete mode 100644 Week6/src/Direction.java delete mode 100644 Week6/src/Main.java delete mode 100644 Week6/src/Node.java delete mode 100644 Week6/src/SlidingGame.java delete mode 100644 Week6/src/Solver.java (limited to 'Week6/src') 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 { - /* - * To obtain the successors for a specific configuration - * @return a collection of configurations containing the successors - */ - public Collection 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 The element this node is based on - */ -@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility. -public class Node implements Comparable> -{ - // the data field - private final T item; - // a reference to the predecessor - private final Node 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 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 getPrevious() { - return previous; - } - - /* - * determines the length of the current list - * @return the length as an integer - */ - public int length () { - int length = 1; - Node prev = previous; - while ( prev != null ) { - prev = prev.previous; - length++; - } - return length; - } - - @Override - public String toString() { - StringBuilder result = new StringBuilder(); - - ArrayList> path; - path = new ArrayList>(); - Node 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) { - 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 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(); - } - -} 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> toExamine = new PriorityQueue>(); - private final HashSet examined = new HashSet(); - - 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; - } - -} -- cgit v1.2.3