agreg/Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table de matières<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Un-exercice-d'algorithmique---mise-en-page-de-paragraphe,-résolutions-gourmande-et-dynamique\" data-toc-modified-id=\"Un-exercice-d'algorithmique---mise-en-page-de-paragraphe,-résolutions-gourmande-et-dynamique-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique</a></span><ul class=\"toc-item\"><li><span><a href=\"#Question-1.\" data-toc-modified-id=\"Question-1.-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Question 1.</a></span><ul class=\"toc-item\"><li><span><a href=\"#Réponse-:-non-!\" data-toc-modified-id=\"Réponse-:-non-!-1.1.1\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>Réponse : non !</a></span></li><li><span><a href=\"#Contre-exemple-de-taille-fixée\" data-toc-modified-id=\"Contre-exemple-de-taille-fixée-1.1.2\"><span class=\"toc-item-num\">1.1.2&nbsp;&nbsp;</span>Contre exemple de taille fixée</a></span></li><li><span><a href=\"#Faire-croître-la-différence-entre-les-deux-coûts-vers-l'infini\" data-toc-modified-id=\"Faire-croître-la-différence-entre-les-deux-coûts-vers-l'infini-1.1.3\"><span class=\"toc-item-num\">1.1.3&nbsp;&nbsp;</span>Faire croître la différence entre les deux coûts vers l'infini</a></span></li><li><span><a href=\"#Bonus-:-faire-croître-le-rapport-vers-l'infini-?\" data-toc-modified-id=\"Bonus-:-faire-croître-le-rapport-vers-l'infini-?-1.1.4\"><span class=\"toc-item-num\">1.1.4&nbsp;&nbsp;</span>Bonus : faire croître le <em>rapport</em> vers l'infini ?</a></span></li><li><span><a href=\"#Code-Python-pour-la-méthode-gloutonne\" data-toc-modified-id=\"Code-Python-pour-la-méthode-gloutonne-1.1.5\"><span class=\"toc-item-num\">1.1.5&nbsp;&nbsp;</span>Code Python pour la méthode gloutonne</a></span></li><li><span><a href=\"#Exemples\" data-toc-modified-id=\"Exemples-1.1.6\"><span class=\"toc-item-num\">1.1.6&nbsp;&nbsp;</span>Exemples</a></span></li></ul></li><li><span><a href=\"#Question-2.\" data-toc-modified-id=\"Question-2.-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Question 2.</a></span><ul class=\"toc-item\"><li><span><a href=\"#Problème-d'optimisation-à-résoudre\" data-toc-modified-id=\"Problème-d'optimisation-à-résoudre-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Problème d'optimisation à résoudre</a></span></li><li><span><a href=\"#Relation-de-récurrence\" data-toc-modified-id=\"Relation-de-récurrence-1.2.2\"><span class=\"toc-item-num\">1.2.2&nbsp;&nbsp;</span>Relation de récurrence</a></span></li><li><span><a href=\"#Implémentation-naïve-par-mémoïsation\" data-toc-modified-id=\"Implémentation-naïve-par-mémoïsation-1.2.3\"><span class=\"toc-item-num\">1.2.3&nbsp;&nbsp;</span>Implémentation naïve par mémoïsation</a></span></li><li><span><a href=\"#Exemples\" data-toc-modified-id=\"Exemples-1.2.4\"><span class=\"toc-item-num\">1.2.4&nbsp;&nbsp;</span>Exemples</a></span></li></ul></li><li><span><a href=\"#Question-3.\" data-toc-modified-id=\"Question-3.-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Question 3.</a></span></li><li><span><a href=\"#Question-4.-Pourquoi-un-coût-cubique-et-pas-linéaire-?\" data-toc-modified-id=\"Question-4.-Pourquoi-un-coût-cubique-et-pas-linéaire-?-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Question 4. Pourquoi un coût cubique et pas linéaire ?</a></span></li><li><span><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Conclusion</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Un exercice d'algorithmique - mise en page de paragraphe, résolutions gourmande et dynamique\n",
    "\n",
    "> Source : http://lacl.fr/~lpellissier/Algo1/TD3.pdf, auteur : [Luc Pélissier](http://lacl.fr/~lpellissier/) (2020-21).\n",
    "\n",
    "Le problème étudié est l’impression équilibrée d’un paragraphe sur une imprimante.\n",
    "Le texte d’entrée est modélisé comme une séquence de $n$ mots de longueurs $l_1,l_2, \\dots, l_n$ (mesurées en caractères, que l'on suppose tous de même largeur - c'est le cas par exemple avec une police dite [*à chasse fixe*](https://fr.wikipedia.org/wiki/Police_d'%C3%A9criture_%C3%A0_chasse_fixe)).\n",
    "\n",
    "On souhaite imprimer ce paragraphe de manière équilibrée sur un certain nombre de lignes qui contiennent un maximum de $M\\geq1$ caractères chacune.\n",
    "Le critère d’équilibre est le suivant :\n",
    "Si une ligne donnée contient les mots $i$ à $j$ (avec $i \\leq j$) et qu’on laisse exactement [une espace](https://fr.wikipedia.org/wiki/Espace_(typographie)) entre deux mots, le nombre de caractères d’espacements supplémentaires à la fin de la ligne est $f(M - j+i - \\sum\\limits_{k=i}^j l_k)$, qui doit être positif ou nul pour que les mots tiennent sur la ligne.\n",
    "L’objectif est de minimiser la somme, sur toutes les lignes *hormis la dernière*, des cubes des nombres de caractères d’espacement présents à la fin de chaque ligne : cela correspond à $f(s) = s^3$.\n",
    "\n",
    "- Auteur: [Lilian Besson](https://github.com/Naereen/)\n",
    "- Date : jeudi 04/02/2021\n",
    "- Licence : [MIT](https://lbesson.mit-license.org/)\n",
    "- Lien : https://github.com/Naereen/notebooks/tree/master/agreg/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Remarque :* pour bien visualiser ces espaces en fin de fichier, je termine chaque ligne par `;`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Question 1.\n",
    "\n",
    "**1. Est-ce que l’algorithme glouton consistant à remplir les lignes une à une en mettant à chaque fois le maximum de mots possibles sur la ligne en cours, fournit l’optimum ?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Réponse : non !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Contre exemple de taille fixée\n",
    "\n",
    "Comme le coût est la somme des cubes d'espaces en fin de ligne, on peut penser à un contre-exemple qui va exploiter le fait que $(2x)^3 >> 2 x^3$, et produire un texte qui aura deux lignes identiques (avec $k$ espaces en fin de lignes) lorsqu'on le met en page optimalement, et une ligne quasi complète mais une deuxième ligne quasi vide :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T08:47:13.879894Z",
     "start_time": "2021-02-04T08:47:13.827954Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA B                    ;\n",
      "AA AA AA AA AA AA B                    ;\n",
      "EOF > /tmp/test_nongreedy_optimal.txt\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "bash: ligne 4: avertissement : « here-document » à la ligne 1 délimité par la fin du fichier (au lieu de « EOF »)\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "cat << EOF\n",
    "AA AA AA AA AA AA B                    ;\n",
    "AA AA AA AA AA AA B                    ;\n",
    "EOF > /tmp/test_nongreedy_optimal.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T08:47:26.685859Z",
     "start_time": "2021-02-04T08:47:26.547394Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA B                    ;\r\n",
      "AA AA AA AA AA AA B                    ;\r\n"
     ]
    }
   ],
   "source": [
    "cat /tmp/test_nongreedy_optimal.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T08:47:14.686342Z",
     "start_time": "2021-02-04T08:47:14.643709Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA B AA AA AA AA AA AA ;\n",
      "B                                     ;\n",
      "EOF > test_greedy_suboptimal.txt\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "bash: ligne 4: avertissement : « here-document » à la ligne 1 délimité par la fin du fichier (au lieu de « EOF »)\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "cat << EOF\n",
    "AA AA AA AA AA AA B AA AA AA AA AA AA ;\n",
    "B                                     ;\n",
    "EOF > test_greedy_suboptimal.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T08:47:33.339316Z",
     "start_time": "2021-02-04T08:47:33.196519Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA AA AA AA AA AA AA AA ;\r\n",
      "B                                      ;\r\n"
     ]
    }
   ],
   "source": [
    "cat /tmp/test_greedy_suboptimal.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour l'instant, j'ai codé ça vite fait en Bash pour calculer le coût des deux fichiers :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T08:47:36.720331Z",
     "start_time": "2021-02-04T08:47:36.566050Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[H\u001b[2J/tmp/test_greedy_suboptimal.txt\n",
      "################################################################################\n",
      "AA AA AA AA AA AA AA AA AA AA AA AA AA ;\n",
      "B                                      ;\n",
      "################################################################################\n",
      "0\n",
      "X\n",
      "n = 0, i = 1\n",
      "=> n = 1, i = 1\n",
      "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n",
      "n = 1, i = 38\n",
      "=> n = 54873, i = 38\n",
      "/tmp/test_nongreedy_optimal.txt\n",
      "################################################################################\n",
      "AA AA AA AA AA AA B                    ;\n",
      "AA AA AA AA AA AA B                    ;\n",
      "################################################################################\n",
      "0\n",
      "XXXXXXXXXXXXXXXXXXXX\n",
      "n = 0, i = 20\n",
      "=> n = 8000, i = 20\n",
      "XXXXXXXXXXXXXXXXXXXX\n",
      "n = 8000, i = 20\n",
      "=> n = 16000, i = 20\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "clear\n",
    "for file in /tmp/test_*txt; do\n",
    "    echo $file\n",
    "    hr\n",
    "    cat $file\n",
    "    hr\n",
    "    n=0\n",
    "    echo $n\n",
    "    for line in $(cat $file | grep -o ' *;' | sed s/';'/''/g | tr ' ' 'X'); do\n",
    "        echo $line; i=$(echo $line | wc -c)\n",
    "        i=$((i-1))\n",
    "        echo \"n = $n, i = $i\"; n=$((n + i*i*i))\n",
    "        echo \"=> n = $n, i = $i\"\n",
    "    done\n",
    "done"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit que la solution gourmande a un coût de 54873 alors que la solution non gourmande (optimale) a un coût de 16000."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Faire croître la différence entre les deux coûts vers l'infini\n",
    "\n",
    "On peut juste produire $n$ fois ces deux lignes, et le coût de la solution gourmande sera $54873 n$ et le coût optimal sera $16000 n$.\n",
    "Cela montre que la **différence** entre les deux coûts n'est pas bornée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bonus : faire croître le *rapport* vers l'infini ?\n",
    "On devrait pouvoir aussi faire croître le rapport des deux coûts vers l'infini : plutôt que de générer ces $n$ lignes identiques, on a juste à augmenter la longueur de ces lignes (et n'en avoir que deux, mais très longues).\n",
    "Comme le coût est cubique en le nombre d'espaces, on aura bien un rapport non borné entre le coût gourmand (sous optimal) et le coût optimal.\n",
    "\n",
    "**Corollaire :** cela montre que la solution gourmande n'est pas un k-approximation du problème étudié.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Code Python pour la méthode gloutonne\n",
    "\n",
    "Même si elle n'est pas efficace, on va commencer par écrire cette méthode gloutonne :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:13:47.884832Z",
     "start_time": "2021-02-04T12:13:47.878866Z"
    }
   },
   "outputs": [],
   "source": [
    "from typing import Tuple, List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:23:32.059174Z",
     "start_time": "2021-02-04T12:23:32.049018Z"
    }
   },
   "outputs": [],
   "source": [
    "def longueur_ligne(ligne: List[str]) -> int:\n",
    "    return sum(len(mot) for mot in ligne)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:25:44.665265Z",
     "start_time": "2021-02-04T12:25:44.634102Z"
    }
   },
   "outputs": [],
   "source": [
    "def mise_en_page_paragraphe_gloutonne(longueur_max:int, mots: List[str]) -> List[List[str]]:\n",
    "    print(f\"Longueur maximum de la ligne = {longueur_max}\")\n",
    "    print(f\"Longueur des mots = {longueurs_mots}\")\n",
    "    \n",
    "    assert all(\n",
    "        1 <= len(mot) <= longueur_max\n",
    "        for mot in mots\n",
    "    )\n",
    "    \n",
    "    mots = list(mots)[::-1]  # on les lit de la fin\n",
    "\n",
    "    paragraphes = []\n",
    "    ligne_actuelle = []\n",
    "    longueur_ligne_actuelle = 0\n",
    "\n",
    "    while mots:\n",
    "        # print(f\"mots = {mots}\")\n",
    "        mot_a_placer = mots.pop()\n",
    "        # print(f\"  mot_a_placer = {mot_a_placer}\")\n",
    "        # print(f\"  ligne_actuelle = {ligne_actuelle}\")\n",
    "        \n",
    "        if longueur_ligne(ligne_actuelle) + len(mot_a_placer) <= longueur_max:\n",
    "            ligne_actuelle += [mot_a_placer]\n",
    "            longueur_ligne_actuelle += len(mot_a_placer)\n",
    "            if longueur_ligne_actuelle < longueur_max:\n",
    "                ligne_actuelle += [\" \"]\n",
    "                longueur_ligne_actuelle += 1\n",
    "\n",
    "        # 1 + car on ajoute l'espace\n",
    "        if longueur_ligne_actuelle + 1 >= longueur_max:\n",
    "            paragraphes.append(ligne_actuelle)\n",
    "            ligne_actuelle = []\n",
    "            longueur_ligne_actuelle = 0\n",
    "\n",
    "        # print(f\"  ligne_actuelle = {ligne_actuelle}\")\n",
    "        # print(f\"  paragraphes = {paragraphes}\")\n",
    "    \n",
    "    # dernière ligne si pas encore ajoutée\n",
    "    if ligne_actuelle:\n",
    "        paragraphes.append(ligne_actuelle)\n",
    "\n",
    "    # puis on complète avec des espaces en fin de lignes\n",
    "    for ligne in paragraphes:\n",
    "        espaces_fin_paragraphe = longueur_max - longueur_ligne(ligne)\n",
    "        ligne += [\" \"] * espaces_fin_paragraphe\n",
    "    \n",
    "    assert all(\n",
    "        longueur_ligne(ligne) == longueur_max\n",
    "        for ligne in paragraphes\n",
    "    )\n",
    "    return paragraphes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:25:44.993465Z",
     "start_time": "2021-02-04T12:25:44.979573Z"
    }
   },
   "outputs": [],
   "source": [
    "def print_paragraphes(paragraphes: List[List[str]]):\n",
    "    print(f\"\\n# Mise en page finale d'un texte de {len(paragraphes)} lignes \")\n",
    "    for ligne in paragraphes:\n",
    "        print(\"\".join(ligne) + \";\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:35:54.354501Z",
     "start_time": "2021-02-04T12:35:54.345021Z"
    }
   },
   "outputs": [],
   "source": [
    "from typing import Callable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:36:00.204485Z",
     "start_time": "2021-02-04T12:36:00.189314Z"
    }
   },
   "outputs": [],
   "source": [
    "def cout_paragraphes(paragraphes: List[List[str]], cout: Callable[[int], int]) -> int:\n",
    "    lignes = [ \"\".join(ligne) for ligne in paragraphes ]\n",
    "    espaces_de_fin = [\n",
    "        len(ligne) - len(ligne.rstrip())\n",
    "        for ligne in lignes\n",
    "    ]\n",
    "    return sum(cout(es) for es in espaces_de_fin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:01.870656Z",
     "start_time": "2021-02-04T12:38:01.857190Z"
    }
   },
   "outputs": [],
   "source": [
    "def print_couts(paragraphes):\n",
    "    print(\"- Nombre d'espaces en fin de lignes =\", cout_paragraphes(paragraphes, cout= lambda i: i))\n",
    "    print(\"- Somme des carrés des nombres d'espaces en fin de lignes =\", cout_paragraphes(paragraphes, cout= lambda i: i**2))\n",
    "    print(\"- Somme des cubes des nombres d'espaces en fin de lignes =\", cout_paragraphes(paragraphes, cout= lambda i: i**3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un premier exemple simple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:37.248579Z",
     "start_time": "2021-02-04T12:38:37.239752Z"
    }
   },
   "outputs": [],
   "source": [
    "longueur_max = len(\"AA AA \")  # sans le ;\n",
    "mots = [\"AA\", \"AA\", \"AA\", \"B\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:37.544404Z",
     "start_time": "2021-02-04T12:38:37.538720Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longueur maximum de la ligne = 6\n",
      "Longueur des mots = [2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:37.958606Z",
     "start_time": "2021-02-04T12:38:37.943294Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA AA ;\n",
      "AA B  ;\n",
      "- Nombre d'espaces en fin de lignes = 3\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 5\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 9\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Peut-on retrouver la solution suivante, qui avait été calculée à la main ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:40.585595Z",
     "start_time": "2021-02-04T12:38:40.467709Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA AA AA AA AA AA AA AA ;\r\n",
      "B                                      ;\r\n"
     ]
    }
   ],
   "source": [
    "cat /tmp/test_greedy_suboptimal.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:40.857877Z",
     "start_time": "2021-02-04T12:38:40.853713Z"
    }
   },
   "outputs": [],
   "source": [
    "longueur_max = len(\"AA AA AA AA AA AA AA AA AA AA AA AA AA \")  # sans le ;\n",
    "mots = [\"AA\"]*13 + [\"B\"]*1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions cela :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:41.591637Z",
     "start_time": "2021-02-04T12:38:41.581389Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longueur maximum de la ligne = 39\n",
      "Longueur des mots = [2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T12:38:41.975305Z",
     "start_time": "2021-02-04T12:38:41.959171Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA AA AA AA AA AA AA AA AA AA AA AA AA ;\n",
      "B                                      ;\n",
      "- Nombre d'espaces en fin de lignes = 39\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 1445\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 54873\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Question 2.\n",
    "\n",
    "**2. Donner un algorithme de programmation dynamique résolvant le problème. Analyser sa complexité en temps et en espace. Et implémenter le dans le langage de votre choix. Vérifier qu'il donne la réponse optimale sur l'exemple trouvé en question 1. (ou en tous cas, une meilleure réponse).**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va déjà écrire le problème d'optimisation à résoudre, puis une relation de récurrence.\n",
    "En écrivant un algorithme récursif naïf mais avec mémoïsation, on obtiendra un algorithme de programmation dynamique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problème d'optimisation à résoudre\n",
    "\n",
    "On se donne $M\\in\\mathbb{N}^*$ la taille de ligne, et un nombre $N\\in\\mathbb{N}^*$ objets, de longueurs $l_k \\in [1,\\dots,M]$.\n",
    "On souhaite minimiser le coût suivant, qui dépend de :\n",
    "\n",
    "- $L$ nombre de ligne,\n",
    "- $\\forall x \\in{1,\\dots,L-1}, \\ell_x$ indique l'indice de fin des mots présents en ligne $x$. Avec $\\ell_0 = 0$ pour indiquer une ligne 0 vide.\n",
    "\n",
    "$$\n",
    "    \\min_{\n",
    "            L\\in\\{1,\\dots,M\\}, \\\\\n",
    "            \\ell_1,\\dots,\\ell_{L-1}\\in\\{1,\\dots,N\\},\\\\\n",
    "            \\forall x\\in\\{1,\\dots,L-1\\}, \\ell_{x+1} \\geq \\ell_x + 1,\n",
    "        }\n",
    "        \\sum_{x=1}^{L-1}\n",
    "        (M - \\ell_{x+1} + \\ell_x - \\sum_{k=\\ell_x}^{\\ell_{x+1}} l_k)^3\n",
    "$$\n",
    "\n",
    "- On ne compte pas les espaces de la dernière ligne, d'où le L-1 dans la somme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Relation de récurrence\n",
    "\n",
    "**Initialisation :**\n",
    "S'il n'y a qu'un seul mot, la solution est triviale : on le place sur la première ligne, et on a terminé.\n",
    "\n",
    "**Hérédité :**\n",
    "On considère le premier mot $l_1$ et le deuxième mot $l_2$.\n",
    "Le coût de la solution optimale est le minimum des coûts des deux solutions optimales aux sous-problèmes suivants (de taille strictement plus petite) :\n",
    "\n",
    "1. on place les deux premiers mots ensemble, et on remplace donc $l_1,l_2$ par $l_1' := l_1 + l_2 + 1$, et la suite des mots est juste décalée : $l_k' := l_{k+1}$. Ce cas a $N-1$ mots ;\n",
    "2. on place le premier mot sur sa propre ligne (cas de base), et on résound avec les mots restants : $l_k' := l_{k+1}$. Ce cas a aussi $1$ et $N-1$ mots sur les deux sous-problèmes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implémentation naïve par mémoïsation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T11:51:11.619820Z",
     "start_time": "2021-02-04T11:51:11.612586Z"
    }
   },
   "outputs": [],
   "source": [
    "from typing import List, Tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T11:50:36.188539Z",
     "start_time": "2021-02-04T11:50:36.181404Z"
    }
   },
   "outputs": [],
   "source": [
    "from functools import lru_cache as memoize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:24:14.875085Z",
     "start_time": "2021-02-04T13:24:14.865125Z"
    }
   },
   "outputs": [],
   "source": [
    "couts = {\n",
    "    \"lineaire\": lambda i: i,\n",
    "    \"quadratique\": lambda i: i**2,\n",
    "    \"cubique\": lambda i: i**3,\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:37:35.928579Z",
     "start_time": "2021-02-04T13:37:35.904777Z"
    }
   },
   "outputs": [],
   "source": [
    "@memoize(maxsize=None)\n",
    "def mise_en_page_paragraphe(\n",
    "        longueur_max:int,\n",
    "        mots: Tuple[str],\n",
    "        choix_cout: str=\"cubique\",\n",
    "    ) -> List[List[str]]:\n",
    "    print(f\"Longueur maximum de la ligne = {longueur_max}\")\n",
    "    mots = list(mots)\n",
    "    print(f\"Longueur des mots = {mots}\")\n",
    "    \n",
    "    assert len(mots) > 0\n",
    "    if len(mots) == 1:\n",
    "        return [ [mots[0]] ]\n",
    "    \n",
    "    else:\n",
    "        cout = couts[choix_cout]\n",
    "        \n",
    "        # première possibilité, on regroupe les deux premiers mots ensemble\n",
    "        mots1 = [mots[0] + \" \" + mots[1]] + mots[2:]\n",
    "        cout1 = float('+inf')\n",
    "        if len(mots1[0]) <= longueur_max:\n",
    "            solution1 = mise_en_page_paragraphe(longueur_max, tuple(mots1))\n",
    "            cout1 = cout_paragraphes(solution1, cout)\n",
    "        \n",
    "        # deuxième possibilité, on place mots[0] tout seul, et on résoud les autres mots\n",
    "        sous_solution2 = mise_en_page_paragraphe(longueur_max, tuple(mots[1:]))\n",
    "        morceau_gauche2 = [ mots[0] ] + [\" \"] * (longueur_max - len(mots[0]))\n",
    "        solution2 = [ morceau_gauche2 ] + sous_solution2\n",
    "        cout2 = cout_paragraphes(solution2, cout)\n",
    "\n",
    "        if cout1 < cout2:\n",
    "            recombinaison_1 = []\n",
    "            for ligne in solution1:\n",
    "                mots_ici = \"\".join(ligne).split(\" \")\n",
    "                ligne_ici = [ mots_ici[0] ]\n",
    "                for mot in mots_ici[1:]:\n",
    "                    if mot:\n",
    "                        ligne_ici += [\" \", mot] \n",
    "                ligne_ici += [\" \"] * (longueur_max - longueur_ligne(ligne_ici))\n",
    "                recombinaison_1.append(ligne_ici)\n",
    "            return recombinaison_1\n",
    "        else:\n",
    "            recombinaison_2 = solution2\n",
    "            return recombinaison_2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exemples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:39:24.355620Z",
     "start_time": "2021-02-04T13:39:24.349805Z"
    }
   },
   "outputs": [],
   "source": [
    "longueur_max = len(\"AA AA AA\")\n",
    "\n",
    "mots = [\"AA\", \"AA\", \"AA\", \"B\"]\n",
    "mots = tuple(mots)  # pour le rendre Hashable pour le @memoize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions cela :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:39:25.009903Z",
     "start_time": "2021-02-04T13:39:24.997780Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA', 'AA', 'AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA AA', 'AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA AA AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA', 'AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA AA', 'B']\n",
      "Longueur maximum de la ligne = 8\n",
      "Longueur des mots = ['AA AA B']\n"
     ]
    }
   ],
   "source": [
    "paragraphes = mise_en_page_paragraphe(longueur_max, mots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:39:39.058032Z",
     "start_time": "2021-02-04T13:39:39.049872Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA      ;\n",
      "AA AA B ;\n",
      "- Nombre d'espaces en fin de lignes = 7\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 37\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 217\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Peut-on retrouver la solution suivante, qui avait été calculée à la main ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:13.318117Z",
     "start_time": "2021-02-04T13:42:13.197826Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AA AA AA AA AA AA B                    ;\r\n",
      "AA AA AA AA AA AA B                    ;\r\n"
     ]
    }
   ],
   "source": [
    "cat /tmp/test_nongreedy_optimal.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:17.810459Z",
     "start_time": "2021-02-04T13:42:17.803151Z"
    }
   },
   "outputs": [],
   "source": [
    "longueur_max = len(\"AA AA AA AA AA AA B                   \")\n",
    "\n",
    "mots = ([\"AA\"]*6 + [\"B\"]*1) * 2\n",
    "mots = tuple(mots)  # pour le rendre Hashable pour le @memoize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions cela :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:27.350655Z",
     "start_time": "2021-02-04T13:42:27.341729Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longueur maximum de la ligne = 38\n",
      "Longueur des mots = (2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1)\n"
     ]
    }
   ],
   "source": [
    "paragraphes = mise_en_page_paragraphe_gloutonne(longueur_max, mots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:28.691726Z",
     "start_time": "2021-02-04T13:42:28.683281Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA AA AA AA AA AA B AA AA AA AA AA AA ;\n",
      "B                                     ;\n",
      "- Nombre d'espaces en fin de lignes = 38\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 1370\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 50654\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et pour la solution dynamique :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:30.867982Z",
     "start_time": "2021-02-04T13:42:30.861229Z"
    }
   },
   "outputs": [],
   "source": [
    "paragraphes = mise_en_page_paragraphe(longueur_max, mots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:42:31.235309Z",
     "start_time": "2021-02-04T13:42:31.229793Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA AA AA AA AA AA B                   ;\n",
      "AA AA AA AA AA AA B                   ;\n",
      "- Nombre d'espaces en fin de lignes = 38\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 722\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 13718\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Question 3.\n",
    "\n",
    "**3. Supposons que pour la fonction de coût à minimiser, on ait simplement choisi la somme des nombres de caractères d’espacement présents à la fin de chaque ligne. Est-ce que l’on peut faire mieux en complexité que pour la question ?**\n",
    "\n",
    "Oui la solution gourmande, qui est donc au plus linéaire en temps et demande une mémoire de travail supplémentaire constante (ou bornée par la taille du plus long mot, selon de savoir si `len(mot)` est en $O(1)$ ou en $O(|\\text{mot}|)$), sera optimale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Question 4. Pourquoi un coût cubique et pas linéaire ?\n",
    "\n",
    "**4. *(Plus informel)* Qu’est-ce qui à votre avis peut justifier le choix de prendre les cubes plutôt quesimplement les nombres de caractères d’espacement en fin de ligne ?**\n",
    "\n",
    "Si le coût est linéaire, alors la solution gourmande sera optimale (ou en tous cas une approximation à facteur constant).\n",
    "Mais c'est aussi que l'affichage ne fera pas de différence entre les deux exemples ci dessous, alors que l'on est clairement plus satisfait du rendu visuel du deuxième, qui équilibre mieux les deux lignes.\n",
    "\n",
    "(*je ne suis pas trop sûr de tout ça*)\n",
    "\n",
    "TODO mieux expliquer !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut vérifier la solution trouvée avec un coût carré et pas cubique :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:44:44.265260Z",
     "start_time": "2021-02-04T13:44:44.261064Z"
    }
   },
   "outputs": [],
   "source": [
    "paragraphes = mise_en_page_paragraphe(longueur_max, mots, choix_cout=\"quadratique\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 293,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-02-04T13:44:44.594181Z",
     "start_time": "2021-02-04T13:44:44.589626Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Mise en page finale d'un texte de 2 lignes \n",
      "AA AA AA AA AA AA B                   ;\n",
      "AA AA AA AA AA AA B                   ;\n",
      "- Nombre d'espaces en fin de lignes = 38\n",
      "- Somme des carrés des nombres d'espaces en fin de lignes = 722\n",
      "- Somme des cubes des nombres d'espaces en fin de lignes = 13718\n"
     ]
    }
   ],
   "source": [
    "print_paragraphes(paragraphes)\n",
    "print_couts(paragraphes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sur cet exemple, on obtient exactement la même solution.\n",
    "\n",
    "Mais je pense qu'on peut trouver des exemples où la solution avec un coût cubique est différente de celle avec un coût quadratique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "Et si vous cherchiez à résoudre ça dans votre langage de programmation favori ?\n",
    "En Python ou en OCaml, cela ne devrait pas être trop difficile."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table de matières",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}