{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.1 - Dictionnaires, fonctions, code de Vigen\u00e8re (correction)\n", "\n", "Le notebook ne fait que crypter et d\u00e9crypter un message sachant le code connu. Casser le code requiert quelques astuces d\u00e9crites dnas ce notebook : [casser le code de Vigen\u00e8re](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/expose_vigenere.html)."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<b>Plan</b>\n", "<div id=\"my_menu_id\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n) {\n", "        a += \"    \";\n", "    }\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    for (i = lfirst; i <= llast; i++) {\n", "        tags.push(\"h\" + i);\n", "    }\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null){\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\").replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\")\n", "        }\n", "\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        while (level < memo_level) {\n", "            text_menu += \"</ul>\\n\";\n", "            memo_level -= 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2) + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += \"</ul>\\n\";\n", "        memo_level -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<li><a href=\"#__HREF__\">__TITLE__</a></li>';\n", "    var send = \"\";\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send);\n", "    var menu = document.getElementById(\"my_menu_id\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 1"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["n a\n"]}], "source": ["def lettre_suivante(lettre) :\n", "    c = ord(lettre) - ord('a')\n", "    c = (c + 1) % 26\n", "    return chr (c + ord('a'))\n", "    \n", "print (lettre_suivante('m'), lettre_suivante('z'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 2"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["['tywin', 'tyrion']\n"]}], "source": ["mots = ['eddard', 'catelyn', 'robb', 'sansa', 'arya', 'brandon',\n", "        'rickon', 'theon', 'rorbert', 'cersei', 'tywin', 'jaime',\n", "        'tyrion', 'shae', 'bronn', 'lancel', 'joffrey', 'sandor',\n", "        'varys', 'renly', 'a' ]\n", "        \n", "def mots_lettre_position (liste, lettre, position) :\n", "    res = [ ]\n", "    for mot in liste :\n", "        if position < len(mot) and mot[position] == lettre :\n", "            res.append (mot)\n", "    return res\n", "    \n", "r = mots_lettre_position ( mots, 'y', 1)\n", "print (r)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 3 : utilisation d'un dictionnaire"]}, {"cell_type": "markdown", "metadata": {}, "source": ["L'\u00e9nonc\u00e9 sugg\u00e8re d'utiliser comme cl\u00e9 de dictionnaire le couple ``(position, lettre)`` et la fonction doit retourne la liste des mots qui ont tous la m\u00eame lettre \u00e0 la m\u00eame position. Le dictionnaire ``dictionnaire_bien_choisi`` de l'\u00e9nonc\u00e9 doit avoir pour cl\u00e9s des couples ``(position, lettre)`` et pour valeurs des listes de pr\u00e9noms."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["r\u00e9sultat= ['tywin', 'tyrion']\n", "dictionnaire= {(0, 'l'): ['lancel'], (4, 'y'): ['renly'], (0, 'e'): ['eddard'], (4, 'n'): ['theon', 'tywin', 'bronn'], (1, 'd'): ['eddard'], (4, 'l'): ['catelyn'], (3, 'd'): ['sandor'], (1, 'r'): ['arya', 'brandon', 'bronn'], (2, 'o'): ['bronn'], (3, 'k'): ['rickon'], (2, 'y'): ['arya'], (2, 'e'): ['theon'], (1, 'y'): ['tywin', 'tyrion'], (1, 'h'): ['theon', 'shae'], (2, 'r'): ['rorbert', 'cersei', 'tyrion', 'varys'], (3, 'y'): ['varys'], (3, 'o'): ['theon'], (2, 'd'): ['eddard'], (4, 'd'): ['brandon'], (1, 'e'): ['cersei', 'renly'], (2, 'w'): ['tywin'], (0, 't'): ['theon', 'tywin', 'tyrion'], (6, 't'): ['rorbert'], (5, 'l'): ['lancel'], (6, 'n'): ['catelyn', 'brandon'], (5, 'e'): ['joffrey'], (0, 's'): ['sansa', 'shae', 'sandor'], (0, 'r'): ['robb', 'rickon', 'rorbert', 'renly'], (2, 'c'): ['rickon'], (0, 'j'): ['jaime', 'joffrey'], (3, 'n'): ['brandon', 'bronn'], (3, 'i'): ['tywin', 'tyrion'], (0, 'c'): ['catelyn', 'cersei'], (1, 'o'): ['robb', 'rorbert', 'joffrey'], (4, 'e'): ['rorbert', 'cersei', 'jaime', 'lancel'], (5, 'd'): ['eddard'], (4, 'r'): ['eddard', 'joffrey'], (3, 'b'): ['robb', 'rorbert'], (2, 'a'): ['brandon', 'shae'], (5, 'o'): ['brandon'], (4, 'a'): ['sansa'], (5, 'i'): ['cersei'], (2, 't'): ['catelyn'], (3, 'f'): ['joffrey'], (3, 'c'): ['lancel'], (6, 'y'): ['joffrey'], (3, 'm'): ['jaime'], (2, 'f'): ['joffrey'], (5, 'r'): ['rorbert', 'sandor'], (0, 'v'): ['varys'], (1, 'a'): ['catelyn', 'sansa', 'jaime', 'lancel', 'sandor', 'varys'], (2, 'i'): ['jaime'], (3, 'a'): ['eddard', 'arya'], (0, 'b'): ['brandon', 'bronn'], (2, 'b'): ['robb'], (5, 'n'): ['rickon', 'tyrion'], (4, 's'): ['varys'], (5, 'y'): ['catelyn'], (4, 'o'): ['rickon', 'tyrion', 'sandor'], (3, 'e'): ['catelyn', 'shae'], (2, 'n'): ['sansa', 'lancel', 'sandor', 'renly'], (3, 'l'): ['renly'], (3, 's'): ['sansa', 'cersei'], (0, 'a'): ['arya', 'a'], (1, 'i'): ['rickon']}\n"]}], "source": ["def dictionnaire_choisi (liste) :\n", "    d = { }\n", "    for mot in liste :\n", "        for i,c in enumerate(mot) :\n", "            d [i,c] = d.get ((i,c), []) + [ mot ]\n", "    return d\n", "    \n", "def mots_lettre_position (d, lettre, position) :\n", "    return d.get ( (position, lettre), [] )\n", "\n", "d = dictionnaire_choisi(mots)\n", "r = mots_lettre_position ( d, 'y', 1)\n", "print (\"r\u00e9sultat=\",r)\n", "print (\"dictionnaire=\",d)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["S'il permet d'aller beaucoup plus vite pour effectuer une recherche, le dictionnaire ``d`` contient beaucoup plus de mots que la liste initiale. Si on suppose que tous les mots sont uniques, il en contient exactement autant que la somme des longueurs de chaque mot.\n", "\n", "**A quoi \u00e7a sert ?** Tout d\u00e9pend du nombre de fois qu'on n'effectue ce type de **recherche**. Il faut d'abord d\u00e9composer les deux m\u00e9thodes en co\u00fbt fixe (pr\u00e9paration du dictionnaire) et co\u00fbt recherche puis regarder la page [Time Complexity](https://wiki.python.org/moin/TimeComplexity). On obtient :\n", "\n", "- liste de l'exercice 2 :  co\u00fbt fixe = 0, co\u00fbt variable $\\sim O(N)$ \n", "- dictionaire de l'exercice 3 : co\u00fbt fixe $\\sim O(L)$, co\u00fbt variable $\\sim O(1)$ \n", "\n", "O\u00f9 :\n", "\n", "- $N$ est le nombre de mots,\n", "- $L$ est la somme des nombres de lettres de chaque mot,\n", "- $M$ est la longueur maximale d'un mot.\n", "\n", "Les dictionnaires en Python utilisent une [table de hashage](http://fr.wikipedia.org/wiki/Table_de_hachage) pour stocker les cl\u00e9s. L'objet ``map`` de Python ne rapproche plus de l'objet ``unordered_map`` de C++ que de l'objet ``map``. Ce dernier (C++ uniquement) est un tableau tri\u00e9. L'acc\u00e8s \u00e0 chaque \u00e9l\u00e9ment se fait par dichotomie en $O(\\ln_2 n)$ (voir [Standard C++ Containers](http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html#map). Le co\u00fbt dans ce cas serait (toujours en C++) :\n", "\n", "- dictionaire de l'exercice 3 : co\u00fbt fixe $\\sim O(L \\, ln_2(26 * M))$, co\u00fbt variable $\\sim O(ln_2(26 * M))$ \n", "\n", "\n", "Si on effectue cette recherche un grand nombre de fois, l'utilisation d'un dictionnaire permet d'\u00eatre beaucoup plus rapide m\u00eame si on doit cr\u00e9er une structure interm\u00e9diaire. Ce sch\u00e9ma revient r\u00e9guli\u00e8rement : **repr\u00e9senter autrement les donn\u00e9es pour acc\u00e9l\u00e9rer un traitement effectu\u00e9 un grand nombre de fois**. \n", "\n", "Vous pouvez lire \u00e9galement :\n", "\n", "- [hash](https://docs.python.org/3.4/reference/datamodel.html#object.__hash__)\n", "- [STL Container Performance ](http://john-ahlgren.blogspot.fr/2013/10/stl-container-performance.html)\n", "- [C++11: unordered_map vs map](http://kariddi.blogspot.fr/2012/07/c11-unorderedmap-vs-map.html)\n", "- [AVL tree](http://en.wikipedia.org/wiki/AVL_tree)\n", "- [List of data structures](http://en.wikipedia.org/wiki/List_of_data_structures)\n", "- [Time complexity of accessing a Python dict](http://stackoverflow.com/questions/1963507/time-complexity-of-accessing-a-python-dict)\n", "- [Hash Table Performance Tests](http://preshing.com/20110603/hash-table-performance-tests/)\n", "- [How to implement a good __hash__ function in python](http://stackoverflow.com/questions/4005318/how-to-implement-a-good-hash-function-in-python)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 4 : crypter et d\u00e9crypter selon Vigen\u00e8re\n", "\n", "Tout d'abord le code de C\u00e9sar :"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["MHQHVXLVSDVFRGH\n"]}], "source": ["def code_cesar(m):\n", "    s = \"\".join( [ chr((ord(l)-65+3)%26+65) for l in m ] )\n", "    return s\n", "\n", "m = \"JENESUISPASCODE\"\n", "print(code_cesar(m))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Et le code de Vigen\u00e8re :"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["MSCHGJLGEDGRRRT\n"]}], "source": ["def code_vigenere ( message, cle) :\n", "    message_code = \"\"\n", "    for i,c in enumerate(message) :\n", "        d = cle[ i % len(cle) ]\n", "        d = ord(d) - 65\n", "        message_code += chr((ord(c)-65+d)%26+65)\n", "    return message_code\n", "\n", "m = \"JENESUISPASCODE\"\n", "print ( code_vigenere (m, \"DOP\") )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Et le d\u00e9cryptage du code de Vigen\u00e8re pour lequel on modifie la fonction pr\u00e9c\u00e9dente qui pourra alors coder et d\u00e9coder."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["MSCHGJLGEDGRRRT JENESUISPASCODE\n"]}], "source": ["def code_vigenere ( message, cle, decode = False) :      # ligne chang\u00e9e\n", "    message_code = \"\"\n", "    for i,c in enumerate(message) :\n", "        d = cle[ i % len(cle) ]\n", "        d = ord(d) - 65\n", "        if decode : d = 26 - d                          # ligne ajout\u00e9e\n", "        message_code += chr((ord(c)-65+d)%26+65)\n", "    return message_code\n", "    \n", "m = \"JENESUISPASCODE\"\n", "c = code_vigenere (m, \"DOP\") \n", "d = code_vigenere (c, \"DOP\", True) \n", "print(c,d)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pour retrouver le code de C\u00e9sar, il suffit de choisir une cl\u00e9 d'une seule lettre :"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["MHQHVXLVSDVFRGH\n"]}], "source": ["c = code_vigenere (m, \"D\") \n", "print(c)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On peut casser le code de Vigen\u00e8re. Vous trouverez la solution ici : [casser le code de Vigen\u00e8re](http://www.xavierdupre.fr/app/ensae_teaching_cs/helpsphinx/notebooks/expose_vigenere.html)."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": []}], "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.1"}}, "nbformat": 4, "nbformat_minor": 2}