Sys.command "ocaml -version";;

type taquin = int array array;;

let t1 : taquin = [|
    [| 10;  6;  4; 12 |];
    [|  1; 14;  3;  7 |];
    [|  5; 15; 11; 13 |];
    [|  8;  0;  2;  9 |]
|];;

let t2 : taquin = [|
    [|  0;  1;  2;  4 |];
    [|  3;  6; 10; 12 |];
    [|  5;  7; 14; 11 |];
    [|  8;  9; 15; 13 |]
|];;

let tf : taquin = [|
    [|  0;  1;  2;  3 |];
    [|  4;  5;  6;  7 |];
    [|  8;  9; 10; 11 |];
    [| 12; 13; 14; 15 |]
|];;

type permutation = int array ;;

let sigma (t : taquin) : permutation =
    (* Initialisation *)
    let n = Array.length t in
    let sigm = Array.make (n * n) 0 in
    (* Remplissons sigm *)
    for i = 0 to n - 1 do
        for j = 0 to n - 1 do
            sigm.( i * n + j ) <- t.(i).(j)
        done;
    done;
    sigm
    (* On aurait aussi pu faire
    Array.init (n * n) (fun ij -> t.(ij mod n).(j / n))
    *)
;;

sigma t1;;
sigma t2;;
sigma tf;;

let print = Printf.printf;;

let sigmaB (t : taquin) : permutation =
    (* Initialisation *)
    let n = Array.length t in
    let sigm = Array.make ((n * n) - 1) 0 in
    let nbzero = ref 0 in
    (* Remplissons sigm *)
    for i = 0 to n - 1 do
        for j = 0 to n - 1 do
            if i mod 2 = 0
            then (* gauche à droite *)
                if t.(i).(j) = 0 then
                    incr nbzero
                else
                    sigm.( i * n + j - !nbzero ) <- t.(i).(j)
            else (* droite à gauche *)
                if t.(i).(n - j - 1) = 0 then
                    incr nbzero
                else
                    sigm.( i * n + j - !nbzero ) <- t.(i).(n - j - 1)
        done;
    done;
    sigm
;;

sigmaB t1;;
sigmaB t2;;
sigmaB tf;;

type deplacement = Nord | Est | Sud | Ouest ;;

let ou_est (x : int) (t : taquin) : (int * int) =
    let n = Array.length t in
    let ij = ref (0, 0) in
    for i = 0 to n - 1 do
        for j = 0 to n - 1 do
            if t.(i).(j) = x then
                ij := (i, j)
        done;
    done;
    !ij
;;

let ou_est_trou = ou_est 0 ;;

let copie (t : taquin) : taquin =
    Array.map (Array.copy) t
;;

let unmouvement (t : taquin) (dir : deplacement) : taquin =
    let n = Array.length t in
    let i, j = ou_est_trou t in
    let tsuivant = copie t in
    match dir with
    | Nord ->
        if i = 0
        then
            failwith "Can't go north here"
        else begin
            tsuivant.(i).(j) <- tsuivant.(i - 1).(j);
            tsuivant.(i - 1).(j) <- 0;
            tsuivant
        end;
    | Est ->
        if j = n - 1
        then failwith "Can't go east here"
        else begin
            tsuivant.(i).(j) <- tsuivant.(i).(j + 1);
            tsuivant.(i).(j + 1) <- 0;
            tsuivant
        end;
    | Sud ->
        if i = n - 1
        then failwith "Can't go south here"
        else begin
            tsuivant.(i).(j) <- tsuivant.(i + 1).(j);
            tsuivant.(i + 1).(j) <- 0;
            tsuivant
        end;
    | Ouest ->
        if j = 0
        then failwith "Can't go west here"
        else begin
            tsuivant.(i).(j) <- tsuivant.(i).(j - 1);
            tsuivant.(i).(j - 1) <- 0;
            tsuivant
        end;
;;

let t1' = unmouvement t1 Nord ;;

sigma t1';;

let nb_inversions (sigm : permutation) : int =
    let nb = ref 0 in
    let m = Array.length sigm in
    for i = 0 to m - 1 do
        for j = i + 1 to m - 1 do
            if sigm.(i) > sigm.(j) then
                incr nb
        done;
    done;
    !nb
;;

let est_paire (sigm : permutation) : bool =
    ((nb_inversions sigm) mod 2) = 0
;;

est_paire (sigmaB t1);;
est_paire (sigmaB t2);;
est_paire (sigmaB tf);;

let tnof = copie tf in
tnof.(0).(1) <- 2;
tnof.(0).(2) <- 1;
est_paire (sigmaB tnof);;

let est_jouable (t : taquin) : bool =
    est_paire (sigmaB t)
;;

let pi_1 (t : taquin) : int =
    nb_inversions (sigma t)
;;

let norme_1 (ij : int * int) (xy : int * int) : int =
    let i, j = ij and x, y = xy in
    abs(i - x) + abs(j - y)
;;

let distance (t : taquin) (i : int) (j : int) : int =
    let n = Array.length t in
    let valeur = t.(i).(j) in
    let ifin, jfin = valeur / n, valeur mod n in
    norme_1 (i, j) (ifin, jfin)
;;

let pi_2 (t : taquin) : int =
    let n = Array.length t in
    let d = ref 0 in
    for i = 0 to n - 1 do
        for j = 0 to n - 1 do
            if t.(i).(j) != 0
            then
                d := !d + (distance t i j)
        done;
    done;
    !d
;;

distance t1 0 3;;

pi_2 t1;;

distance t2 0 3;;

pi_2 t2;;

distance tf 0 3;;

pi_2 tf;;