diff options
Diffstat (limited to 'Week6/src')
| -rw-r--r-- | Week6/src/LICENSE | 21 | ||||
| -rw-r--r-- | Week6/src/Main.java | 35 | ||||
| -rw-r--r-- | Week6/src/Node.java | 46 | ||||
| -rw-r--r-- | Week6/src/SlidingGame.java | 147 | ||||
| -rw-r--r-- | Week6/src/Solver.java | 44 | ||||
| -rw-r--r-- | Week6/src/week6/Week6.java | 21 |
6 files changed, 248 insertions, 66 deletions
diff --git a/Week6/src/LICENSE b/Week6/src/LICENSE new file mode 100644 index 0000000..10b7271 --- /dev/null +++ b/Week6/src/LICENSE @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2015 Camil Staps <info@camilstaps.nl> + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE.
\ No newline at end of file diff --git a/Week6/src/Main.java b/Week6/src/Main.java index 9122749..4225013 100644 --- a/Week6/src/Main.java +++ b/Week6/src/Main.java @@ -1,16 +1,35 @@ /**
- *
- * @author Pieter Koopman, Sjaak Smetsers
+ * 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) {
- int [] game = {1,2,3, 4,5,6, 7,9,8};
-
- SlidingGame s = new SlidingGame (game);
- System.out.println(s);
-// Solver solver = new Solver(s);
-// System.out.println(solver.solve());
+ // 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 index 2a33cc4..cb5c900 100644 --- a/Week6/src/Node.java +++ b/Week6/src/Node.java @@ -1,16 +1,21 @@ +import java.util.ArrayList;
+
/**
* For maintaining lists of T-elements enabling
* a structure suited for backwards traversal
+ *
* @author Pieter Koopman, Sjaak Smetsers
- * @version 1.2
- * @date 28-02-2015
+ * @author Camil Staps, s4498062
+ *
+ * @param <T> The element this node is based on
*/
-public class Node<T>
+@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 T item;
+ private final T item;
// a reference to the predecessor
- private Node<T> previous;
+ private final Node<T> previous;
/* A constructor that initializes each node
* with the specified values
@@ -53,6 +58,35 @@ public class Node<T> @Override
public String toString() {
- throw new UnsupportedOperationException("toString : not supported yet.");
+ 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 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();
+ }
}
diff --git a/Week6/src/Solver.java b/Week6/src/Solver.java index 137646c..9b78f27 100644 --- a/Week6/src/Solver.java +++ b/Week6/src/Solver.java @@ -1,37 +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
- * @version 1.3
- * @date 28-02-2013
+ * @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.
- Queue<Configuration> toExamine;
+ 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) {
- throw new UnsupportedOperationException("Solver: not supported yet.");
+ toExamine.add(new Node(null, g));
}
/* A skeleton implementation of the solver
* @return a string representation of the solution
*/
- public String solve () {
- while (! toExamine.isEmpty() ) {
- Configuration next = toExamine.remove();
- if ( next.isSolution() ) {
- return "Success!";
+ 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: next.successors() ) {
- toExamine.add (succ);
+ for (Configuration succ: nextConfiguration.successors()) {
+ if (!examined.contains(succ)) {
+ toExamine.add(new Node(next, succ));
+ }
}
}
}
- return "Failure!";
+ 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;
}
}
diff --git a/Week6/src/week6/Week6.java b/Week6/src/week6/Week6.java deleted file mode 100644 index 832b947..0000000 --- a/Week6/src/week6/Week6.java +++ /dev/null @@ -1,21 +0,0 @@ -/* - * To change this license header, choose License Headers in Project Properties. - * To change this template file, choose Tools | Templates - * and open the template in the editor. - */ -package week6; - -/** - * - * @author camilstaps - */ -public class Week6 { - - /** - * @param args the command line arguments - */ - public static void main(String[] args) { - // TODO code application logic here - } - -} |