horses.scala

/**
 * Problem statement: You have 25 horses, each of which run around a track at a consistent speed
 * (i.e. running the same horse around the track yields the same speed every time). You do not 
 * have a stopwatch to time them but you are able to race them in groups around the track and
 * rank them in order.
 * 
 * The race track can only fit 5 horses at a time. Find the top 3 fastest horses, in the least
 * amount of races possible.
 */
 
var totalRaceCounter = 0

case class Horse(label: String, speed: Double)

implicit class BunchaHorses(horses: List[Horse]) {
  def race(): List[Horse]  = {
    totalRaceCounter = totalRaceCounter + 1

    println("Racing the following horses: ")
    horses.foreach(h => println(" - " + h.toString))
    horses.sortBy(_.speed)
  }
}

def findTopNHorses(trackSize: Int, topN: Int, horses: List[Horse]): List[Horse] = {

  // If the track fits all the horses,
  // just return the topN horses
  if (trackSize >= horses.size || topN >= horses.size) {
    horses.race().take(topN)
  } else {
    // Break the horses into trackSize buckets
    val groupedHorses = horses.grouped(trackSize)

    // Race all the horses in the groups
    val racedHorses = groupedHorses.map(_.race).toList

    // Label each horse group with the label of the fastest horse
    val labeledHorseGroups = racedHorses.map { hg =>
      hg.head.label -> hg
    }.toMap

    // Find the TopN of these top horses (basically by racing them)
    val topHorses = findTopNHorses(trackSize, topN, racedHorses.map(_.head))

    val indexedTopHorses = topHorses.zipWithIndex

    // The potential topN fastest horses in each group is
    // the top (groupRank - topN) horses from each group
    val trimmedHorses = indexedTopHorses.flatMap { case(fastHorse, rank) =>
      // Taking negative returns an empty List
      labeledHorseGroups(fastHorse.label).take(topN - rank)
    }

    // We already know the top horse is #1
    // so find the topN - 1 in the remaining pile
    trimmedHorses.head +: findTopNHorses(trackSize, topN - 1, trimmedHorses.tail)
  }
}


val nHorses = 25
val trackSize = 5
val topN = 3

val horses = (1 to nHorses).map { label =>
  Horse(label.toString, util.Random.nextDouble)
}.toList

val topHorses = findTopNHorses(trackSize, topN, horses)
val topHorsesCheck = horses.sortBy(_.speed).take(topN).toList

println()
println(s"Racing!!")
println(s"   Number of Horses: $nHorses")
println(s"   Track size : $trackSize")
println(s"   TopN : $topN")
println("Using limited race track: ")
println(topHorses)
println(s"Total Races: $totalRaceCounter")
println()
println("Sanity check using one race on a huge track: ")
println(topHorsesCheck)