Magical Forest: Goats, Wolves, and Lions

forest.ml

(* "Magical Forest: Goats, Wolves, and Lions"
 *
 * Inspired by this reddit post:
 * http://www.reddit.com/r/programming/comments/27e7r3/performance_comparison_of_java_8_c_11_and_the/
 *
 * The following code can be pasted into an OCaml REPL.
 * Then a solution is called for like this:
 *
 *   magical_forest (683, 1054, 1290);;
 *
 * This example returns: 1737, 0, 0 -- meaning 1737 goats is the maximized final population.
 *
 *)


(* -- Greedy solution for final 'c' population -- *)

(* Calling b_eats_a (a,b,c) greedily optimizes for 'c' and returns its
 * final population. ie. 'c' is assumed to be the 'winner'. *)

let rec b_eats_a ((a,b,c) as f) =
  (* eat all the a's we can *)
  let n = min a b in
  if n > 0 then c_eats_a (a-n,b-n,c+n)
           else c_eats_a f

and c_eats_a ((a,b,c) as f) =
  let m = min a c in
  if m > 0 then
    (* want a ~= b *)
    let n = min m ((a-b+1) lsr 1) in
    b_eats_a (a-n,b+n,c-n)
  else
    c_eats_b f

and c_eats_b (a,b,c) =
  let m = min b c in
  if m > 0 then
    (* want a ~= b *)
    let n = min m ((b-a+1) lsr 1) in
    b_eats_a (a+n,b-n,c-n)
  else c (* final result: return the population we're optimizing for (c) *)


(* ------------------------- *)

let rotate n (a,b,c) =
  match n mod 3 with
  | 0 -> (a,b,c)
  | 1 -> (b,c,a)
  | 2 -> (c,a,b)
  | _ -> failwith "modular artithmetic please"

let show (g,w,l) = Printf.printf "%d, %d, %d\n" g w l

let magical_forest tuple =
  (* Rotate through goats, wolves, and lions, maximizing survival of each to
   * determine which solution has greatest final population. *)
  let rec loop best rot =
    if rot > 2 then best else begin
      let n = b_eats_a (rotate rot tuple) in
      let _,highest = best in
      loop (if n > highest then (rot,n) else best) (rot+1)
    end
  in
  let rot,n = loop (0,0) 0 in
  show (rotate (3-rot) (0,0,n))