From 3f702ed231134d224ee5fd5525f627a8058909a1 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Fri, 13 Mar 2015 19:34:04 +0100 Subject: Solutions w6 --- Week6/nbproject/project.properties | 8 +- Week6/src/LICENSE | 21 ++++++ Week6/src/Main.java | 35 +++++++-- Week6/src/Node.java | 46 ++++++++++-- Week6/src/SlidingGame.java | 147 ++++++++++++++++++++++++++++++++----- Week6/src/Solver.java | 44 +++++++---- Week6/src/week6/Week6.java | 21 ------ 7 files changed, 253 insertions(+), 69 deletions(-) create mode 100644 Week6/src/LICENSE delete mode 100644 Week6/src/week6/Week6.java (limited to 'Week6') diff --git a/Week6/nbproject/project.properties b/Week6/nbproject/project.properties index e21778e..f4df81f 100644 --- a/Week6/nbproject/project.properties +++ b/Week6/nbproject/project.properties @@ -1,9 +1,10 @@ annotation.processing.enabled=true annotation.processing.enabled.in.editor=false -annotation.processing.processor.options= annotation.processing.processors.list= annotation.processing.run.all.processors=true annotation.processing.source.output=${build.generated.sources.dir}/ap-source-output +application.title=Week6 +application.vendor=camilstaps build.classes.dir=${build.dir}/classes build.classes.excludes=**/*.java,**/*.form # This directory is removed when the project is cleaned: @@ -26,6 +27,7 @@ dist.archive.excludes= dist.dir=dist dist.jar=${dist.dir}/Week6.jar dist.javadoc.dir=${dist.dir}/javadoc +endorsed.classpath= excludes= includes=** jar.compress=false @@ -53,7 +55,7 @@ javadoc.splitindex=true javadoc.use=true javadoc.version=false javadoc.windowtitle= -main.class=week6.Week6 +main.class=Main manifest.file=manifest.mf meta.inf.dir=${src.dir}/META-INF mkdist.disabled=false @@ -64,7 +66,7 @@ run.classpath=\ # Space-separated list of JVM arguments used when running the project. # You may also define separate properties like run-sys-prop.name=value instead of -Dname=value. # To set system properties for unit tests define test-sys-prop.name=value: -run.jvmargs= +run.jvmargs=-ea run.test.classpath=\ ${javac.test.classpath}:\ ${build.test.classes.dir} 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 + +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 The element this node is based on */ -public class Node +@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility. +public class Node implements Comparable> { // the data field - private T item; + private final T item; // a reference to the predecessor - private Node previous; + private final Node previous; /* A constructor that initializes each node * with the specified values @@ -53,6 +58,35 @@ public class Node @Override public String toString() { - throw new UnsupportedOperationException("toString : not supported yet."); + 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 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 successors () { - throw new UnsupportedOperationException("successors : not supported yet."); + 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 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 toExamine; + private final Queue> toExamine = new PriorityQueue>(); + private final HashSet examined = new HashSet(); + + 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 - } - -} -- cgit v1.2.3