(* Zadnie przelewanki
Autor: Michał Kardaś
Reviewer: Witalis Domitrz *)

(* Sprawdza czy jakaś oczekiwana szklanka jest pusta
lub pełna. Warunek konieczny do istnienia rozwiązania
ponieważ każda operacja zostawia jedna szklankę pustą lub pełną*)

let pelna_pusta arr =
let czy = ref false in
for i = 0 to (Array.length arr - 1) do
let (pojemnosc, stan) = arr.(i) in
czy := !czy || stan = 0 || stan = pojemnosc
done;
!czy

let rec nwd a b =
if b = 0 then a else nwd b (a mod b);;

(* Liczy nwd ze wszystkich objętości szklanek *)
let licz_NWD arr =
let (a, _) = arr.(0) in
let nwd_szklanek = ref a in
for i = 0 to (Array.length arr - 1) do
let (pojemnosc, _) = arr.(i) in
nwd_szklanek := nwd !nwd_szklanek pojemnosc
done;
!nwd_szklanek

(* Sprawdza czy kandydat jest oczekiwanym stanem szklanek *)
let rowne szklanki kandydat =
let czy = ref true in
for i = 0 to (Array.length szklanki - 1) do
let (_, stan) = szklanki.(i) in
czy := !czy && stan = kandydat.(i)
done;
!czy

(* Sprawdza czy oczekiwana ilość wody w szklance nie jest
względnie pierwsza z NWD objętości szklanek jeżeli NWD
nie jest równe 1. Warunek konieczny do istnienia rozwiązania *)
let sprawdz_NWD arr nwd_szklanek =
let czy = ref true in
if nwd_szklanek = 1 then true
else
begin
for i = 0 to (Array.length arr - 1) do
let (_, stan) = arr.(i) in
czy := !czy && (nwd nwd_szklanek stan) != 1
done;
!czy
end

(* Sprawdza czy oczekiwanym stanem nie są puste szklanki *)
let gotowe arr =
let czy = ref true in
for i = 0 to (Array.length arr - 1) do
let (_, stan) = arr.(i) in
czy := !czy && stan = 0
done;
!czy



let przelewanka szklanki =
let n = Array.length szklanki in
if n = 0 || gotowe szklanki then 0 else
if not (sprawdz_NWD szklanki (licz_NWD szklanki) ||
(pelna_pusta szklanki) ) then -1 else
let queue = Queue.create () in
let wyn = ref (-1) in
(* Tablica, która spamiętuje, które stany zostały już przetworzone *)
let vis = Hashtbl.create n in
let sprawdz stan warstwa =
if rowne szklanki stan && !wyn = -1 then wyn := warstwa
else if not (Hashtbl.mem vis stan) then
begin
Hashtbl.add vis (Array.copy stan) true;
Queue.add (Array.copy stan, warstwa + 1) queue;
end in
begin
sprawdz (Array.make n 0) 0;
(* Dopóki nie znaleziono wyniku i sa jeszcze jakieś
nierozpatrzone stany *)
while  !wyn = (-1) && not (Queue.is_empty queue)  do

let (stany, warstwa) = Queue.take queue in
begin
(* Symuluje wylewanie i wlewanie wody do szklanek *)
for i = 0 to n - 1 do
let pom = stany.(i) in
let (pojemnosc, _) = szklanki.(i) in
stany.(i) <- pojemnosc;
sprawdz stany warstwa;
stany.(i) <- 0;
sprawdz stany warstwa;
stany.(i) <- pom;
done;
(* Symuluje przelanie ze szklanki j do szklanki i *)
for i = 0 to n - 1 do
for j = 0 to n - 1 do
if i != j then
let (pojemnosc_i, _) = szklanki.(i) in
let stan_i = stany.(i) and stan_j = stany.(j) in
begin
stany.(i) <- min pojemnosc_i (stan_i + stan_j);
stany.(j) <- max 0 (stan_j - pojemnosc_i + stan_i);
sprawdz stany warstwa;
stany.(i) <- stan_i;
stany.(j) <- stan_j;
end;
done;
done;
end
done;
!wyn
end