Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math._
- val exitfloor = 9
- val exitpos = 9
- val width = 19
- val nbfloors = 10
- val elevators = Map(0 -> List(3,9), 1 -> List(4,17), 2 -> List(3,9), 3 -> List(4,17), 4 -> List(3,9), 5 -> List(4,17), 6 -> List(3,9), 7 -> List(4,17), 8 -> List(9))
- def getDirection(from: Int, to: Int): String =
- if (from < to)
- "RIGHT"
- else
- "LEFT"
- def shortestRoute(fromFloor: Int, fromPos: Int, direction: String, ladders: Int): (Int, Map[Int, Int]) = {
- val floorElevators = elevators.getOrElse(fromFloor, Nil)
- def blockedExtra(toPos: Int) =
- if (direction == "RIGHT" && fromPos > toPos || direction == "LEFT" && fromPos < toPos)
- 3
- else
- 0
- if (fromFloor == exitfloor) {
- (abs(fromPos - exitpos) + blockedExtra(exitpos), Map.empty)
- }
- else if (floorElevators contains fromPos) {
- val next = shortestRoute(fromFloor + 1, fromPos, direction, ladders)
- (next._1 + 1, next._2 + (fromFloor -> fromPos))
- }
- else {
- val leftElevator = floorElevators.filter(fromPos >).lastOption
- val rightElevator = floorElevators.find(fromPos <)
- val leftmost = leftElevator.getOrElse(0)
- val rightmost = rightElevator.getOrElse(width - 1)
- val ladderPositions: Seq[Int] = leftmost to rightmost
- val elevatorPositions: Seq[Int] = leftElevator ++ rightElevator toSeq
- if (ladders == 0) {
- if (elevatorPositions.isEmpty)
- (nbfloors * width, Map.empty)
- else
- elevatorPositions.map(pos => {
- val next = shortestRoute(fromFloor + 1, pos, getDirection(fromPos, pos), 0)
- (blockedExtra(pos) + abs(pos - fromPos) + 1 + next._1, next._2 + (fromFloor -> pos))
- }).minBy(_._1)
- }
- else
- ladderPositions.map(pos => {
- val newLadderCount = if (elevatorPositions contains pos) ladders else ladders - 1
- val next = shortestRoute(fromFloor + 1, pos, getDirection(fromPos, pos), newLadderCount)
- (blockedExtra(pos) + abs(pos - fromPos) + 1 + next._1, next._2 + (fromFloor -> pos))
- }).minBy(_._1)
- }
- }
- val solution = Array(9, 4, 3, 4, 3, 4, 3, 4, 9)
- shortestRoute(0, 6, "RIGHT", 0)._2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement