diff options
4 files changed, 56 insertions, 14 deletions
diff --git a/Scala/streams/src/main/scala/streams/GameDef.scala b/Scala/streams/src/main/scala/streams/GameDef.scala index 22a679e..d04079d 100644 --- a/Scala/streams/src/main/scala/streams/GameDef.scala +++ b/Scala/streams/src/main/scala/streams/GameDef.scala @@ -84,7 +84,7 @@ trait GameDef { * This function returns the block at the start position of * the game. */ - def startBlock: Block = ??? + def startBlock: Block = Block(startPos, startPos) /** * A block is represented by the position of the two cubes that @@ -134,23 +134,24 @@ trait GameDef { * Returns the list of blocks that can be obtained by moving * the current block, together with the corresponding move. */ - def neighbors: List[(Block, Move)] = ??? + def neighbors: List[(Block, Move)] = List((left, Left), (right, Right), (up, Up), (down, Down)) /** * Returns the list of positions reachable from the current block * which are inside the terrain. */ - def legalNeighbors: List[(Block, Move)] = ??? + def legalNeighbors: List[(Block, Move)] = neighbors filter { x => x._1.isLegal } + // { case (block, _) => block.isLegal } /** * Returns `true` if the block is standing. */ - def isStanding: Boolean = ??? + def isStanding: Boolean = b1 == b2 /** * Returns `true` if the block is entirely inside the terrain. */ - def isLegal: Boolean = ??? + def isLegal: Boolean = terrain(b1) && terrain(b2) } } diff --git a/Scala/streams/src/main/scala/streams/Solver.scala b/Scala/streams/src/main/scala/streams/Solver.scala index d6aa237..8350b50 100644 --- a/Scala/streams/src/main/scala/streams/Solver.scala +++ b/Scala/streams/src/main/scala/streams/Solver.scala @@ -10,7 +10,8 @@ trait Solver extends GameDef { /** * Returns `true` if the block `b` is at the final position */ - def done(b: Block): Boolean = ??? + def done(b: Block): Boolean = b == Block(goal, goal) + // b.b1 == goal && b.b2 == goal /** * This function takes two arguments: the current block `b` and @@ -28,7 +29,8 @@ trait Solver extends GameDef { * 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])] = ??? + def neighborsWithHistory(b: Block, history: List[Move]): Stream[(Block, List[Move])] = + (b.legalNeighbors map { case (b, m) => (b, m :: history) }).toStream /** * This function returns the list of neighbors without the block @@ -36,7 +38,8 @@ trait Solver extends GameDef { * make sure that we don't explore circular paths. */ def newNeighborsOnly(neighbors: Stream[(Block, List[Move])], - explored: Set[Block]): Stream[(Block, List[Move])] = ??? + explored: Set[Block]): Stream[(Block, List[Move])] = + neighbors.filter { case (block, _) => !explored.contains(block) } /** * The function `from` returns the stream of all possible paths @@ -62,18 +65,24 @@ trait Solver extends GameDef { * construct the correctly sorted stream. */ def from(initial: Stream[(Block, List[Move])], - explored: Set[Block]): Stream[(Block, List[Move])] = ??? + explored: Set[Block]): Stream[(Block, List[Move])] = initial match { + case (block,moves) #:: xs => { + val blocks = newNeighborsOnly(neighborsWithHistory(block, moves), explored) + (block, moves) #:: from(xs ++ blocks, explored + block) + } + case _ => Stream.empty + } /** * The stream of all paths that begin at the starting block. */ - lazy val pathsFromStart: Stream[(Block, List[Move])] = ??? + lazy val pathsFromStart: Stream[(Block, List[Move])] = from(Stream((startBlock, Nil)), Set.empty) /** * 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])] = ??? + lazy val pathsToGoal: Stream[(Block, List[Move])] = pathsFromStart filter { b => done(b._1) } /** * The (or one of the) shortest sequence(s) of moves to reach the @@ -83,5 +92,8 @@ trait Solver extends GameDef { * the first move that the player should perform from the starting * position. */ - lazy val solution: List[Move] = ??? + lazy val solution: List[Move] = pathsToGoal match { + case (block, moves) #:: _ => moves.reverse + case _ => Nil + } } diff --git a/Scala/streams/src/main/scala/streams/StringParserTerrain.scala b/Scala/streams/src/main/scala/streams/StringParserTerrain.scala index 12e9a8b..e2c83d2 100644 --- a/Scala/streams/src/main/scala/streams/StringParserTerrain.scala +++ b/Scala/streams/src/main/scala/streams/StringParserTerrain.scala @@ -52,7 +52,10 @@ trait StringParserTerrain extends GameDef { * a valid position (not a '-' character) inside the terrain described * by `levelVector`. */ - def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = ??? + def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = + p => p.x >= 0 && p.y >= 0 && + p.x < levelVector.length && p.y < levelVector(p.x).size && + levelVector(p.x)(p.y) != '-' /** * This function should return the position of character `c` in the @@ -62,7 +65,10 @@ trait StringParserTerrain extends GameDef { * Hint: you can use the functions `indexWhere` and / or `indexOf` of the * `Vector` class */ - def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = ??? + def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = { + val x = levelVector.indexWhere(_.contains(c)) + Pos(x, levelVector(x).indexOf(c)) + } private lazy val vector: Vector[Vector[Char]] = Vector(level.split("\n").map(str => Vector(str: _*)): _*) diff --git a/Scala/streams/src/test/scala/streams/BloxorzSuite.scala b/Scala/streams/src/test/scala/streams/BloxorzSuite.scala index 3f9329b..72ef1a4 100644 --- a/Scala/streams/src/test/scala/streams/BloxorzSuite.scala +++ b/Scala/streams/src/test/scala/streams/BloxorzSuite.scala @@ -53,6 +53,29 @@ class BloxorzSuite extends FunSuite { } } + test("neighborsWithHistory") { + new Level1 { + assert(neighborsWithHistory(Block(Pos(1,1),Pos(1,1)), List(Left,Up)) === + Stream( + (Block(Pos(1,2),Pos(1,3)), List(Right,Left,Up)), + (Block(Pos(2,1),Pos(3,1)), List(Down,Left,Up)) + )) + } + } + + test("newNeighborsOnly") { + new Level1 { + assert(newNeighborsOnly( + Set( + (Block(Pos(1,2),Pos(1,3)), List(Right,Left,Up)), + (Block(Pos(2,1),Pos(3,1)), List(Down,Left,Up))).toStream, + Set(Block(Pos(1,2),Pos(1,3)), Block(Pos(1,1),Pos(1,1))) + ) == + Set((Block(Pos(2,1),Pos(3,1)), List(Down,Left,Up))).toStream + ) + } + } + test("optimal solution for level 1") { new Level1 { assert(solve(solution) == Block(goal, goal)) |