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