diff options
Diffstat (limited to 'Scala/streams/src')
7 files changed, 488 insertions, 0 deletions
diff --git a/Scala/streams/src/main/scala/common/package.scala b/Scala/streams/src/main/scala/common/package.scala new file mode 100644 index 0000000..f1c74c3 --- /dev/null +++ b/Scala/streams/src/main/scala/common/package.scala @@ -0,0 +1,40 @@ +import java.io.File + +package object common { + + /** An alias for the `Nothing` type. + * Denotes that the type should be filled in. + */ + type ??? = Nothing + + /** An alias for the `Any` type. + * Denotes that the type should be filled in. + */ + type *** = Any + + + /** + * Get a child of a file. For example, + * + * subFile(homeDir, "b", "c") + * + * corresponds to ~/b/c + */ + def subFile(file: File, children: String*) = { + children.foldLeft(file)((file, child) => new File(file, child)) + } + + /** + * Get a resource from the `src/main/resources` directory. Eclipse does not copy + * resources to the output directory, then the class loader cannot find them. + */ + def resourceAsStreamFromSrc(resourcePath: List[String]): Option[java.io.InputStream] = { + val classesDir = new File(getClass.getResource(".").toURI) + val projectDir = classesDir.getParentFile.getParentFile.getParentFile.getParentFile + val resourceFile = subFile(projectDir, ("src" :: "main" :: "resources" :: resourcePath): _*) + if (resourceFile.exists) + Some(new java.io.FileInputStream(resourceFile)) + else + None + } +} diff --git a/Scala/streams/src/main/scala/streams/Bloxorz.scala b/Scala/streams/src/main/scala/streams/Bloxorz.scala new file mode 100644 index 0000000..b0eaf6f --- /dev/null +++ b/Scala/streams/src/main/scala/streams/Bloxorz.scala @@ -0,0 +1,49 @@ +package streams + +/** + * A main object that can be used to execute the Bloxorz solver + */ +object Bloxorz extends App { + + /** + * A level constructed using the `InfiniteTerrain` trait which defines + * the terrain to be valid at every position. + */ + object InfiniteLevel extends Solver with InfiniteTerrain { + val startPos = Pos(1,3) + val goal = Pos(5,8) + } + + println(InfiniteLevel.solution) + + /** + * A simple level constructed using the StringParserTerrain + */ + abstract class Level extends Solver with StringParserTerrain + + object Level0 extends Level { + val level = + """------ + |--ST-- + |--oo-- + |--oo-- + |------""".stripMargin + } + + println(Level0.solution) + + /** + * Level 1 of the official Bloxorz game + */ + object Level1 extends Level { + val level = + """ooo------- + |oSoooo---- + |ooooooooo- + |-ooooooooo + |-----ooToo + |------ooo-""".stripMargin + } + + println(Level1.solution) +} diff --git a/Scala/streams/src/main/scala/streams/GameDef.scala b/Scala/streams/src/main/scala/streams/GameDef.scala new file mode 100644 index 0000000..22a679e --- /dev/null +++ b/Scala/streams/src/main/scala/streams/GameDef.scala @@ -0,0 +1,156 @@ +package streams + +import common._ + +/** + * This trait represents the layout and building blocks of the game + * + * @TODO: SHOULD RENAME `x` and `y` in class Pos to `row` and `col`. It's + * confusing to have `x` being the vertical axis. + */ +trait GameDef { + + /** + * The case class `Pos` encodes positions in the terrain. + * + * IMPORTANT NOTE + * - The `x` coordinate denotes the position on the vertical axis + * - The `y` coordinate is used for the horizontal axis + * - The coordinates increase when moving down and right + * + * Illustration: + * + * 0 1 2 3 <- y axis + * 0 o o o o + * 1 o o o o + * 2 o # o o # is at position Pos(2, 1) + * 3 o o o o + * + * ^ + * | + * + * x axis + */ + case class Pos(x: Int, y: Int) { + /** The position obtained by changing the `x` coordinate by `d` */ + def dx(d: Int) = copy(x = x + d) + + /** The position obtained by changing the `y` coordinate by `d` */ + def dy(d: Int) = copy(y = y + d) + } + + /** + * The position where the block is located initially. + * + * This value is left abstract, it will be defined in concrete + * instances of the game. + */ + val startPos: Pos + + /** + * The target position where the block has to go. + * This value is left abstract. + */ + val goal: Pos + + /** + * The terrain is represented as a function from positions to + * booleans. The function returns `true` for every position that + * is inside the terrain. + * + * As explained in the documentation of class `Pos`, the `x` axis + * is the vertical one and increases from top to bottom. + */ + type Terrain = Pos => Boolean + + + /** + * The terrain of this game. This value is left abstract. + */ + val terrain: Terrain + + + /** + * In Bloxorz, we can move left, right, Up or down. + * These moves are encoded as case objects. + */ + sealed abstract class Move + case object Left extends Move + case object Right extends Move + case object Up extends Move + case object Down extends Move + + /** + * This function returns the block at the start position of + * the game. + */ + def startBlock: Block = ??? + + /** + * A block is represented by the position of the two cubes that + * it consists of. We make sure that `b1` is lexicographically + * smaller than `b2`. + */ + case class Block(b1: Pos, b2: Pos) { + + // checks the requirement mentioned above + require(b1.x <= b2.x && b1.y <= b2.y, "Invalid block position: b1=" + b1 + ", b2=" + b2) + + /** + * Returns a block where the `x` coordinates of `b1` and `b2` are + * changed by `d1` and `d2`, respectively. + */ + def dx(d1: Int, d2: Int) = Block(b1.dx(d1), b2.dx(d2)) + + /** + * Returns a block where the `y` coordinates of `b1` and `b2` are + * changed by `d1` and `d2`, respectively. + */ + def dy(d1: Int, d2: Int) = Block(b1.dy(d1), b2.dy(d2)) + + + /** The block obtained by moving left */ + def left = if (isStanding) dy(-2, -1) + else if (b1.x == b2.x) dy(-1, -2) + else dy(-1, -1) + + /** The block obtained by moving right */ + def right = if (isStanding) dy(1, 2) + else if (b1.x == b2.x) dy(2, 1) + else dy(1, 1) + + /** The block obtained by moving up */ + def up = if (isStanding) dx(-2, -1) + else if (b1.x == b2.x) dx(-1, -1) + else dx(-1, -2) + + /** The block obtained by moving down */ + def down = if (isStanding) dx(1, 2) + else if (b1.x == b2.x) dx(1, 1) + else dx(2, 1) + + + /** + * Returns the list of blocks that can be obtained by moving + * the current block, together with the corresponding move. + */ + def neighbors: List[(Block, Move)] = ??? + + /** + * Returns the list of positions reachable from the current block + * which are inside the terrain. + */ + def legalNeighbors: List[(Block, Move)] = ??? + + /** + * Returns `true` if the block is standing. + */ + def isStanding: Boolean = ??? + + /** + * Returns `true` if the block is entirely inside the terrain. + */ + def isLegal: Boolean = ??? + + } +} diff --git a/Scala/streams/src/main/scala/streams/InfiniteTerrain.scala b/Scala/streams/src/main/scala/streams/InfiniteTerrain.scala new file mode 100644 index 0000000..61d2e99 --- /dev/null +++ b/Scala/streams/src/main/scala/streams/InfiniteTerrain.scala @@ -0,0 +1,15 @@ +package streams + +/** + * This trait defines an infinite terrain, where the block can + * go on any position. + * + * It keeps the `startPos` and the `goal` positions abstract. + * + * Using this trait is useful for testing. It can be used to find + * the shortest path between two positions without terrain + * restrictions. + */ +trait InfiniteTerrain extends GameDef { + val terrain: Terrain = (pos: Pos) => true +} diff --git a/Scala/streams/src/main/scala/streams/Solver.scala b/Scala/streams/src/main/scala/streams/Solver.scala new file mode 100644 index 0000000..d6aa237 --- /dev/null +++ b/Scala/streams/src/main/scala/streams/Solver.scala @@ -0,0 +1,87 @@ +package streams + +import common._ + +/** + * This component implements the solver for the Bloxorz game + */ +trait Solver extends GameDef { + + /** + * Returns `true` if the block `b` is at the final position + */ + def done(b: Block): Boolean = ??? + + /** + * This function takes two arguments: the current block `b` and + * a list of moves `history` that was required to reach the + * position of `b`. + * + * The `head` element of the `history` list is the latest move + * that was executed, i.e. the last move that was performed for + * the block to end up at position `b`. + * + * The function returns a stream of pairs: the first element of + * the each pair is a neighboring block, and the second element + * is the augmented history of moves required to reach this block. + * + * It should only return valid neighbors, i.e. block positions + * that are inside the terrain. + */ + def neighborsWithHistory(b: Block, history: List[Move]): Stream[(Block, List[Move])] = ??? + + /** + * This function returns the list of neighbors without the block + * positions that have already been explored. We will use it to + * make sure that we don't explore circular paths. + */ + def newNeighborsOnly(neighbors: Stream[(Block, List[Move])], + explored: Set[Block]): Stream[(Block, List[Move])] = ??? + + /** + * The function `from` returns the stream of all possible paths + * that can be followed, starting at the `head` of the `initial` + * stream. + * + * The blocks in the stream `initial` are sorted by ascending path + * length: the block positions with the shortest paths (length of + * move list) are at the head of the stream. + * + * The parameter `explored` is a set of block positions that have + * been visited before, on the path to any of the blocks in the + * stream `initial`. When search reaches a block that has already + * been explored before, that position should not be included a + * second time to avoid cycles. + * + * The resulting stream should be sorted by ascending path length, + * i.e. the block positions that can be reached with the fewest + * amount of moves should appear first in the stream. + * + * Note: the solution should not look at or compare the lengths + * of different paths - the implementation should naturally + * construct the correctly sorted stream. + */ + def from(initial: Stream[(Block, List[Move])], + explored: Set[Block]): Stream[(Block, List[Move])] = ??? + + /** + * The stream of all paths that begin at the starting block. + */ + lazy val pathsFromStart: Stream[(Block, List[Move])] = ??? + + /** + * Returns a stream of all possible pairs of the goal block along + * with the history how it was reached. + */ + lazy val pathsToGoal: Stream[(Block, List[Move])] = ??? + + /** + * The (or one of the) shortest sequence(s) of moves to reach the + * goal. If the goal cannot be reached, the empty list is returned. + * + * Note: the `head` element of the returned list should represent + * the first move that the player should perform from the starting + * position. + */ + lazy val solution: List[Move] = ??? +} diff --git a/Scala/streams/src/main/scala/streams/StringParserTerrain.scala b/Scala/streams/src/main/scala/streams/StringParserTerrain.scala new file mode 100644 index 0000000..12e9a8b --- /dev/null +++ b/Scala/streams/src/main/scala/streams/StringParserTerrain.scala @@ -0,0 +1,74 @@ +package streams + +import common._ + +/** + * This component implements a parser to define terrains from a + * graphical ASCII representation. + * + * When mixing in that component, a level can be defined by + * defining the field `level` in the following form: + * + * val level = + * """------ + * |--ST-- + * |--oo-- + * |--oo-- + * |------""".stripMargin + * + * - The `-` character denotes parts which are outside the terrain + * - `o` denotes fields which are part of the terrain + * - `S` denotes the start position of the block (which is also considered + inside the terrain) + * - `T` denotes the final position of the block (which is also considered + inside the terrain) + * + * In this example, the first and last lines could be omitted, and + * also the columns that consist of `-` characters only. + */ +trait StringParserTerrain extends GameDef { + + /** + * A ASCII representation of the terrain. This field should remain + * abstract here. + */ + val level: String + + /** + * This method returns terrain function that represents the terrain + * in `levelVector`. The vector contains parsed version of the `level` + * string. For example, the following level + * + * val level = + * """ST + * |oo + * |oo""".stripMargin + * + * is represented as + * + * Vector(Vector('S', 'T'), Vector('o', 'o'), Vector('o', 'o')) + * + * The resulting function should return `true` if the position `pos` is + * a valid position (not a '-' character) inside the terrain described + * by `levelVector`. + */ + def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = ??? + + /** + * This function should return the position of character `c` in the + * terrain described by `levelVector`. You can assume that the `c` + * appears exactly once in the terrain. + * + * Hint: you can use the functions `indexWhere` and / or `indexOf` of the + * `Vector` class + */ + def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = ??? + + private lazy val vector: Vector[Vector[Char]] = + Vector(level.split("\n").map(str => Vector(str: _*)): _*) + + lazy val terrain: Terrain = terrainFunction(vector) + lazy val startPos: Pos = findChar('S', vector) + lazy val goal: Pos = findChar('T', vector) + +} diff --git a/Scala/streams/src/test/scala/streams/BloxorzSuite.scala b/Scala/streams/src/test/scala/streams/BloxorzSuite.scala new file mode 100644 index 0000000..3f9329b --- /dev/null +++ b/Scala/streams/src/test/scala/streams/BloxorzSuite.scala @@ -0,0 +1,67 @@ +package streams + +import org.scalatest.FunSuite + +import org.junit.runner.RunWith +import org.scalatest.junit.JUnitRunner + +import Bloxorz._ + +@RunWith(classOf[JUnitRunner]) +class BloxorzSuite extends FunSuite { + + trait SolutionChecker extends GameDef with Solver with StringParserTerrain { + /** + * This method applies a list of moves `ls` to the block at position + * `startPos`. This can be used to verify if a certain list of moves + * is a valid solution, i.e. leads to the goal. + */ + def solve(ls: List[Move]): Block = + ls.foldLeft(startBlock) { case (block, move) => move match { + case Left => block.left + case Right => block.right + case Up => block.up + case Down => block.down + } + } + } + + trait Level1 extends SolutionChecker { + /* terrain for level 1*/ + + val level = + """ooo------- + |oSoooo---- + |ooooooooo- + |-ooooooooo + |-----ooToo + |------ooo-""".stripMargin + + val optsolution = List(Right, Right, Down, Right, Right, Right, Down) + } + + test("terrain function level 1") { + new Level1 { + assert(terrain(Pos(0,0)), "0,0") + assert(!terrain(Pos(4,11)), "4,11") + } + } + + test("findChar level 1") { + new Level1 { + assert(startPos == Pos(1,1)) + } + } + + test("optimal solution for level 1") { + new Level1 { + assert(solve(solution) == Block(goal, goal)) + } + } + + test("optimal solution length for level 1") { + new Level1 { + assert(solution.length == optsolution.length) + } + } +} |