_doc/notebooks/td1a/td1a_correction_session5.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# 1A.2 - Classes, m\u00e9thodes, attributs, op\u00e9rateurs et carr\u00e9 magique (correction)\n",
        "\n",
        "Correction."
      ]
    },
    {
      "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 : carr\u00e9 magique"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1,3,4\n",
            "2,6,9\n",
            "8,7,5\n",
            "--\n",
            "2,6,8\n",
            "4,12,18\n",
            "16,14,10\n"
          ]
        }
      ],
      "source": [
        "class CarreMagique :\n",
        "    def __init__(self, coef) :\n",
        "        self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]\n",
        "    def __str__(self) :\n",
        "        return \"\\n\".join ( [ \",\".join( [ str(n) for n in row ] ) for row in self.mat ] )\n",
        "    def __add__ (self, carre) :\n",
        "        coef = []\n",
        "        for i in range(3) :\n",
        "            for j in range(3) :\n",
        "                coef.append ( self.mat[i][j] + carre.mat[i][j])\n",
        "        return CarreMagique(coef)\n",
        "\n",
        "c = CarreMagique ( [ 1,3,4, 2,6,9, 8,7,5 ] )\n",
        "print (c)\n",
        "print(\"--\")\n",
        "print (c + c)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Exercice 2 : \u00e0 faire \u00e0 trois, carr\u00e9 magique (suite)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "False\n",
            "False\n",
            "False\n",
            "True\n"
          ]
        }
      ],
      "source": [
        "class CarreMagique :\n",
        "    def __init__(self, coef) :\n",
        "        self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]\n",
        "    def __str__(self) :\n",
        "        return \"\\n\".join ( [ \",\".join( str(n) for n in row ) for row in self.mat ] )\n",
        "    def __add__ (self, carre) :\n",
        "        coef = []\n",
        "        for i in range(3) :\n",
        "            for j in range(3) :\n",
        "                coef.append ( self.mat[i][j] + carre.mat[i][j])\n",
        "        return CarreMagique(coef)\n",
        "\n",
        "    def somme_ligne_colonne_diagonale(self):\n",
        "        tout = [ sum ( ligne ) for ligne in self.mat ] + \\\n",
        "               [ sum ( self.mat[i][j] for i in range(3) ) for j in range(3) ] + \\\n",
        "               [ sum ( self.mat[i][i] for i in range(3) ) ] + \\\n",
        "               [ sum ( self.mat[2-i][i] for i in range(3) ) ] \n",
        "        return tout\n",
        "        \n",
        "    def coefficient_unique(self): \n",
        "        d = { }\n",
        "        for ligne in self.mat :\n",
        "            for c in ligne :\n",
        "                d [c] = d.get(c,0) + 1\n",
        "        return len(d) == 9\n",
        "        \n",
        "    def est_magique(self):\n",
        "        unique = self.coefficient_unique()\n",
        "        if not unique : return False\n",
        "        somme = self.somme_ligne_colonne_diagonale()\n",
        "        return min(somme) == max(somme) \n",
        "        \n",
        "c = CarreMagique ( [ 1,1,1, 1,1,1, 1,1,1 ] )\n",
        "print (c.est_magique())\n",
        "c = CarreMagique ( [ 1,4,8, 5,2,6, 7,9,3 ] )\n",
        "print (c.est_magique())\n",
        "c = CarreMagique ( [ 1,6,8, 7,5,3, 2,4,9 ] )\n",
        "print (c.est_magique())\n",
        "c = CarreMagique ( [ 2,7,6, 9,5,1, 4,3,8 ] )\n",
        "print (c.est_magique())"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Exercice 3 : trouver tous les carr\u00e9s magiques\n",
        "\n",
        "La premi\u00e8re version est fastidieuse \u00e0 \u00e9crire mais simple \u00e0 comprendre."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [],
      "source": [
        "def tous_les_carre_naif() :\n",
        "    res = []\n",
        "    for a1 in range(9) :\n",
        "        for a2 in range(9) :\n",
        "            for a3 in range(9) :\n",
        "                for b1 in range(9) :\n",
        "                    for b2 in range(9) :\n",
        "                        for b3 in range(9) :\n",
        "                            for c1 in range(9) :\n",
        "                                for c2 in range(9) :\n",
        "                                    for c3 in range(9) :\n",
        "                                        carre = CarreMagique( [a1,a2,a3, b1,b2,b3, c1,c2,c3 ])\n",
        "                                        if carre.est_magique() :\n",
        "                                            res.append (carre)\n",
        "                                            print (carre)\n",
        "    return res\n",
        "\n",
        "# tous_les_carre_naif() (c'est tr\u00e8s long)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "La seconde version n'est pas plus rapide mais elle contient moins de boucles."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": [
        "def tous_les_carre_naif2() :\n",
        "    # on choisit l'ensemble de tous les tableaux de 9 chiffres compris entre 1 et 9\n",
        "    coef = [ 1 ] * 9\n",
        "    res = [ ]\n",
        "    while coef [0] < 10 :\n",
        "        carre = CarreMagique(coef)\n",
        "        if carre.est_magique() :\n",
        "            res.append (carre)\n",
        "            print (carre)\n",
        "        coef[-1] += 1\n",
        "        if coef[-1] >= 10 :\n",
        "            i = len(coef)-1\n",
        "            while coef[i] >= 10 and i > 0 :\n",
        "                coef[i] = 1\n",
        "                coef[i-1] += 1\n",
        "                i -= 1\n",
        "                \n",
        "# tous_les_carre_naif2() (c'est tr\u00e8s long)                "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "La troisi\u00e8me version utilise le fait que les chiffres d'un carr\u00e9 magique sont tous diff\u00e9rents. Il suffit de regarder seulement tous les permutations. La variable ``stop_after`` permet de se limiter seulement aux premiers."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "2,7,6\n",
            "9,5,1\n",
            "4,3,8\n",
            "\n",
            "2,9,4\n",
            "7,5,3\n",
            "6,1,8\n",
            "\n",
            "4,3,8\n",
            "9,5,1\n",
            "2,7,6\n",
            "\n",
            "4,9,2\n",
            "3,5,7\n",
            "8,1,6\n",
            "\n",
            "nombre de carr\u00e9s 4\n"
          ]
        }
      ],
      "source": [
        "def tous_les_carres_permutation( permut = None, pos = 0, stop_after = 3):\n",
        "    if pos == 9 :\n",
        "        carre = CarreMagique (permut) \n",
        "        if carre.est_magique() :\n",
        "            print (carre)\n",
        "            print ()\n",
        "            return [ carre ]\n",
        "        else :\n",
        "            return []\n",
        "    else :\n",
        "        res = [ ]\n",
        "        if permut == None :\n",
        "            permut = [ i+1 for i in range(9) ]\n",
        "        for i in range (pos,9) :\n",
        "            # on permute les \u00e9l\u00e9ments i et pos\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "\n",
        "            res += tous_les_carres_permutation(permut, pos+1)\n",
        "            \n",
        "            if stop_after > 0 and len(res) >= stop_after :\n",
        "                return res\n",
        "            \n",
        "            # on effectue la permutation inverse\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "        return res\n",
        "   \n",
        "res = tous_les_carres_permutation()\n",
        "print (\"nombre de carr\u00e9s\", len(res))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Le langage Python propose une fonction qui parcourt toutes les permutations d'un ensemble : [itertools.permutation](https://docs.python.org/3.4/library/itertools.html#itertools.permutations). Cela r\u00e9duit de beaucoup la longueur du programme."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "2,7,6\n",
            "9,5,1\n",
            "4,3,8\n",
            "\n",
            "2,9,4\n",
            "7,5,3\n",
            "6,1,8\n",
            "\n",
            "4,3,8\n",
            "9,5,1\n",
            "2,7,6\n",
            "\n",
            "nombre de carr\u00e9s 3\n"
          ]
        }
      ],
      "source": [
        "import itertools\n",
        "def tous_les_carres_permutation( stop_after = 3):\n",
        "    res = [ ]\n",
        "    firstn = list(range(1,10))\n",
        "    for permut in itertools.permutations(firstn) :\n",
        "        carre = CarreMagique (permut) \n",
        "        if carre.est_magique() :\n",
        "            res.append( carre )\n",
        "            if stop_after >= 0 :\n",
        "                print (carre)\n",
        "                print ()\n",
        "                if len(res) >= stop_after :\n",
        "                    return res\n",
        "    return res\n",
        "   \n",
        "res = tous_les_carres_permutation()\n",
        "print (\"nombre de carr\u00e9s\", len(res))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Exercice 4 : faire plus rapide"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Est-il possible d'aller plus vite que de parcourir l'ensemble des permutations ? La r\u00e9ponse est oui. En parcourant les permutations, la fonction qui teste si les chiffres sont uniques est devenue inutile. Pour v\u00e9rifier qu'on va plus vite, on peut mesurer le temps que met la fonction pour trouver tous les carr\u00e9s :"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "nombre de carr\u00e9s 8  en  32.244037248859705 seconds\n"
          ]
        }
      ],
      "source": [
        "import time\n",
        "d = time.perf_counter()\n",
        "res = tous_les_carres_permutation(-1)\n",
        "d = time.perf_counter() - d\n",
        "print (\"nombre de carr\u00e9s\", len(res), \" en \", d, \"seconds\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Pour aller plus vite, il faut utiliser la contrainte des sommes. Comment ? Lorsqu'on permute les nombres, on peut simplement v\u00e9rifier que les deux premi\u00e8res lignes ont la m\u00eame somme. L'utilisation de cette contrainte nous permet de d'aller 10 fois plus vite et d'obtenir le r\u00e9sultat en moins d'une seconde. L'inconv\u00e9nient est que l'optimisation fonctionne parce qu'on ne parcourt pas toutes les permutations. On ne peut plus utiliser la fonction [itertools.permutation](https://docs.python.org/3.4/library/itertools.html#itertools.permutations)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "nombre de carr\u00e9s 112  en  5.413181214436662\n"
          ]
        }
      ],
      "source": [
        "def tous_les_carres_permutation_ligne12_meme_somme( permut = None, pos = 0):\n",
        "    if pos == 9 :\n",
        "        carre = CarreMagique (permut) \n",
        "        if carre.est_magique() :\n",
        "            #print (carre)\n",
        "            #print ()\n",
        "            return [ carre ]\n",
        "        else :\n",
        "            return []\n",
        "    else :\n",
        "        if pos >= 6 :                                       # ajout\n",
        "            if sum ( permut[:3]) != sum(permut[3:6]) :      # ajout\n",
        "                return [ ]                                  # ajout\n",
        "        \n",
        "        res = [ ]\n",
        "        if permut == None :\n",
        "            permut = [ i+1 for i in range(9) ]\n",
        "        for i in range (pos,9) :\n",
        "            # on permute les \u00e9l\u00e9ments i et pos\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "\n",
        "            res += tous_les_carres_permutation_ligne12_meme_somme(permut, pos+1)  # chang\u00e9\n",
        "            \n",
        "            # on effectue la permutation inverse\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "        return res\n",
        "    \n",
        "import time\n",
        "d = time.perf_counter()\n",
        "res = tous_les_carres_permutation_ligne12_meme_somme()\n",
        "d = time.perf_counter() - d\n",
        "print (\"nombre de carr\u00e9s\", len(res), \" en \", d)    "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Programme complet"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "nombre de carr\u00e9s 8  en  4.024395385971979\n"
          ]
        }
      ],
      "source": [
        "class CarreMagique :\n",
        "    def __init__(self, coef) :\n",
        "        self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]\n",
        "    def __str__(self) :\n",
        "        return \"\\n\".join ( [ \",\".join( [ str(n) for n in row ] ) for row in self.mat ] )\n",
        "    def __add__ (self, carre) :\n",
        "        coef = []\n",
        "        for i in range(3) :\n",
        "            for j in range(3) :\n",
        "                coef.append ( self.mat[i][j] + carre.mat[i][j])\n",
        "        return CarreMagique(coef)\n",
        "        \n",
        "    def somme_ligne_colonne_diagonale(self):\n",
        "        tout = [ sum ( ligne ) for ligne in self.mat ] + \\\n",
        "               [ sum ( self.mat[i][j] for i in range(3) ) for j in range(3) ] + \\\n",
        "               [ sum ( self.mat[i][i] for i in range(3) ) ] + \\\n",
        "               [ sum ( self.mat[2-i][i] for i in range(3) ) ] \n",
        "        return tout\n",
        "        \n",
        "    def coefficient_unique(self): \n",
        "        d = { }\n",
        "        for ligne in self.mat :\n",
        "            for c in ligne :\n",
        "                d [c] = d.get(c,0) + 1\n",
        "        return len(d) == 9\n",
        "        \n",
        "    def est_magique(self):\n",
        "        unique = self.coefficient_unique()\n",
        "        if not unique : return False\n",
        "        somme = self.somme_ligne_colonne_diagonale()\n",
        "        return min(somme) == max(somme) \n",
        "        \n",
        "def tous_les_carres_permutation_ligne12_meme_somme( permut = None, pos = 0):\n",
        "    if pos == 9 :\n",
        "        carre = CarreMagique (permut) \n",
        "        if carre.est_magique() :\n",
        "            #print (carre)\n",
        "            #print ()\n",
        "            return [ carre ]\n",
        "        else :\n",
        "            return []\n",
        "    else :\n",
        "        if pos >= 6 :                                       # ajout\n",
        "            if sum ( permut[:3]) != sum(permut[3:6]) :      # ajout\n",
        "                return [ ]                                  # ajout\n",
        "        \n",
        "        res = [ ]\n",
        "        if permut == None :\n",
        "            permut = [ i+1 for i in range(9) ]\n",
        "        for i in range (pos,9) :\n",
        "            # on permute les \u00e9l\u00e9ments i et pos\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "\n",
        "            res += tous_les_carres_permutation_ligne12_meme_somme(permut, pos+1)  # chang\u00e9\n",
        "            \n",
        "            # on effectue la permutation inverse\n",
        "            a = permut[i]\n",
        "            permut[i] = permut[pos]\n",
        "            permut[pos] = a\n",
        "        return res\n",
        "        \n",
        "import time\n",
        "d = time.perf_counter()\n",
        "res = tous_les_carres_permutation_ligne12_meme_somme()\n",
        "d = time.perf_counter() - d\n",
        "print (\"nombre de carr\u00e9s\", len(res), \" en \", d)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "On peut faire encore plus rapide en utilisant les contraintes pour inf\u00e9rer les autres coefficients (solution venant d'un \u00e9l\u00e8ve) :"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1 loops, best of 3: 200 ms per loop\n"
          ]
        }
      ],
      "source": [
        "def tous_les_carres():\n",
        "    for a1 in range(1,10):\n",
        "        for a2 in range(1,10):\n",
        "            for a3 in range(1,10):\n",
        "                for b1 in range(1,10):\n",
        "                    somme = a1 + a2 + a3\n",
        "                    c1 = somme - a1 - b1\n",
        "                    b2 = somme - a3 - c1\n",
        "                    b3 = somme - b1 - b2\n",
        "                    c2 = somme - a2 - b2\n",
        "                    c3 = somme - c1 - c2\n",
        "                    M = CarreMagique([a1,a2,a3,b1,b2,b3,c1,c2,c3])\n",
        "                    if M.est_magique() and 0 < b2 < 10 and 0 < b3 < 10 and 0 < c1 < 10 and 0 < c2 < 10 and 0 < c3 < 10 :\n",
        "                        #print(M)\n",
        "                        #print(\"---------------\")    \n",
        "                        pass\n",
        "%timeit tous_les_carres()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "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": 1
}