TP6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5f490edd",
   "metadata": {},
   "source": [
    "# ITC - MPSI\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f6bfecc",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "76445bf801e61f6730e89c9bb09c4f95",
     "grade": false,
     "grade_id": "cell-9522cce5160cdb0f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# TP6 : Récursivité et plongée dans la nature des listes\n",
    "On a vu dans le TP5 un exemple de fonction qui s'appelle elle-même. C'est ce qu'on appelle une fonction _récursive_.\n",
    "\n",
    "La démarche quand on implémente une fonction récursive est très proche de la démarche lors d'une démonstration par récurrence:\n",
    "* on sait résoudre le problème pour le cas de base ou pour des cas de base,\n",
    "* on suppose qu'on sait le faire à un certain rang ou jusqu'à un certain rang, et alors on le résoud pour le rang suivant en se ramenant à des instances plus petites du même problème."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86edb354",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f39bc6025ca5b535b2935088d2ddfb4b",
     "grade": false,
     "grade_id": "cell-6c61de1cb943bc35",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "#### Exemple : de combien de façon peut-on monter un escalier à $n$ marches ?\n",
    "Supposons qu'on puisse monter les marches soit une à la fois, soit deux à la fois et qu'on se trouve devant un escalier comportant $n$ marches, comment calculer le nombre de façons de monter cet escalier ? Notons $F_n$ ce nombre.\n",
    "\n",
    "**case de base** : \n",
    "* si $n=0$, il y a une seule façon de monter l'escalier : on reste là où on est\n",
    "* si $n=1$, il y a une seule façon de monter l'escalier : on franchit l'unique marche\n",
    "\n",
    "**héréditée** : si on suppose qu'on sait compter le nombre de façons de monter un escalier ayant au plus $n$ marches pour un certain $n\\geq 1$, alors pour un escalier ayant $n+1$ marche :\n",
    "* soit on commence par franchir un seule marche et on se retrouve devant un escalier de $n$, on a donc $F_n$ façons de franchir les marches restantes,\n",
    "* soit on commence par enjamber deux marches d'un coup et on se retrouve devant un escalier de $n-1$ marches, on a donc $F_{n+1}$ façons de franchir les marches restantes."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f799159",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "1658f76eb695cd1379257fc4ec4ff391",
     "grade": false,
     "grade_id": "cell-8e5a5f80f7dd8f06",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "La fonction associée est donc :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6b5d1fe",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "78213ab3c03a1c3900d535eb669e9759",
     "grade": false,
     "grade_id": "cell-b8845525eb720e86",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "\"\"\"n : un entier positif ou nul qui représente le nombre de marches d'un escalier\n",
    "sortie : le nombre de façons de monter l'escalier avec des pas d'une ou deux marches\"\"\"\n",
    "def montee_escaliers(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    return montee_escaliersiers(n-1) + montee_escaliers(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e5c5244",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b18d625fba80813316ea0734a2044775",
     "grade": false,
     "grade_id": "cell-d89d4edd8aa836f5",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Si on n'a pas de cas de base on risque de faire des appels récursifs à l'infini, et comme la mémoire du processus n'est pas illimitée, on risque un débordement de pile.\n",
    "\n",
    "Vous pouvez regarder un exemple de débordement de pile sur python tutor (ici embarqué dans le notebook) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8211d45",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "cc2204a5408892592448b08cbd610a82",
     "grade": false,
     "grade_id": "cell-8dece42c7879839a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "IFrame('https://pythontutor.com/iframe-embed.html#code=def%20f%28%29%20%3A%0A%20%20%20%20f%28%29%0A%20%20%20%20%0Af%28%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width=980, height=350)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d08fce36",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "801057006efc23ae71345bf7562d33a2",
     "grade": false,
     "grade_id": "cell-af5bd1c193340a8a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 1 : Calcul récursif de puissance\n",
    "En remarquant que $x^{2k}=(x^k)^2$ et $x^{2k+1}=x(x^k)^2$, écrire et documenter une fonction **récursive** `puissance` qui permet de calculer une puissance entière positive d'un entier (sans utiliser l'opérateur python `**`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4d98d5e",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d9de11ff255bedc45287a9a5bc91c872",
     "grade": false,
     "grade_id": "cell-757a46694f22026b",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "00e206c7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1a3ade8cd86e68a39b614351ac2aa98f",
     "grade": true,
     "grade_id": "cell-af35c7281e8ce885",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(puissance(5, 0) == 1)\n",
    "assert(puissance(2, 12) == 2**12)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da728586",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0b8f0ce95529c8f6fefb158be6a4ad66",
     "grade": false,
     "grade_id": "cell-7690596aeca0536f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## C'est quoi la valeur d'une liste?\n",
    "On a vu qu'une variable sert à désigner une valeur. Ainsi, après ces instructions :\n",
    "```python\n",
    "p = 2.5\n",
    "q = p\n",
    "```\n",
    "les variables `p` et `q` désignent la même valeur, comme on peut le voir ici :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "364a71c9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a8e57436150d4b77cc7e2499c50fb030",
     "grade": false,
     "grade_id": "cell-ec098de5a8aa3c41",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "IFrame('https://pythontutor.com/visualize.html#code=p%20%3D%202.5%0Aq%20%3D%20p&cumulative=false&curInstr=0&heapPrimitives=true&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width=980, height=350)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ef00054",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "b915661a519195eb5e36b591642813c3",
     "grade": false,
     "grade_id": "cell-786549f45186da40",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Si on change par la suite la valeur désignée par `p`, comme ici :\n",
    "```python\n",
    "p = 2.5\n",
    "q = p\n",
    "p = 1.\n",
    "```\n",
    "on voit que `q` continue à désigner la même valeur, et c'est `p` qui change de cible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c8250cf",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bf4d4570f895a9b4c88658fbcef9727f",
     "grade": false,
     "grade_id": "cell-771f747c626823e7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "IFrame('https://pythontutor.com/visualize.html#code=p%20%3D%202.5%0Aq%20%3D%20p%0Ap%20%3D%201.&cumulative=false&curInstr=0&heapPrimitives=true&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false', width=980, height=350)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9557a8bb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "0c69ee2aa48d4e9f89b9925942d1f34b",
     "grade": false,
     "grade_id": "cell-370ad44ab4352b9c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Que se passe-t-il quand une variable désigne une liste ?\n",
    "```python\n",
    "L = [1, 2, 3]\n",
    "M = L\n",
    "N = L\n",
    "N = [1, 2]\n",
    "M[1] = 'a'\n",
    "```\n",
    "Regardons graphiquement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba1493aa",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "bcf253660e02f50b71c5b5afc86f6adc",
     "grade": false,
     "grade_id": "cell-c8e1ea7a58d3337b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "IFrame(\"https://pythontutor.com/visualize.html#code=L%20%3D%20%5B1,%202,%203%5D%0AM%20%3D%20L%0AN%20%3D%20L%0AN%20%3D%20%5B1,%202%5D%0AM%5B1%5D%20%3D%20'a'&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\", width=980, height=350)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f14205bc",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "80f1bf744cb76a51897cd0e82f68c522",
     "grade": false,
     "grade_id": "cell-7b53cb24219617f8",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Si on modifie la liste désignée par `N`, cela n'a pas de conséquence sur la liste désignée par `L`, alors que si on modifie une case **dans la liste** désignée par `M`, la liste désignée par `L` étant la même, ce changement aura des conséquences.\n",
    "\n",
    "Ainsi si dans une fonction récursive on transmet la même liste d'appel en appel, les modifications apportées à cette liste à chaque appel ont des répercussions pour tous les appels en cours.\n",
    "\n",
    "Regardons par exemple le code suivant:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb53f6b5",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "af7bda879c877dec9ffbcd2101c33aa8",
     "grade": false,
     "grade_id": "cell-03ecfae3048be169",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "from IPython.display import IFrame\n",
    "IFrame(\"https://pythontutor.com/visualize.html#code=%22%22%22L%20%3A%20liste%20d'entiers%0An%20%3A%20entier%20inf%C3%A9rieur%20%C3%A0%20len%28L%29%0Asortie%20%3A%20tous%20les%20%C3%A9l%C3%A9ments%20impairs%20de%20L%20d'indice%20au%20moins%20n%20on%20%C3%A9t%C3%A9%20mis%20%C3%A0%20z%C3%A9ro%22%22%22%0Adef%20annuler_les_impairs%28L,%20n%29%3A%0A%20%20%20%20if%20L%5Bn%5D%252%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20L%5Bn%5D%20%3D%200%0A%20%20%20%20if%20n%2B1%20%3C%20len%28L%29%3A%0A%20%20%20%20%20%20%20%20annuler_les_impairs%28L,%20n%2B1%29%0A%0AL%20%3D%20%5B1,%202,%203,%204%20,%205,%206,%207%5D%0Aannuler_les_impairs%28L,%200%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false\", width=980, height=550)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e85df20e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "caef2ae60bd7a4887363f4f489cd57d4",
     "grade": false,
     "grade_id": "cell-848e3a20d287e522",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 2 : Croissance\n",
    "Écrire et documenter une fonction **récursive** `fin_croissante` qui prend en argument une liste de nombres et un indice dans cette liste (sans avoir à le vérifier) et teste si les nombres de la liste sont dans l'ordre croissant (au sens large) à partir de l'indice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c341b7d2",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "19dd55ea4b378b8e2d6b83d0e9531919",
     "grade": false,
     "grade_id": "cell-db7072e3ef90dcda",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84446d59",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d819f5aa65ccb54c0bf67e48f6cf561c",
     "grade": true,
     "grade_id": "cell-b728248fe704c93f",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(fin_croissante([3, 3, 3, 2, 3, 4, 4], 3))\n",
    "assert(not fin_croissante([3, 3, 3, 2, 3, 4, 4], 2))\n",
    "assert(fin_croissante([1], 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9aae7e00",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ac37db7512e99583e03977772e10bc58",
     "grade": false,
     "grade_id": "cell-91a306afa57fa5c7",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 3 : Remplissage par diffusion 1D\n",
    "Le _remplissage par diffusion_ est un algorithme d'infographie qui permet de colorer tous les pixels d'une forme fermée d'une même couleur (sous `gimp`, pour ceux qui connaissent, cela correspond à l'icône du petit seau qui se renverse).\n",
    "\n",
    "Nous allons appliquer ce principe en dimension 1. On dispose d'un tableau d'entier, et d'une position dans ce tableau, et il s'agit de mettre à 0 toutes les cases ayant la même valeur que la case à la position donnée et atteignables en ne passant que par des cases qui ont cette même valeur.\n",
    "\n",
    "exemple :\n",
    "\n",
    "tableau de départ : $\\begin{array}{|c|c|c|c|c|c|c|c|} \\hline 2 & 3 & 1 & 1 & 1 & 2 & 2 & 1\\\\ \\hline\\end{array}$\n",
    ", position : 2\n",
    "\n",
    "tableau d'arrivée : $\\begin{array}{|c|c|c|c|c|c|c|c|} \\hline 2 & 3 & 0 & 0 & 0 & 2 & 2 & 1\\\\ \\hline\\end{array}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b88af16",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "65a19dbf99629764903a34b56b355178",
     "grade": false,
     "grade_id": "cell-f7f8667db074fb5f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Écrire et documenter une fonction **récursive** `remplissage1D` qui réalise cette opération."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66288744",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "aa0ea83c83dfb2da9c8eb633a76ab328",
     "grade": false,
     "grade_id": "cell-02d3806600ef2806",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3f164130",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d3287f9e9d5784bc3189fa556ba9b6fe",
     "grade": true,
     "grade_id": "cell-c348d1fac3d6b1a7",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tab = [2, 3, 1, 1, 1, 2, 2, 1]\n",
    "remplissage1D(tab, 2)\n",
    "assert(tab == [2, 3, 0, 0, 0, 2, 2, 1])\n",
    "\n",
    "remplissage1D(tab, 0)\n",
    "assert(tab == [0, 3, 0, 0, 0, 2, 2, 1])\n",
    "\n",
    "tab = [2, 3, 1, 1, 1, 2, 2, 1, 1, 1, 1]\n",
    "remplissage1D(tab, 8)\n",
    "assert(tab == [2, 3, 1, 1, 1, 2, 2, 0, 0, 0, 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8b6dcb4e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "135b712869d140445ec0f9618a76cbf9",
     "grade": true,
     "grade_id": "cell-c348d1fac3d6b1a8",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "tab = [2, 3, 1, 1, 1, 0, 0, 1, 1, 1, 1]\n",
    "remplissage1D(tab, 5)\n",
    "assert(tab == [2, 3, 1, 1, 1, 0, 0, 1, 1, 1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41af9cfa",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e56919e4922fe3d1061087288de8e41d",
     "grade": false,
     "grade_id": "cell-38c0916f775e0107",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Listes multi-dimensionnelles\n",
    "Jusqu'à présent, on a surtout utilisé des types numériques dans les cases des listes, mais on peut également utiliser une liste comme élément d'une liste.\n",
    "\n",
    "Par exemple :\n",
    "```python\n",
    "L = [ [1, 2, 3], [4, 5, 6] ]\n",
    "```\n",
    "`L[0]` désigne alors la liste de la case 0, soit la liste `[1, 2, 3]` et `L[1]` la liste de la case 1, soit `[4, 5, 6]`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8517acb6",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "9d8cdc66a67130bdf4eccd386ef1d550",
     "grade": false,
     "grade_id": "cell-c50b631be7540cba",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 4 : Rectangle\n",
    "Écrire et documenter une fonction `rectangle` qui prend en argument une liste de listes et vérifient que les listes de toutes les cases ont la même longueur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb2189b7",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5ba4c5572a35c78cdab0409efa54a531",
     "grade": false,
     "grade_id": "cell-891960d07a1e1dc2",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1cb60821",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2ad02e2a5c5a48fe895d3996144ba288",
     "grade": true,
     "grade_id": "cell-eab87d2449f077f4",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(rectangle([]))\n",
    "assert(rectangle([[], [], [], []]))\n",
    "assert(not rectangle([[], [], [], [1]]))\n",
    "assert(not rectangle([[1], [1], [1, 2], [5]]))\n",
    "assert(rectangle([[1], [2], [3], [4]]))\n",
    "assert(rectangle([[4, 5, -3, 6]]*10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5249527f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "65b1785b62833a94ec8caa93b23281fd",
     "grade": false,
     "grade_id": "cell-76c7b7a53d338c87",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exo 5 : Remplissage par diffusion 2D\n",
    "Le principe est le même en 2D qu'en 1D, mais chaque point a maintenant 4 voisins.\n",
    "\n",
    "Écrire et documenter une fonction **récursive** `remplissage2D` qui réalise cette opération : on lui donne une liste de listes d'entiers supposées toutes de la même longueur (sans avoir à le vérifier) et deux entiers représentant des coordonnées dans le tableau, et la fonction met à 0 toutes les cases ayant la même valeur que la case à la position donnée et atteignables en ne passant que par des cases qui ont cette même valeur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51da80f1",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0bbac164579c13d37d21607d6a58d69d",
     "grade": true,
     "grade_id": "cell-8bf52cadd9fe2603",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Écrire votre code ici\n",
    "raise NotImplementedError # effacer cette ligne une fois le code écrit"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "266a2e3b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8eae3b68ecc7144c46f53bee2fd9e0de",
     "grade": false,
     "grade_id": "cell-f209a18048716594",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Pour tester votre code, exécuter les trois cellules suivantes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80ac6820",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "44b2109bf7308e4159bc9c234423f5c1",
     "grade": false,
     "grade_id": "cell-4e0a82450a2de953",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import random\n",
    "from IPython.display import Image\n",
    "\n",
    "\"\"\"nom : nom d'un fichier\n",
    "image : liste de listes d'entiers positifs ou nuls\n",
    "couleurs : tableau de couleurs\n",
    "sortie : fichier image d'extension ppm créé et représentant l'image\"\"\"\n",
    "def creer_image(nom, image, couleurs = None):\n",
    "    nb_couleurs = max( [ max(ligne) for ligne in image ] )\n",
    "    if not couleurs:\n",
    "        couleurs = [ None ] * (nb_couleurs+1)\n",
    "        couleurs[0] = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))\n",
    "    with open(nom+'.ppm', 'w') as fichier:\n",
    "        fichier.write('P3\\n')\n",
    "        fichier.write(str(len(image[0])) + ' ' + str(len(image)) + '\\n')\n",
    "        fichier.write('256\\n')\n",
    "        for ligne in image:\n",
    "            for pixel in ligne:\n",
    "                if not couleurs[pixel]:\n",
    "                    couleurs[pixel] = (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))\n",
    "                fichier.write(str(couleurs[pixel][0]) + ' '\n",
    "                             + str(couleurs[pixel][1]) + ' '\n",
    "                             + str(couleurs[pixel][2]) + ' ')\n",
    "            fichier.write('\\n')\n",
    "    fichier.close()\n",
    "    return couleurs\n",
    "\n",
    "n = 15\n",
    "k = 30\n",
    "image = [ [1]*(k+2*n) for i in range(n) ]\n",
    "image.append( [1]*n+[2]*k+[1]*n )\n",
    "for i in range(2*n):\n",
    "    image.append( [1]*n + [2] + [1]*(k-2) + [2] + [1]*n )\n",
    "image.append( [1]*n+[2]*k+[1]*n )\n",
    "image.extend([ [1]*(k+2*n) for i in range(n) ])\n",
    "\n",
    "couleurs = creer_image('toto', image)\n",
    "\n",
    "!convert toto.ppm toto.png  # pas du python; crée un fichier d'extension png\n",
    "!rm toto.ppm                # pas du python; supprime le fichier d'extension ppm\n",
    "\n",
    "print(\"image d'origine :\")\n",
    "Image('toto.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ff06816",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "503fda557f6bc2e5f073870256dda904",
     "grade": false,
     "grade_id": "cell-4e0a82450a2de954",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "remplissage2D(image, len(image[0])//2, len(image)//2)\n",
    "creer_image('toto2', image, couleurs)\n",
    "\n",
    "!convert toto2.ppm toto2.png  # pas du python; crée un fichier d'extension png\n",
    "!rm toto2.ppm                 # pas du python; supprime le fichier d'extension ppm\n",
    "\n",
    "print(\"image remplie à partir du centre :\")\n",
    "Image('toto2.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "680423db",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ee4fb38c37fe46d40ea64bea20f75390",
     "grade": false,
     "grade_id": "cell-0e00cd93d72e32f3",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "n = 15\n",
    "k = 30\n",
    "image = [ [1]*(k+2*n) for i in range(n) ]\n",
    "image.append( [1]*n+[2]*k+[1]*n )\n",
    "for i in range(2*n):\n",
    "    image.append( [1]*n + [2] + [1]*(k-2) + [2] + [1]*n )\n",
    "image.append( [1]*n+[2]*k+[1]*n )\n",
    "image.extend([ [1]*(k+2*n) for i in range(n) ])\n",
    "\n",
    "remplissage2D(image, 0, 0)\n",
    "creer_image('toto3', image, couleurs)\n",
    "\n",
    "!convert toto3.ppm toto3.png  # pas du python; crée un fichier d'extension png\n",
    "!rm toto3.ppm                 # pas du python; supprime le fichier d'extension ppm\n",
    "\n",
    "print(\"image remplie à partir d'un coin :\")\n",
    "Image('toto3.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cbd2164d",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "d309e8de1961c179ada92843409225b1",
     "grade": false,
     "grade_id": "cell-d609705fbbee0ebc",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <h2>Les points à retenir</h2>\n",
    "    \n",
    "* structure d'une fonction récursive (cas de base + héréditée)\n",
    "* la valeur d'une liste est son adresse mémoire, pas la valeur de ses cases\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}