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/Assignment (in Dutch).pdf | Bin 223530 -> 0 bytes Week6/build.xml | 73 -- Week6/manifest.mf | 3 - Week6/nbproject/build-impl.xml | 1413 ----------------------------------- Week6/nbproject/genfiles.properties | 8 - Week6/nbproject/project.properties | 75 -- Week6/nbproject/project.xml | 15 - 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 -- Week6/week6.tar.gz | Bin 5434 -> 0 bytes 14 files changed, 2021 deletions(-) delete mode 100644 Week6/Assignment (in Dutch).pdf delete mode 100644 Week6/build.xml delete mode 100644 Week6/manifest.mf delete mode 100644 Week6/nbproject/build-impl.xml delete mode 100644 Week6/nbproject/genfiles.properties delete mode 100644 Week6/nbproject/project.properties delete mode 100644 Week6/nbproject/project.xml 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 delete mode 100644 Week6/week6.tar.gz (limited to 'Week6') diff --git a/Week6/Assignment (in Dutch).pdf b/Week6/Assignment (in Dutch).pdf deleted file mode 100644 index dbf029b..0000000 Binary files a/Week6/Assignment (in Dutch).pdf and /dev/null differ diff --git a/Week6/build.xml b/Week6/build.xml deleted file mode 100644 index 2b74971..0000000 --- a/Week6/build.xml +++ /dev/null @@ -1,73 +0,0 @@ - - - - - - - - - - - Builds, tests, and runs the project Week6. - - - diff --git a/Week6/manifest.mf b/Week6/manifest.mf deleted file mode 100644 index 328e8e5..0000000 --- a/Week6/manifest.mf +++ /dev/null @@ -1,3 +0,0 @@ -Manifest-Version: 1.0 -X-COMMENT: Main-Class will be added automatically by build - diff --git a/Week6/nbproject/build-impl.xml b/Week6/nbproject/build-impl.xml deleted file mode 100644 index ba6b406..0000000 --- a/Week6/nbproject/build-impl.xml +++ /dev/null @@ -1,1413 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must set src.dir - Must set test.src.dir - Must set build.dir - Must set dist.dir - Must set build.classes.dir - Must set dist.javadoc.dir - Must set build.test.classes.dir - Must set build.test.results.dir - Must set build.classes.excludes - Must set dist.jar - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must set javac.includes - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - No tests executed. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must set JVM to use for profiling in profiler.info.jvm - Must set profiler agent JVM arguments in profiler.info.jvmargs.agent - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must select some files in the IDE or set javac.includes - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - To run this application from the command line without Ant, try: - - java -jar "${dist.jar.resolved}" - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must select one file in the IDE or set run.class - - - - Must select one file in the IDE or set run.class - - - - - - - - - - - - - - - - - - - - - - - Must select one file in the IDE or set debug.class - - - - - Must select one file in the IDE or set debug.class - - - - - Must set fix.includes - - - - - - - - - - This target only works when run from inside the NetBeans IDE. - - - - - - - - - Must select one file in the IDE or set profile.class - This target only works when run from inside the NetBeans IDE. - - - - - - - - - This target only works when run from inside the NetBeans IDE. - - - - - - - - - - - - - This target only works when run from inside the NetBeans IDE. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must select one file in the IDE or set run.class - - - - - - Must select some files in the IDE or set test.includes - - - - - Must select one file in the IDE or set run.class - - - - - Must select one file in the IDE or set applet.url - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Must select some files in the IDE or set javac.includes - - - - - - - - - - - - - - - - - - - - Some tests failed; see details above. - - - - - - - - - Must select some files in the IDE or set test.includes - - - - Some tests failed; see details above. - - - - Must select some files in the IDE or set test.class - Must select some method in the IDE or set test.method - - - - Some tests failed; see details above. - - - - - Must select one file in the IDE or set test.class - - - - Must select one file in the IDE or set test.class - Must select some method in the IDE or set test.method - - - - - - - - - - - - - - Must select one file in the IDE or set applet.url - - - - - - - - - Must select one file in the IDE or set applet.url - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff --git a/Week6/nbproject/genfiles.properties b/Week6/nbproject/genfiles.properties deleted file mode 100644 index 92d1292..0000000 --- a/Week6/nbproject/genfiles.properties +++ /dev/null @@ -1,8 +0,0 @@ -build.xml.data.CRC32=bcd01398 -build.xml.script.CRC32=6a261b85 -build.xml.stylesheet.CRC32=8064a381@1.75.2.48 -# This file is used by a NetBeans-based IDE to track changes in generated files such as build-impl.xml. -# Do not edit this file. You may delete it but then the IDE will never regenerate such files for you. -nbproject/build-impl.xml.data.CRC32=bcd01398 -nbproject/build-impl.xml.script.CRC32=e0655e71 -nbproject/build-impl.xml.stylesheet.CRC32=876e7a8f@1.75.2.48 diff --git a/Week6/nbproject/project.properties b/Week6/nbproject/project.properties deleted file mode 100644 index f4df81f..0000000 --- a/Week6/nbproject/project.properties +++ /dev/null @@ -1,75 +0,0 @@ -annotation.processing.enabled=true -annotation.processing.enabled.in.editor=false -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: -build.dir=build -build.generated.dir=${build.dir}/generated -build.generated.sources.dir=${build.dir}/generated-sources -# Only compile against the classpath explicitly listed here: -build.sysclasspath=ignore -build.test.classes.dir=${build.dir}/test/classes -build.test.results.dir=${build.dir}/test/results -# Uncomment to specify the preferred debugger connection transport: -#debug.transport=dt_socket -debug.classpath=\ - ${run.classpath} -debug.test.classpath=\ - ${run.test.classpath} -# Files in build.classes.dir which should be excluded from distribution jar -dist.archive.excludes= -# This directory is removed when the project is cleaned: -dist.dir=dist -dist.jar=${dist.dir}/Week6.jar -dist.javadoc.dir=${dist.dir}/javadoc -endorsed.classpath= -excludes= -includes=** -jar.compress=false -javac.classpath= -# Space-separated list of extra javac options -javac.compilerargs= -javac.deprecation=false -javac.processorpath=\ - ${javac.classpath} -javac.source=1.7 -javac.target=1.7 -javac.test.classpath=\ - ${javac.classpath}:\ - ${build.classes.dir} -javac.test.processorpath=\ - ${javac.test.classpath} -javadoc.additionalparam= -javadoc.author=false -javadoc.encoding=${source.encoding} -javadoc.noindex=false -javadoc.nonavbar=false -javadoc.notree=false -javadoc.private=false -javadoc.splitindex=true -javadoc.use=true -javadoc.version=false -javadoc.windowtitle= -main.class=Main -manifest.file=manifest.mf -meta.inf.dir=${src.dir}/META-INF -mkdist.disabled=false -platform.active=default_platform -run.classpath=\ - ${javac.classpath}:\ - ${build.classes.dir} -# 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=-ea -run.test.classpath=\ - ${javac.test.classpath}:\ - ${build.test.classes.dir} -source.encoding=UTF-8 -src.dir=src -test.src.dir=test diff --git a/Week6/nbproject/project.xml b/Week6/nbproject/project.xml deleted file mode 100644 index 1042c24..0000000 --- a/Week6/nbproject/project.xml +++ /dev/null @@ -1,15 +0,0 @@ - - - org.netbeans.modules.java.j2seproject - - - Week6 - - - - - - - - - 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; - } - -} diff --git a/Week6/week6.tar.gz b/Week6/week6.tar.gz deleted file mode 100644 index b5bca35..0000000 Binary files a/Week6/week6.tar.gz and /dev/null differ -- cgit v1.2.3