In [1]:
Sys.command "ocaml -version";;
Out[1]:
La question de programmation pour ce texte était donnée en page 5, et était assez courte :
"Implanter l'algorithme qui, à partir d'une table $T$ du jeu de taquin, calcule les coordonnées du trou et la valeur de $\pi_2(T)$."
On doit pouvoir représenter $T$, une table du jeu de taquin.
On utilisera la structure de données suggérée par l'énoncé :
"Une table $T$ du jeu de taquin est codée par un tableau carré (encore noté $T$) où, pour $i, j \in [| 0, n - 1 |]$, $T[i, j]$ désigne le numéro de la pièce située en ligne $i$ et colonne $j$, le trou étant codé par l’entier $0$."
La figure 1 présente trois tables du jeu pour $n=4$; la première, notée $T_1$ , est aléatoire, la troisième est la table finale $T_f$ et la deuxième, notée $T_2$, peut être qualifiée d’intermédiaire : il est possible de passer en un certain nombre de coups de $T_1$ à $T_2$, puis de $T_2$ à $T_f$.
Par exemple, dans la table $T_1$ de la figure $1$, $T_1[2, 0] = 5$ et le trou est situé à la position $[3, 1]$.
In [2]:
type taquin = int array array;;
Out[2]:
In [3]:
let t1 : taquin = [|
[| 10; 6; 4; 12 |];
[| 1; 14; 3; 7 |];
[| 5; 15; 11; 13 |];
[| 8; 0; 2; 9 |]
|];;
Out[3]:
In [4]:
let t2 : taquin = [|
[| 0; 1; 2; 4 |];
[| 3; 6; 10; 12 |];
[| 5; 7; 14; 11 |];
[| 8; 9; 15; 13 |]
|];;
Out[4]:
In [5]:
let tf : taquin = [|
[| 0; 1; 2; 3 |];
[| 4; 5; 6; 7 |];
[| 8; 9; 10; 11 |];
[| 12; 13; 14; 15 |]
|];;
Out[5]:
In [6]:
type permutation = int array ;;
Out[6]:
In [7]:
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))
*)
;;
Out[7]:
Exemples :
In [8]:
sigma t1;;
sigma t2;;
sigma tf;;
Out[8]:
Out[8]:
Out[8]:
C'était facile. Maintenant pour la permutation de Boustrophédon, $\sigma^B(T)$. On va quand même stoquer le $0$, en position $0$.
In [9]:
let print = Printf.printf;;
Out[9]:
In [10]:
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
;;
Out[10]:
Exemples :
In [11]:
sigmaB t1;;
sigmaB t2;;
sigmaB tf;;
Out[11]:
Out[11]:
Out[11]:
In [12]:
type deplacement = Nord | Est | Sud | Ouest ;;
Out[12]:
On va avoir besoin d'une fonction qui trouve la position $(i,j)$ du trou :
In [13]:
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 ;;
Out[13]:
Out[13]:
In [14]:
let copie (t : taquin) : taquin =
Array.map (Array.copy) t
;;
Out[14]:
In [15]:
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;
;;
Out[15]:
In [16]:
let t1' = unmouvement t1 Nord ;;
sigma t1';;
Out[16]:
Out[16]:
Ça semble fonctionner comme dans l'exemple du texte.
In [17]:
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
;;
Out[17]:
In [18]:
let est_paire (sigm : permutation) : bool =
((nb_inversions sigm) mod 2) = 0
;;
Out[18]:
On peut vérifier que les trois tables de l'énoncé ont bien une permutation de Boustrophédon paire :
In [19]:
est_paire (sigmaB t1);;
est_paire (sigmaB t2);;
est_paire (sigmaB tf);;
Out[19]:
Out[19]:
Out[19]:
Et l'exemple de l'énonce qui n'est plus jouable :
In [20]:
let tnof = copie tf in
tnof.(0).(1) <- 2;
tnof.(0).(2) <- 1;
est_paire (sigmaB tnof);;
Out[20]:
In [21]:
let est_jouable (t : taquin) : bool =
est_paire (sigmaB t)
;;
Out[21]:
In [22]:
let pi_1 (t : taquin) : int =
nb_inversions (sigma t)
;;
Out[22]:
Pour $\pi_2(T)$, on peut être inquiet de voir dans la définition de cette distance la table finale, qui est l'objectif de la résolution du problème, mais en fait les tables finales $T_f$ ont toutes la même forme : en case $(i,j)$ se trouve $i \times n + j$ !
On commence par définir la norme $\ell_1$, sur deux couples $(i,j)$ et $(x,y)$ : $$ \ell_1 : (i,j), (x, y) \mapsto |i-x| + |j-y| $$
In [23]:
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)
;;
Out[23]:
Puis la distance définie $d(T[i,j])$ dans l'énoncé :
In [24]:
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)
;;
Out[24]:
Et enfin la fonction $\pi_2(T)$ est facile à obtenir :
In [25]:
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
;;
Out[25]:
In [26]:
distance t1 0 3;;
Out[26]:
In [27]:
pi_2 t1;;
Out[27]:
Ça semble bon !
Avec $T_2$ :
In [28]:
distance t2 0 3;;
Out[28]:
In [29]:
pi_2 t2;;
Out[29]:
Avec $T_f$, évidemment $\pi_2(T) = 0$ puisque $T_f$ est résolue :
In [30]:
distance tf 0 3;;
Out[30]:
In [31]:
pi_2 tf;;
Out[31]:
Voilà pour les deux questions obligatoires de programmation :
Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.