From d0972c57cc23d7a6c913594e8166770fc1b28ff6 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Wed, 11 Mar 2015 10:50:52 +0100 Subject: Added framework --- Week6/src/Configuration.java | 21 ++++++++++ Week6/src/Direction.java | 26 ++++++++++++ Week6/src/Main.java | 16 ++++++++ Week6/src/Node.java | 58 +++++++++++++++++++++++++++ Week6/src/SlidingGame.java | 94 ++++++++++++++++++++++++++++++++++++++++++++ Week6/src/Solver.java | 37 +++++++++++++++++ 6 files changed, 252 insertions(+) create mode 100644 Week6/src/Configuration.java create mode 100644 Week6/src/Direction.java create mode 100644 Week6/src/Main.java create mode 100644 Week6/src/Node.java create mode 100644 Week6/src/SlidingGame.java create mode 100644 Week6/src/Solver.java (limited to 'Week6/src') diff --git a/Week6/src/Configuration.java b/Week6/src/Configuration.java new file mode 100644 index 0000000..7264c5f --- /dev/null +++ b/Week6/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/src/Direction.java b/Week6/src/Direction.java new file mode 100644 index 0000000..d4837b9 --- /dev/null +++ b/Week6/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/src/Main.java b/Week6/src/Main.java new file mode 100644 index 0000000..9122749 --- /dev/null +++ b/Week6/src/Main.java @@ -0,0 +1,16 @@ +/** + * + * @author Pieter Koopman, Sjaak Smetsers + */ +public class Main +{ + + 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()); + } +} diff --git a/Week6/src/Node.java b/Week6/src/Node.java new file mode 100644 index 0000000..2a33cc4 --- /dev/null +++ b/Week6/src/Node.java @@ -0,0 +1,58 @@ +/** + * 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 + */ +public class Node +{ + // the data field + private T item; + // a reference to the predecessor + private 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() { + throw new UnsupportedOperationException("toString : not supported yet."); + } +} diff --git a/Week6/src/SlidingGame.java b/Week6/src/SlidingGame.java new file mode 100644 index 0000000..29e76fc --- /dev/null +++ b/Week6/src/SlidingGame.java @@ -0,0 +1,94 @@ +import java.util.Collection; + +/** + * @author Pieter Koopman, Sjaak Smetsers + * @version 1.2 + * @date 28-02-2015 + * A template implementation of a sliding game also + * implementing the Graph interface + */ +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 + */ + private int [][] board; + private int holeX, holeY; + + /* + * 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 == N*N: "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; + } + } + } + + /* + * 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]; + buf.append(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 a boolean indicating equality + */ + @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 () { + throw new UnsupportedOperationException("isGoal : not supported yet."); + } + + @Override + public Collection successors () { + throw new UnsupportedOperationException("successors : not supported yet."); + } + + @Override + public int compareTo(Configuration g) { + throw new UnsupportedOperationException("compareTo : not supported yet."); + } + +} diff --git a/Week6/src/Solver.java b/Week6/src/Solver.java new file mode 100644 index 0000000..137646c --- /dev/null +++ b/Week6/src/Solver.java @@ -0,0 +1,37 @@ +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 + */ +public class Solver +{ + // A queue for maintaining graphs that are not visited yet. + Queue toExamine; + + public Solver(Configuration g) { + throw new UnsupportedOperationException("Solver: not supported yet."); + } + + /* 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!"; + } else { + for ( Configuration succ: next.successors() ) { + toExamine.add (succ); + } + } + } + return "Failure!"; + } + +} -- cgit v1.2.3