{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapitre 10 : \"Programmation avancée\" - solutions\n",
    "\n",
    "---\n",
    "\n",
    "<table class=\"appbclp1\">\n",
    "<tr> <td style=\"font-weight: bold!;\">auteurs :</td><td style=\"text-align: left!;\">Laurent Pointal &lt;<a href=\"mailtp:laurent.pointal@limsi.fr\">laurent.pointal@limsi.fr</a>&gt; &amp; Bob Cordeau &lt;<a href=\"pycours@kordeo.eu\">pycours@kordeo.eu</a>&gt; </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">licence :</td><td style=\"text-align: left!;\">Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0) </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">source :</td><td style=\"text-align: left!;\"><a href=\"https://github.com/lpointal/appbclp\">https://github.com/lpointal/appbclp</a></td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">description :</td><td style=\"text-align: left!;\">Les programmes dans ce Notebook Jupyter servent de support au livre <span style=\"font-style: italic!;\">« Python 3 - Apprendre à  programmer dans l'écosystème Python»</span>, édition Dunod, dans lequel les différentes sections sont expliquées </td> </tr>\n",
    "<tr> <td style=\"font-weight: bold!;\">url :</td><td style=\"text-align: left!;\"><a href=\"https://www.dunod.com/sciences-techniques/python-3\">https://www.dunod.com/EAN/9782100809141</a></td> </tr>\n",
    "</table>\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_01"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_01\n",
    "\n",
    "print([(i+3 if i>= 8 else i) for i in range(1, 21, 2)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_02"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_02\n",
    "\n",
    "print(sum([i for i in range(10)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_03"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_03\n",
    "\n",
    "print([i+j for i in \"abc\" for j in \"de\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_04"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_04\n",
    "\n",
    "# import ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "from pprint import pprint  # améliore l'affichage\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def compterMots(fic):\n",
    "    freq = dict()\n",
    "    with open(fic, encoding='utf8') as f:\n",
    "        for ligne in f:\n",
    "            listeMots = ligne.split()\n",
    "            \n",
    "            for mot in listeMots:\n",
    "                if mot in freq:\n",
    "                    freq[mot] += 1\n",
    "                else:\n",
    "                    freq[mot] = 1\n",
    "    return freq\n",
    "\n",
    "# programme principal =========================================================\n",
    "freq_mots = compterMots(\"../data/indata_exo05_bateauivre.txt\")\n",
    "\n",
    "pprint(freq_mots)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On remarque que le split a découpé sur les espaces… et a donc laissé collé aux mots les signes syntaxiques (`,`, `;`, `.`…). Et on signale la classe [`Counter`](https://docs.python.org/3/library/collections.html#collections.Counter) du module `collections` qui permet de compter des occurrences d'apparitions d'informations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_05"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_05\n",
    "\n",
    "# Procédure\n",
    "def affiche(m):\n",
    "    \"Affichage d'une matrice.\"\n",
    "    for i in range(n):\n",
    "        print(\"\\t\", m[i])\n",
    "        \n",
    "# programme principal -----------------------------------------------\n",
    "n = 5  # dimension des matrices carrees\n",
    "\n",
    "# initialisation des 3 matrices:\n",
    "# on prépare les trois listes qui seront remplies avec des sous-listes\n",
    "m1, m2, m3 = [None] * n, [None] * n, [None] * n\n",
    "for i in range(n):\n",
    "    m1[i], m2[i], m3[i] = [0] * n, [0] * n, [0] * n\n",
    "    \n",
    "# calcul des matrices\n",
    "k = 2\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        # matrice d'éléments pairs\n",
    "        m1[i][j] = k\n",
    "        k += 2\n",
    "        \n",
    "        # matrice identité\n",
    "        if i == j:\n",
    "            m2[i][j] = 1  \n",
    "        \n",
    "        # calcul de m3\n",
    "        m3[i][j] = m1[i][j] - m2[i][j]  \n",
    "\n",
    "# Affichages\n",
    "print(\"m1 :\")\n",
    "affiche(m1)\n",
    "print(\"\\nm2 :\")\n",
    "affiche(m2)\n",
    "print(\"\\nm3 = m1 - m2 :\")\n",
    "affiche(m3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### exo10_06"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_06\n",
    "\"\"\"\n",
    "    Exercice adapté du MOOC bioinformatique de François Rechenmann & Thierry Parmentelat (inria)\n",
    "    https://www.fun-mooc.fr/courses/course-v1:inria+41003+selfpaced/about\n",
    "\"\"\"\n",
    "\n",
    "# Table du code génétique (correspondance codon -> acide aminé)\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",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def translate_rna_to_amino_acids(rna):\n",
    "    \"\"\"\n",
    "    Traduction d'un brin d'ARN en une chaine encodant les acides aminés correspondants. \n",
    "    \n",
    "    L'ARN en entrée est découpé en groupes de 3 bases nucléiques (codon).\n",
    "    Les lettres superflues en fin de chaine sont ignorées.\n",
    "    \"\"\"\n",
    "\n",
    "    # initialisation : la variable 'offset' indique le début d'un codon\n",
    "    offset = 0\n",
    "    longueur = len(rna)\n",
    "    resultat = ''\n",
    "    # la boucle principale\n",
    "    while offset <= longueur - 3:\n",
    "        codon = rna[offset:offset+3]\n",
    "        resultat += lookup_table[codon]\n",
    "        offset += 3  # groupe suivant\n",
    "    return resultat\n",
    "\n",
    "\n",
    "# Programme principal =========================================================\n",
    "with open(\"../chapitre_10/indata_exo10_adn.txt\", encoding='utf8') as f:\n",
    "    dna = f.read()\n",
    "\n",
    "rna = dna.replace('T', 'U')  # passage ADN => ARN\n",
    "\n",
    "# affichages\n",
    "print(\"dna :\", dna)\n",
    "print(\"rna :\", rna)\n",
    "print(\"\\nTraduction en acides aminés :\")\n",
    "print(translate_rna_to_amino_acids(rna))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_07"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_07\n",
    "\"\"\"\n",
    "    Exercice adapté du MOOC bioinformatique de François Rechenmann & Thierry Parmentelat (inria)\n",
    "    https://www.fun-mooc.fr/courses/course-v1:inria+41003+selfpaced/about\n",
    "\"\"\"\n",
    "\n",
    "# import ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "from pprint import pprint\n",
    "\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def indexMots(seq):\n",
    "    \"\"\"Retourne le dictionnaire index de la séquence.\"\"\"\n",
    "    lng = len(seq)\n",
    "    d = dict()\n",
    "\n",
    "    for i in range(lng - 2):\n",
    "        triplet = seq[i:i+3]\n",
    "        r = seq.find(triplet)\n",
    "        while r != -1:   # il peut y en avoir plusieurs...\n",
    "            # on stocke \"r+1\" pour respecter la convention algo\n",
    "            d.setdefault(triplet, set()).add(r+1)\n",
    "            r = seq.find(triplet, r+1)\n",
    "\n",
    "    return d\n",
    "\n",
    "# Programme principal =========================================================\n",
    "s = 'TTGATCGTATGTCGTCAT'\n",
    "pprint(indexMots(s))  # affiche le dictionnaire ordonné suivant les triplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_08"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_08\n",
    "\n",
    "# Import ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "import re\n",
    "from pprint import pprint\n",
    "\n",
    "\n",
    "# Programme principal =========================================================\n",
    "motif = re.compile(r'\\d+')\n",
    "freq = {}\n",
    "\n",
    "with open('../data/indata_exo10_re.txt', encoding='utf8') as f:\n",
    "    for ligne in f:\n",
    "        nombres = motif.findall(ligne)\n",
    "        for nombre in nombres:\n",
    "            chiffre = nombre[0]\n",
    "            if chiffre != '0':\n",
    "                try:\n",
    "                    freq[chiffre] += 1\n",
    "                except:\n",
    "                    freq[chiffre] = 1\n",
    "\n",
    "pprint(freq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_09"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_09\n",
    "\"\"\"\n",
    "    Exercice adapté du MOOC bioinformatique de François Rechenmann & Thierry Parmentelat (inria)\n",
    "    https://www.fun-mooc.fr/courses/course-v1:inria+41003+selfpaced/about\n",
    "\"\"\"\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def hamming(dna1, dna2):\n",
    "    length = min(len(dna1), len(dna2))\n",
    "    return sum(n1 != n2 for n1, n2 in zip(dna1[:length], dna2[:length]))\n",
    "\n",
    "\n",
    "# Programme principal =========================================================\n",
    "s1 = 'TTGCATTGCTTAGGCATA'\n",
    "s2 = 'TTGCGTTGCTTAGCCATA'\n",
    "s3 = 'TTGCAGTCCTTAGGCATT'\n",
    "\n",
    "d1, d2, d3 = hamming(s1, s2), hamming(s2, s3), hamming(s1, s3)\n",
    "print(f\"D({'s1'}, {'s2'}) = {d1}\")\n",
    "print(f\"D({'s2'}, {'s3'}) = {d2}\")\n",
    "print(f\"D({'s1'}, {'s3'}) = {d3}\")\n",
    "\n",
    "print('\\nInégalité triangulaire :')\n",
    "print('\\td1 + d2 =', d1 + d2)\n",
    "print('\\td3      =', d3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_10\n",
    "\n",
    "# Définition de fonction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n",
    "def hamming(s, t):\n",
    "    if len(s) == 0:\n",
    "        return len(t)\n",
    "    elif len(t) == 0:\n",
    "        return len(s)\n",
    "    else:\n",
    "        distance = 0\n",
    "\n",
    "    if s[-1] != t[-1]:\n",
    "        distance = 1\n",
    "\n",
    "    return min(hamming(s[:-2], t) + 1,\n",
    "               hamming(s, t[:-2]) + 1,\n",
    "               hamming(s[:-2], t[:-2]) + distance)\n",
    "\n",
    "# Programme principal ========================================================\n",
    "s1 = input('Entrez une chaîne : ')\n",
    "s2 = input('Entrez une seconde chaîne : ')\n",
    "\n",
    "print(f'\\nDistance de Hamming entre {s1} et {s2} : {hamming(s1, s2)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### exo10_11\n",
    "\n",
    "**La permutation**\n",
    "\n",
    "Pour construire la permutation sur les chaînes, nous allons commencer \"petit\" et voir comment construire l'algorithme. La permutation de deux caractères `\"ab\"` est simple : `\"ab\"`, `\"ba\"`. La permutation de trois caractères `\"abc\"` est déjà plus longue : `\"abc\"`, `\"acb\"`, `\"bac\"`, `\"bca\"`, `\"cab\"`, `\"cba\"`. Nous pouvons remarquer que dans le résultat on a pris et placé en tête tour à tour *un des caractères*, puis ajouté derrière les *permutations des caractères restants*. Nous avons là un joli cas généralisable en *fonction récursive*.\n",
    "\n",
    "Pour compléter, il est possible de construire la permutation sous forme de listes `list`, auquel cas il sera possible d'avoir des valeurs permutées identiques (vu qu'on autorise que certains chiffres soient égaux), ou sous forme d'ensembles `set` où ça ne sera pas possible. Pour notre exercice, nous n'avons pas besoin de dénombrer le nombre combinaisons, il est donc intéressant d'utiliser des `set` afin de limiter l'[explosion combinatoire](https://fr.wikipedia.org/wiki/Explosion_combinatoire) du traitement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exo10_11\n",
    "\n",
    "def permut(s):\n",
    "    \"Retourne l'ensemble des permutations possibles différentes.\"\n",
    "    if len(s) == 1:                   # cas d'arrêt de récursion\n",
    "        return set([s])\n",
    "    else:\n",
    "        res = set()\n",
    "        for i in range(len(s)):\n",
    "            debut = s[i]              # le caractère de tête\n",
    "            reste = s[:i] + s[i+1:]   # les caractères restants\n",
    "            for resteperm in permut(reste):\n",
    "                res.add(debut + resteperm)\n",
    "        return res\n",
    "    \n",
    "def permut_int4(n):\n",
    "    \"Retourne la liste des permutations possibles des chiffres d'un entier.\"\n",
    "    lst = []\n",
    "    nstr = \"{:04d}\".format(n)  # assure 4 chiffres (zéros en tête si besoin)\n",
    "    for v in permut(nstr):\n",
    "        lst.append(int(v))\n",
    "    return lst\n",
    "    \n",
    "def entier4ok(n):\n",
    "    \"Vérifie entier de 4 chiffres pas tous identiques.\"\n",
    "    return (1000 <= n < 10000) and (n not in\n",
    "            [1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999])\n",
    "\n",
    "# La saisie contrôlée\n",
    "nb4 = 0   # valeur invalide pour entrer dans la boucle\n",
    "while not entier4ok(nb4):\n",
    "    nb4 = int(input(\"Saisir entier (4 chiffres pas tous égaux) :\"))\n",
    "\n",
    "print(nb4, end=' ')\n",
    "nbcoups = 0\n",
    "while nb4 != 6174:\n",
    "    permutations= permut_int4(nb4)\n",
    "    nbcoups += 1\n",
    "    PP = min(permutations)\n",
    "    PG = max(permutations)\n",
    "    nb4 = PG - PP\n",
    "    print(\"=> ({}-{}) = {}\".format(PG, PP, nb4), end=' ')\n",
    "print()\n",
    "print(\"Obtenu 6174 en \", nbcoups, \"coups\")"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
