pkallos · September 10, 2015 23:31 · Sep 10, 2015
diff --git a/horses.scala b/horses.scala
@@ -0,0 +1,83 @@
+/**
+ * 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)
No results found