Scala : add streams assignment

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)
+    }
+  }
+}