camps.scala

object camps {
 
  import scala.collection.mutable.Queue
  import scala.math.Ordering.Implicits._ //do porównywania tupli, można też napisać własną funkcję
 
  //zakładam, że na początku mamy wybór do którego z pierwszych trzech kampów zawitać i że musimy trafić do ostatniego
 
  def getBestRoute( camps: List[Int]): Tuple2[Int, List[Int]] = {
    if(camps.length == 0) { //jak nie ma żadnych campingów
      (0, List())
    } else if(camps.length <= 3) { //jak można dopłynąć w jeden dzień
      (camps.last, List(camps.length - 1))
    } else {
      var bestRoutes: Queue[Tuple2[Int, List[Int]]] = Queue((camps(0), List(0)),
                                                            (camps(1), List(1)),
                                                            (camps(2), List(2)))
      var nextCamp = 3;
  
      while (nextCamp < camps.length) {
        //wybieramy z którego jest nam najtaniej dopłynąć do tego punktu
        var bestTuple = if(bestRoutes(0) < bestRoutes(1)) bestRoutes(0) else bestRoutes(1)
        bestTuple = if(bestTuple < bestRoutes(2)) bestTuple else bestRoutes(2)
      
        var newTuple = bestTuple match { //pattern matching, można to też zrobić inaczej
          case (cost, ls) => (cost + camps(nextCamp), ls :+ nextCamp)
        }
        bestRoutes += newTuple //dodajemy parę (koszt, trasa) do kolejki trzech ostatnich campingów
        bestRoutes.dequeue() //z 4 ostatnich robią się 3 ostatnie
        nextCamp += 1;
      } 
      bestRoutes.last //zwracamy jak dotrzeć do ostatniego
    }
  }
 
  getBestRoute(List(3,2,2,12,32,2,4,11,12,2))     //> res0: (Int, List[Int]) = (10,List(2, 5, 6, 9))
}