(* Autor: Jan Kociniak
   Reviewer: Piotr Wojtczak
   WPF 2017Z - Przelewanka  *)



(* funkcja dorzucajaca do kolejki q wszystkie stany osiagalne ze stanu arr
   z zaktualizowaną liczbą ruchów *)

let states (arr, d) q =
  let n = Array.length arr and d1 = d+1 in
    for i = 0 to n-1 do
      let (xi, yi) = arr.(i) in
      (* dolanie do pełna i-tej szklanki *)
        arr.(i) <- (xi, xi);
        Queue.add (Array.copy arr, d1) q;
      (* oproznienie i-tej szklanki *)
        arr.(i) <- (xi, 0);
        Queue.add (Array.copy arr, d1) q;
        (* reset *)
        arr.(i) <- (xi, yi);
      for j = i+1 to n-1 do
        let (xj, yj) = arr.(j) in
      (* przelanie z i do j *)
        arr.(j) <- (xj, min (yj + yi) xj);
        arr.(i) <- (xi, max 0 (yi - xj + yj));
        Queue.add (Array.copy arr, d1) q;
      (* przelanie z j do i *)
        arr.(i) <- (xi, min (yi + yj) xi);
        arr.(j) <- (xj, max 0 (yj - xi + yi));
        Queue.add (Array.copy arr, d1) q;
        (* reset *)
        arr.(i) <- (xi, yi);
        arr.(j) <- (xj, yj);
      done;
  done



  let przelewanka arr =
    let n = Array.length arr in
      let q = Queue.create() and been = Hashtbl.create (n*n)
      and searching = ref true and res = ref 0 in
       Queue.add ((Array.map (fun (x, _) -> (x, 0)) arr), 0) q;
       while !searching && not (Queue.is_empty q) do
         let (st, d) = Queue.take q in
         if st = arr then
           begin
             res := d;
             searching := false;
           end
         else
           if not (Hashtbl.mem been (st, d)) then
             begin
               Hashtbl.add been (st, d) true;
               states (st, d) q;
             end
       done;
    if Queue.is_empty q then -1 else !res