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 Sliding game solver/src/Configuration.java | 21 +++ Week6 Sliding game solver/src/Direction.java | 26 +++ Week6 Sliding game solver/src/Main.java | 35 ++++ Week6 Sliding game solver/src/Node.java | 92 ++++++++++ Week6 Sliding game solver/src/SlidingGame.java | 205 +++++++++++++++++++++++ Week6 Sliding game solver/src/Solver.java | 55 ++++++ 6 files changed, 434 insertions(+) create mode 100644 Week6 Sliding game solver/src/Configuration.java create mode 100644 Week6 Sliding game solver/src/Direction.java create mode 100644 Week6 Sliding game solver/src/Main.java create mode 100644 Week6 Sliding game solver/src/Node.java create mode 100644 Week6 Sliding game solver/src/SlidingGame.java create mode 100644 Week6 Sliding game solver/src/Solver.java (limited to 'Week6 Sliding game solver/src') 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 { + /* + * 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 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 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 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 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 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> 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