TP10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "baa6eafe",
   "metadata": {},
   "source": [
    "# ITC - MPSI\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "476ef0ef",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "abb28f914528f7de96e78f9e67fd6a5f",
     "grade": false,
     "grade_id": "cell-54d24854840b16be",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# TP10 : Compréhension de listes\n",
    "On a déjà vu comment écrire une liste _in extenso_ (exemple : `[1,2,3]`) et comment ajouter un élément à une liste avec `append`. Nous explorons ici une autre méthode de construction de liste appelée _compréhension de liste_. Cette méthode consiste à partir d'une liste existante (ou d'une suite d'éléments donnée sous une autre forme, comme on le verra), et à déduire, à partir des éléments de cette liste, les éléments de la nouvelle liste.\n",
    "\n",
    "\n",
    "Supposons qu'on dispose d'une liste d'entiers `L` et on veut obtenir une nouvelle liste qui contient les doubles des éléments de `L`. Avec ce que vous connaissez pour l'instant, vous devez écrire:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b83722ca",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "00bd69b28c29794dafc11ebdaaa14a56",
     "grade": false,
     "grade_id": "cell-8dbf68ac4ff0fa26",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [23, -1, 5, 92, -543, 32, 57] #exemple de liste pour les tests\n",
    "doubleL = []\n",
    "for i in L:\n",
    "    doubleL.append(2*i)\n",
    "doubleL"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f72a8443",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "685e13ecc39b521d770959ac63d42e84",
     "grade": false,
     "grade_id": "cell-ba31677b9a769d4c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "En fait, on peut faire nettement plus court:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d882fe79",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "67add397936f238ad6167ad51d8b795a",
     "grade": false,
     "grade_id": "cell-da2cd5cff7c41cec",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "L = [23, -1, 5, 92, -543, 32, 57] #exemple de liste pour les tests\n",
    "[ 2*i for i in L ]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3802e4e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f9a11710c9e485a35a505a649e39d8ae",
     "grade": false,
     "grade_id": "cell-6677ffff348b161d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Cette opération\n",
    "```python\n",
    "[ e(x) for x in L ]\n",
    "```\n",
    "s'appelle une _compréhension de liste_ (traduction horrible de l'anglais, mais c'est le terme effectivement utilisé).\n",
    "\n",
    "Elle signifie qu'on parcourt les éléments de `L` (`for x in L`) et que pour chaque élément on évalue une certaine expression (`e(x)`). On obtient donc une liste de même longueur que `L` et telle que la case `i` de cette liste contient l'évaluation de l'expression `e(L[i])`.\n",
    "\n",
    "On peut appliquer la même opération à tout type de `python` qui est _itérable_ (c'est-à-dire sur lequel on peut faire un `for`); on obtient à chaque fois une nouvelle liste.\n",
    "\n",
    "Exemple:\n",
    "\n",
    "```python\n",
    "[ i**3 for i in range(5) ]   # donne [0, 1, 8, 27, 64]\n",
    "[ i*2 for i in 'bonjour' ]   # donne ['bb', 'oo', 'nn', 'jj', 'oo', 'uu', 'rr']\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05e884cb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "18dcc4bcf44d425f86b38a0f5b716824",
     "grade": false,
     "grade_id": "cell-38c40421fc4e2a57",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 1 : Passage en majuscule\n",
    "La fonction `str.upper` renvoie une copie de son argument (une chaîne de caractères), en passant toutes les lettres en majuscules (il s'agit en fait de la fonction `upper` de la classe `str`, mais la notion de classe est hors programme).\n",
    "\n",
    "Écrire et documenter une fonction `upper` qui prend en argument une liste de chaînes de caractères et renvoie une nouvelle liste avec une copie de ces chaînes en majuscules, en utilisant une compréhension de liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe109d48",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "92fc4602c13604774569802fcf37521c",
     "grade": false,
     "grade_id": "cell-75e74172cad64643",
     "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": "de183def",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "18104bfb2f5482c7cd647d44a674d1f3",
     "grade": true,
     "grade_id": "cell-028a8b1c5c280af8",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(upper([]) == [])\n",
    "assert(upper(['toto', '', '123', 'titi']) == ['TOTO', '', '123', 'TITI'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2f2ac48",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "7105ac8bf93fbc68d4d0e1e6848dd245",
     "grade": false,
     "grade_id": "cell-3160727a73bfe63c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 2 : Nombre de caractères\n",
    "Écrire et documenter une fonction `longueur` qui prend en argument une liste de chaînes de caractères et renvoie le nombre **total** de caractères dans l'ensemble de ces chaînes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b5fc041",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "174a6c06c2a42e4a6bdcd18929c41f90",
     "grade": false,
     "grade_id": "cell-8696f3bb60bd00ca",
     "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": "3445f4a3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "0335580fead45c53f0111b3dee1cdf0d",
     "grade": true,
     "grade_id": "cell-7c266bcd28f0987d",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(longueur([]) == 0)\n",
    "assert(longueur(['toto', '', '123', 'titi']) == 11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e90405b",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "34eedc74f32d5cd9495b4f502e80e34a",
     "grade": false,
     "grade_id": "cell-04b9b618adb1cd65",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 3 : Compréhensions imbriquées.\n",
    "\n",
    "On peut imbriquer des compréhensions car l'expression calculée peut elle-même être calculée par compréhension, exemple:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98c98cb3",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8f75322786faf4799b0fdb2b9bde3c4f",
     "grade": false,
     "grade_id": "cell-e801bfe8a44c50f6",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "[ ['a'*i+'b'*j for j in range(i)] for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a10b664",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "e92761cc63e598c1fe34e74523d65f96",
     "grade": false,
     "grade_id": "cell-04b9b618adb1cd66",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Écrire et documenter une fonction `puissances` qui prend en argument une liste d'entiers `L` et un entier `n` et renvoie une liste de listes telle que la liste située en case `i` contienne les puissance `i`e des éléments de la liste d'origine, pour `i` allant de `0` à `n-1`. (Aucune contrainte sur la complexité, je veux juste que vous utilisiez des compréhensions de listes imbriquées.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8d8acd2",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e73d1f3451dc318ccade06e296bae3f3",
     "grade": false,
     "grade_id": "cell-799933c2fc8c8aa5",
     "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": "c1b03c3e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "5813dd1739ab0c2077f353843b46e5e4",
     "grade": true,
     "grade_id": "cell-9eff47d70a58d8b9",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "assert(puissances([], 5) == [[], [], [], [], []])\n",
    "assert(puissances([-1], 5) == [[1], [-1], [1], [-1], [1]])\n",
    "assert(puissances([-1, 7, 2, 3], 5) == [[1, 1, 1, 1],\n",
    " [-1, 7, 2, 3],\n",
    " [1, 49, 4, 9],\n",
    " [-1, 343, 8, 27],\n",
    " [1, 2401, 16, 81]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc81d5f0",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "ef5f2a195a34bfdd066f2f70550ac0d3",
     "grade": false,
     "grade_id": "cell-1daf42819117f4aa",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 4 : Intersection d'images\n",
    "Dans cet exercice, nous représentons une image par une liste bidimensionnelle de booléens: `False` représente la couleur blanc, et `True` la couleur noir.\n",
    "\n",
    "Un petit exemple avec une fonction d'affichage:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "37e93d2f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8d26f5d22c8618a2fefe76e25af351a7",
     "grade": false,
     "grade_id": "cell-58bb32167128ff75",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def affiche(img):\n",
    "    for ligne in img:\n",
    "        for pixel in ligne:\n",
    "            print(u'\\u2B1B' if pixel else u'\\u2B1C', end='')\n",
    "        print()\n",
    "                \n",
    "affiche([[True, False, True, False], [True, True, False, True], [False, False, True, True]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62d92c51",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5aff8e82b8462b6b55920b01a801cf8f",
     "grade": false,
     "grade_id": "cell-1daf42819117f4ab",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Écrire et documenter une fonction `intersection` qui prend en argument deux listes de listes de mêmes dimensions et rectangulaires contenant des `True` et des `False` et renvoie une liste de listes de mêmes dimensions dont une case vaut `True` si et seulement si les cases de mêmes coordonnées des listes fournies en argument valent toutes les deux `True`. Pas de boucle, uniquement des compréhensions de listes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84716e65",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "6743ca9b7bbeb63809bb69d397d39e53",
     "grade": false,
     "grade_id": "cell-439ac1387fe249c6",
     "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": "53e65b63",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9054eb6ef67118eb5adb63e89e5c8524",
     "grade": true,
     "grade_id": "cell-2e6d1a7d303e228d",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "img1 = [[True, False, True, False], [True, True, False, True], [False, False, True, True]]\n",
    "img2 = [ [True] * 4 for i in range(3)]\n",
    "img3 = intersection(img1, img2)\n",
    "assert(img3 == img1)\n",
    "\n",
    "img2 = [ [False] * 4 for i in range(3)]\n",
    "img3 = intersection(img1, img2)\n",
    "assert(img3 == img2)\n",
    "\n",
    "img2 = [ [True]*4, [False]*4, [True]*4 ]\n",
    "img3 = intersection(img1, img2)\n",
    "assert(img3 == [[True, False, True, False], [False, False, False, False], [False, False, True, True]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20bb00ba",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a7e0b73826398a78421be198ad565297",
     "grade": false,
     "grade_id": "cell-69debf01c6c2f55f",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Exercice 4 : Liste de listes\n",
    "On a parfois besoin de créer une liste de listes imbriquées d'une certaine taille, par exemple pour travailler sur une image. Une première idée (mauvaise) consiste à faire\n",
    "```python\n",
    "image = [ [ 0 ] * 10 ] * 15\n",
    "```\n",
    "Cette idée est mauvaise à cause de ce qui se passe en mémoire:\n",
    "![](alloc.png)\n",
    "\n",
    "On voit que la liste imbriquée (`[0] * 10`) est partagée par toutes les cases de `L`, ainsi on n'a pas vraiment 150 données, mais une suite de 10 données référencée 15 fois. La raison de cette situation est simple: on a vu que la valeur d'une liste n'est pas le contenu de ses cases, mais l'adresse où se trouve cette liste en mémoire, le `*15` externe recopie 15 fois cette valeur.\n",
    "\n",
    "Il faudrait en fait fabriquer une nouvelle liste de 10 cases pour chaque case de `image`. Ceci peut se faire par compréhension de liste :\n",
    "```python\n",
    "image = [ [ 0 ] * 10 for i in range(15) ]\n",
    "```\n",
    "On se retrouve alors avec une situation tout à fait différente en mémoire :\n",
    "![](alloc2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac7943ca",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5ad10379369eb1ad80573ea65066995e",
     "grade": false,
     "grade_id": "cell-c3c635a4316c0b6d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "On considère des représentations d'images au même format que dans l'exercice précédent (listes de listes de booléens). Écrire et documenter une fonction `mega_image` qui prend une représentation d'image dans ce format et  entiers `larg` et `haut` strictement positifs et fabrique la représentation d'une image qui correspond à la juxtaposition de l'image d'origine, à la manière d'Andy Warhol, mais sans modifier la couleur (dans cet exemple, les valeurs respectives de `larg` et `haut` seraient 5 et 3):\n",
    "![](https://www.cnewyork.net/wp-content/uploads/resizefly/2018/11/warhol-marilyn-monroe-2-1200x750-696x435@1.jpg)\n",
    "\n",
    "À cette fin, votre fonction commencera par créer une liste de listes aux bonnes dimensions, puis modifiera les contenus des cases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95741612",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "2c1821df25b50c4e12fa34a2fe4c873f",
     "grade": false,
     "grade_id": "cell-e273d1d6e9327daf",
     "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": "127b7f77",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "aebb47922b1a337695a3311361350cd3",
     "grade": false,
     "grade_id": "cell-4be02a760dc2c9f0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "img = [[True, False, True, False], [True, True, False, True], [False, False, True, True]]\n",
    "affiche(mega_image(img, 2, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bff5f6cd",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a19b2680e99f9bdcba6b80d8428934a9",
     "grade": true,
     "grade_id": "cell-ec93bafdd6510267",
     "locked": true,
     "points": 2,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "img = [[True, False, True, False], [True, True, False, True], [False, False, True, True]]\n",
    "assert(mega_image(img, 2, 3) == [[True, False, True, False, True, False, True, False],\n",
    " [True, True, False, True, True, True, False, True],\n",
    " [False, False, True, True, False, False, True, True],\n",
    " [True, False, True, False, True, False, True, False],\n",
    " [True, True, False, True, True, True, False, True],\n",
    " [False, False, True, True, False, False, True, True],\n",
    " [True, False, True, False, True, False, True, False],\n",
    " [True, True, False, True, True, True, False, True],\n",
    " [False, False, True, True, False, False, True, True]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43f1d04c",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "96d467ae1afa629c484d0c3767a6e22c",
     "grade": false,
     "grade_id": "cell-c011cf93a16a679a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "<div class=\"alert alert-success\">\n",
    "    <h2>Les points à retenir</h2>\n",
    "    \n",
    "* le principe de la compréhension de liste\n",
    "* il n'est pas prudent de créer des listes multi-dimensionnelles en multipliant des listes de dimension inférieure\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
}