agreg/Plus long sous mot commun (python3).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Table-des-matières\" data-toc-modified-id=\"Table-des-matières-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Table des matières</a></div><div class=\"lev1 toc-item\"><a href=\"#1.-Agrégation-externe-de-mathématiques\" data-toc-modified-id=\"1.-Agrégation-externe-de-mathématiques-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>1. Agrégation externe de mathématiques</a></div><div class=\"lev2 toc-item\"><a href=\"#1.1-Leçon-orale,-option-informatique\" data-toc-modified-id=\"1.1-Leçon-orale,-option-informatique-21\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>1.1 Leçon orale, option informatique</a></div><div class=\"lev4 toc-item\"><a href=\"#Feedbacks?\" data-toc-modified-id=\"Feedbacks?-2101\"><span class=\"toc-item-num\">2.1.0.1&nbsp;&nbsp;</span>Feedbacks?</a></div><div class=\"lev1 toc-item\"><a href=\"#2.-Calcul-du-plus-long-sous-mot-commun\" data-toc-modified-id=\"2.-Calcul-du-plus-long-sous-mot-commun-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>2. Calcul du plus long sous mot commun</a></div><div class=\"lev3 toc-item\"><a href=\"#2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907.\" data-toc-modified-id=\"2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907.-301\"><span class=\"toc-item-num\">3.0.1&nbsp;&nbsp;</span>2.0.1 Implémentation d'un développement pour les leçons 906, 907.</a></div><div class=\"lev3 toc-item\"><a href=\"#2.0.2-Références-:\" data-toc-modified-id=\"2.0.2-Références-:-302\"><span class=\"toc-item-num\">3.0.2&nbsp;&nbsp;</span>2.0.2 Références :</a></div><div class=\"lev3 toc-item\"><a href=\"#2.0.3-Applications,-généralisations-:\" data-toc-modified-id=\"2.0.3-Applications,-généralisations-:-303\"><span class=\"toc-item-num\">3.0.3&nbsp;&nbsp;</span>2.0.3 Applications, généralisations :</a></div><div class=\"lev1 toc-item\"><a href=\"#3.-Algorithme-naïf-(exponentiel)\" data-toc-modified-id=\"3.-Algorithme-naïf-(exponentiel)-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>3. Algorithme naïf (exponentiel)</a></div><div class=\"lev2 toc-item\"><a href=\"#3.1-Détecter-si-$u$-est-sous-mot-de-$y$\" data-toc-modified-id=\"3.1-Détecter-si-$u$-est-sous-mot-de-$y$-41\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>3.1 Détecter si <span class=\"MathJax_Preview\" style=\"color: inherit;\"><span class=\"MJXp-math\" id=\"MJXp-Span-112\"><span class=\"MJXp-mi MJXp-italic\" id=\"MJXp-Span-113\">u</span></span></span><script type=\"math/tex\" id=\"MathJax-Element-19\">u</script> est sous mot de <span class=\"MathJax_Preview\" style=\"color: inherit;\"><span class=\"MJXp-math\" id=\"MJXp-Span-114\"><span class=\"MJXp-mi MJXp-italic\" id=\"MJXp-Span-115\">y</span></span></span><script type=\"math/tex\" id=\"MathJax-Element-20\">y</script></a></div><div class=\"lev2 toc-item\"><a href=\"#3.2-Trouver-un-sous-mot-de-longueur-k\" data-toc-modified-id=\"3.2-Trouver-un-sous-mot-de-longueur-k-42\"><span class=\"toc-item-num\">4.2&nbsp;&nbsp;</span>3.2 Trouver <em>un</em> sous-mot de longueur <code>k</code></a></div><div class=\"lev2 toc-item\"><a href=\"#3.3-Sous-mot-de-longueur-maximale-(version-naïve)\" data-toc-modified-id=\"3.3-Sous-mot-de-longueur-maximale-(version-naïve)-43\"><span class=\"toc-item-num\">4.3&nbsp;&nbsp;</span>3.3 Sous-mot de longueur maximale (version naïve)</a></div><div class=\"lev1 toc-item\"><a href=\"#4.-Méthode-gloutonne-(programmation-dynamique)\" data-toc-modified-id=\"4.-Méthode-gloutonne-(programmation-dynamique)-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>4. Méthode gloutonne (programmation dynamique)</a></div><div class=\"lev2 toc-item\"><a href=\"#4.1-Programmation-dynamique,-sans-optimisation-mémoire\" data-toc-modified-id=\"4.1-Programmation-dynamique,-sans-optimisation-mémoire-51\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>4.1 Programmation dynamique, sans optimisation mémoire</a></div><div class=\"lev2 toc-item\"><a href=\"#4.2-Utilisation-d'une-matrice-creuse\" data-toc-modified-id=\"4.2-Utilisation-d'une-matrice-creuse-52\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span>4.2 Utilisation d'une matrice <em>creuse</em></a></div><div class=\"lev3 toc-item\"><a href=\"#4.2.1-Version-condensée\" data-toc-modified-id=\"4.2.1-Version-condensée-521\"><span class=\"toc-item-num\">5.2.1&nbsp;&nbsp;</span>4.2.1 Version condensée</a></div><div class=\"lev1 toc-item\"><a href=\"#5.-Calcule-de-la-plus-longue-sous-séquence-commune\" data-toc-modified-id=\"5.-Calcule-de-la-plus-longue-sous-séquence-commune-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>5. Calcule de la plus longue sous-séquence commune</a></div><div class=\"lev2 toc-item\"><a href=\"#5.1-Vérifier-qu'une-sous-séquence-est-une-bonne-sous-séquence\" data-toc-modified-id=\"5.1-Vérifier-qu'une-sous-séquence-est-une-bonne-sous-séquence-61\"><span class=\"toc-item-num\">6.1&nbsp;&nbsp;</span>5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence</a></div><div class=\"lev2 toc-item\"><a href=\"#5.2-Algorithme-pour-la-plus-longue-sous-séquence\" data-toc-modified-id=\"5.2-Algorithme-pour-la-plus-longue-sous-séquence-62\"><span class=\"toc-item-num\">6.2&nbsp;&nbsp;</span>5.2 Algorithme pour la plus longue sous-séquence</a></div><div class=\"lev3 toc-item\"><a href=\"#5.2.1-Exemple,-venant-du-développement\" data-toc-modified-id=\"5.2.1-Exemple,-venant-du-développement-621\"><span class=\"toc-item-num\">6.2.1&nbsp;&nbsp;</span>5.2.1 Exemple, venant du développement</a></div><div class=\"lev3 toc-item\"><a href=\"#5.2.2-Autres-exemples\" data-toc-modified-id=\"5.2.2-Autres-exemples-622\"><span class=\"toc-item-num\">6.2.2&nbsp;&nbsp;</span>5.2.2 Autres exemples</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "b4d399ae-27e7-426f-a2ac-c79b5a6cb02f"
    }
   },
   "source": [
    "# Table des matières\n",
    "* [1. Agrégation externe de mathématiques](#1.-Agrégation-externe-de-mathématiques)\n",
    "\t* [1.1 Leçon orale, option informatique](#1.1-Leçon-orale,-option-informatique)\n",
    "* [2. Calcul du plus long sous mot commun](#2.-Calcul-du-plus-long-sous-mot-commun)\n",
    "\t* &nbsp;\n",
    "\t\t* [2.0.1 Implémentation d'un développement pour les leçons 906, 907.](#2.0.1-Implémentation-d'un-développement-pour-les-leçons-906,-907.)\n",
    "\t\t* [2.0.2 Références :](#2.0.2-Références-:)\n",
    "\t\t* [2.0.3 Applications, généralisations :](#2.0.3-Applications,-généralisations-:)\n",
    "* [3. Algorithme naïf (exponentiel)](#3.-Algorithme-naïf-%28exponentiel%29)\n",
    "\t* [3.1 Détecter si $u$ est sous mot de $y$](#3.1-Détecter-si-$u$-est-sous-mot-de-$y$)\n",
    "\t* [3.2 Trouver *un* sous-mot de longueur ``k``](#3.2-Trouver-*un*-sous-mot-de-longueur-k)\n",
    "\t* [3.3 Sous-mot de longueur maximale (version naïve)](#3.3-Sous-mot-de-longueur-maximale-%28version-naïve%29)\n",
    "* [4. Méthode gloutonne (programmation dynamique)](#4.-Méthode-gloutonne-%28programmation-dynamique%29)\n",
    "\t* [4.1 Programmation dynamique, sans optimisation mémoire](#4.1-Programmation-dynamique,-sans-optimisation-mémoire)\n",
    "\t* [4.2 Utilisation d'une matrice *creuse*](#4.2-Utilisation-d'une-matrice-*creuse*)\n",
    "\t\t* [4.2.1 Version condensée](#4.2.1-Version-condensée)\n",
    "* [5. Calcule de la plus longue sous-séquence commune](#5.-Calcule-de-la-plus-longue-sous-séquence-commune)\n",
    "\t* [5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence](#5.1-Vérifier-qu'une-sous-séquence-est-une-bonne-sous-séquence)\n",
    "\t* [5.2 Algorithme pour la plus longue sous-séquence](#5.2-Algorithme-pour-la-plus-longue-sous-séquence)\n",
    "\t\t* [5.2.1 Exemple, venant du développement](#5.2.1-Exemple,-venant-du-développement)\n",
    "\t\t* [5.2.2 Autres exemples](#5.2.2-Autres-exemples)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "8dbcdbe6-b5e4-4803-b5bf-d591a1c0c4c4"
    }
   },
   "source": [
    "# 1. Agrégation externe de mathématiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "5ec8bf14-57ad-4e1b-8b13-d7da42924760"
    }
   },
   "source": [
    "## 1.1 Leçon orale, option informatique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e8ba8fa2-6f98-4431-8222-c897d1145a15"
    }
   },
   "source": [
    "> - Ce [notebook Jupyter](http://jupyter.org/) est une implémentation d'un algorithme constituant un développement pour l'option informatique de l'agrégation externe de mathématiques.\n",
    "> - Il s'agit du calcul du [plus long sous mot commun](https://fr.wikipedia.org/wiki/Plus_longue_sous-séquence_commune).\n",
    "> - Cette implémentation (partielle) a été rédigée par [Lilian Besson](http://perso.crans.org/besson/) ([sur GitHub ?](https://github.com/Naereen/), [sur Bitbucket ?](https://bitbucket.org/lbesson)), et [est open-source](https://github.com/Naereen/notebooks/blob/master/agreg/Plus%20long%20sous%20mot%20commun%20%28python3%29.ipynb).\n",
    "\n",
    "> #### Feedbacks?\n",
    "> - Vous avez trouvé un bug ? → [Signalez-le moi svp !](https://github.com/Naereen/notebooks/issues/new), merci d'avance.\n",
    "> - Vous avez une question ? → [Posez la svp !](https://github.com/Naereen/ama.fr) [![Demandez moi n'importe quoi !](https://img.shields.io/badge/Demandez%20moi-n'%20importe%20quoi-1abc9c.svg)](https://GitHub.com/Naereen/ama.fr)\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "30fc4b21-e1d3-4823-b437-4e300f2f07b9"
    }
   },
   "source": [
    "# 2. Calcul du plus long sous mot commun"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7ccc0315-1973-4d63-849a-246a327f7e98"
    }
   },
   "source": [
    "### 2.0.1 Implémentation d'un développement pour les leçons 906, 907."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "bfb9ef9f-8bcf-4100-8c99-57bf8959c57b"
    }
   },
   "source": [
    "On présente ici un algorithme de programmation dynamique pour **le calcul du plus long sous mot commun** (attention, c'est différent de la plus longue sous séquence commune !).\n",
    "\n",
    "Étant donnés deux mots $X = x_1 \\dots x_m$ et $Y = y_1 \\dots y_n$ sur un alphabet $\\Sigma$, on cherche à savoir quel est le plus long sous-mot commun à $X$ et $Y$.\n",
    "Un sous-mot correspond à un morceau commun aux deux mots : on extraie de **façon consécutive** une sous-séquence de $x$ et $y$ et elles doivent être égales : $u = x_{i_0} \\dots x_{i_0 + k} = y_{j_0} \\dots y_{j_0 + k} = v$ !\n",
    "\n",
    "La solution naïve est d’énumérer tous les sous-mots de $X$, et de regarder ensuite s'ils sont aussi sous-mots de\n",
    "$Y$, mais cette solution est inefficace : il y a $\\mathcal{O}(2^m)$ sous-mots de X...\n",
    "\n",
    "L'objectif est donc d'obtenir un algorithme plus efficace, si possible polynomial en $m = |X|$ et $n = |Y|$ (il sera en $\\mathcal{O}(m n)$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "1d33ae35-b5e7-4ccc-8c63-39831848cbed"
    }
   },
   "source": [
    "### 2.0.2 Références :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "2e792d1e-c43e-486e-8edc-6ad23f73fa03"
    }
   },
   "source": [
    "- Bien traité dans [\"Cormen\", Ch15.4 p341](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=15671),\n",
    "- Esquissé dans [\"Aho, Hopcroft, Ullman\", Ch5.6 p192](https://catalogue.ens-cachan.fr/cgi-bin/koha/opac-detail.pl?biblionumber=35831),\n",
    "- [Dévéloppement tapé en PDF ici](http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "fe95c114-6e8b-498d-9c9a-41cb8d9208ce"
    }
   },
   "source": [
    "### 2.0.3 Applications, généralisations :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "78e99f8a-7548-4572-b1b2-f8bec7116db0"
    }
   },
   "source": [
    "- Un généralisation est le calcul de la plus longue sous-sequence commune, pour lequel on ne se restreint plus à extraire de façon consécutive (ca semble plus compliqué, mais le même algorithme permet de régler le problème avec la même complexité, en fait).\n",
    "- On peut citer en application la comparaison de chaînes d'ADN, mais aussi la commande ``diff`` des systèmes GNU/Linux.\n",
    "- Généralisation : aucune chance d'avoir un algorithme aussi efficace s'il s'agit de trouver le plus long sous mot commun à $K$ chaînes de caractères (et en fait, le probleme général est $\\mathcal{NP}$, en le nombre de chaînes, [comme expliqué ici (en anglais)](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Complexity)).\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "fdd83dc1-2853-4125-8090-947f35da5a5c"
    }
   },
   "source": [
    "# 3. Algorithme naïf (exponentiel)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "bd505a24-4f2d-4f14-9a90-126ad2c5c2ea"
    }
   },
   "source": [
    "On va d'abord montrer rapidement une implémentation simple de l'algorithme naïf, pour ensuite vérifier que l'algorithme plus complexe fonctionne aussi bien."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d9f646a4-f5b9-482b-aaf2-eaa055292db0"
    }
   },
   "source": [
    "## 3.1 Détecter si $u$ est sous mot de $y$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "42af5ecb-6024-4366-94ef-a3e32a6db894"
    }
   },
   "source": [
    "L'objectif de toutes les fonctions suivantes est de proscrire toute recopie de chaines (*slicing*, ``x[i:j]``), qui sont très couteuse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "nbpresent": {
     "id": "874d2766-f8ac-47c6-8315-fb5ff2c1016b"
    }
   },
   "outputs": [],
   "source": [
    "def indiceSousMotAux(u, n, k, y, m, i, delta=0):\n",
    "    \"\"\" Fonction tail-récursive qui trouve l'indice j tel que u[k:k+n] = y[i+j:i+j+n], ou -1 en cas d'échec.\"\"\"\n",
    "    # print(\"{}indiceSousMotAux(u = {}, n = {}, k = {}, y = {}, m = {}, i = {}, delta = {})\".format('  '*delta, u, n, k, y, m, i, delta))  # DEBUG\n",
    "    if n == 0:  # Mot vide, commun partout, par defaut on donne 0\n",
    "        return 0\n",
    "    else:       # Mot pas vide\n",
    "        if k >= len(u) or i >= m:  # On a cherché trop loin, échec\n",
    "            return -1         # -1 signifie échec\n",
    "        elif u[k] == y[i]:    # Lettre en commun\n",
    "            if delta == n - 1:    # On a fini, on a trouvé !\n",
    "                return i - n + 1  # i est l'indice de la derniere lettre ici\n",
    "            else:  # On continue de chercher, une lettre de moins\n",
    "                return indiceSousMotAux(u, n, k + 1, y, m, i + 1, delta=delta+1)\n",
    "        else:      # On recommence a chercher en i+1\n",
    "            return indiceSousMotAux(u, n, k - delta, y, m, i + 1)\n",
    "\n",
    "\n",
    "def indiceSousMot(u, y):\n",
    "    \"\"\" En O(|u|), trouve l'indice j tel que u = y[j:j+|u|], ou -1 en cas d'échec.\"\"\"\n",
    "    return indiceSousMotAux(u, len(u), 0, y, len(y), 0)\n",
    "\n",
    "\n",
    "def estSousMot(u, y):\n",
    "    \"\"\" Vérifie en O(|u|) si u est sous-mot de y.\"\"\"\n",
    "    return indiceSousMotAux(u, len(u), 0, y, len(y), 0) >= 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "77640a71-1cc5-47c9-ae52-940ec6c95024"
    }
   },
   "source": [
    "Quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbpresent": {
     "id": "69a559a9-9d4f-43d5-bc83-12c2b0abc776"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Le mot u = 'cde' est sous-mot de y = 'abcdefghijklmnopqrstuvwxyz', a partir de l'indice i = 2.\n",
      "Le mot u = 'cde' n'est pas sous-mot de y = 'abcDefghijklmnopqrstuvwxyz'.\n"
     ]
    }
   ],
   "source": [
    "def test_estSousMot(u, y):\n",
    "    \"\"\" Teste et affiche. \"\"\"\n",
    "    i = indiceSousMot(u, y)\n",
    "    if i >= 0:\n",
    "        print(\"Le mot u = '{}' est sous-mot de y = '{}', a partir de l'indice i = {}.\".format(u, y, i))\n",
    "    else:\n",
    "        print(\"Le mot u = '{}' n'est pas sous-mot de y = '{}'.\".format(u, y))        \n",
    "\n",
    "\n",
    "u = \"cde\"\n",
    "y1 = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "test_estSousMot(u, y1)  # True\n",
    "\n",
    "y2 = \"abcDefghijklmnopqrstuvwxyz\"\n",
    "test_estSousMot(u, y2)  # False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "861c638f-ec78-4001-b39c-875cce76dfdc"
    }
   },
   "source": [
    "## 3.2 Trouver *un* sous-mot de longueur ``k``"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d7fdbdf8-251b-4756-9e47-ac3110b5c849"
    }
   },
   "source": [
    "On peut chercher **tous** les sous-mots de longueur ``k`` dans ``x`` et regarder si l'**un d'entre eux** est inclus dans y (on s'arrête dès qu'on en a trouvé un) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbpresent": {
     "id": "35222aea-86e6-4146-9019-9528e53a7570"
    }
   },
   "outputs": [],
   "source": [
    "def aSousMotDeLongueur(x, y, k):\n",
    "    \"\"\" Trouve le premier sous-mot de x de longueur k et renvoit i, j, u, ou échoue avec une ValueError. \"\"\"\n",
    "    imax = len(x) - k + 1\n",
    "    # Les sous mots seront x0..xk-1, .., ximax-1,..,xn-1\n",
    "    for debut in range(imax):\n",
    "        j = indiceSousMotAux(x, k, debut, y, len(y), 0)\n",
    "        if j >= 0:\n",
    "            return debut, debut + j, x[debut:debut+k]\n",
    "    # Pas trouvé !\n",
    "    raise ValueError(\"Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.\".format(k, x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "3c02fca1-76e3-45f8-8a66-71708b4ddc6b"
    }
   },
   "source": [
    "Un test :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "nbpresent": {
     "id": "97260746-1fd8-4fa0-8c0f-1a71a4a54c11"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "==> Sous-mot de longueur k = 0 de x = 'aabcde' dans y = 'aABcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.\n",
      "==> Sous-mot de longueur k = 1 de x = 'aabcde' dans y = 'aABcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.\n",
      "==> Sous-mot de longueur k = 2 de x = 'aabcde' dans y = 'aABcdE' : u = 'cd' en indice i = 3 pour x et j = 6 pour y.\n",
      "==> Aucun sous-mot de longueur k = 3 de x = 'aabcde' n'est dans y = 'aABcdE'.\n",
      "==> Aucun sous-mot de longueur k = 4 de x = 'aabcde' n'est dans y = 'aABcdE'.\n",
      "==> Aucun sous-mot de longueur k = 5 de x = 'aabcde' n'est dans y = 'aABcdE'.\n",
      "==> Aucun sous-mot de longueur k = 6 de x = 'aabcde' n'est dans y = 'aABcdE'.\n",
      "==> Sous-mot de longueur k = 0 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.\n",
      "==> Sous-mot de longueur k = 1 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.\n",
      "==> Sous-mot de longueur k = 2 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'cd' en indice i = 5 pour x et j = 13 pour y.\n",
      "==> Aucun sous-mot de longueur k = 3 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n",
      "==> Aucun sous-mot de longueur k = 4 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n",
      "==> Aucun sous-mot de longueur k = 5 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n",
      "==> Aucun sous-mot de longueur k = 6 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n",
      "==> Aucun sous-mot de longueur k = 7 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n",
      "==> Aucun sous-mot de longueur k = 8 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.\n"
     ]
    }
   ],
   "source": [
    "def test_aSousMotDeLongueur(x, y, k):\n",
    "    \"\"\" Teste et affiche. \"\"\"\n",
    "    try:\n",
    "        i, j, u = aSousMotDeLongueur(x, y, k)\n",
    "        print(\"==> Sous-mot de longueur k = {} de x = '{}' dans y = '{}' : u = '{}' en indice i = {} pour x et j = {} pour y.\".format(k, x, y, u, i, j))\n",
    "    except ValueError:\n",
    "        print(\"==> Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.\".format(k, x, y))\n",
    "\n",
    "x = \"aabcde\"\n",
    "y = \"aABcdE\"\n",
    "for k in range(0, min(len(x), len(y)) + 1):\n",
    "    test_aSousMotDeLongueur(x, y, k)\n",
    "\n",
    "x = \"aabffcde\"\n",
    "y = \"aABGGGGGcdE\"\n",
    "for k in range(0, min(len(x), len(y)) + 1):\n",
    "    test_aSousMotDeLongueur(x, y, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "c4aafc17-eed8-4830-8333-02a98f4ccb8b"
    }
   },
   "source": [
    "## 3.3 Sous-mot de longueur maximale (version naïve)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "nbpresent": {
     "id": "b8b90419-d1ec-4439-890e-9717780094b3"
    }
   },
   "outputs": [],
   "source": [
    "def _sousMotMax(x, y, verb=True):\n",
    "    \"\"\" |x| doit etre plus petit que |y|.\"\"\"\n",
    "    k = len(x)\n",
    "    while k >= 0:\n",
    "        if verb:\n",
    "            print(\"  On essaie de trouver un sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...\".format(x, y, k))\n",
    "        try:\n",
    "            i, j, u = aSousMotDeLongueur(x, y, k)\n",
    "            if verb:\n",
    "                print(\"  ==> On a un sous-mot commun à x = '{}' et y = '{}' de taille k = {} : u = '{}' (i = {}, j = {}) !\".format(x, y, k, u, i, j))\n",
    "            return i, j, u\n",
    "        except ValueError:\n",
    "            if verb:\n",
    "                print(\"  ==> Aucun sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...\".format(x, y, k))\n",
    "        k -= 1\n",
    "\n",
    "            \n",
    "def sousMotMax(x, y, verb=True):\n",
    "    \"\"\" Trouve un sous-mot de longueur maximale (le plus à gauche possible de x et y), en temps exponentiel en n = |x|.\"\"\"\n",
    "    if len(x) <= len(y):\n",
    "        return _sousMotMax(x, y, verb=verb)\n",
    "    else:\n",
    "        return _sousMotMax(y, x, verb=verb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4519e7df-5d72-44be-ab36-44c1e2d04268"
    }
   },
   "source": [
    "Quelques tests :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "nbpresent": {
     "id": "7fa5fa37-e894-4caa-8052-55d6ce2677d4"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9, 18, '123456abc')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"abcABCabc123456abcABCabc99\"\n",
    "y = \"abcDEFdef123456abcDEFdef9999\"\n",
    "sousMotMax(x, y, verb=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "nbpresent": {
     "id": "6c587b6e-3c08-48f2-877d-11454634634d"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...\n",
      "  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...\n",
      "  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 ...\n",
      "  ==> On a un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 : u = 'abc' (i = 0, j = 0) !\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0, 0, 'abc')"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"abcABCabc\"\n",
    "y = \"abcDEFdef\"\n",
    "sousMotMax(x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4e2a85b7-6833-442a-bfae-cfd3fb98ca45"
    }
   },
   "source": [
    "# 4. Méthode gloutonne (programmation dynamique)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "bd1de069-0df7-48bc-83f7-f5e061a7d06e"
    }
   },
   "source": [
    "On passe désormais à la seconde approche, qui sera bien plus efficace (et qui montrera que le probleme du plus long sous-mot commun de deux mots est dans $\\mathcal{P}$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "80e8a873-9828-444d-9c44-e5d980c7c0eb"
    }
   },
   "source": [
    "Cette approche a l'avantage d'être bien plus efficace, mais aussi plus simple à coder.\n",
    "On a juste besoin d'une matrice de taille $(|x|+1)(|y|+1)$ (un ``numpy.array``, pour être plus efficace qu'une liste de liste), et quelques boucles ``for``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "nbpresent": {
     "id": "5cc3b653-680e-4d7f-b888-f84b5af084dd"
    }
   },
   "outputs": [],
   "source": [
    "# On a besoin du module numpy. Cf. http://numpy.org/ pour l'installer si besoin\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "21cc9ac6-1dd1-4456-a880-56876759502b"
    }
   },
   "source": [
    "## 4.1 Programmation dynamique, sans optimisation mémoire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "d4e520ac-1237-43a3-9364-64aad7136867"
    }
   },
   "source": [
    "La fonction ci-dessous procède en 4 étapes :\n",
    "\n",
    "1. Initialisation de la matrice ``longueurs``, pleine de $0$ et de taille $(n+1) \\times (m+1)$ où $y := |x|$ et $m := |y|$,\n",
    "2. Calcul \"bottom-up\" de la matrice ``longueurs``, par l'équation suivante :\n",
    "    $$ \\mathrm{longueurs}[i, j] = 1 + \\mathrm{longueurs}[i-1, j-1] \\; \\text{si} \\; x[i-1] = y[i-1]. $$\n",
    "3. Calcul de la longueur maximale d'une correspondance entre ``x`` et ``y``, par un simple parcours (``longueur_max``), et calcul des indices de début de cette coresspondance maximale (= plus long sous-mot !), ``idebut`` et ``jdebut``.\n",
    "4. (optionnel) On vérifie que ``x[idebut : idebut + longueur_max]`` = ``y[jdebut : jdebut + longueur_max]``.\n",
    "\n",
    "\n",
    "On commence en utilisant une matrice, pleine de $0$ (ie. une matrice nulle).\n",
    "Comme on va le voir dans les exemples ci-dessous, en pratique cette matrice restera presque \"vide\", consommant beaucoup de memoire ($\\mathcal{O}(n m)$) inutilement.\n",
    "La version suivante sera optimisée (en utilisant une matrice *sparse*, ie. creuse)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "38788d23-75be-41f6-9145-ce2c398f2822"
    }
   },
   "source": [
    "Cet algorithme sera en :\n",
    "\n",
    "- $\\mathcal{O}(n m)$ en mémoire, dans tous les cas (mais on peut faire mieux),\n",
    "- $\\mathcal{O}(n m)$ en temps, dans tous les cas (et on ne peut pas faire mieux).\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "nbpresent": {
     "id": "05ce1f79-4f0b-445b-95a7-fba4ddf88b56"
    }
   },
   "outputs": [],
   "source": [
    "def sousMotMaxGlouton(x, y, verb=False, verifie=True):\n",
    "    \"\"\" Calcule le plus long sous-mot commun a x et y, par programmation dynamique.\n",
    "    \n",
    "        - affiche un peu ce qu'il se passe si verb=True,\n",
    "        - vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.\n",
    "    \"\"\"\n",
    "    def message(*args):\n",
    "        if verb:\n",
    "            print(*args) \n",
    "    # 1. et 2. Initialisation et construction Matrice longueurs\n",
    "    n = len(x)\n",
    "    m = len(y)\n",
    "    message(\"\\n1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n",
    "    longueurs = np.zeros((n+1, m+1), dtype=int)\n",
    "    message(\"2. Construction bottom-up de la loop-up matrice longueurs ...\")\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, m+1):\n",
    "            if x[i-1] == y[j-1]:\n",
    "                longueurs[i, j] = 1 + longueurs[i-1, j-1]\n",
    "                message(\"      Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n",
    "    # 3. Utilisation de la matrice longueurs\n",
    "    iFin, jFin = 0, 0\n",
    "    longueur_max = -1  # Pas encore\n",
    "    message(\"3. Calcul de la position du plus long sous mot via la matrice longueurs ...\")\n",
    "    for i in range(0, n+1):\n",
    "        for j in range(0, m+1):\n",
    "            if longueur_max < longueurs[i, j]:\n",
    "                longueur_max = longueurs[i, j]\n",
    "                iFin, jFin = i, j\n",
    "    # Note : avec les fonctions numpy np.max et np.argmax on pourrait faire ça plus vite (pour des matrices) :\n",
    "    # longueur_max = np.max(longueurs)\n",
    "    # iFin, jFin = np.unravel_index(np.argmax(longueurs), np.shape(longueurs))\n",
    "    # Calcul des indices de debut\n",
    "    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max\n",
    "    message(\"4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...\".format(iDebut, jDebut, longueur_max))\n",
    "\n",
    "    # 4. Vérification\n",
    "    if verifie:\n",
    "        xSous = x[iDebut: iDebut + longueur_max]\n",
    "        ySous = y[jDebut: jDebut + longueur_max]\n",
    "        message(\"      Sous-mot dans x = {}, et sous-mot dans y = {} ...\".format(xSous, ySous))\n",
    "        assert xSous == ySous, \"Erreur, xSous et ySous sont différents !\"\n",
    "    \n",
    "    leSousMot = x[iDebut: iDebut + longueur_max]\n",
    "    return iDebut, jDebut, leSousMot, longueurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e9e66dc0-c61a-46a7-87b6-ac376fc2d781"
    }
   },
   "source": [
    "On peut faire quelques tests, comme pour l'approche initiale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "nbpresent": {
     "id": "189c0d2e-0093-447a-866b-671dc5216b01"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 6 m = 7 ...\n",
      "2. Construction bottom-up de la loop-up matrice longueurs ...\n",
      "      Correspondance en cours, u[0] = B et v[1] = B, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[0] = B et v[3] = B, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[0] = B et v[6] = B, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[1] = D et v[4] = D, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[2] = C et v[2] = C, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = A et v[0] = A, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = A et v[5] = A, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[4] = B et v[1] = B, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[4] = B et v[3] = B, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[4] = B et v[6] = B, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[5] = A et v[0] = A, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[5] = A et v[5] = A, de longueur courante 1 ...\n",
      "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n",
      "4. On a obtenu iDebut = 0 et jDebut = 3 et longueur_max = 2 ...\n",
      "      Sous-mot dans x = BD, et sous-mot dans y = BD ...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0, 3, 'BD', array([[0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 1, 0, 1, 0, 0, 1],\n",
       "        [0, 0, 0, 0, 0, 2, 0, 0],\n",
       "        [0, 0, 0, 1, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 0, 0, 1, 0],\n",
       "        [0, 0, 2, 0, 1, 0, 0, 2],\n",
       "        [0, 1, 0, 0, 0, 0, 1, 0]]))"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"BDCABA\"\n",
    "y = \"ABCBDAB\"\n",
    "sousMotMaxGlouton(x, y, verb=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "nbpresent": {
     "id": "7bb9f155-8411-4e5c-af83-da460ef3d52d"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 26 m = 28 ...\n",
      "2. Construction bottom-up de la loop-up matrice longueurs ...\n",
      "      Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[0] = a et v[15] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[1] = b et v[16] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[2] = c et v[2] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[2] = c et v[17] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[6] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[6] = a et v[15] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[7] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[7] = b et v[16] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[8] = c et v[2] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[8] = c et v[17] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[9] = 1 et v[9] = 1, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[10] = 2 et v[10] = 2, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[11] = 3 et v[11] = 3, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[12] = 4 et v[12] = 4, de longueur courante 4 ...\n",
      "      Correspondance en cours, u[13] = 5 et v[13] = 5, de longueur courante 5 ...\n",
      "      Correspondance en cours, u[14] = 6 et v[14] = 6, de longueur courante 6 ...\n",
      "      Correspondance en cours, u[15] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[15] = a et v[15] = a, de longueur courante 7 ...\n",
      "      Correspondance en cours, u[16] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[16] = b et v[16] = b, de longueur courante 8 ...\n",
      "      Correspondance en cours, u[17] = c et v[2] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[17] = c et v[17] = c, de longueur courante 9 ...\n",
      "      Correspondance en cours, u[21] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[21] = a et v[15] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[22] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[22] = b et v[16] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[23] = c et v[2] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[23] = c et v[17] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[24] = 9 et v[24] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[24] = 9 et v[25] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[24] = 9 et v[26] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[24] = 9 et v[27] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[25] = 9 et v[24] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[25] = 9 et v[25] = 9, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[25] = 9 et v[26] = 9, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[25] = 9 et v[27] = 9, de longueur courante 2 ...\n",
      "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n",
      "4. On a obtenu iDebut = 9 et jDebut = 9 et longueur_max = 9 ...\n",
      "      Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(9,\n",
       " 9,\n",
       " '123456abc',\n",
       " array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,\n",
       "         0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 1, 1, 1, 1],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "         0, 0, 0, 1, 2, 2, 2]]))"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"abcABCabc123456abcABCabc99\"\n",
    "y = \"abcDEFdef123456abcDEFdef9999\"\n",
    "sousMotMaxGlouton(x, y, verb=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "be75ea87-42f6-4c1c-a38c-a2a1a147830a"
    }
   },
   "source": [
    "On commence à constater que la matrice `longueurs` est toujours presque remplie de zéros, même après tous les calculs ! Peut-être qu'on peut faire mieux, niveau espace de stockage (complexité en mémoire), pour éviter de stocker un nombre trop grand de zéros inutiles. Une version améliorée est présentée ci-dessous, on parvient à diminuer grandement la complexité (moyenne) en mémoire en utilisant une structure intelligente de matrice *\"creuse\"*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "nbpresent": {
     "id": "8ee08570-75e7-4d93-8c2a-a46fd707c7ed"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 12 m = 16 ...\n",
      "2. Construction bottom-up de la loop-up matrice longueurs ...\n",
      "      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...\n",
      "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n",
      "4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...\n",
      "      Sous-mot dans x = FG, et sous-mot dans y = FG ...\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(7, 5, 'FG', array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"abcZZdeFG597\"\n",
    "y = \"AbCdEFG413ZAQCWQ\"\n",
    "sousMotMaxGlouton(x, y, verb=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "534391af-839f-4ee6-b6d3-cccc89272bad"
    }
   },
   "source": [
    "## 4.2 Utilisation d'une matrice *creuse*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "99eac7dc-c7d5-419c-afd4-1e7a8a6ef96e"
    }
   },
   "source": [
    "On va utiliser le module [``scipy.sparse``](https://docs.scipy.org/doc/scipy/reference/sparse.html) pour utiliser un codage efficace pour cette matrice ``longueurs`` : un codage dit creux qui permettra de ne pas stocker tous ces zéros inutiles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "nbpresent": {
     "id": "f47df73d-5867-4efe-b999-d4ce1b83c7dd"
    }
   },
   "outputs": [],
   "source": [
    "from scipy.sparse import lil_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "96bc8eb2-feff-46e5-b296-729b4de0039a"
    }
   },
   "source": [
    "On utilise la structure ``lil_matrix`` (``lil`` pour *\"LInked List\"*), car c'est la plus efficace quant la matrice change de structure *sparse* (on rajoute des valeurs non-nulles au fur et à mesure de sa construction).\n",
    "\n",
    "Exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "nbpresent": {
     "id": "09532d01-e5b2-4105-a9cd-bfa84c1a2dd3"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I_12 pleine :\n",
      " [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]]\n",
      "I_12 creuse :\n",
      "   (0, 0)\t1.0\n",
      "  (1, 1)\t1.0\n",
      "  (2, 2)\t1.0\n",
      "  (3, 3)\t1.0\n",
      "  (4, 4)\t1.0\n",
      "  (5, 5)\t1.0\n",
      "  (6, 6)\t1.0\n",
      "  (7, 7)\t1.0\n",
      "  (8, 8)\t1.0\n",
      "  (9, 9)\t1.0\n",
      "  (10, 10)\t1.0\n",
      "  (11, 11)\t1.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<12x12 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 12 stored elements in LInked List format>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(\"I_12 pleine :\\n\", np.eye(12))\n",
    "I12 = lil_matrix(np.eye(12))\n",
    "print(\"I_12 creuse :\\n\", I12)\n",
    "I12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "nbpresent": {
     "id": "aeae66fa-b1bc-4c62-83a3-f1e5d1cdf67a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Taille de I_12 creuse = 12\n"
     ]
    }
   ],
   "source": [
    "print(\"Taille de I_12 creuse =\", I12.size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e9c0d0ef-7fb9-4d13-b0ab-12f7ef0095b9"
    }
   },
   "source": [
    "On peut prendre exactement la même fonction, et changer la ligne qui crée la matrice ``longueurs`` : on ajoute un appel à ``lil_matrix`` pour en faire une matrice creuse.\n",
    "\n",
    "Et voilà comment on passe, en une ligne, de $\\mathcal{O}(n m)$ en mémoire dans tous les cas à un $\\mathcal{O}(n m)$ dans le pire des cas et $\\mathcal{O}(\\sum \\text{longueur des sous-mots de x et y})$ dans tous les cas (en moyenne, ce sera $\\mathcal{O}(\\min(n, m))$ au pire).\n",
    "Notez que ce sera un poil moins efficace, mais on garde la complexité en temps en $\\mathcal{O}(n m)$ de toute façon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "nbpresent": {
     "id": "0ba86758-f1f8-4303-8546-6e7438d7b569"
    }
   },
   "outputs": [],
   "source": [
    "def sousMotMaxGloutonCreux(x, y, verb=False, verifie=True):\n",
    "    \"\"\" Calcule le plus long sous-mot commun a x et y, par programmation dynamique.\n",
    "    \n",
    "        - affiche un peu ce qu'il se passe si verb=True,\n",
    "        - vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.\n",
    "    \"\"\"\n",
    "    def message(*args):\n",
    "        if verb:\n",
    "            print(*args) \n",
    "    # 1. et 2. Initialisation et construction Matrice longueurs\n",
    "    n = len(x)\n",
    "    m = len(y)\n",
    "    message(\"\\n1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n",
    "    longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))\n",
    "    message(\"2. Construction bottom-up de la loop-up matrice longueurs ...\")\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, m+1):\n",
    "            if x[i-1] == y[j-1]:\n",
    "                longueurs[i, j] = 1 + longueurs[i-1, j-1]\n",
    "                message(\"      Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n",
    "    # 3. Utilisation de la matrice longueurs\n",
    "    iFin, jFin = 0, 0\n",
    "    longueur_max = -1  # Pas encore\n",
    "    message(\"3. Calcul de la position du plus long sous mot via la matrice longueurs ...\")\n",
    "    for i in range(0, n+1):\n",
    "        for j in range(0, m+1):\n",
    "            if longueur_max < longueurs[i, j]:\n",
    "                longueur_max = longueurs[i, j]\n",
    "                iFin, jFin = i, j\n",
    "    # Calcul des indices de debut\n",
    "    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max\n",
    "    message(\"4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...\".format(iDebut, jDebut, longueur_max))\n",
    "\n",
    "    # 4. Vérification\n",
    "    if verifie:\n",
    "        xSous = x[iDebut: iDebut + longueur_max]\n",
    "        ySous = y[jDebut: jDebut + longueur_max]\n",
    "        message(\"      Sous-mot dans x = {}, et sous-mot dans y = {} ...\".format(xSous, ySous))\n",
    "        assert xSous == ySous, \"Erreur, xSous et ySous sont différents !\"\n",
    "    \n",
    "    leSousMot = x[iDebut: iDebut + longueur_max]\n",
    "    return iDebut, jDebut, leSousMot, longueurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4773db1d-567a-42b6-9c33-79b6fa0b96a6"
    }
   },
   "source": [
    "On peut faire quelques exemples en plus, et on calcule aussi la taille de la matrice creuse ``longueurs`` (pour comparer a la taille de la matrice pleine de la fonction d'avant) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "nbpresent": {
     "id": "5feab5e3-f15a-490c-8722-935bf5dd84c6"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 28 m = 38 ...\n",
      "2. Construction bottom-up de la loop-up matrice longueurs ...\n",
      "      Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[0] = a et v[25] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[1] = b et v[26] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[2] = 0 et v[12] = 0, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[2] = 0 et v[16] = 0, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = c et v[10] = c, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = c et v[27] = c, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[6] = C et v[5] = C, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[7] = 0 et v[12] = 0, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[7] = 0 et v[16] = 0, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[8] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[8] = a et v[25] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[9] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[9] = b et v[26] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[10] = c et v[10] = c, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[10] = c et v[27] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[11] = 1 et v[19] = 1, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[12] = 2 et v[20] = 2, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[13] = 3 et v[21] = 3, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[14] = 4 et v[22] = 4, de longueur courante 4 ...\n",
      "      Correspondance en cours, u[15] = 5 et v[23] = 5, de longueur courante 5 ...\n",
      "      Correspondance en cours, u[16] = 6 et v[24] = 6, de longueur courante 6 ...\n",
      "      Correspondance en cours, u[17] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[17] = a et v[25] = a, de longueur courante 7 ...\n",
      "      Correspondance en cours, u[18] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[18] = b et v[26] = b, de longueur courante 8 ...\n",
      "      Correspondance en cours, u[19] = c et v[10] = c, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[19] = c et v[27] = c, de longueur courante 9 ...\n",
      "      Correspondance en cours, u[22] = C et v[5] = C, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[23] = a et v[0] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[23] = a et v[25] = a, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[24] = b et v[1] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[24] = b et v[26] = b, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[25] = c et v[10] = c, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[25] = c et v[27] = c, de longueur courante 3 ...\n",
      "      Correspondance en cours, u[26] = 9 et v[34] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[26] = 9 et v[35] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[26] = 9 et v[36] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[26] = 9 et v[37] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[27] = 9 et v[34] = 9, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[27] = 9 et v[35] = 9, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[27] = 9 et v[36] = 9, de longueur courante 2 ...\n",
      "      Correspondance en cours, u[27] = 9 et v[37] = 9, de longueur courante 2 ...\n",
      "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n",
      "4. On a obtenu iDebut = 11 et jDebut = 19 et longueur_max = 9 ...\n",
      "      Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...\n",
      "Taille de la matrice pleine = (n+1)(m+1) = 1131\n",
      "Taille de la matrice creuse longueurs = 44\n"
     ]
    }
   ],
   "source": [
    "x = \"ab0cABC0abc123456abcABCabc99\"\n",
    "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999\"\n",
    "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)\n",
    "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n",
    "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "c026476c-371c-4f75-8754-21fe897e324c"
    }
   },
   "source": [
    "Ici, sur deux mots de tailles raisonnables (``x = \"ab0cABC0abc123456abcABCabc99\"`` et ``y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999\"``), on passe d'une matrice pleine de taille ``1131`` entiers à une matrice creuse de taille ``44`` entiers : le gain est considérable ! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "nbpresent": {
     "id": "42faa621-3766-4ef9-adc8-f8a1f1e7cc5f"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 12 m = 16 ...\n",
      "2. Construction bottom-up de la loop-up matrice longueurs ...\n",
      "      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...\n",
      "      Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...\n",
      "3. Calcul de la position du plus long sous mot via la matrice longueurs ...\n",
      "4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...\n",
      "      Sous-mot dans x = FG, et sous-mot dans y = FG ...\n",
      "Taille de la matrice pleine = (n+1)(m+1) = 221\n",
      "Taille de la matrice creuse longueurs = 6\n"
     ]
    }
   ],
   "source": [
    "x = \"abcZZdeFG597\"\n",
    "y = \"AbCdEFG413ZAQCWQ\"\n",
    "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)\n",
    "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n",
    "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "39788369-262a-49c6-a335-a90b04bc57b0"
    }
   },
   "source": [
    "Avec des mots ``x`` et ``y`` plus longs, le gain en mémoire induit par le codage creux est encore plus impressionnant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "nbpresent": {
     "id": "adce5d12-902d-4b0a-9e33-7f6ff2a1685d"
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Taille de la matrice pleine = (n+1)(m+1) = 44215\n",
      "Taille de la matrice creuse longueurs = 1046\n"
     ]
    }
   ],
   "source": [
    "x = \"ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù\"\n",
    "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd\"\n",
    "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=False)\n",
    "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n",
    "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "32b2eb7b-1f5b-45dc-bb9b-0913756c1358"
    }
   },
   "source": [
    "### 4.2.1 Version condensée"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "0b453f22-b605-4285-a1f6-24d4f54865fa"
    }
   },
   "source": [
    "Le code de cette fonction `sousMotMaxGloutonCreux` peut sembler un peu long, mais sans messages ni commentaires il est vraiment court et simple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "nbpresent": {
     "id": "02caf31c-8652-445c-a8a3-f257bb2e1bb4"
    }
   },
   "outputs": [],
   "source": [
    "def sousMotMaxGloutonCreux2(x, y):\n",
    "    n = len(x)\n",
    "    m = len(y)\n",
    "    \n",
    "    longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, m+1):\n",
    "            if x[i-1] == y[j-1]:\n",
    "                longueurs[i, j] = 1 + longueurs[i-1, j-1]\n",
    "    \n",
    "    iFin, jFin = 0, 0\n",
    "    longueur_max = -1  # Pas encore\n",
    "    for i in range(0, n+1):\n",
    "        for j in range(0, m+1):\n",
    "            if longueur_max < longueurs[i, j]:\n",
    "                longueur_max = longueurs[i, j]\n",
    "                iFin, jFin = i, j\n",
    "    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max\n",
    "\n",
    "    leSousMot = x[iDebut: iDebut + longueur_max]\n",
    "    return iDebut, jDebut, leSousMot, longueurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f21c577a-a8ba-4a28-95d2-f038c705804c"
    }
   },
   "source": [
    "Et le même exemple donne pareil :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "nbpresent": {
     "id": "37e58043-93b4-427b-ba89-ac5175983835"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Taille de la matrice pleine = (n+1)(m+1) = 44215\n",
      "Taille de la matrice creuse longueurs = 1046\n",
      "Sous-mot : 1249721325414765132486513486565465\n"
     ]
    }
   ],
   "source": [
    "x = \"ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù\"\n",
    "y = \"abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd\"\n",
    "iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux2(x, y)\n",
    "print(\"Taille de la matrice pleine = (n+1)(m+1) =\", (len(x) + 1) * (len(y) + 1))\n",
    "print(\"Taille de la matrice creuse longueurs =\", longueurs.size)\n",
    "print(\"Sous-mot :\", sousxy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "71aad76b-3065-4bc6-b778-547ed96aaea6"
    }
   },
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "071fe529-377f-46d0-986a-aaf7da101fef"
    }
   },
   "source": [
    "# 5. Calcule de la plus longue sous-séquence commune"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e172a934-fc99-4cd9-81ab-1afcc9875423"
    }
   },
   "source": [
    "Maintenant qu'on a fait tout ca, on peut implementer, de facon tres semblable, l'algorithme glouton pour le calcul de la plus longue sous-séquence commune.\n",
    "\n",
    "Dans cet autre problème, on cherche des sous-séquences et plus des sous-mots, donc on peut extraire de facon non consécutives.\n",
    "Le développement d'agrégation devrait concerner le second problème, qui est plus intéressant:\n",
    "Par exemple, voici une version tapée en PDF : http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "43bf9fa4-82e6-44a7-938d-de9304b7835b"
    }
   },
   "source": [
    "## 5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "e8f68e52-0412-4e94-8392-1cf1ae090978"
    }
   },
   "source": [
    "On commencer par écrire une petite fonction qui permet de vérifier rapidement qu'une chaine est une sous-séquence d'une autre, juste en regardant la définition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "nbpresent": {
     "id": "d5241d34-488d-4175-b8a8-a241226b7a3c"
    }
   },
   "outputs": [],
   "source": [
    "def estSousSeq(seq, x, verb=True, indices=True):\n",
    "    \"\"\" Verifie en temps O(|seq| |x|) que seq est une bonne sous-sequence de x.\n",
    "    \"\"\"\n",
    "    result = False\n",
    "    indices_x = []\n",
    "    try:\n",
    "        i = -1\n",
    "        for l in seq:\n",
    "            j = i+1 + x[i+1:].index(l)\n",
    "            indices_x.append(j)\n",
    "            i = j\n",
    "        result = True\n",
    "    except Exception as e:\n",
    "        if verb:\n",
    "            print(\"Erreur dans estSousSeq(seq = {}, x = {}):\\n{}\".format(seq, x, e))\n",
    "    if indices:\n",
    "        return result, indices_x\n",
    "    else:\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "7ff35116-bcd8-4402-880d-f6d3c8071a67"
    }
   },
   "source": [
    "## 5.2 Algorithme pour la plus longue sous-séquence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "3af0c210-e6b4-4eed-9e59-f6a6b4ecf677"
    }
   },
   "source": [
    "On adapte l'algorithme du plus long sous-mot pour détecter les séquences aussi.\n",
    "Cf. le PDF page 2/3.\n",
    "\n",
    "TODO meilleures explications"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "nbpresent": {
     "id": "85bd73dd-62e7-48c3-865f-27e20b2ffc16"
    }
   },
   "outputs": [],
   "source": [
    "def utiliseTableOrigines_x(x, origines, i, j, accu=''):\n",
    "    \"\"\" Renvoie la sous-séquence de x codée dans la table origines. Cf. PDF (Algorithme 2).\n",
    "    \n",
    "        - Calcul tail récursif (stocké dans la variable accu).\n",
    "    \"\"\"\n",
    "    # print(\"  utiliseTableOrigines(x = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...\".format(x, i, j, accu, origines[i, j]))  # DEBUG\n",
    "    if i == 0 or j == 0:\n",
    "        return accu\n",
    "    if origines[i, j] == '↖':    # Vraie correspondance, on ajoute une lettre !\n",
    "        return utiliseTableOrigines_x(x, origines, i-1, j-1, x[i-1] + accu)\n",
    "    elif origines[i, j] == '↑':  # Fausse correspondance, on continue a gauche...\n",
    "        return utiliseTableOrigines_x(x, origines, i-1, j, accu)\n",
    "    elif origines[i, j] == '←':  # Fausse correspondance, on continue en haut...\n",
    "        return utiliseTableOrigines_x(x, origines, i, j-1, accu)\n",
    "    else:\n",
    "        raise ValueError(\"Erreur dans la table 'origines', invalide pour le mot x = {} ...\".format(x))\n",
    "\n",
    "\n",
    "def utiliseTableOrigines_y(x, origines, i, j, accu=''):\n",
    "    \"\"\" Renvoie la sous-séquence de y codée dans la table origines. Cf. PDF (Algorithme 2).\n",
    "    \n",
    "        - Calcul tail récursif (stocké dans la variable accu).\n",
    "    \"\"\"\n",
    "    # print(\"  utiliseTableOrigines(y = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...\".format(y, i, j, accu, origines[i, j]))  # DEBUG\n",
    "    if i == 0 or j == 0:\n",
    "        return accu\n",
    "    if origines[i, j] == '↖':    # Vraie correspondance, on ajoute une lettre !\n",
    "        return utiliseTableOrigines_y(x, origines, i-1, j-1, y[j-1] + accu)\n",
    "    elif origines[i, j] == '↑':  # Fausse correspondance, on continue a gauche...\n",
    "        return utiliseTableOrigines_y(x, origines, i-1, j, accu)\n",
    "    elif origines[i, j] == '←':  # Fausse correspondance, on continue en haut...\n",
    "        return utiliseTableOrigines_y(x, origines, i, j-1, accu)\n",
    "    else:\n",
    "        raise ValueError(\"Erreur dans la table 'origines', invalide pour le mot y = {} ...\".format(y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "cb50812e-6786-4637-8875-4192cc230fcf"
    }
   },
   "source": [
    "TODO meilleures explications"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "nbpresent": {
     "id": "48e14a23-1f2a-4b8e-a439-950dd9975515"
    }
   },
   "outputs": [],
   "source": [
    "def sousMotSeqGlouton(x, y, verb=False, verifie=True):\n",
    "    \"\"\" Calcule la plus longue sous-mot séquence a x et y, par programmation dynamique.\n",
    "    \n",
    "        - affiche un peu ce qu'il se passe si verb=True,\n",
    "        - vérifie que la sous-séquence commun est bien une bonne sous-séquence commune si verifie=True,\n",
    "        - renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=False,\n",
    "        - renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=True.\n",
    "    \"\"\"\n",
    "    def message(*args):\n",
    "        if verb:\n",
    "            print(*args) \n",
    "    # 1. et 2. Initialisation et construction Matrice longueurs\n",
    "    n = len(x)\n",
    "    m = len(y)\n",
    "    message(\"\\n1. Initialisation des look-up matrices longueurs et origines de taille (n+1, m+1) : n = {} m = {} ...\".format(n, m))\n",
    "    longueurs = np.zeros((n+1, m+1), dtype=int)     # Matrice c du dev en PDF\n",
    "    origines = np.array([[' '] * (m+1)] * (n+1), dtype=str)  # Matrice b du dev en PDF\n",
    "    # Note : on pourrait utiliser un codage a base d'entier, 0 1 2 3 pour ' ' '←' '↑' '↖' mais c'est moins joli...\n",
    "    message(\"2. Construction bottom-up des loop-up matrices longueurs et origines ...\")\n",
    "    for i in range(1, n+1):\n",
    "        for j in range(1, m+1):\n",
    "            if x[i-1] == y[j-1]:\n",
    "                longueurs[i, j] = 1 + longueurs[i-1, j-1]\n",
    "                origines[i, j] = '↖'\n",
    "                message(\"      Vraie correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n",
    "            elif longueurs[i-1, j] >= longueurs[i, j-1]:\n",
    "                longueurs[i, j] = longueurs[i-1, j]\n",
    "                origines[i, j] = '↑'\n",
    "                message(\"      Correspondance gauche (u) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n",
    "            else:\n",
    "                longueurs[i, j] = longueurs[i, j-1]\n",
    "                origines[i, j] = '←'\n",
    "                message(\"      Correspondance haute (v) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...\".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))\n",
    "\n",
    "    # 3. Utilisation de la matrice longueurs\n",
    "    laSousSeq = utiliseTableOrigines_x(x, origines, n, m, accu='')\n",
    "\n",
    "    # 4. Vérification\n",
    "    if verifie:\n",
    "        res_x, indices_x = estSousSeq(laSousSeq, x, indices=True)\n",
    "        if not res_x:\n",
    "            raise ValueError(\"Erreur: La séquence {} de x (aux indices {}) n'est pas une bonne sous-séquence de x = {}.\".format(laSousSeq, indices_x, x))\n",
    "        \n",
    "        laSousSeq_y = utiliseTableOrigines_y(y, origines, n, m, accu='')\n",
    "        if laSousSeq != laSousSeq_y:\n",
    "            raise ValueError(\"Erreur: La sous-séquence {} de x est différente de celle de y : {} ...\".format(laSousSeq, laSousSeq_y))\n",
    "\n",
    "        res_y, indices_y = estSousSeq(laSousSeq, y, indices=True)\n",
    "        if not res_y:\n",
    "            raise ValueError(\"Erreur: La séquence {} de y (aux indices {}) n'est pas une bonne sous-séquence de y = {}.\".format(laSousSeq, indices_y, y))\n",
    "        \n",
    "        # Fini !\n",
    "        return laSousSeq, longueurs, origines, indices_x, indices_y\n",
    "    else:\n",
    "        return laSousSeq, longueurs, origines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ff3fd202-2ddb-4a3a-b28a-e68b99afe8b1"
    }
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "0c0c8cad-eaee-44e5-9a17-5186cf661c91"
    }
   },
   "source": [
    "### 5.2.1 Exemple, venant du développement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "15d06766-c839-4390-a7c0-2ced861ea9c5"
    }
   },
   "source": [
    "Blabla"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "nbpresent": {
     "id": "cf445208-e3a7-4baf-8c23-cc3a460bc34a"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sous-seq de taille 4 valant BCBA ...\n",
      "   - aux indices [1, 2, 3, 5] pour x = ABCBDAB ...\n",
      "   - aux indices [0, 2, 4, 5] pour y = BDCABA ...\n",
      "Et la table longueurs vaut :\n",
      " [[0 0 0 0 0 0 0]\n",
      " [0 0 0 0 1 1 1]\n",
      " [0 1 1 1 1 2 2]\n",
      " [0 1 1 2 2 2 2]\n",
      " [0 1 1 2 2 3 3]\n",
      " [0 1 2 2 2 3 3]\n",
      " [0 1 2 2 3 3 4]\n",
      " [0 1 2 2 3 4 4]] ...\n",
      "Et la table origines vaut :\n",
      " [[' ' ' ' ' ' ' ' ' ' ' ' ' ']\n",
      " [' ' '↑' '↑' '↑' '↖' '←' '↖']\n",
      " [' ' '↖' '←' '←' '↑' '↖' '←']\n",
      " [' ' '↑' '↑' '↖' '←' '↑' '↑']\n",
      " [' ' '↖' '↑' '↑' '↑' '↖' '←']\n",
      " [' ' '↑' '↖' '↑' '↑' '↑' '↑']\n",
      " [' ' '↑' '↑' '↑' '↖' '↑' '↖']\n",
      " [' ' '↖' '↑' '↑' '↑' '↖' '↑']] ...\n"
     ]
    }
   ],
   "source": [
    "x = \"ABCBDAB\"\n",
    "y = \"BDCABA\"\n",
    "laSousSeq, longueurs, origines, indices_x, indices_y = sousMotSeqGlouton(x, y, verifie=True)\n",
    "print(\"Sous-seq de taille\", len(laSousSeq), \"valant\", laSousSeq, \"...\")\n",
    "print(\"   - aux indices\", indices_x, \"pour x =\", x, \"...\")\n",
    "print(\"   - aux indices\", indices_y, \"pour y =\", y, \"...\")\n",
    "print(\"Et la table longueurs vaut :\\n\", longueurs, \"...\")\n",
    "print(\"Et la table origines vaut :\\n\", origines, \"...\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "9689610e-f181-4377-a878-aeaf261e8567"
    }
   },
   "source": [
    "### 5.2.2 Autres exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "96dc1ad2-d5db-4ed7-931d-cdd3107f3fd5"
    }
   },
   "source": [
    "TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "636d18ab-b153-4566-81d5-3b608284d2e4"
    }
   },
   "source": [
    "----\n",
    "\n",
    "> *C'est tout pour aujourd'hui les amis !*\n",
    "> [Allez voir d'autres notebooks](https://github.com/Naereen/notebooks/tree/master/agreg) si vous voulez."
   ]
  }
 ],
 "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.6"
  },
  "nbpresent": {
   "slides": {
    "054f873f-fc0c-43f8-9ffb-5b4b70e36525": {
     "id": "054f873f-fc0c-43f8-9ffb-5b4b70e36525",
     "prev": "66942006-40b7-4b08-94c1-ab4b27693b7c",
     "regions": {
      "a1c27410-7876-4b2d-be97-94ca3169eb5b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "09532d01-e5b2-4105-a9cd-bfa84c1a2dd3",
        "part": "whole"
       },
       "id": "a1c27410-7876-4b2d-be97-94ca3169eb5b"
      }
     }
    },
    "067d3558-5fe3-4116-aafd-0d1ac44c460a": {
     "id": "067d3558-5fe3-4116-aafd-0d1ac44c460a",
     "prev": "3cd85433-8ab0-4087-8f4b-b642a04bc77d",
     "regions": {
      "74f4f12b-f06d-4318-8072-6dcc75704f47": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "21cc9ac6-1dd1-4456-a880-56876759502b",
        "part": "whole"
       },
       "id": "74f4f12b-f06d-4318-8072-6dcc75704f47"
      }
     }
    },
    "06fdad76-73ed-4bb9-9008-d3c9117eb783": {
     "id": "06fdad76-73ed-4bb9-9008-d3c9117eb783",
     "prev": "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55",
     "regions": {
      "be8f30f7-843d-40dd-b0ec-2ad49a8bde0e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e8ba8fa2-6f98-4431-8222-c897d1145a15",
        "part": "whole"
       },
       "id": "be8f30f7-843d-40dd-b0ec-2ad49a8bde0e"
      }
     }
    },
    "13af60a5-502c-409f-b1db-306d3546673e": {
     "id": "13af60a5-502c-409f-b1db-306d3546673e",
     "prev": "2b1e9a92-db79-49ba-a823-a3310a4d8b82",
     "regions": {
      "a565c42d-fbfa-4df2-83a0-00249b64379c": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e8f68e52-0412-4e94-8392-1cf1ae090978",
        "part": "whole"
       },
       "id": "a565c42d-fbfa-4df2-83a0-00249b64379c"
      }
     }
    },
    "1537ce27-bbb3-482a-b930-61128dfaa5fc": {
     "id": "1537ce27-bbb3-482a-b930-61128dfaa5fc",
     "prev": "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2",
     "regions": {
      "26365346-f58c-41cf-ae5d-8921e5dc9ce6": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "6c587b6e-3c08-48f2-877d-11454634634d",
        "part": "whole"
       },
       "id": "26365346-f58c-41cf-ae5d-8921e5dc9ce6"
      }
     }
    },
    "1bdba887-217a-43fe-9f80-bd6830d26787": {
     "id": "1bdba887-217a-43fe-9f80-bd6830d26787",
     "prev": "054f873f-fc0c-43f8-9ffb-5b4b70e36525",
     "regions": {
      "cbffc2f5-895d-43ab-b3f3-d292cd0e549d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "aeae66fa-b1bc-4c62-83a3-f1e5d1cdf67a",
        "part": "whole"
       },
       "id": "cbffc2f5-895d-43ab-b3f3-d292cd0e549d"
      }
     }
    },
    "1d7bd639-1931-42bc-ab90-9fe0f2f4feae": {
     "id": "1d7bd639-1931-42bc-ab90-9fe0f2f4feae",
     "prev": "80edbb16-b6a1-4233-8833-0d4f6addea00",
     "regions": {
      "2bfd3f5f-27be-46cc-8b51-b2bcc005da0f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "35222aea-86e6-4146-9019-9528e53a7570",
        "part": "whole"
       },
       "id": "2bfd3f5f-27be-46cc-8b51-b2bcc005da0f"
      }
     }
    },
    "1e187c07-2118-486e-abbc-0fbb90d33727": {
     "id": "1e187c07-2118-486e-abbc-0fbb90d33727",
     "prev": "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e",
     "regions": {
      "0444cd52-edb4-4c99-88bd-b929b56fcd69": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "be75ea87-42f6-4c1c-a38c-a2a1a147830a",
        "part": "whole"
       },
       "id": "0444cd52-edb4-4c99-88bd-b929b56fcd69"
      }
     }
    },
    "1eb71078-a076-49a3-b399-7b00d19bf154": {
     "id": "1eb71078-a076-49a3-b399-7b00d19bf154",
     "prev": "e688f732-8379-4090-baee-d74e938ba845",
     "regions": {
      "eeea3537-7d0c-480d-b516-45d7b93e21b4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5feab5e3-f15a-490c-8722-935bf5dd84c6",
        "part": "whole"
       },
       "id": "eeea3537-7d0c-480d-b516-45d7b93e21b4"
      }
     }
    },
    "223ff166-4f0b-4bb8-9790-e6dd8baaa596": {
     "id": "223ff166-4f0b-4bb8-9790-e6dd8baaa596",
     "prev": "1eb71078-a076-49a3-b399-7b00d19bf154",
     "regions": {
      "03c25d93-3281-49da-be77-7e281ef6f8b5": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "c026476c-371c-4f75-8754-21fe897e324c",
        "part": "whole"
       },
       "id": "03c25d93-3281-49da-be77-7e281ef6f8b5"
      }
     }
    },
    "22a5b54c-6bab-4a6a-9e2a-284251395517": {
     "id": "22a5b54c-6bab-4a6a-9e2a-284251395517",
     "prev": "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f",
     "regions": {
      "d6ba9f77-cf66-4d48-b250-aeb275df6249": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "cb50812e-6786-4637-8875-4192cc230fcf",
        "part": "whole"
       },
       "id": "d6ba9f77-cf66-4d48-b250-aeb275df6249"
      }
     }
    },
    "236a6645-3284-442b-8949-2d8c3862d978": {
     "id": "236a6645-3284-442b-8949-2d8c3862d978",
     "prev": "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d",
     "regions": {
      "d92c8c26-6cd8-465f-afd0-62367f0b167f": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "05ce1f79-4f0b-445b-95a7-fba4ddf88b56",
        "part": "whole"
       },
       "id": "d92c8c26-6cd8-465f-afd0-62367f0b167f"
      }
     }
    },
    "23e8d199-7954-4110-aa00-268a4780d229": {
     "id": "23e8d199-7954-4110-aa00-268a4780d229",
     "prev": "1d7bd639-1931-42bc-ab90-9fe0f2f4feae",
     "regions": {
      "318a5ace-e981-4c5f-91a3-eaba49b0f4f0": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3c02fca1-76e3-45f8-8a66-71708b4ddc6b",
        "part": "whole"
       },
       "id": "318a5ace-e981-4c5f-91a3-eaba49b0f4f0"
      }
     }
    },
    "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c": {
     "id": "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c",
     "prev": "c8c721ae-658b-4ab2-9d84-b90908992724",
     "regions": {
      "859f277d-69eb-4bb6-b250-09f2f3b0c7d4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "534391af-839f-4ee6-b6d3-cccc89272bad",
        "part": "whole"
       },
       "id": "859f277d-69eb-4bb6-b250-09f2f3b0c7d4"
      }
     }
    },
    "27b11791-c0ea-4bea-9fbf-63fa48817d50": {
     "id": "27b11791-c0ea-4bea-9fbf-63fa48817d50",
     "prev": "3c6725f6-bc47-40a9-94e2-014861c0aaa9",
     "regions": {
      "fcc64b20-b382-4958-90c1-1af02266472b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "fe95c114-6e8b-498d-9c9a-41cb8d9208ce",
        "part": "whole"
       },
       "id": "fcc64b20-b382-4958-90c1-1af02266472b"
      }
     }
    },
    "286a64ba-5991-4131-bae4-9bc5f703c587": {
     "id": "286a64ba-5991-4131-bae4-9bc5f703c587",
     "prev": "2efc19be-5e2b-49e6-b09c-ad31f997b49e",
     "regions": {
      "a76f7335-0e9b-4ab6-9cef-8a42f0e6a815": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "189c0d2e-0093-447a-866b-671dc5216b01",
        "part": "whole"
       },
       "id": "a76f7335-0e9b-4ab6-9cef-8a42f0e6a815"
      }
     }
    },
    "2b1e9a92-db79-49ba-a823-a3310a4d8b82": {
     "id": "2b1e9a92-db79-49ba-a823-a3310a4d8b82",
     "prev": "aceeab4b-ab16-432d-9f6c-5447735b45aa",
     "regions": {
      "6d8cfe60-941c-4421-bd22-baa74594e5b8": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "43bf9fa4-82e6-44a7-938d-de9304b7835b",
        "part": "whole"
       },
       "id": "6d8cfe60-941c-4421-bd22-baa74594e5b8"
      }
     }
    },
    "2efc19be-5e2b-49e6-b09c-ad31f997b49e": {
     "id": "2efc19be-5e2b-49e6-b09c-ad31f997b49e",
     "prev": "236a6645-3284-442b-8949-2d8c3862d978",
     "regions": {
      "8149b52a-52d7-41ba-8e2b-89299e7a5b12": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e9e66dc0-c61a-46a7-87b6-ac376fc2d781",
        "part": "whole"
       },
       "id": "8149b52a-52d7-41ba-8e2b-89299e7a5b12"
      }
     }
    },
    "31ea5d42-cbb0-4f5c-ba85-30991589589e": {
     "id": "31ea5d42-cbb0-4f5c-ba85-30991589589e",
     "prev": "27b11791-c0ea-4bea-9fbf-63fa48817d50",
     "regions": {
      "393db737-c5d6-47e5-92be-7cbff464bbf9": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "78e99f8a-7548-4572-b1b2-f8bec7116db0",
        "part": "whole"
       },
       "id": "393db737-c5d6-47e5-92be-7cbff464bbf9"
      }
     }
    },
    "3c6725f6-bc47-40a9-94e2-014861c0aaa9": {
     "id": "3c6725f6-bc47-40a9-94e2-014861c0aaa9",
     "prev": "ade912c4-b81e-467c-ab6f-deb527b0403e",
     "regions": {
      "026d3ebd-0e73-4da1-a754-fb7863569017": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "2e792d1e-c43e-486e-8edc-6ad23f73fa03",
        "part": "whole"
       },
       "id": "026d3ebd-0e73-4da1-a754-fb7863569017"
      }
     }
    },
    "3cd85433-8ab0-4087-8f4b-b642a04bc77d": {
     "id": "3cd85433-8ab0-4087-8f4b-b642a04bc77d",
     "prev": "69e8c329-6de9-4d81-bc36-30b914a3b1a0",
     "regions": {
      "02b1ec57-7a4a-4b12-97c8-e8322cdd61a0": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5cc3b653-680e-4d7f-b888-f84b5af084dd",
        "part": "whole"
       },
       "id": "02b1ec57-7a4a-4b12-97c8-e8322cdd61a0"
      }
     }
    },
    "3cdb3114-6e24-4903-96e2-f40297203d1a": {
     "id": "3cdb3114-6e24-4903-96e2-f40297203d1a",
     "prev": "ce5b519b-be27-475a-b316-163d53ae89b9",
     "regions": {
      "07fd106c-8632-400a-849a-21f14f01c976": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "071fe529-377f-46d0-986a-aaf7da101fef",
        "part": "whole"
       },
       "id": "07fd106c-8632-400a-849a-21f14f01c976"
      }
     }
    },
    "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8": {
     "id": "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8",
     "prev": "1bdba887-217a-43fe-9f80-bd6830d26787",
     "regions": {
      "20c3e1bf-d22d-4e64-b4e9-f2f413f846ee": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e9c0d0ef-7fb9-4d13-b0ab-12f7ef0095b9",
        "part": "whole"
       },
       "id": "20c3e1bf-d22d-4e64-b4e9-f2f413f846ee"
      }
     }
    },
    "49200624-0a03-4694-8554-e9d9e24ab75f": {
     "id": "49200624-0a03-4694-8554-e9d9e24ab75f",
     "prev": "40d9250c-0bf8-4eb1-99cd-2e27b04bc3e8",
     "regions": {
      "a1894abd-9c6f-4df2-bbae-513e0c7016b0": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "0ba86758-f1f8-4303-8546-6e7438d7b569",
        "part": "whole"
       },
       "id": "a1894abd-9c6f-4df2-bbae-513e0c7016b0"
      }
     }
    },
    "4a531b84-65c7-4b54-ba9a-329ea45c3270": {
     "id": "4a531b84-65c7-4b54-ba9a-329ea45c3270",
     "prev": "97bdcf66-ffea-49f3-b367-eb46ae8584b6",
     "regions": {
      "6e0d949c-6014-409d-b75f-6abf8df43af6": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "15d06766-c839-4390-a7c0-2ced861ea9c5",
        "part": "whole"
       },
       "id": "6e0d949c-6014-409d-b75f-6abf8df43af6"
      }
     }
    },
    "4ce88900-a885-49e9-9229-431d70ad25df": {
     "id": "4ce88900-a885-49e9-9229-431d70ad25df",
     "prev": "c790ea0b-37f6-4f69-937f-5d651da48601",
     "regions": {
      "5aff0d19-262e-4fed-bae7-286c9beb59d1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "0b453f22-b605-4285-a1f6-24d4f54865fa",
        "part": "whole"
       },
       "id": "5aff0d19-262e-4fed-bae7-286c9beb59d1"
      }
     }
    },
    "5032b6ad-f2dc-4a4a-8232-51307d785be5": {
     "id": "5032b6ad-f2dc-4a4a-8232-51307d785be5",
     "prev": "d7bb974a-4cee-417e-8ae2-37897bbda801",
     "regions": {
      "543b1253-3137-4d63-aaf4-db711a577fed": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "77640a71-1cc5-47c9-ae52-940ec6c95024",
        "part": "whole"
       },
       "id": "543b1253-3137-4d63-aaf4-db711a577fed"
      }
     }
    },
    "58f94107-080a-4c92-92d5-77572c38595a": {
     "id": "58f94107-080a-4c92-92d5-77572c38595a",
     "prev": "1537ce27-bbb3-482a-b930-61128dfaa5fc",
     "regions": {
      "aae44782-7b3b-4de1-a2cc-ff47ce8e451a": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4e2a85b7-6833-442a-bfae-cfd3fb98ca45",
        "part": "whole"
       },
       "id": "aae44782-7b3b-4de1-a2cc-ff47ce8e451a"
      }
     }
    },
    "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f": {
     "id": "5a15637b-9b0d-4d3f-a5ea-7ad444b66e0f",
     "prev": "d797644c-769d-4dca-ace3-b5b80cd83bca",
     "regions": {
      "0bb5cae3-7ee7-405a-8ec8-cdbfb326e9eb": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "85bd73dd-62e7-48c3-865f-27e20b2ffc16",
        "part": "whole"
       },
       "id": "0bb5cae3-7ee7-405a-8ec8-cdbfb326e9eb"
      }
     }
    },
    "5bd7b2f8-7942-4b57-97e3-1523fc403278": {
     "id": "5bd7b2f8-7942-4b57-97e3-1523fc403278",
     "prev": "79848694-9e95-4bfa-9589-acc949f2dc0f",
     "regions": {
      "bc5c04b7-d3f8-4fc6-958f-c29eefdedc24": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f21c577a-a8ba-4a28-95d2-f038c705804c",
        "part": "whole"
       },
       "id": "bc5c04b7-d3f8-4fc6-958f-c29eefdedc24"
      }
     }
    },
    "5e3c3e16-eff0-48cb-9523-a6711e3c73e1": {
     "id": "5e3c3e16-eff0-48cb-9523-a6711e3c73e1",
     "prev": "abc8aabe-20bf-4af1-9ffe-145f0ff4db01",
     "regions": {
      "67177a4e-b9e7-4bca-9849-6e48cda581de": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "861c638f-ec78-4001-b39c-875cce76dfdc",
        "part": "whole"
       },
       "id": "67177a4e-b9e7-4bca-9849-6e48cda581de"
      }
     }
    },
    "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde": {
     "id": "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde",
     "prev": "a64a9a11-1ada-4951-bb3e-7b545e7ae93e",
     "regions": {
      "4a412fda-3924-463f-8925-e98ee61eeb22": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "39788369-262a-49c6-a335-a90b04bc57b0",
        "part": "whole"
       },
       "id": "4a412fda-3924-463f-8925-e98ee61eeb22"
      }
     }
    },
    "60066575-1881-4528-93eb-300c304a4342": {
     "id": "60066575-1881-4528-93eb-300c304a4342",
     "prev": "6ebd9705-73b1-40a7-81ba-52661f96afe2",
     "regions": {
      "07702d81-3992-4081-ad46-48df67b3409b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "bd505a24-4f2d-4f14-9a90-126ad2c5c2ea",
        "part": "whole"
       },
       "id": "07702d81-3992-4081-ad46-48df67b3409b"
      }
     }
    },
    "6522066d-1956-47bc-ae36-5912628d835f": {
     "id": "6522066d-1956-47bc-ae36-5912628d835f",
     "prev": "a8ae03d3-7805-40c7-be3d-9c52caaf52fd",
     "regions": {
      "545af007-b9ee-4da3-b3b3-600cd315a182": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "bfb9ef9f-8bcf-4100-8c99-57bf8959c57b",
        "part": "whole"
       },
       "id": "545af007-b9ee-4da3-b3b3-600cd315a182"
      }
     }
    },
    "66942006-40b7-4b08-94c1-ab4b27693b7c": {
     "id": "66942006-40b7-4b08-94c1-ab4b27693b7c",
     "prev": "e446495f-108d-45f6-ba1a-a969b912750b",
     "regions": {
      "9e983782-98b1-4956-9e92-a3b1dc7ffbd7": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "96bc8eb2-feff-46e5-b296-729b4de0039a",
        "part": "whole"
       },
       "id": "9e983782-98b1-4956-9e92-a3b1dc7ffbd7"
      }
     }
    },
    "69e8c329-6de9-4d81-bc36-30b914a3b1a0": {
     "id": "69e8c329-6de9-4d81-bc36-30b914a3b1a0",
     "prev": "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952",
     "regions": {
      "79df5a58-e178-4551-b8f1-033c41cde61a": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "80e8a873-9828-444d-9c44-e5d980c7c0eb",
        "part": "whole"
       },
       "id": "79df5a58-e178-4551-b8f1-033c41cde61a"
      }
     }
    },
    "6ebd9705-73b1-40a7-81ba-52661f96afe2": {
     "id": "6ebd9705-73b1-40a7-81ba-52661f96afe2",
     "prev": "31ea5d42-cbb0-4f5c-ba85-30991589589e",
     "regions": {
      "e384199c-40a6-40f6-8c82-b13b14aa13a1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "fdd83dc1-2853-4125-8090-947f35da5a5c",
        "part": "whole"
       },
       "id": "e384199c-40a6-40f6-8c82-b13b14aa13a1"
      }
     }
    },
    "74760939-8196-4861-a640-82556ac326e0": {
     "id": "74760939-8196-4861-a640-82556ac326e0",
     "prev": "7714a1fd-114e-4a07-b7df-09dac566ef2c",
     "regions": {
      "27056150-d637-4a50-b7e3-e93cc1841a31": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "636d18ab-b153-4566-81d5-3b608284d2e4",
        "part": "whole"
       },
       "id": "27056150-d637-4a50-b7e3-e93cc1841a31"
      }
     }
    },
    "75639f5b-0444-4adf-bc17-6fa09cd11e4f": {
     "id": "75639f5b-0444-4adf-bc17-6fa09cd11e4f",
     "prev": "23e8d199-7954-4110-aa00-268a4780d229",
     "regions": {
      "91414a49-bc36-4d94-841d-cf621cbd1d2b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "97260746-1fd8-4fa0-8c0f-1a71a4a54c11",
        "part": "whole"
       },
       "id": "91414a49-bc36-4d94-841d-cf621cbd1d2b"
      }
     }
    },
    "7714a1fd-114e-4a07-b7df-09dac566ef2c": {
     "id": "7714a1fd-114e-4a07-b7df-09dac566ef2c",
     "prev": "ad309bb4-6c88-4e11-8449-6ae247c95ab8",
     "regions": {
      "b81b7f31-0342-46c9-9d8d-c0e3727c84c9": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "96dc1ad2-d5db-4ed7-931d-cdd3107f3fd5",
        "part": "whole"
       },
       "id": "b81b7f31-0342-46c9-9d8d-c0e3727c84c9"
      }
     }
    },
    "79848694-9e95-4bfa-9589-acc949f2dc0f": {
     "id": "79848694-9e95-4bfa-9589-acc949f2dc0f",
     "prev": "4ce88900-a885-49e9-9229-431d70ad25df",
     "regions": {
      "aad0690b-c3a1-4ed8-8572-0a96aa217605": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "02caf31c-8652-445c-a8a3-f257bb2e1bb4",
        "part": "whole"
       },
       "id": "aad0690b-c3a1-4ed8-8572-0a96aa217605"
      }
     }
    },
    "80edbb16-b6a1-4233-8833-0d4f6addea00": {
     "id": "80edbb16-b6a1-4233-8833-0d4f6addea00",
     "prev": "5e3c3e16-eff0-48cb-9523-a6711e3c73e1",
     "regions": {
      "c202597f-d64f-42b6-aa97-b71b020ac093": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d7fdbdf8-251b-4756-9e47-ac3110b5c849",
        "part": "whole"
       },
       "id": "c202597f-d64f-42b6-aa97-b71b020ac093"
      }
     }
    },
    "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3": {
     "id": "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3",
     "prev": null,
     "regions": {
      "1bfa9a1a-2f0a-48de-a2d3-b66b1df07933": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "b4d399ae-27e7-426f-a2ac-c79b5a6cb02f",
        "part": "whole"
       },
       "id": "1bfa9a1a-2f0a-48de-a2d3-b66b1df07933"
      }
     }
    },
    "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55": {
     "id": "8c8a0fc3-6191-447e-a2e8-ad5c66d7bb55",
     "prev": "aa9424f6-6619-449d-83af-4719ad42e3ae",
     "regions": {
      "30fe711c-8907-45d6-ac55-ac30de2b2a98": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "5ec8bf14-57ad-4e1b-8b13-d7da42924760",
        "part": "whole"
       },
       "id": "30fe711c-8907-45d6-ac55-ac30de2b2a98"
      }
     }
    },
    "8e9740f7-a327-4809-a72a-65cad5c3720c": {
     "id": "8e9740f7-a327-4809-a72a-65cad5c3720c",
     "prev": "23ea59ee-f9eb-4bbd-9abf-fe2faf91940c",
     "regions": {
      "f980d771-df3b-45ae-afac-fea9d27c7ab4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "99eac7dc-c7d5-419c-afd4-1e7a8a6ef96e",
        "part": "whole"
       },
       "id": "f980d771-df3b-45ae-afac-fea9d27c7ab4"
      }
     }
    },
    "9063a41d-0c8f-46e6-b1b2-af0f273651f9": {
     "id": "9063a41d-0c8f-46e6-b1b2-af0f273651f9",
     "prev": "5e6bfa51-005a-4ac3-a6bb-4c7f0de82fde",
     "regions": {
      "32d58d61-c9a4-4551-9832-32720bffd761": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "adce5d12-902d-4b0a-9e33-7f6ff2a1685d",
        "part": "whole"
       },
       "id": "32d58d61-c9a4-4551-9832-32720bffd761"
      }
     }
    },
    "93d373b9-1605-42b8-b613-65a22a86457a": {
     "id": "93d373b9-1605-42b8-b613-65a22a86457a",
     "prev": "b7f6b015-7ae2-4473-abfe-2350ff7b7a74",
     "regions": {
      "b311a3ed-17e1-4f3d-88cc-65dc7adb7576": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7ff35116-bcd8-4402-880d-f6d3c8071a67",
        "part": "whole"
       },
       "id": "b311a3ed-17e1-4f3d-88cc-65dc7adb7576"
      }
     }
    },
    "94c99125-eda5-43c9-8a6e-4e25b65c3ad7": {
     "id": "94c99125-eda5-43c9-8a6e-4e25b65c3ad7",
     "prev": "a1b0d131-cc76-4359-8b13-57092129f3ee",
     "regions": {
      "c8616b9f-4328-4545-bb21-e73a43e25082": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "ff3fd202-2ddb-4a3a-b28a-e68b99afe8b1",
        "part": "whole"
       },
       "id": "c8616b9f-4328-4545-bb21-e73a43e25082"
      }
     }
    },
    "97bdcf66-ffea-49f3-b367-eb46ae8584b6": {
     "id": "97bdcf66-ffea-49f3-b367-eb46ae8584b6",
     "prev": "94c99125-eda5-43c9-8a6e-4e25b65c3ad7",
     "regions": {
      "2dd96cf8-aba6-4e94-be3b-5a434e544cbc": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "0c0c8cad-eaee-44e5-9a17-5186cf661c91",
        "part": "whole"
       },
       "id": "2dd96cf8-aba6-4e94-be3b-5a434e544cbc"
      }
     }
    },
    "9ee094cd-3ad0-401d-8544-abc9b7f8910f": {
     "id": "9ee094cd-3ad0-401d-8544-abc9b7f8910f",
     "prev": "06fdad76-73ed-4bb9-9008-d3c9117eb783",
     "regions": {
      "bfc2695a-953a-44d2-a952-4e26f8c555ef": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "30fc4b21-e1d3-4823-b437-4e300f2f07b9",
        "part": "whole"
       },
       "id": "bfc2695a-953a-44d2-a952-4e26f8c555ef"
      }
     }
    },
    "a06df86d-1723-47b7-a3c5-3b42a1867829": {
     "id": "a06df86d-1723-47b7-a3c5-3b42a1867829",
     "prev": "4a531b84-65c7-4b54-ba9a-329ea45c3270",
     "regions": {
      "fac15ceb-c752-4113-9952-2b56d8266204": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "cf445208-e3a7-4baf-8c23-cc3a460bc34a",
        "part": "whole"
       },
       "id": "fac15ceb-c752-4113-9952-2b56d8266204"
      }
     }
    },
    "a1b0d131-cc76-4359-8b13-57092129f3ee": {
     "id": "a1b0d131-cc76-4359-8b13-57092129f3ee",
     "prev": "22a5b54c-6bab-4a6a-9e2a-284251395517",
     "regions": {
      "74c6031a-0a08-4221-99e1-434276672e84": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "48e14a23-1f2a-4b8e-a439-950dd9975515",
        "part": "whole"
       },
       "id": "74c6031a-0a08-4221-99e1-434276672e84"
      }
     }
    },
    "a64a9a11-1ada-4951-bb3e-7b545e7ae93e": {
     "id": "a64a9a11-1ada-4951-bb3e-7b545e7ae93e",
     "prev": "223ff166-4f0b-4bb8-9790-e6dd8baaa596",
     "regions": {
      "8733407c-3582-4cb8-bd3e-d92e851f5c61": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "42faa621-3766-4ef9-adc8-f8a1f1e7cc5f",
        "part": "whole"
       },
       "id": "8733407c-3582-4cb8-bd3e-d92e851f5c61"
      }
     }
    },
    "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e": {
     "id": "a71c3f64-e3c1-4810-b2f1-dc1d3f19582e",
     "prev": "286a64ba-5991-4131-bae4-9bc5f703c587",
     "regions": {
      "1fcc4a10-48c2-47fa-8a46-e99cf060e1b1": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7bb9f155-8411-4e5c-af83-da460ef3d52d",
        "part": "whole"
       },
       "id": "1fcc4a10-48c2-47fa-8a46-e99cf060e1b1"
      }
     }
    },
    "a8ae03d3-7805-40c7-be3d-9c52caaf52fd": {
     "id": "a8ae03d3-7805-40c7-be3d-9c52caaf52fd",
     "prev": "9ee094cd-3ad0-401d-8544-abc9b7f8910f",
     "regions": {
      "ff7e8867-e66c-43bc-9c27-493cc2099901": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7ccc0315-1973-4d63-849a-246a327f7e98",
        "part": "whole"
       },
       "id": "ff7e8867-e66c-43bc-9c27-493cc2099901"
      }
     }
    },
    "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2": {
     "id": "a90c03e9-50ce-4af3-ac3e-ad0a6517f2b2",
     "prev": "e778dcb9-b482-4919-81af-f22fde87e026",
     "regions": {
      "cf9adabf-24a2-4502-95a2-37b7be2873b7": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "7fa5fa37-e894-4caa-8052-55d6ce2677d4",
        "part": "whole"
       },
       "id": "cf9adabf-24a2-4502-95a2-37b7be2873b7"
      }
     }
    },
    "aa9424f6-6619-449d-83af-4719ad42e3ae": {
     "id": "aa9424f6-6619-449d-83af-4719ad42e3ae",
     "prev": "828f54ef-bb4f-4628-8fdd-f9dcb6afccc3",
     "regions": {
      "c0187196-5d1f-4e9a-8ce2-67253da07c3e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "8dbcdbe6-b5e4-4803-b5bf-d591a1c0c4c4",
        "part": "whole"
       },
       "id": "c0187196-5d1f-4e9a-8ce2-67253da07c3e"
      }
     }
    },
    "abc8aabe-20bf-4af1-9ffe-145f0ff4db01": {
     "id": "abc8aabe-20bf-4af1-9ffe-145f0ff4db01",
     "prev": "5032b6ad-f2dc-4a4a-8232-51307d785be5",
     "regions": {
      "24ea2c92-f65c-4976-b7d6-a8d5c2cc1c02": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "69a559a9-9d4f-43d5-bc83-12c2b0abc776",
        "part": "whole"
       },
       "id": "24ea2c92-f65c-4976-b7d6-a8d5c2cc1c02"
      }
     }
    },
    "aceeab4b-ab16-432d-9f6c-5447735b45aa": {
     "id": "aceeab4b-ab16-432d-9f6c-5447735b45aa",
     "prev": "3cdb3114-6e24-4903-96e2-f40297203d1a",
     "regions": {
      "270384cc-6c46-496e-be93-9308489cb2d6": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "e172a934-fc99-4cd9-81ab-1afcc9875423",
        "part": "whole"
       },
       "id": "270384cc-6c46-496e-be93-9308489cb2d6"
      }
     }
    },
    "ad309bb4-6c88-4e11-8449-6ae247c95ab8": {
     "id": "ad309bb4-6c88-4e11-8449-6ae247c95ab8",
     "prev": "a06df86d-1723-47b7-a3c5-3b42a1867829",
     "regions": {
      "e717a043-952a-4207-af94-f7b1063c007e": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "9689610e-f181-4377-a878-aeaf261e8567",
        "part": "whole"
       },
       "id": "e717a043-952a-4207-af94-f7b1063c007e"
      }
     }
    },
    "ade912c4-b81e-467c-ab6f-deb527b0403e": {
     "id": "ade912c4-b81e-467c-ab6f-deb527b0403e",
     "prev": "6522066d-1956-47bc-ae36-5912628d835f",
     "regions": {
      "dc9001c6-926e-4b85-b76f-3daebf26aca0": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "1d33ae35-b5e7-4ccc-8c63-39831848cbed",
        "part": "whole"
       },
       "id": "dc9001c6-926e-4b85-b76f-3daebf26aca0"
      }
     }
    },
    "b7f6b015-7ae2-4473-abfe-2350ff7b7a74": {
     "id": "b7f6b015-7ae2-4473-abfe-2350ff7b7a74",
     "prev": "13af60a5-502c-409f-b1db-306d3546673e",
     "regions": {
      "6f9ffdd1-72d7-45ea-80a5-27017764d19b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d5241d34-488d-4175-b8a8-a241226b7a3c",
        "part": "whole"
       },
       "id": "6f9ffdd1-72d7-45ea-80a5-27017764d19b"
      }
     }
    },
    "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d": {
     "id": "ba50a6b2-dc8e-4d6c-aad2-73e8ad79009d",
     "prev": "e2c44a3e-8997-499b-b2f5-c033ce4782cb",
     "regions": {
      "ef670ea7-c5aa-477e-8b12-873019747b45": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "38788d23-75be-41f6-9145-ce2c398f2822",
        "part": "whole"
       },
       "id": "ef670ea7-c5aa-477e-8b12-873019747b45"
      }
     }
    },
    "bf9a2ce6-4a53-4f90-97aa-64c615b42af4": {
     "id": "bf9a2ce6-4a53-4f90-97aa-64c615b42af4",
     "prev": "75639f5b-0444-4adf-bc17-6fa09cd11e4f",
     "regions": {
      "177e3268-4533-434e-98c4-431fa298f314": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "c4aafc17-eed8-4830-8333-02a98f4ccb8b",
        "part": "whole"
       },
       "id": "177e3268-4533-434e-98c4-431fa298f314"
      }
     }
    },
    "c790ea0b-37f6-4f69-937f-5d651da48601": {
     "id": "c790ea0b-37f6-4f69-937f-5d651da48601",
     "prev": "9063a41d-0c8f-46e6-b1b2-af0f273651f9",
     "regions": {
      "14718b54-effc-4274-b93a-3f004c2de83a": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "32b2eb7b-1f5b-45dc-bb9b-0913756c1358",
        "part": "whole"
       },
       "id": "14718b54-effc-4274-b93a-3f004c2de83a"
      }
     }
    },
    "c81bbceb-6c06-4989-ab5d-4e0002ed988e": {
     "id": "c81bbceb-6c06-4989-ab5d-4e0002ed988e",
     "prev": "f4456832-176a-43f1-b5c7-42607ca0a1ba",
     "regions": {
      "612f5fd0-05ce-40c6-94bf-01c174e2f6d4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "42af5ecb-6024-4366-94ef-a3e32a6db894",
        "part": "whole"
       },
       "id": "612f5fd0-05ce-40c6-94bf-01c174e2f6d4"
      }
     }
    },
    "c8c721ae-658b-4ab2-9d84-b90908992724": {
     "id": "c8c721ae-658b-4ab2-9d84-b90908992724",
     "prev": "1e187c07-2118-486e-abbc-0fbb90d33727",
     "regions": {
      "798f0056-6bf6-4ad5-8e2d-e4be0ecd3282": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "8ee08570-75e7-4d93-8c2a-a46fd707c7ed",
        "part": "whole"
       },
       "id": "798f0056-6bf6-4ad5-8e2d-e4be0ecd3282"
      }
     }
    },
    "ce5b519b-be27-475a-b316-163d53ae89b9": {
     "id": "ce5b519b-be27-475a-b316-163d53ae89b9",
     "prev": "d1d19576-767a-4986-9673-60710110c7cf",
     "regions": {
      "9d4fce6c-372a-4cdc-911f-f3e250c5fb1b": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "71aad76b-3065-4bc6-b778-547ed96aaea6",
        "part": "whole"
       },
       "id": "9d4fce6c-372a-4cdc-911f-f3e250c5fb1b"
      }
     }
    },
    "d1d19576-767a-4986-9673-60710110c7cf": {
     "id": "d1d19576-767a-4986-9673-60710110c7cf",
     "prev": "5bd7b2f8-7942-4b57-97e3-1523fc403278",
     "regions": {
      "5e9a49bd-3397-466d-a7a1-a98d3f67d2d2": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "37e58043-93b4-427b-ba89-ac5175983835",
        "part": "whole"
       },
       "id": "5e9a49bd-3397-466d-a7a1-a98d3f67d2d2"
      }
     }
    },
    "d797644c-769d-4dca-ace3-b5b80cd83bca": {
     "id": "d797644c-769d-4dca-ace3-b5b80cd83bca",
     "prev": "93d373b9-1605-42b8-b613-65a22a86457a",
     "regions": {
      "ade6c14b-8434-44c3-acdc-3bd0627963af": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "3af0c210-e6b4-4eed-9e59-f6a6b4ecf677",
        "part": "whole"
       },
       "id": "ade6c14b-8434-44c3-acdc-3bd0627963af"
      }
     }
    },
    "d7bb974a-4cee-417e-8ae2-37897bbda801": {
     "id": "d7bb974a-4cee-417e-8ae2-37897bbda801",
     "prev": "c81bbceb-6c06-4989-ab5d-4e0002ed988e",
     "regions": {
      "a08eea5d-f846-447a-9b1a-4e92d5af1c14": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "874d2766-f8ac-47c6-8315-fb5ff2c1016b",
        "part": "whole"
       },
       "id": "a08eea5d-f846-447a-9b1a-4e92d5af1c14"
      }
     }
    },
    "e2c44a3e-8997-499b-b2f5-c033ce4782cb": {
     "id": "e2c44a3e-8997-499b-b2f5-c033ce4782cb",
     "prev": "067d3558-5fe3-4116-aafd-0d1ac44c460a",
     "regions": {
      "57ccbf20-430c-4a3e-9cd1-4132802cd5b5": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d4e520ac-1237-43a3-9364-64aad7136867",
        "part": "whole"
       },
       "id": "57ccbf20-430c-4a3e-9cd1-4132802cd5b5"
      }
     }
    },
    "e2e22cc1-0ad6-4045-845e-0ef700d2e83e": {
     "id": "e2e22cc1-0ad6-4045-845e-0ef700d2e83e",
     "prev": "bf9a2ce6-4a53-4f90-97aa-64c615b42af4",
     "regions": {
      "ba8e9e1b-44ff-4dbb-a8ce-27b7fbb4a22d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "b8b90419-d1ec-4439-890e-9717780094b3",
        "part": "whole"
       },
       "id": "ba8e9e1b-44ff-4dbb-a8ce-27b7fbb4a22d"
      }
     }
    },
    "e446495f-108d-45f6-ba1a-a969b912750b": {
     "id": "e446495f-108d-45f6-ba1a-a969b912750b",
     "prev": "8e9740f7-a327-4809-a72a-65cad5c3720c",
     "regions": {
      "64cc2992-3254-4026-925e-3c5948953d3d": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "f47df73d-5867-4efe-b999-d4ce1b83c7dd",
        "part": "whole"
       },
       "id": "64cc2992-3254-4026-925e-3c5948953d3d"
      }
     }
    },
    "e688f732-8379-4090-baee-d74e938ba845": {
     "id": "e688f732-8379-4090-baee-d74e938ba845",
     "prev": "49200624-0a03-4694-8554-e9d9e24ab75f",
     "regions": {
      "888a7e34-06b6-4a42-88d5-899aa7e2bfd4": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4773db1d-567a-42b6-9c33-79b6fa0b96a6",
        "part": "whole"
       },
       "id": "888a7e34-06b6-4a42-88d5-899aa7e2bfd4"
      }
     }
    },
    "e778dcb9-b482-4919-81af-f22fde87e026": {
     "id": "e778dcb9-b482-4919-81af-f22fde87e026",
     "prev": "e2e22cc1-0ad6-4045-845e-0ef700d2e83e",
     "regions": {
      "aa89fea5-9aa9-4ac5-9d99-610c673fd606": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "4519e7df-5d72-44be-ab36-44c1e2d04268",
        "part": "whole"
       },
       "id": "aa89fea5-9aa9-4ac5-9d99-610c673fd606"
      }
     }
    },
    "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952": {
     "id": "ea8db5d2-d9d8-4c6a-abe9-72f81aea2952",
     "prev": "58f94107-080a-4c92-92d5-77572c38595a",
     "regions": {
      "d7661bbb-ffb2-449c-b7db-0c4a3de5b092": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "bd1de069-0df7-48bc-83f7-f5e061a7d06e",
        "part": "whole"
       },
       "id": "d7661bbb-ffb2-449c-b7db-0c4a3de5b092"
      }
     }
    },
    "f4456832-176a-43f1-b5c7-42607ca0a1ba": {
     "id": "f4456832-176a-43f1-b5c7-42607ca0a1ba",
     "prev": "60066575-1881-4528-93eb-300c304a4342",
     "regions": {
      "ffef117a-cb35-43dc-8590-a61b23f082db": {
       "attrs": {
        "height": 0.8,
        "width": 0.8,
        "x": 0.1,
        "y": 0.1
       },
       "content": {
        "cell": "d9f646a4-f5b9-482b-aaf2-eaa055292db0",
        "part": "whole"
       },
       "id": "ffef117a-cb35-43dc-8590-a61b23f082db"
      }
     }
    }
   },
   "themes": {}
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "422.857px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_position": {
    "height": "413.143px",
    "left": "0px",
    "right": "914.384px",
    "top": "134.857px",
    "width": "182.759px"
   },
   "toc_section_display": "block",
   "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": 1
}