すごいH本の 「ヒースロー空港からロンドンへ」を Scala でやってみた

gistfile1.scala

case class Section(getA: Int, getB: Int, getC: Int)

type RoadSystem = List[Section]

val heathrowToLondon: RoadSystem = List(Section(50,10,30),Section(5,90,20),Section(40,2,25),Section(10,8,0))

object Label extends Enumeration {
  val A,B,C = Value
}

case class Path(label: Label.Value, cost: Int)

def roadStep(p:(List[Path],List[Path]))(s:Section):(List[Path],List[Path]) = {
  val priceA = p._1.map{x => x.cost}.sum
  val priceB = p._2.map{x => x.cost}.sum
  val forwardPriceToA = priceA + s.getA
  val crossPriceToA = priceB + s.getB + s.getC
  val forwardPriceToB = priceB + s.getB
  val crossPriceToB = priceA + s.getA + s.getC
  val newPathToA = if (forwardPriceToA <= crossPriceToA) 
                     {Path(Label.A,s.getA)::p._1} 
                   else 
                     {Path(Label.C,s.getC)::Path(Label.B,s.getB)::p._2}
  val newPathToB = if (forwardPriceToB <= crossPriceToB) 
                     {Path(Label.B,s.getB)::p._2} 
                   else 
                     {Path(Label.C,s.getC)::Path(Label.A,s.getA)::p._1}  
  (newPathToA,newPathToB)
}


def optimalPath(r:RoadSystem):List[Path] = {
//  val (bestAPath, bestBPath) = r.foldLeft((List():List[Path],List():List[Path])){(x,y) => roadStep(x)(y)}
  val (bestAPath, bestBPath) = (((List():List[Path],List():List[Path])) /: r){(x,y) => roadStep(x)(y)}
  if (bestAPath.map{x => x.cost}.sum <= bestBPath.map{x => x.cost}.sum) bestAPath.reverse else bestBPath.reverse
}

/*
def groupsOf[A](i:Int)(l:List[A]):List[List[A]] = {
    (i,l) match {
      case (_,List()) => List()
      case (0,_) => List()
      case _ => l.take(i) :: groupsOf(i){l.drop(i)}
    }
}
*/

val bestway = optimalPath(heathrowToLondon)

println("The best path to take is: %s".format(bestway.map{_.label}.mkString))
println("The price is: %s".format(bestway.map{_.cost}.sum))