(* Autor: Gabriel Bożek   *)
(* Code review :  *)


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

let array_nwd ar = Array.fold_left (fun acc x -> nwd acc x) 0 ar

let array_fst ar2 = Array.init (Array.length ar2) (fun n -> fst (ar2.(n)))

let array_snd ar2 = Array.init (Array.length ar2) (fun n -> snd (ar2.(n)))


(*sprawdza czy jest w ogole szansa, zeby rozwiazanie istniało *)
let check_end_state ar2 =
  let ar_nwd = array_nwd (array_fst ar2) in
   if ar_nwd = 0 then
    true  (*przypadek gdzie mamy zero szklanek lub szklanki zerowe*)
    else
      (Array.fold_left (fun a (_, y) -> (a && (y mod ar_nwd = 0))) true ar2)
      (*sprawdza czy nwd pojemnosci dzieli koncowe stany *)
      &&
      (Array.fold_left (fun a (x, y) -> (a || x = y || y = 0)) false ar2)
      (*czy ostatni stan jest osiagalny*)
      (*w ostatnim ruchu albo opróżniamy jedną szklanke do 0
        albo jedna dolewamy do zera *)

let refill state k capacity= (*dolanie do k szklanki *)
    let copy = Array.copy state in
    (
      copy.(k) <- capacity.(k);
      copy;
    )

let spill state k  = (*opróżnienie k szklanki *)
    let copy = Array.copy state in
    (
      copy.(k) <- 0;
      copy;
    )

let pour state k1 k2 capacity = (*przelanie z k1 to k2*)
    let copy = Array.copy state in
      if (capacity.(k2) - copy.(k2) < copy.(k1)) then
              (
                copy.(k1) <- copy.(k1) - capacity.(k2) + copy.(k2);
                copy.(k2) <- capacity.(k2);
                copy;
                )
            else
              (
                copy.(k2) <- copy.(k2) + copy.(k1);
                copy.(k1) <- 0;
                copy;
              )
(* dodaje do tablicy hashy stan tylko jeśli wczesniej w nim nie byliśmy *)
let add_state hash_table states_queue state time =
  if not (Hashtbl.mem hash_table state) then
  (
    Hashtbl.add hash_table state time;
    Queue.push state states_queue;
  )

(*Na kolejkę wrzucamy stany do rozpatrzenia, wrzucamy tylko te ktore
  nie są w tablicy hashy, żeby ich nie rozpatrywać wielokrotnie*)

let przelewanka glass =
  let capacity = array_fst glass in
  let end_state = array_snd glass in
  let size = Array.length glass in

  if check_end_state glass then
  (
    let state = Array.make (size) 0 in
    let hash_table = Hashtbl.create 123 in
    let states_queue = Queue.create () in
    let answer = ref (-1) in
      (
        Hashtbl.add hash_table state 0;
        Queue.push state states_queue;
        while (not (Queue.is_empty states_queue) && !answer = -1) do
          let temp_state = Queue.pop states_queue in
          let time = Hashtbl.find hash_table temp_state + 1 in
          if (temp_state=end_state) then (answer := time - 1;)
          (*Z powodu tego, że używamy BFS jest to najszybszy możliwy sposób *)
          else
            (
              for i = 0 to (size - 1) do
              (
                add_state hash_table states_queue
                                          (refill temp_state i capacity) time;
                add_state hash_table states_queue (spill temp_state i ) time;
                for j=0 to (size-1) do
                if j<>i then add_state hash_table states_queue
                                          (pour temp_state i j capacity) time;
                done;
                )
              done;
              );
        done;
        !answer;
        );
  )
  else (-1);;  (* Jeżeli stan końcowy nie osiągalny *)