zombies.fsx

//Problem:
//You have N zombies, you wish to find the strongest and weakest zombie in population
//The only way to compare 2 zombies is by directly comparing their strength with either > or <
//Zombie strength in this implementation is specified with an integer
//The problem must be solved with a maximum of 3n/2 comparisons or "fights" between 2 zombies

open System

//Find the highest power of 2 which is less then or equal to n
let highestPower2 n =
  let l = int (Math.Log(float n, 2.0))
  pown 2 l

//Put 2 zombies against eachother based on operator, return tuple with result, also count fights
let mutable totalFights = 0
let fight a b op = 
  totalFights <- totalFights + 1
  if op a b then (a, b) else (b, a)

//Returns 2 lists where each element in list a is <op> each element in list b
let comparePairs (pop:list<int>) op =
 List.unzip [ 
    for i in 0 .. 2 .. pop.Length - 1 do
      yield (fight pop.[i] pop.[i + 1] op) ]

//Select either winners or losers based on operator
let rec select (pop:list<int>) op =
  match pop.Length with
  | 1 -> pop.[0]
  | _ -> let winners, losers = comparePairs pop op; 
         select winners op

//Recursively subdivide the population in powers of 2 and run the select function on the subdivisions
let rec divideAndSelect (pop:list<int>) op =
  let offset = highestPower2 pop.Length
  let here = select pop.[..(offset-1)] op
  if offset = pop.Length then
      here
  else
      let deeper = divideAndSelect pop.[offset..] op
      fst (fight here deeper op)

//Find best and worst zombie, return them in a tuple
let findZombies (zombies:list<int>) = 
  let pop = zombies.[(zombies.Length % 2)..]
  
  let winners, losers = comparePairs pop (>)
  
  let winner = (divideAndSelect winners (>))
  let loser = (divideAndSelect losers (<))
  
  //Compare with last zombie for uneven populations
  if zombies.Length % 2 = 1 then
    (fst (fight zombies.[0] winner (>)),
     fst (fight zombies.[0] loser (<)))
  else
    (winner, loser)

//Test case
let testCase = [9;3;6;8;4;1;7;5;9;3;6;2;1;4;10]
let winner, loser = findZombies testCase
printfn "Winner: %A" winner
printfn "Loser %A" loser
printfn "Used fights: %A" totalFights
printfn "Max fights allowed: %A" (int (float testCase.Length * 3.0 / 2.0))