Skip to content

Instantly share code, notes, and snippets.

@atavener
Created June 6, 2014 05:24
Show Gist options
  • Save atavener/bde55d35caa06914c50a to your computer and use it in GitHub Desktop.
Save atavener/bde55d35caa06914c50a to your computer and use it in GitHub Desktop.
Magical Forest: Goats, Wolves, and Lions
(* "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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment