(** Zadanie Przelewanka    **)
(** Autor : Michał Szostek **)
(** Reviewer: Rafał Łyżwa  **)

(** Heurystyki **)

let rec nwd a b =
  if a = 0 then b
  else if b = 0 then a
  else let (a,b) = (max a b, min a b) in
  nwd (a mod b) b

(* Test czy wymagany poziom wody nie jest wyższy od szklanki *)
let test_bucket_size n t_max t_fin =
  let test = ref true in
  begin
    for i = 0 to (n - 1) do
      if t_max.(i) < t_fin.(i) then test:=false;
    done;
    !test;
  end

(* Test czy wszystkie końcowe wysokości są podzielne przez nwd wysokosci szklanek *)
let test_nwd t_max t_fin =
  let nd = Array.fold_left nwd 0 t_max in
  if nd = 0 then true else
  Array.fold_left (fun t a -> t && (a mod nd = 0)) true t_fin

(* Test czy jest choć jedna pusta lub pełna (z uwzględnieniem szklanek wysokości zero) *)
let test_empty_or_full n t_max t_fin =
  let test = ref false in
  let only0 = ref true in
  begin
    for i = 0 to (n - 1) do
      if t_max.(i) <> 0 then
      begin
        only0 := false;
        if t_fin.(i) = 0 || t_fin.(i) = t_max.(i) then test := true;
      end;
    done;
    (!test || !only0);
  end

(* Główna funkcja sprawdzająca heurystyki *)
let heuristics n t_max t_fin =
  let t1 = test_bucket_size n t_max t_fin in
  let t2 = test_nwd t_max t_fin in
  let t3 = test_empty_or_full n t_max t_fin in
  let heur_array = [|t1;t2;t3|] in
  Array.fold_left (fun t a -> t && a) true heur_array

(** Funkcje pomocnicze **)

(* Opróżnianie szklanki (i) *)
let empty_bucket state i =
  let t = Array.copy state in
  begin
    t.(i) <- (0);
    t;
  end

(* Napełnianie szklanki (i) *)
let fill_bucket state t_max i =
  let t = Array.copy state in
  begin
    t.(i) <- t_max.(i);
    t;
  end

(* Przelewanie ze szklanki (i) do szklanki (j) *)
let modify_state state t_max i j =
  let t = Array.copy state in
  let a1 = t.(i) in
  let b1 = t.(j) in
  let b2 = t_max.(j) in
  let d = b2-b1 in
    begin
    t.(i) <- (max 0 (a1 - d));
    t.(j) <- (min b2 (b1 + a1));
    t;
    end

(** Główny algorytm **)

let hash stan =
        let wyn = ref 0 in
        Array.iter (fun x -> wyn:= !wyn * 499 + x mod 1000000007) stan;
        (!wyn, stan)

(* Główne przeszukiwanie grafu *)
let state_search n t_start t_max t_fin =
  let wyn = ref (-1) in
  let q = Queue.create() in
  let ht = Hashtbl.create 100000 in
  begin
    Queue.add t_start q;
    Hashtbl.add ht (hash t_start) 0;
    while not (Queue.is_empty q) do
      if (Queue.top q) = t_fin then
        begin
        wyn := (Hashtbl.find ht (hash (Queue.top q)));
        Queue.clear q;
        end else
        let top = (Queue.pop q) in
        let k = Hashtbl.find ht (hash top) in
        begin
          for i = 0 to (n-1) do
            begin
              let e = (empty_bucket top i) in
              if not (Hashtbl.mem ht (hash e)) then
              begin  (* Opróżnianie *)
                Queue.add e q;
                Hashtbl.add ht (hash e) (k+1);
              end;
              let e = (fill_bucket top t_max i) in
              if not (Hashtbl.mem ht (hash e)) then
              begin  (* Napełnianie*)
                Queue.add e q;
                Hashtbl.add ht (hash e) (k+1);
              end;
              for j = 0 to (n-1) do
                if i <> j then
                let e = modify_state top t_max i j in
                if not (Hashtbl.mem ht (hash e)) then
                begin  (*Przelwanie*)
                  Queue.add e q;
                  Hashtbl.add ht (hash e) (k+1);
                end;
              done;
            end;
          done;
        end;
    done;
  !wyn;
end

(* Funkcja wynikowa *)
let przelewanka t =
let n = Array.length t in
let t_start = Array.make n 0 in
let t_max = Array.map (fun (a,_) -> a) t in
let t_fin = Array.map (fun (_,b) -> b) t in
if (heuristics n t_max t_fin) then
  state_search n t_start t_max t_fin
else -1