gistfile1.scala

import java.io.FileInputStream

import scala.collection.mutable
import scala.io.Source

object RouteSolver {
  // First line is number of streets followed by line for each street then line with start/end then line with period in day of travel
  // I don't currently bother verifying valid input file, but this is added easily enough
  def solveFromCSVFile(filename: String) = {
    val numStreetsStr :: streetsAndGoal = Source.fromInputStream(new FileInputStream(filename))
        .getLines().toList
    val numStreets = numStreetsStr.trim.toInt

    val streetsStr = streetsAndGoal.take(numStreets)
    val streets = streetsStr.map(_.split(",")).map(strs => {
      (Intersection(strs(0).trim.charAt(0)), Intersection(strs(1).trim.charAt(0)), Street(strs(2).trim, strs.drop(3).map(_.trim.toInt)))
    })

    val goalStr = streetsAndGoal.drop(numStreets).head
    val (start, end) = (Intersection( goalStr.split(",")(0).trim.charAt(0)), Intersection(goalStr.split(",")(1).trim.charAt(0)))

    val travelPeriod = streetsAndGoal.drop(numStreets + 1).head.trim.toInt

    solveFromStreetList(streets, start, end, travelPeriod)
  }

  def solveFromStreetList(streetList: Seq[(Intersection, Intersection, Street)], start: Intersection, end: Intersection, travelPeriod: Int): Option[Solution] = {
    val bothDirs = streetList.flatMap{case (i1, i2, s) => Seq( (i1, i2, s), (i2, i1, s) )}
    val grouped = bothDirs.groupBy{case (i1, i2, s) => i1}.map({case (i, set) => (i, set.map(is => (is._2, is._3)).toSeq)})
    solve(grouped, start, end, travelPeriod)
  }

  def solve(intToStreets: Map[Intersection, Seq[(Intersection, Street)]], start: Intersection, end: Intersection, travelPeriod: Int): Option[Solution] = {
    val minNumTravelPeriods = intToStreets.values.minBy(_.length).length
    if (travelPeriod < 0 || travelPeriod > minNumTravelPeriods) {
      throw new IllegalArgumentException("Must provide a valid travel period")
    }

    // initial state
    val (visited, solutionsSoFar) = {
      (mutable.Set[Intersection](), mutable.Map(intToStreets.keys.map(i => i -> Solution(Int.MaxValue, Seq())).toSeq:_*))
    }

    // for use in frontier priority queue
    implicit val ord = new Ordering[Intersection] {
      override def compare(x: Intersection, y: Intersection): Int = {
        solutionsSoFar(y).curDist.compare(solutionsSoFar(x).curDist)
      }
    }
    val frontier = new mutable.PriorityQueue[Intersection]()
    frontier.enqueue(start)
    solutionsSoFar.put(start, Solution(0, Seq()))

    // explore the frontier until we no longer can or we reach the end point
    Stream.continually({
      frontier.dequeue() match {
        case next if next == end => Some( solutionsSoFar(next) )
        case next =>
          // visit next
          visited.add(next)

          // get new neighbors
          val newNeighbors = for {
            nextOptions <- intToStreets.get(next).toSeq
            (to, street) <- nextOptions if !visited.contains(to)
          } yield (to, street)

          // update distances
          newNeighbors.foreach{case (to, street) =>
            for {
              fromStatus <- solutionsSoFar.get(next)
              toStatus <- solutionsSoFar.get(to) if fromStatus.curDist + street.travelTimes(travelPeriod) < toStatus.curDist
            } solutionsSoFar.update(to, toStatus.copy(curDist = fromStatus.curDist + street.travelTimes(travelPeriod), route = fromStatus.route :+ street))
          }

          // add new neighbors to frontier
          frontier.enqueue(newNeighbors.map(_._1).toSeq:_*)
          None
      }
    }).find(_.nonEmpty || frontier.isEmpty).getOrElse(None)
  }
}

case class Solution(curDist: Int, route: Seq[Street])
case class Street(name: String, travelTimes: Seq[Int])
case class Intersection(name: Char)