A star (A*) Graph traversal to find lowest cost

AstarGraph.scala

//CodinGame - Bender
object Solution extends App {
  val n = readInt
  val exterior = -1 -> new Room(-1, 0, -1, -1)
  val roomsRead = for {
    i <- (0 until n).toList
    Array(id, value, next1, next2) = readLine split " "
  } yield id.toInt -> Room(id.toInt, value.toInt, if (next1 == "E") -1 else next1.toInt, if (next2 == "E") -1 else next2.toInt)

  val rooms = (exterior :: roomsRead).toMap

  val graph = new Graph {
    type Node = Room
    def validMoves(r: Room) =
      if (r.id == -1) Nil
      else List(Move(r, rooms(r.next1), "LEFT", -r.value),
        Move(r, rooms(r.next2), "RIGHT", -r.value))
  }
  val from = rooms(0)
  val to = rooms(-1)
  val cost = graph.shortestPath(from, to).get.cost.toInt
  println(-cost)

}

case class Room(id: Int, value: Int, next1: Int, next2: Int)

trait Graph {
  import scala.annotation.tailrec

  type Node

  case class Move(from: Node, to: Node, name: String, cost: Double = 1)

  case class Path(moves: List[Move] = Nil) {
    lazy val cost = moves.map(_.cost).sum

    lazy val end = moves.head.to

    def append(m: Move) = Path(m :: moves)
  }

  def shortestPath(from: Node, to: Node): Option[Path] = {
    val pathsToIt = pathImpl(validMoves(from).map(m => Path(List(m))), Nil)
    pathsToIt.filter(_.end == to) match {
      case Nil => None
      case l   => Some(l.minBy(_.cost))
    }
  }

  def validMoves(from: Node): List[Move]

  implicit class PathOps(paths: List[Path]) {
    def minCost(target: Node): Double = {
      val costsToTarget = for {
        p <- paths
        if p.end == target
      } yield p.cost
      (Double.MaxValue :: costsToTarget).min
    }
  }

  @tailrec
  private def pathImpl(
    toExplore: List[Path],
    explored: List[Path]): List[Path] = toExplore match {
    case Nil => explored
    case nextPath :: tail =>
      val nextNode = nextPath.end
      val newPaths = for {
        m <- validMoves(nextNode)
        newPath = nextPath.append(m)
        previousCost = explored.minCost(m.to)
        if newPath.cost < previousCost
      } yield newPath
      pathImpl(tail ::: newPaths, nextPath :: explored)
  }
}

case class SimpleNode(x: Int, y: Int) {
  override def toString = s"($x, $y)"
}

case class SimpleGraph(impediments: List[SimpleNode], maxX: Int = 15, maxY: Int = 8, minX: Int = 0, minY: Int = 0) extends Graph {
  type Node = SimpleNode

  def validMoves(n: SimpleNode): List[Move] = for {
    (dx, dy, name) <- List((0, 1, "DOWN"), (-1, 0, "LEFT"), (1, 0, "RIGHT"), (0, -1, "UP"))
    x = n.x + dx
    y = n.y + dy
    if (x >= minX && y >= minY && x <= maxX && y <= maxY)
    if (!impediments.contains(SimpleNode(x, y)))
  } yield Move(n, SimpleNode(x, y), name)
}

object GraphDemo extends App {
  val graph = SimpleGraph(Nil)
  val from = SimpleNode(0, 0)
  val to = SimpleNode(4, 6)
  val moves = graph.shortestPath(from, to).get.moves
  moves.reverse.map(_.name).foreach(println)
}