agreg/Taquin.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Texte-d'oral-de-modélisation---Agrégation-Option-Informatique\" data-toc-modified-id=\"Texte-d'oral-de-modélisation---Agrégation-Option-Informatique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Texte d'oral de modélisation - Agrégation Option Informatique</a></div><div class=\"lev2 toc-item\"><a href=\"#Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17\" data-toc-modified-id=\"Préparation-à-l'agrégation---ENS-de-Rennes,-2016-17-11\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Préparation à l'agrégation - ENS de Rennes, 2016-17</a></div><div class=\"lev2 toc-item\"><a href=\"#À-propos-de-ce-document\" data-toc-modified-id=\"À-propos-de-ce-document-12\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>À propos de ce document</a></div><div class=\"lev2 toc-item\"><a href=\"#Question-de-programmation\" data-toc-modified-id=\"Question-de-programmation-13\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Question de programmation</a></div><div class=\"lev2 toc-item\"><a href=\"#Réponse-à-l'exercice-requis\" data-toc-modified-id=\"Réponse-à-l'exercice-requis-14\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Réponse à l'exercice requis</a></div><div class=\"lev3 toc-item\"><a href=\"#Structures-de-données\" data-toc-modified-id=\"Structures-de-données-141\"><span class=\"toc-item-num\">1.4.1&nbsp;&nbsp;</span>Structures de données</a></div><div class=\"lev3 toc-item\"><a href=\"#Exemples-de-grilles\" data-toc-modified-id=\"Exemples-de-grilles-142\"><span class=\"toc-item-num\">1.4.2&nbsp;&nbsp;</span>Exemples de grilles</a></div><div class=\"lev3 toc-item\"><a href=\"#Permutations\" data-toc-modified-id=\"Permutations-143\"><span class=\"toc-item-num\">1.4.3&nbsp;&nbsp;</span>Permutations</a></div><div class=\"lev3 toc-item\"><a href=\"#Un-déplacement\" data-toc-modified-id=\"Un-déplacement-144\"><span class=\"toc-item-num\">1.4.4&nbsp;&nbsp;</span>Un déplacement</a></div><div class=\"lev3 toc-item\"><a href=\"#Test-de-la-parité-de-$\\sigma^B$\" data-toc-modified-id=\"Test-de-la-parité-de-$\\sigma^B$-145\"><span class=\"toc-item-num\">1.4.5&nbsp;&nbsp;</span>Test de la parité de <span class=\"MathJax_Preview\" style=\"color: inherit;\"><span class=\"MJXp-math\" id=\"MJXp-Span-169\"><span class=\"MJXp-msubsup\" id=\"MJXp-Span-170\"><span class=\"MJXp-mi MJXp-italic\" id=\"MJXp-Span-171\" style=\"margin-right: 0.05em;\">σ</span><span class=\"MJXp-mi MJXp-italic MJXp-script\" id=\"MJXp-Span-172\" style=\"vertical-align: 0.5em;\">B</span></span></span></span><span class=\"MathJax MathJax_Processing\" id=\"MathJax-Element-38-Frame\" tabindex=\"0\"></span><script type=\"math/tex\" id=\"MathJax-Element-38\">\\sigma^B</script></a></div><div class=\"lev3 toc-item\"><a href=\"#Fonctions-demandées\" data-toc-modified-id=\"Fonctions-demandées-146\"><span class=\"toc-item-num\">1.4.6&nbsp;&nbsp;</span>Fonctions demandées</a></div><div class=\"lev3 toc-item\"><a href=\"#Exemples\" data-toc-modified-id=\"Exemples-147\"><span class=\"toc-item-num\">1.4.7&nbsp;&nbsp;</span>Exemples</a></div><div class=\"lev2 toc-item\"><a href=\"#Bonus-?\" data-toc-modified-id=\"Bonus-?-15\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Bonus ?</a></div><div class=\"lev3 toc-item\"><a href=\"#Complexité\" data-toc-modified-id=\"Complexité-151\"><span class=\"toc-item-num\">1.5.1&nbsp;&nbsp;</span>Complexité</a></div><div class=\"lev3 toc-item\"><a href=\"#Autres-idées\" data-toc-modified-id=\"Autres-idées-152\"><span class=\"toc-item-num\">1.5.2&nbsp;&nbsp;</span>Autres idées</a></div><div class=\"lev2 toc-item\"><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-16\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Conclusion</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Texte d'oral de modélisation - Agrégation Option Informatique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Préparation à l'agrégation - ENS de Rennes, 2016-17"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- *Date* : 29 mai 2017\n",
    "- *Auteur* : [Lilian Besson](https://GitHub.com/Naereen/notebooks/)\n",
    "- *Texte*: [Taquin (pub2008-D2)](http://agreg.org/Textes/pub2008-D2.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## À propos de ce document"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Ceci est une *proposition* de correction, partielle et probablement non-optimale, pour la partie implémentation d'un [texte d'annale de l'agrégation de mathématiques, option informatique](http://Agreg.org/Textes/).\n",
    "- Ce document est un [notebook Jupyter](https://www.Jupyter.org/), et [est open-source sous Licence MIT sur GitHub](https://github.com/Naereen/notebooks/tree/master/agreg/), comme les autres solutions de textes de modélisation que [j](https://GitHub.com/Naereen)'ai écrite cette année.\n",
    "- L'implémentation sera faite en OCaml, version 4+ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The OCaml toplevel, version 4.04.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sys.command \"ocaml -version\";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Notez que certaines fonctions des modules usuels [`List`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) et [`Array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html) ne sont pas disponibles en OCaml 3.12.\n",
    "> J'essaie autant que possible de ne pas les utiliser, ou alors de les redéfinir si je m'en sers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question de programmation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La question de programmation pour ce texte était donnée en page 5, et était assez courte :\n",
    "\n",
    "> \"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)$.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Réponse à l'exercice requis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Structures de données\n",
    "\n",
    "On doit pouvoir représenter $T$, une table du jeu de taquin.\n",
    "\n",
    "On utilisera la structure de données suggérée par l'énoncé :\n",
    "\n",
    "> \"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$.\"\n",
    "\n",
    "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$.\n",
    "\n",
    "![images/taquin.png](images/taquin.png)\n",
    "\n",
    "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]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type taquin = int array array\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type taquin = int array array;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemples de grilles\n",
    "\n",
    "On reproduit les trois exemples ci-dessous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val t1 : taquin =\n",
       "  [|[|10; 6; 4; 12|]; [|1; 14; 3; 7|]; [|5; 15; 11; 13|]; [|8; 0; 2; 9|]|]\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let t1 : taquin = [|\n",
    "    [| 10;  6;  4; 12 |];\n",
    "    [|  1; 14;  3;  7 |];\n",
    "    [|  5; 15; 11; 13 |];\n",
    "    [|  8;  0;  2;  9 |]\n",
    "|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val t2 : taquin =\n",
       "  [|[|0; 1; 2; 4|]; [|3; 6; 10; 12|]; [|5; 7; 14; 11|]; [|8; 9; 15; 13|]|]\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let t2 : taquin = [|\n",
    "    [|  0;  1;  2;  4 |];\n",
    "    [|  3;  6; 10; 12 |];\n",
    "    [|  5;  7; 14; 11 |];\n",
    "    [|  8;  9; 15; 13 |]\n",
    "|];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tf : taquin =\n",
       "  [|[|0; 1; 2; 3|]; [|4; 5; 6; 7|]; [|8; 9; 10; 11|]; [|12; 13; 14; 15|]|]\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tf : taquin = [|\n",
    "    [|  0;  1;  2;  3 |];\n",
    "    [|  4;  5;  6;  7 |];\n",
    "    [|  8;  9; 10; 11 |];\n",
    "    [| 12; 13; 14; 15 |]\n",
    "|];;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutations\n",
    "\n",
    "On peut essayer d'obtenir les deux permutations, $\\sigma(T)$ et $\\sigma^B(T)$, pour une table $T$ donnée.\n",
    "\n",
    "Une permutation sera un simple tableau, de tailles $n^2$ (pour $\\sigma$) et $n^2 - 1$ (pour $\\sigma^B$), qui stocke en case $i$ la valeur $\\sigma(T)[i]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type permutation = int array\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type permutation = int array ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sigma : taquin -> permutation = <fun>\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let sigma (t : taquin) : permutation =\n",
    "    (* Initialisation *)\n",
    "    let n = Array.length t in\n",
    "    let sigm = Array.make (n * n) 0 in\n",
    "    (* Remplissons sigm *)\n",
    "    for i = 0 to n - 1 do\n",
    "        for j = 0 to n - 1 do\n",
    "            sigm.( i * n + j ) <- t.(i).(j)\n",
    "        done;\n",
    "    done;\n",
    "    sigm\n",
    "    (* On aurait aussi pu faire\n",
    "    Array.init (n * n) (fun ij -> t.(ij mod n).(j / n))\n",
    "    *)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : permutation = [|10; 6; 4; 12; 1; 14; 3; 7; 5; 15; 11; 13; 8; 0; 2; 9|]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : permutation = [|0; 1; 2; 4; 3; 6; 10; 12; 5; 7; 14; 11; 8; 9; 15; 13|]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : permutation = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15|]\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sigma t1;;\n",
    "sigma t2;;\n",
    "sigma tf;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'était facile.\n",
    "Maintenant pour la permutation de Boustrophédon, $\\sigma^B(T)$.\n",
    "On va quand même stoquer le $0$, en position $0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val print : ('a, out_channel, unit) format -> 'a = <fun>\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print = Printf.printf;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val sigmaB : taquin -> permutation = <fun>\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let sigmaB (t : taquin) : permutation =\n",
    "    (* Initialisation *)\n",
    "    let n = Array.length t in\n",
    "    let sigm = Array.make ((n * n) - 1) 0 in\n",
    "    let nbzero = ref 0 in\n",
    "    (* Remplissons sigm *)\n",
    "    for i = 0 to n - 1 do\n",
    "        for j = 0 to n - 1 do\n",
    "            if i mod 2 = 0\n",
    "            then (* gauche à droite *)\n",
    "                if t.(i).(j) = 0 then\n",
    "                    incr nbzero\n",
    "                else\n",
    "                    sigm.( i * n + j - !nbzero ) <- t.(i).(j)\n",
    "            else (* droite à gauche *)\n",
    "                if t.(i).(n - j - 1) = 0 then\n",
    "                    incr nbzero\n",
    "                else\n",
    "                    sigm.( i * n + j - !nbzero ) <- t.(i).(n - j - 1)\n",
    "        done;\n",
    "    done;\n",
    "    sigm\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exemples :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : permutation = [|10; 6; 4; 12; 7; 3; 14; 1; 5; 15; 11; 13; 9; 2; 8|]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : permutation = [|1; 2; 4; 12; 10; 6; 3; 5; 7; 14; 11; 13; 15; 9; 8|]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : permutation = [|1; 2; 3; 7; 6; 5; 4; 8; 9; 10; 11; 15; 14; 13; 12|]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sigmaB t1;;\n",
    "sigmaB t2;;\n",
    "sigmaB tf;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Un déplacement\n",
    "\n",
    "On a $4$ déplacements possibles, $\\{N, E, S, O\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type deplacement = Nord | Est | Sud | Ouest\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type deplacement = Nord | Est | Sud | Ouest ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va avoir besoin d'une fonction qui trouve la position $(i,j)$ du trou :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val ou_est : int -> taquin -> int * int = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val ou_est_trou : taquin -> int * int = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let ou_est (x : int) (t : taquin) : (int * int) =\n",
    "    let n = Array.length t in\n",
    "    let ij = ref (0, 0) in\n",
    "    for i = 0 to n - 1 do\n",
    "        for j = 0 to n - 1 do\n",
    "            if t.(i).(j) = x then\n",
    "                ij := (i, j)\n",
    "        done;\n",
    "    done;\n",
    "    !ij\n",
    ";;\n",
    "\n",
    "let ou_est_trou = ou_est 0 ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val copie : taquin -> taquin = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let copie (t : taquin) : taquin =\n",
    "    Array.map (Array.copy) t\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val unmouvement : taquin -> deplacement -> taquin = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let unmouvement (t : taquin) (dir : deplacement) : taquin =\n",
    "    let n = Array.length t in\n",
    "    let i, j = ou_est_trou t in\n",
    "    let tsuivant = copie t in\n",
    "    match dir with\n",
    "    | Nord ->\n",
    "        if i = 0\n",
    "        then\n",
    "            failwith \"Can't go north here\"\n",
    "        else begin\n",
    "            tsuivant.(i).(j) <- tsuivant.(i - 1).(j);\n",
    "            tsuivant.(i - 1).(j) <- 0;\n",
    "            tsuivant\n",
    "        end;\n",
    "    | Est ->\n",
    "        if j = n - 1\n",
    "        then failwith \"Can't go east here\"\n",
    "        else begin\n",
    "            tsuivant.(i).(j) <- tsuivant.(i).(j + 1);\n",
    "            tsuivant.(i).(j + 1) <- 0;\n",
    "            tsuivant\n",
    "        end;\n",
    "    | Sud ->\n",
    "        if i = n - 1\n",
    "        then failwith \"Can't go south here\"\n",
    "        else begin\n",
    "            tsuivant.(i).(j) <- tsuivant.(i + 1).(j);\n",
    "            tsuivant.(i + 1).(j) <- 0;\n",
    "            tsuivant\n",
    "        end;\n",
    "    | Ouest ->\n",
    "        if j = 0\n",
    "        then failwith \"Can't go west here\"\n",
    "        else begin\n",
    "            tsuivant.(i).(j) <- tsuivant.(i).(j - 1);\n",
    "            tsuivant.(i).(j - 1) <- 0;\n",
    "            tsuivant\n",
    "        end;\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val t1' : taquin =\n",
       "  [|[|10; 6; 4; 12|]; [|1; 14; 3; 7|]; [|5; 0; 11; 13|]; [|8; 15; 2; 9|]|]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : permutation = [|10; 6; 4; 12; 1; 14; 3; 7; 5; 0; 11; 13; 8; 15; 2; 9|]\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let t1' = unmouvement t1 Nord ;;\n",
    "\n",
    "sigma t1';;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça semble fonctionner comme dans l'exemple du texte."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test de la parité de $\\sigma^B$\n",
    "\n",
    "Le critère suivant permet de savoir si une table de taquin est jouable, i.e, si on peut la résoudre :\n",
    "\n",
    "> $T$ est jouable si et seulement si $\\sigma^B(T)$ est paire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val nb_inversions : permutation -> int = <fun>\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let nb_inversions (sigm : permutation) : int =\n",
    "    let nb = ref 0 in\n",
    "    let m = Array.length sigm in\n",
    "    for i = 0 to m - 1 do\n",
    "        for j = i + 1 to m - 1 do\n",
    "            if sigm.(i) > sigm.(j) then\n",
    "                incr nb\n",
    "        done;\n",
    "    done;\n",
    "    !nb\n",
    ";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val est_paire : permutation -> bool = <fun>\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let est_paire (sigm : permutation) : bool =\n",
    "    ((nb_inversions sigm) mod 2) = 0\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut vérifier que les trois tables de l'énoncé ont bien une permutation de Boustrophédon paire :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : bool = true\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "est_paire (sigmaB t1);;\n",
    "est_paire (sigmaB t2);;\n",
    "est_paire (sigmaB tf);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et l'exemple de l'énonce qui n'est plus *jouable* :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : bool = false\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tnof = copie tf in\n",
    "tnof.(0).(1) <- 2;\n",
    "tnof.(0).(2) <- 1;\n",
    "est_paire (sigmaB tnof);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val est_jouable : taquin -> bool = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let est_jouable (t : taquin) : bool =\n",
    "    est_paire (sigmaB t)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fonctions demandées\n",
    "\n",
    "- On a déjà écrit la fonction $\\pi_1(T)$, `nb_inversions`.\n",
    "- Pour $\\pi_2(T)$, on doit réfléchir un peu plus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val pi_1 : taquin -> int = <fun>\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let pi_1 (t : taquin) : int =\n",
    "    nb_inversions (sigma t)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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$ !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On commence par définir la norme $\\ell_1$, sur deux couples $(i,j)$ et $(x,y)$ :\n",
    "$$ \\ell_1 : (i,j), (x, y) \\mapsto |i-x| + |j-y| $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val norme_1 : int * int -> int * int -> int = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let norme_1 (ij : int * int) (xy : int * int) : int =\n",
    "    let i, j = ij and x, y = xy in\n",
    "    abs(i - x) + abs(j - y)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puis la distance définie $d(T[i,j])$ dans l'énoncé :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val distance : taquin -> int -> int -> int = <fun>\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let distance (t : taquin) (i : int) (j : int) : int =\n",
    "    let n = Array.length t in\n",
    "    let valeur = t.(i).(j) in\n",
    "    let ifin, jfin = valeur / n, valeur mod n in\n",
    "    norme_1 (i, j) (ifin, jfin)\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et enfin la fonction $\\pi_2(T)$ est facile à obtenir :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val pi_2 : taquin -> int = <fun>\n"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let pi_2 (t : taquin) : int =\n",
    "    let n = Array.length t in\n",
    "    let d = ref 0 in\n",
    "    for i = 0 to n - 1 do\n",
    "        for j = 0 to n - 1 do\n",
    "            if t.(i).(j) != 0\n",
    "            then\n",
    "                d := !d + (distance t i j)\n",
    "        done;\n",
    "    done;\n",
    "    !d\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemples\n",
    "\n",
    "On prend l'exemple du texte avec $T_1$.\n",
    "\n",
    "- $d(T_1[0,3]) = 6$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 6\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance t1 0 3;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $\\pi_2(T) = 38$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 38\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_2 t1;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça semble bon !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec $T_2$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance t2 0 3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 26\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_2 t2;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec $T_f$, évidemment $\\pi_2(T) = 0$ puisque $T_f$ est résolue :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance tf 0 3;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 0\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_2 tf;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Bonus ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Complexité\n",
    "- La fonction $\\pi_1(T)$ est en $\\mathcal{O}(N)$ en temps et mémoire, si $N = n^2$ est le nombre d'éléments dans le tableau.\n",
    "- La fonction $\\pi_2(T)$ est aussi en $\\mathcal{O}(N)$ en temps et mémoire, si $N = n^2$ est le nombre d'éléments dans le tableau."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Autres idées\n",
    "\n",
    "- On pourrait faire deux versions améliorées des fonctions $\\pi_1$ et $\\pi_2$ pour calculer $\\pi(s_a(T))$ efficacement en fonction de $\\pi(t)$ et $a \\in \\{N, E, S, O\\}$. Sans écrire le code, elles seraient en temps constant, puisqu'il faut enlever et rajouter une (ou deux) valeurs dans une somme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- On pourrait implémenter l'algorithme \"ligne à ligne\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- On pourrait implémenter d'autres algorithmes de résolution, et les vérifier sur un exemple non trivial."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "## Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voilà pour les deux questions obligatoires de programmation :\n",
    "\n",
    "- on a décomposé le problème en sous-fonctions,\n",
    "- on a essayé d'être fainéant, en réutilisant les sous-fonctions,\n",
    "- on a fait des exemples et *on les garde* dans ce qu'on présente au jury,\n",
    "- on a testé la fonction exigée sur un exemple venant du texte,\n",
    "- et on a essayé d'en faire un peu plus (au début).\n",
    "\n",
    "> Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.04.2",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.04.2"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "289px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "610px",
    "left": "0px",
    "right": "1223px",
    "top": "124px",
    "width": "249px"
   },
   "toc_section_display": "block",
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}