{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Chapitre 10 : \"Programmation avancée\"\n",
    "\n",
    "### <span class=\"bg-info\">« *Informatique : rencontre de la logique formelle et du fer à souder* »</span>\n",
    "\n",
    "Maurice Nivat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <span class=\"bg-success\">CE QU'IL FAUT RETENIR</span>\n",
    "\n",
    "**Techniques procédurales**\n",
    "\n",
    "- L'introspection permet d'avoir des informations sur les données manipulées au moment de l'exécution.\n",
    "- Les gestionnaires de contexte offrent une sécurité en mettant en place des blocs de code assurant que l'appel du code de *finition* est bien réalisé dans tous les cas.\n",
    "- Les fonctions récursives facilitent des traitements sur des données imbriquées en arborescence.\n",
    "- Les expressions en compréhension des listes, dictionnaires et ensembles permettent d'avoir une syntaxe simple réalisant implicitement des boucles de calcul pour construire les valeurs.\n",
    "- Les générateurs en compréhension permettent, avec le même genre de syntaxe, de produire des valeurs au fur et à mesure des besoins.\n",
    "- La définition de fonctions incluses couplées à la fermeture (capture de données du contexte) permet de produire des fonctions paramétrées adaptées au besoin.\n",
    "- Les décorateurs offrent un moyen d'enrichir les définitions de fonctions ou de classes par des mécanismes communs.\n",
    "\n",
    "**Techniques objets**\n",
    "\n",
    "- Les fonctions sont des objets de premier niveau, manipulables comme toute donnée.\n",
    "- Outre la définition par `def`, on distingue plus largement les *functors* : il est possible de donner à des objets le comportement de fonctions.\n",
    "- Les accesseurs permettent de définir des méthodes qui seront appelées lorsque des attributs particuliers seront accédés en lecture ou en modification.\n",
    "- Le duck typing consiste à s'affranchir de la définition stricte d'une hiérarchie de type en considérant qu'il suffit qu'un objet fournisse la bonne *interface* (les bonnes méthodes) pour qu'il soit utilisable.\n",
    "\n",
    "**Techniques fonctionnelles**\n",
    "\n",
    "- Autre *functor*, les fonctions-expressions `lamda`.\n",
    "- Les opérateurs issus de la programmation fonctionnelle, `map`, `filter` et `reduce`, sont disponibles en Python (mais on leur préfère souvent les expressions en compréhension).\n",
    "- L'application partielle de fonction (PFA) permet de créer des raccourcis pour des fonctions, fournissant d'office certains paramètres.\n",
    "- La programmation fonctionnelle pure consiste à définir des fonctions dont le résultat ne dépend que de leurs paramètres, et qui n'ont aucun effet de bord (ne touchent ni les globales, ni leurs paramètres). Cela permet de définir des fonctions facilement vérifiables.\n",
    "\n",
    "**Persistance et sérialisation**\n",
    "\n",
    "- La sérialisation est la représentation des données sous forme de flots d'octets interprétables.\n",
    "- La persistance est l'enregistrement de ces flots d'octets sur un support permettant la relecture ultérieure.\n",
    "- Pickle et JSON sont deux des formats possibles pour la persistance des données en Python ; Pickle est limité au monde Python mais JSON permet d'échanger des données avec d'autres langages de programmation.\n",
    "- Les bases de données relationnelles et la librairie légère `sqlite3` sont aussi un moyen de stocker des données d'une façon structurée et lisible par d'autres langages de programmation.\n",
    "\n",
    "**Tests**\n",
    "\n",
    "- Tests unitaires pour vérifier qu'une fonction réalise bien le service qui est attendu.\n",
    "- Tests fonctionnels pour vérifier qu'un programme complet offre les services pour lequel il a été écrit, qu'il respecte bien le *cahier des charges*.\n",
    "- Python offre des outils pour automatiser ces tests.\n",
    "\n",
    "**Documentation des sources**\n",
    "\n",
    "- Les documentations des modules / classes / fonctions / méthodes, directement dans les fichiers sources, peuvent être enrichies avec des fichiers de documentation externe.\n",
    "- Le format reStructuredText (reST) permet d'écrire la documentation avec une syntaxe textuelle simple, à partir de laquelle différents formats de sortie peuvent être générés.\n",
    "- Cette documentation peut contenir des exemples d'utilisation qui font partie de tests.\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_01 ✓\n",
    "\n",
    "Utiliser une liste en compréhension pour ajouter 3 à chaque élément d’une liste d’entiers impairs inférieurs à 20, mais seulement si l’élément est supérieur ou égal à 8. Afficher la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_01"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_02 ✓\n",
    "\n",
    "Utiliser une liste en compréhension pour calculer la somme d’une liste d’entiers de 0 à 9. Afficher la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_02"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_03 ✓\n",
    "\n",
    "Utiliser deux boucles `for` imbriquées dans une liste en compréhension pour obtenir la liste :\n",
    "```python\n",
    "['ad', 'ae', 'bd', 'be', 'cd', 'ce']\n",
    "```\n",
    "à partir des chaînes `\"abc\"` et `\"de\"`.\n",
    "\n",
    "Afficher la liste."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_03"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_04 ✓\n",
    "\n",
    "Écrire une fonction `compterMots(nom_fichier)` qui renvoie un dictionnaire contenant la fréquence de tous les mots du fichier texte passé en argument. On utilisera, par exemple, le fichier `bateauivre.txt` (`\"../data/indata_exo05_bateauivre.txt\"`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_04"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_05 ✓✓\n",
    "\n",
    "Pour faire des calculs sur les matrices carrées, on peut utiliser la structure de données \"liste de listes\" et indexer un élément de la 3<sup>e</sup> ligne et 4<sup>e</sup> colonne de la matrice `m` par `m[2][3]` (compte tenu du fait que les indices commencent à 0).\n",
    "\n",
    "On déclare trois matrices carrées de dimension $N$ : `m1`, `m2` et `m3` contenant des entiers.  \n",
    "On affecte `m1`, ligne à ligne, par les $N^2$ premiers entiers pairs commençant à 2 ; `m2` est la matrice unité, c’est-à-dire qu’elle contient des 1 sur la diagonale principle (NW-SE) et des 0 partout ailleurs.\n",
    "\n",
    "Calculer et afficher `m3 = m1 − m2` pour $N = 5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_05"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_06 ✓✓✓\n",
    "\n",
    "Il s'agit de traduire un brin d'ADN en une chaîne d'acides aminés.\n",
    "Pour cela, on va découper la séquence en **codons**, c'est-à-dire en triplets de 3 bases nucléiques (pour nous en chaînes de 3 caractères), puis, à l'aide du dictionnaire fourni (le « code génétique »), nous allons construire la chaîne d'acides aminés correspondante.\n",
    "\n",
    "Voici le **code génétique**, correspondance entre un codon et un acide aminé :\n",
    "```python\n",
    "lookup_table = {\n",
    "    'UUU': 'F', 'UCU': 'S', 'UAU': 'Y', 'UGU': 'C',\n",
    "    'UUC': 'F', 'UCC': 'S', 'UAC': 'Y', 'UGC': 'C',\n",
    "    'UUA': 'L', 'UCA': 'S', 'UAA': '#', 'UGA': '#',\n",
    "    'UUG': 'L', 'UCG': 'S', 'UAG': '#', 'UGG': 'W',\n",
    "    'CUU': 'L', 'CCU': 'P', 'CAU': 'H', 'CGU': 'R',\n",
    "    'CUC': 'L', 'CCC': 'P', 'CAC': 'H', 'CGC': 'R',\n",
    "    'CUA': 'L', 'CCA': 'P', 'CAA': 'Q', 'CGA': 'R',\n",
    "    'CUG': 'L', 'CCG': 'P', 'CAG': 'Q', 'CGG': 'R',\n",
    "    'AUU': 'I', 'ACU': 'T', 'AAU': 'N', 'AGU': 'S',\n",
    "    'AUC': 'I', 'ACC': 'T', 'AAC': 'N', 'AGC': 'S',\n",
    "    'AUA': 'I', 'ACA': 'T', 'AAA': 'K', 'AGA': 'R',\n",
    "    'AUG': 'M', 'ACG': 'T', 'AAG': 'K', 'AGG': 'R',\n",
    "    'GUU': 'V', 'GCU': 'A', 'GAU': 'D', 'GGU': 'G',\n",
    "    'GUC': 'V', 'GCC': 'A', 'GAC': 'D', 'GGC': 'G',\n",
    "    'GUA': 'V', 'GCA': 'A', 'GAA': 'E', 'GGA': 'G',\n",
    "    'GUG': 'V', 'GCG': 'A', 'GAG': 'E', 'GGG': 'G',\n",
    "}\n",
    "```\n",
    "\n",
    "La chaîne d'ADN à traduire est dans le fichier texte `\"../data/indata_exo10_adn.txt\"` dont on lira le contenu.\n",
    "\n",
    "Écrire une première fonction `translate_dna_to_rna(dna)` qui traduise cette chaîne d'ADN en ARN en remplaçant toutes les bases `'T'` en base `'U'`.\n",
    "\n",
    "Écrire une seconde fonction `translate_rna_to_amino_acids(rna)` qui effectue la traduction demandée. À l'aide du dictionnaire du code génétique (`lookup_table`), découper l'ARN en codons et construire la chaîne d'acides aminés résultante. \n",
    "Si la chaîne d'ARN en entrée ne comporte pas un nombre de bases multiple de 3, ignorer les lettres superflues en fin de chaîne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_06"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_07 ✓✓✓\n",
    "\n",
    "Il s'agit de produire l'**index** d'une séquence d'ADN (pour nous, d'une chaîne de caractères), c'est-à-dire que l'on veut afficher toutes les positions de tous les triplets issus d'une chaîne.\n",
    "\n",
    "Par exemple, à partir de la chaîne `\"CCTAGTCTAG\"`, on peut, par décalage, extraire tous les triplets que l'on stocke de façon  **unique** :\n",
    "```python\n",
    "'CCT'\n",
    "'CTA'\n",
    "'TAG'\n",
    "'AGT'\n",
    "'GTC'\n",
    "'TCT'\n",
    "```\n",
    "Dans notre chaîne d'exemple, ils apparaissent respectivement aux positions :\n",
    "```python\n",
    "(1,)\n",
    "(2, 7)\n",
    "(3, 8)\n",
    "(4,)\n",
    "(5,)\n",
    "(6,)\n",
    "```\n",
    "\n",
    "Écrire une fonction `indexMots(seq)` qui reçoit une séquence d'ADN et retourne un dictionnaire (l'**index**) dont les clés sont les triplets de la séquence et les valeurs un tuple des positions correspondantes.\n",
    "\n",
    "Afficher l'index de la séquence :\n",
    "```python\n",
    "s = 'TTGATCGTATGTCGTCAT'\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_07"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_08 ✓✓\n",
    "\n",
    "On se propose d'extraire le premier chiffre significatif de nombres contenus dans un fichier de données (positives) en utilisant une *expression régulière*.\n",
    "\n",
    "Plus précisément, le fichier `../data/indata_exo10_re.txt` est constitué de lignes, chacune contenant des nombres dont il faut extraire le premier chiffre. S'il s'agit d'un chiffre significatif (donc différent de 0), on va stocker sa fréquence dans un tableau. Le tableau `freq` contient donc 9 clés (`1`, `2`... `9`) et chaque clé est associée à une valeur, sa fréquence, c'est-à-dire, au nombre de fois où ce chiffre significatif aura été extrait.\n",
    "\n",
    "On demande d'afficher ce tableau"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_08"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_09 ✓\n",
    "\n",
    "La [distance de Hamming](https://fr.wikipedia.org/wiki/Distance_de_Hamming) entre deux séquences nucléotidiques (pour nous, entre deux chaînes de caractères) est simplement le nombres de différences entres les caractères de même indice de deux séquences.\n",
    "\n",
    "Par exemple : `hamming(\"AATCGC\", \"ACTCGG\") = 2`, car les 2<sup>e</sup> et 6<sup>e</sup> caractères diffèrent.  \n",
    "On note $D(\"AATCGC\", \"ACTCGG\") = 2$.\n",
    "\n",
    "On donne 3 séquences :\n",
    "```python\n",
    "s1 = 'TTGCATTGCTTAGGCATA'\n",
    "s2 = 'TTGCGTTGCTTAGCCATA'\n",
    "s3 = 'TTGCAGTCCTTAGGCATT'\n",
    "```\n",
    "On demande de calculer les distances de Hamming $D(s1, s2)$, $D(s2, s3)$ et $D(s1, s3)$.\n",
    "\n",
    "On vérifiera sur l'exemple que $D$ est bien une [distance](https://fr.wikipedia.org/wiki/Distance_de_Hamming#Distance) au sens mathématique, à savoir qu'elle vérifie les propriétés :\n",
    "\n",
    "- $D(s1, s1) = 0$\n",
    "- $D(s1, s2) = D(s2, s1)$\n",
    "- $D(s1, s2) + D(s2, s3) ≥ D(s1, s3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_09"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_10 ✓✓✓\n",
    "\n",
    "On se propose de calculer **récursivement** la [distance de Hamming](https://fr.wikipedia.org/wiki/Distance_de_Hamming) entre deux chaînes de caractères.\n",
    "\n",
    "Écrire une fonction récursive `hamming(s, t)` qui reçoit deux chaînes de caractères et retourne leur distance de Hamming.\n",
    "\n",
    "On donne le pseudo-code de cette fonction :\n",
    "\n",
    "```text\n",
    "fonction Hamming(s, t : chaine) retourne entier\n",
    "    si long(s) = 0\n",
    "        retourne long(t)\n",
    "    sinon si long(t) = 0\n",
    "        retourne long(s)\n",
    "    sinon\n",
    "        distance <- 0\n",
    "        \n",
    "    si s[long(s) - 1] != t[long(t) - 1]\n",
    "        // les deux derniers caractères sont différents\n",
    "        distance <- 1\n",
    "        \n",
    "    d1 <- Hamming(s[long(s) - 1], t) + 1\n",
    "    d2 <- Hamming(s, t[long(t) - 1]) + 1\n",
    "    d1 <- Hamming(s[long(s) - 1], t[long(t) - 1]) + distance\n",
    "    \n",
    "    retourne min(d1, d2, d3)\n",
    "```\n",
    "\n",
    "Calculer la distance de Hamming entre `s = \"ramer\"` et `t = \"cases\"`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_11 ✓✓✓\n",
    "\n",
    "**Note :** Reprise de l'exercice 06_12.\n",
    "\n",
    "À partir d'un entier *N* de 4 chiffres non nuls pas tous égaux (on peut avoir plusieurs chiffres égaux, mais pas tous les 4 en même temps), on génère par permutation des chiffres le plus grand (*PG*) et le plus petit (*PP*) entier et on calcule le nouvel entier *N = PG* $-$ *PP*.\n",
    "\t\t\n",
    "On itère le processus jusqu'à obtenir la constante : 6174 (appelé [\"constante de Kaprekar\"](https://fr.wikipedia.org/wiki/Dattatreya_Ramachandra_Kaprekar))\n",
    "\t\t\n",
    "Par exemple : \n",
    "- 7068 => (8760 $-$ 678) = 8082 => (8820 $-$ 288) = 8532 => (8532 $-$ 2358) = **6174**\n",
    "- 5379 => (9753 $-$ 3579) = ** 6174 **\n",
    "\n",
    "Dans cet exercice, au lieu d'utiliser la fonction standard Python de permutation donnée à l'exercice 06_12, on demande d'écrire cette fonction de permutation sous forme récursive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# exo10_11"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
