TP1+v4+corrige_v5.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "celltoolbar": "Edit 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"
    },
    "colab": {
      "name": "TP1+v4+corrigeě_v5.ipynb",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Jthirot/NSIT/blob/main/TP1%2Bv4%2Bcorrige_v5.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g2wp_eV02yQh"
      },
      "source": [
        "   # TP Graphes : modéliser un labyrinthe\n",
        "   adaptation d'un TP publié sur : https://www.di.ens.fr/~mauborgn/td-99/programmation/tp8.html\n",
        "   "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t1xODin32yQj"
      },
      "source": [
        "Considérons le problème suivant :\n",
        "\n",
        "Comment rechercher le chemin le plus long entre deux stations dans le métro? Indépendamment de l'aspect ludique, c'est en fait un problème difficile qu'on aurait bien du mal à résoudre de façon raisonnable sur un gros graphe comme celui du métro. \n",
        "Pour simplifier, nous allons donc considérer des labyrinthes.\n",
        "\n",
        "## Les labyrinthes\n",
        "\n",
        "Voici l'image d'un labyrinthe :\n",
        "\n",
        "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petitlab.gif\">"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UyRkPGkJ2yQk"
      },
      "source": [
        "Ce labyrinthe peut etre représenter par le graphe suivant :\n",
        "\n",
        "<img src=\"https://www.di.ens.fr/~mauborgn/td-99/programmation/petit.gif\">\n",
        "\n",
        "**- Chaque somment du graphe correspond à une case du labyrinthe**\n",
        "\n",
        "**- une arête relie 2 cases voisines quand le passage est possible.**\n",
        "\n",
        "**- Si une paroie empêche de passer on ne met pas l'arête.**\n",
        "\n",
        "Par exemple il n'y a pas d'arête entre les sommets (1,1) et (1,2) mais il y en a une entre (1,1) et (2,1).\n",
        "\n",
        "Implémentez ce labyrinthe avec un graphe.\n",
        "Vous utiliserez l'implémentation de graphe fournie ci-dessous, vous nommerez les sommets (1,1) (1,2) .. etc \n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ckfoTG1W2yQl"
      },
      "source": [
        "class graph() :\n",
        "    def __init__(self) :\n",
        "        self.lstAdj={}\n",
        "    def __str__(self):\n",
        "        return str(self.lstAdj)\n",
        "    def addSommet(self,sommet):\n",
        "        self.lstAdj[sommet]=[]\n",
        "    def addArete(self,sa,sb) :\n",
        "        self.lstAdj[sa].append(sb)\n",
        "        self.lstAdj[sb].append(sa)\n",
        "\n",
        "# 1) créez un graphe labyrinthe\n",
        "# 2) ajoutez les sommets (1,1) et (1,2 puis l'arête (1,1)--(1,2)\n",
        "labyrinthe=graph()\n",
        "labyrinthe.addSommet((1,1))\n",
        "labyrinthe.addSommet((1,2))\n",
        "labyrinthe.addArete((1,1),(1,2))\n",
        "\n"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cp2Cgxzy2yQr"
      },
      "source": [
        "assert labyrinthe.lstAdj[(1,1)] == [(1,2)],\"vous avez fait une erreur...\""
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jkbB5khF2yQv"
      },
      "source": [
        "## Ajoutons tous les sommets dans le graphe représentant ce labyrinthe\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T01gbufU2yQw"
      },
      "source": [
        "# Entrez tous les sommets. Vous ne devez pas les entrer un par un, utilisez deux boucles imbriquées...\n",
        "for i in range(1,5):\n",
        "    for j in range(1,9):\n",
        "        labyrinthe.addSommet( (i,j) )"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-0yrRTuW2yQz"
      },
      "source": [
        "## Ajoutons les arêtes.\n",
        "C'est un peu fastidieux, alors nous vous fournissons une version avec la plupart des arêtes déjà ajoutées, mais il en manque quelques unes...."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EhEHJbx72yQz",
        "outputId": "ec1dc269-fe92-4a6d-fca7-5ada438c99ba",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        }
      },
      "source": [
        "labyrinthe.addArete((1,1),(2,1))\n",
        "labyrinthe.addArete((2,1),(2,2))\n",
        "labyrinthe.addArete((2,2),(2,3))\n",
        "labyrinthe.addArete((2,2),(3,2))\n",
        "labyrinthe.addArete((2,3),(1,3))\n",
        "labyrinthe.addArete((1,3),(1,4))\n",
        "labyrinthe.addArete((1,4),(1,5))\n",
        "labyrinthe.addArete((1,4),(2,4))\n",
        "labyrinthe.addArete((1,5),(2,5))\n",
        "labyrinthe.addArete((2,7),(3,7))\n",
        "labyrinthe.addArete((1,6),(1,7))\n",
        "labyrinthe.addArete((2,4),(3,4))\n",
        "labyrinthe.addArete((1,7),(1,8))\n",
        "labyrinthe.addArete((1,8),(2,8))\n",
        "labyrinthe.addArete((3,2),(4,2))\n",
        "labyrinthe.addArete((4,2),(4,3))\n",
        "labyrinthe.addArete((4,3),(4,4))\n",
        "labyrinthe.addArete((3,4),(3,5))\n",
        "labyrinthe.addArete((3,5),(3,6))\n",
        "labyrinthe.addArete((3,6),(4,6))\n",
        "labyrinthe.addArete((3,6),(3,7))\n",
        "labyrinthe.addArete((4,6),(4,5))\n",
        "labyrinthe.addArete((3,7),(4,7))\n",
        "labyrinthe.addArete((4,7),(4,8))\n",
        "labyrinthe.addArete((4,8),(3,8))\n",
        "labyrinthe.addArete((2,8),(3,8))\n",
        "\n",
        "#print(str(labyrinthe))\n",
        "print(labyrinthe.lstAdj[(1,1)])\n",
        "print(labyrinthe)"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(2, 1)]\n",
            "{(1, 1): [(2, 1)], (1, 2): [], (1, 3): [(2, 3), (1, 4)], (1, 4): [(1, 3), (1, 5), (2, 4)], (1, 5): [(1, 4), (2, 5)], (1, 6): [(1, 7)], (1, 7): [(1, 6), (1, 8)], (1, 8): [(1, 7), (2, 8)], (2, 1): [(1, 1), (2, 2)], (2, 2): [(2, 1), (2, 3), (3, 2)], (2, 3): [(2, 2), (1, 3)], (2, 4): [(1, 4), (3, 4)], (2, 5): [(1, 5)], (2, 6): [], (2, 7): [(3, 7)], (2, 8): [(1, 8), (3, 8)], (3, 1): [], (3, 2): [(2, 2), (4, 2)], (3, 3): [], (3, 4): [(2, 4), (3, 5)], (3, 5): [(3, 4), (3, 6)], (3, 6): [(3, 5), (4, 6), (3, 7)], (3, 7): [(2, 7), (3, 6), (4, 7)], (3, 8): [(4, 8), (2, 8)], (4, 1): [], (4, 2): [(3, 2), (4, 3)], (4, 3): [(4, 2), (4, 4)], (4, 4): [(4, 3)], (4, 5): [(4, 6)], (4, 6): [(3, 6), (4, 5)], (4, 7): [(3, 7), (4, 8)], (4, 8): [(4, 7), (3, 8)]}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VZnyAIFp2yQ3"
      },
      "source": [
        "# dessin de votre labyrinthe\n",
        "En creant votre graphe vous avez creer votre labyrinthe.\n",
        "Pour visualiser le labyrinthe vous allez avoir besoin des fonctions ci-dessous.\n",
        "Vpus n'avez pas besoin de les regarder, la seule chose dont vous avez besoin c'est de dessiner ce labyrinthe en executant dans la cellule suivante la commande showLabyrinthe(cote,nli,ncol) ou :\n",
        "cote est un entier qui code la longuer des coté des cases (ici on va prendre 50)\n",
        "nli et ncol sont les nombres de lignes et de colones de votre labyrinthe, donc ici 4 et 8"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FZwiR1bm2yQ4"
      },
      "source": [
        "import turtle as t\n",
        "\n",
        "def showLabyrinthe(labyrinthe,cote,nli,ncol):\n",
        "  lab=t.Turtle()\n",
        "  t.speed(0)\n",
        "\n",
        "  cadre(nli,ncol,cote)\n",
        "  paroiesVerticales(nli,ncol,cote)\n",
        "  paroiesHorizontales(nli,ncol,cote)\n",
        "  #t.exitonclick()\n",
        "  t.mainloop()\n",
        "\n",
        "\n",
        "def cadre(nli,ncol,cote):\n",
        "    t.up()\n",
        "    t.goto(-100,100)\n",
        "    t.down()\n",
        "    #dessin parois extérieures\n",
        "\n",
        "    for _ in range(2):\n",
        "        for i in range(ncol):\n",
        "            t.forward(cote)\n",
        "        t.right(90)\n",
        "        for i in range(nli):\n",
        "            t.forward(cote)\n",
        "        t.right(90)\n",
        "\n",
        "def paroiesVerticales(nli,ncol,dist):\n",
        "    # dessin des parois internes verticales\n",
        "\n",
        "    for i in range(1,nli+1):\n",
        "        for j in range(1,ncol) :\n",
        "            dess=(i,j+1) not in labyrinthe.lstAdj[(i,j)]\n",
        "            if dess :\n",
        "                t.up()\n",
        "                t.forward(dist)\n",
        "                t.down()\n",
        "                t.right(90)\n",
        "                t.forward(dist)\n",
        "                t.backward(dist)\n",
        "                t.left(90)\n",
        "            else :\n",
        "                t.up()\n",
        "                t.forward(dist)\n",
        "\n",
        "        t.up()\n",
        "        t.goto(-100,100)\n",
        "        t.right(90)\n",
        "        t.forward(dist*i)\n",
        "        t.left(90)\n",
        "def paroiesHorizontales(nli,ncol,cote):\n",
        "\n",
        "    # dessin des parois internes horizontales\n",
        "    t.up()\n",
        "    t.goto(-100,100-cote)\n",
        "    for i in range(1,nli):\n",
        "        for j in range(1,ncol) :\n",
        "            dess=(i+1,j) not in labyrinthe.lstAdj[(i,j)]\n",
        "            if dess :\n",
        "                t.down()\n",
        "                t.forward(cote)\n",
        "            else :\n",
        "                t.up()\n",
        "                t.forward(cote)\n",
        "\n",
        "        t.up()\n",
        "        t.goto(-100,100-cote*(i+1))\n",
        "\n"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kEIDt08a2yQ7",
        "outputId": "beff7ddd-606a-496f-ed1b-6f50aa4389e1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 361
        }
      },
      "source": [
        "#exécutez le dessin :\n",
        "showLabyrinthe(labyrinthe,50,4,8)\n",
        "\n",
        "#le dessin peut s'ouvrir dans une fenêtre qui sera peut-être en bas de l'écran dans la barre de tâches\n",
        "######### ATTENTION ##############\n",
        "# avant de poursuivre vous devez ouvrir la fenêtre.\n",
        "# Vous devrez ensuite ne pas oublier de fermer cette fenêtre"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "error",
          "ename": "TclError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTclError\u001b[0m                                  Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-15-f605e41649ef>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m#exécutez le dessin :\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mshowLabyrinthe\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlabyrinthe\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m50\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m8\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;31m#le dessin peut s'ouvrir dans une fenêtre qui sera peut-être en bas de l'écran dans la barre de tâches\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;31m######### ATTENTION ##############\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-14-6a10fd6f9d38>\u001b[0m in \u001b[0;36mshowLabyrinthe\u001b[0;34m(labyrinthe, cote, nli, ncol)\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mshowLabyrinthe\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlabyrinthe\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mcote\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mnli\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mncol\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m   \u001b[0mlab\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTurtle\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m   \u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mspeed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, shape, undobuffersize, visible)\u001b[0m\n\u001b[1;32m   3810\u001b[0m                  visible=_CFG[\"visible\"]):\n\u001b[1;32m   3811\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3812\u001b[0;31m             \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mScreen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3813\u001b[0m         RawTurtle.__init__(self, Turtle._screen,\n\u001b[1;32m   3814\u001b[0m                            \u001b[0mshape\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mshape\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36mScreen\u001b[0;34m()\u001b[0m\n\u001b[1;32m   3660\u001b[0m     else return the existing one.\"\"\"\n\u001b[1;32m   3661\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3662\u001b[0;31m         \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_Screen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3663\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3664\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m   3676\u001b[0m         \u001b[0;31m# preserved (perhaps by passing it as an optional parameter)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3677\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3678\u001b[0;31m             \u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_Root\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3679\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtitle\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_title\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3680\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mondestroy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_destroy\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    432\u001b[0m     \u001b[0;34m\"\"\"Root class for Screen based on Tkinter.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    433\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__init__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 434\u001b[0;31m         \u001b[0mTK\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTk\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__init__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    435\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    436\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0msetupcanvas\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwidth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mheight\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcwidth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcheight\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/tkinter/__init__.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, screenName, baseName, className, useTk, sync, use)\u001b[0m\n\u001b[1;32m   2021\u001b[0m                 \u001b[0mbaseName\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbaseName\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mext\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2022\u001b[0m         \u001b[0minteractive\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 2023\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtk\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_tkinter\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcreate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mscreenName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbaseName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mclassName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minteractive\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwantobjects\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0museTk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msync\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0muse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   2024\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0museTk\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2025\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_loadtk\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mTclError\u001b[0m: no display name and no $DISPLAY environment variable"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c-PXbKNa2yQ-"
      },
      "source": [
        "Maintenant comme pour comme pour le labyrinthe, vous allez pouvoir visualiser le graphe avec le code ci-dessous.\n",
        "Vous pourrez l'exécuter  la cellule suivante."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WHIHjrRT2yQ-"
      },
      "source": [
        "import turtle as t\n",
        "\n",
        "def drawGraph() :\n",
        "    lab=t.Turtle()\n",
        "    t.speed(0)\n",
        "    t.up()\n",
        "    t.ht()\n",
        "    t.goto(-100,100)\n",
        "    for i in range(1,5) :\n",
        "        for j in range(1,9) :\n",
        "            drawCircle(50,i,j)\n",
        "            t.forward(50)\n",
        "        t.right(90)\n",
        "        t.forward(50)\n",
        "        t.left(90)\n",
        "        t.backward(50*8)\n",
        "    #t.exitonclick()\n",
        "    t.mainloop()\n",
        "            \n",
        "def drawCircle(cote,i,j) :\n",
        "    t.up()\n",
        "    t.forward(cote/2)\n",
        "    t.left(90)\n",
        "    t.forward(cote/4)\n",
        "    t.right(90)\n",
        "    t.down()\n",
        "    t.circle(cote/4)\n",
        "    t.left(90)\n",
        "    t.forward(5)\n",
        "    t.write(str(i)+','+str(j),align='center')\n",
        "    t.backward(5)\n",
        "    t.right(90)\n",
        "    if (i+1,j) in labyrinthe.lstAdj[(i,j)] :\n",
        "        drawArreteVert(50)\n",
        "    if (i,j+1) in labyrinthe.lstAdj[(i,j)] :\n",
        "        drawArreteHor(50)\n",
        "    t.up()\n",
        "    t.left(90)\n",
        "    t.backward(cote/4)\n",
        "    t.right(90)\n",
        "    t.backward(cote/2)\n",
        "\n",
        "def drawArreteHor(cote):\n",
        "    t.up()\n",
        "    t.pencolor(\"red\")\n",
        "    t.forward(cote/4)\n",
        "    t.left(90)\n",
        "    t.forward(cote/4)\n",
        "    t.right(90)\n",
        "    t.down()\n",
        "    t.forward(cote/2)\n",
        "    t.up()\n",
        "    t.backward(cote/2)\n",
        "    t.left(90)\n",
        "    t.backward(cote/4)\n",
        "    t.right(90)\n",
        "    t.backward(cote/4)\n",
        "    t.pencolor(\"black\")\n",
        "    \n",
        "def drawArreteVert(cote):\n",
        "        t.pencolor(\"red\")\n",
        "        t.right(90)\n",
        "        t.forward(cote/2)\n",
        "        t.backward(cote/2)\n",
        "        t.left(90)\n",
        "        t.pencolor(\"black\")\n",
        "        \n"
      ],
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PZiuj4N_2yRB",
        "outputId": "3ac01a45-a772-4569-e1cc-9455c09717f6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 296
        }
      },
      "source": [
        "drawGraph()"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "error",
          "ename": "TclError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTclError\u001b[0m                                  Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-19-a259729fedb2>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mdrawGraph\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-18-a7bf9a289f8b>\u001b[0m in \u001b[0;36mdrawGraph\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mdrawGraph\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0mlab\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTurtle\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m     \u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mspeed\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m     \u001b[0mt\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mup\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, shape, undobuffersize, visible)\u001b[0m\n\u001b[1;32m   3810\u001b[0m                  visible=_CFG[\"visible\"]):\n\u001b[1;32m   3811\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3812\u001b[0;31m             \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mScreen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3813\u001b[0m         RawTurtle.__init__(self, Turtle._screen,\n\u001b[1;32m   3814\u001b[0m                            \u001b[0mshape\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mshape\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36mScreen\u001b[0;34m()\u001b[0m\n\u001b[1;32m   3660\u001b[0m     else return the existing one.\"\"\"\n\u001b[1;32m   3661\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3662\u001b[0;31m         \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_Screen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3663\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mTurtle\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_screen\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3664\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m   3676\u001b[0m         \u001b[0;31m# preserved (perhaps by passing it as an optional parameter)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3677\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 3678\u001b[0;31m             \u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_Root\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   3679\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtitle\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0m_Screen\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_title\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   3680\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_root\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mondestroy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_destroy\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/turtle.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    432\u001b[0m     \u001b[0;34m\"\"\"Root class for Screen based on Tkinter.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    433\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__init__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 434\u001b[0;31m         \u001b[0mTK\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTk\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__init__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    435\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    436\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0msetupcanvas\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwidth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mheight\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcwidth\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcheight\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/usr/lib/python3.6/tkinter/__init__.py\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self, screenName, baseName, className, useTk, sync, use)\u001b[0m\n\u001b[1;32m   2021\u001b[0m                 \u001b[0mbaseName\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbaseName\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mext\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2022\u001b[0m         \u001b[0minteractive\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 2023\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtk\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_tkinter\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcreate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mscreenName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbaseName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mclassName\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minteractive\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mwantobjects\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0museTk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msync\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0muse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   2024\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0museTk\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   2025\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_loadtk\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mTclError\u001b[0m: no display name and no $DISPLAY environment variable"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XEkauTjw2yRE"
      },
      "source": [
        "Comme vous pouvez le constater, toutes les arêtes issues de (2,6) ont été oubliées....\n",
        "A vous de les ajouter, puis de redessiner le labyrinthe et le graphe pour vérifier."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UDMHUSbB2yRE"
      },
      "source": [
        "labyrinthe.addArete((2,5),(2,6))\n",
        "labyrinthe.addArete((2,6),(1,6))\n",
        "labyrinthe.addArete((2,6),(3,6))\n",
        "labyrinthe.addArete((2,6),(2,7))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22W7Ript2yRH"
      },
      "source": [
        "#réexécutez le dessin du labyrinthe:\n",
        "showLabyrinthe(labyrinthe,50,4,8)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MiQqzUge2yRJ"
      },
      "source": [
        "#réexécutez le dessin du graphe:\n",
        "drawGraph()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IYQJiS232yRM"
      },
      "source": [
        "<center><font color=\"red\" size=\"10\">Questions</font></center>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4aJNEmXB2yRN"
      },
      "source": [
        "<b>1) Faites afficher les case ou je peux me rendre si je suis en (3,4)</b>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ENjuIsdp2yRN"
      },
      "source": [
        "print(labyrinthe.lstAdj[(3,4)])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WtbQqC8M2yRQ"
      },
      "source": [
        "<b>2) Ecrire une fonction passage(case1,case2) qui renvoie True si on peut passer de case1 à case2 et False sinon.\n",
        "</br>    \n",
        "</b>\n",
        "La fonction doit vérifier que les 2 cases sont contiguës et qu'il n'y a pas de paroie empêchant le passage"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1x1NuZxM2yRR"
      },
      "source": [
        "def passage(case1,case2) :\n",
        "    voisinH = case1[0]==case2[0] and abs(case1[1]-case2[1])==1\n",
        "\n",
        "    voisinV = case1[1]==case2[1] and abs(case1[0]-case2[0])==1\n",
        "\n",
        "    paroie = case2 not in labyrinthe.lstAdj[case1]\n",
        "    if (voisinH or voisinV) and  not paroie :\n",
        "        return True\n",
        "    else :\n",
        "        return False\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yHnCqArD2yRT"
      },
      "source": [
        "#tests :\n",
        "ok=True\n",
        "if passage( (1,2),(2,2))!=False : ok=False\n",
        "if passage( (2,2),(3,2))!=True  : ok=False\n",
        "if passage( (2,2),(3,3))!=False : ok=False\n",
        "if passage( (2,2),(2,2))!=False : ok=False\n",
        "if passage( (2,2),(1,1))!=False : ok=False\n",
        "if passage( (2,3),(2,5))!=False : ok=False\n",
        "\n",
        "if ok :\n",
        "    print('Tests ok') \n",
        "else :\n",
        "    print(\"passage n'a pas passé les tests\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0CkHiE9g2yRV"
      },
      "source": [
        "## IV. Représentation du graphe  et approfondissement de la notion de dictionnaire"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Gw8obfGg2yRW"
      },
      "source": [
        "Il n'est pas habituel de représenter des noeuds pas des couples. On rencontre habituellement de simples numéros.\n",
        "\n",
        "1.  Au lieu de choisir comme clés du dictionnnaire des tuples, aurait-il été possible de choisir des listes ?\n",
        "Par exemple à la clé [1,1], correspondrait la valeur [(2, 1)]."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cJk5Bf5y2yRW"
      },
      "source": [
        "Réponse : Non, ce n'est pas possible car les clés des dictionnaires doivent être de type non mutable, ce qui n'est pas le cas des listes.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PDy4IJlK2yRW"
      },
      "source": [
        "Sur son site, David Roche explique : \"l'implémentation des dictionnaires dans les langages de programmation peut se faire à l'aide des tables de hachage. Les tables de hachages ainsi que les fonctions de hachages qui sont utilisées pour construire les tables de hachages, ne sont pas au programme de NSI. Cependant, l'utilisation des fonctions de hachages est omniprésente en informatique, il serait donc bon, pour votre \"culture générale informatique\", de connaitre le principe des fonctions de hachages.\n",
        "Pour avoir quelques idées sur le principe des tables de hachages, je vous recommande le visionnage de cette vidéo : [https://www.youtube.com/watch?v=CkLctGYWFPA]\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "96SpwZZ-2yRX"
      },
      "source": [
        "2. Pour simplifier la représentation de ce graphe, nous allons remplacer chaque noeud (i,j) par un simple numéro:\n",
        "(1,1) sera remplacé par 1, (1,2) par 2, (1,3) par 3 ... (2,1) par 9 etc...\n",
        "D'une manière générale, (i,j) sera remplacé par le numéro (i-1)*8+j.\n",
        "Dans la première partie, nous avons créé le dictionnaire suivant :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8Upa23342yRZ"
      },
      "source": [
        "labyrinthe = {(1, 1): [(2, 1)], (1, 2): [], (1, 3): [(2, 3), (1, 4)], (1, 4): [(1, 3), (1, 5), (2, 4)], (1, 5): [(1, 4), (2, 5)],\\\n",
        " (1, 6): [(2, 6), (1, 7)], (1, 7): [(1, 6), (1, 8)], (1, 8): [(1, 7), (2, 8)], (2, 1): [(1, 1), (2, 2)],\\\n",
        " (2, 2): [(2, 1), (2, 3), (3, 2)], (2, 3): [(2, 2), (1, 3)], (2, 4): [(1, 4), (3, 4)], (2, 5): [(1, 5), (2, 6)],\\\n",
        " (2, 6): [(2, 5), (1, 6), (3, 6), (2, 7)], (2, 7): [(3, 7), (2, 6)], (2, 8): [(1, 8), (3, 8)], (3, 1): [],\\\n",
        " (3, 2): [(2, 2), (4, 2)], (3, 3): [], (3, 4): [(2, 4), (3, 5)], (3, 5): [(3, 4), (3, 6)], \\\n",
        " (3, 6): [(2, 6), (3, 5), (4, 6), (3, 7)], (3, 7): [(2, 7), (3, 6), (4, 7)], (3, 8): [(2, 8), (4, 8)], (4, 1): [],\\\n",
        " (4, 2): [(3, 2), (4, 3)], (4, 3): [(4, 2), (4, 4)], (4, 4): [(4, 3)], (4, 5): [(4, 6)], (4, 6): [(3, 6), (4, 5)],\\\n",
        " (4, 7): [(3, 7), (4, 8)], (4, 8): [(4, 7), (3, 8)]}"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6ANwRpo32yRc"
      },
      "source": [
        "Vous devez créer un dictionnaire qui représente le même graphe, mais avec les noeuds simplifiés. On obtient :  \n",
        "`graphe_allege = {1: [9], 2: [], 3: [11, 4] etc...}`  \n",
        "Pour cela vous pouvez créer des correspondances entre les couples (i,j) et le numéro correspondant. Réfléchissez à la structure adaptée que vous allez utiliser pour cela.\n",
        "Utilisez cette structure pour écrire le script qui crée ce nouveau dictionnaire."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S7zs6VmX2yRc"
      },
      "source": [
        "corresp = {}\n",
        "for i in range(1,5):\n",
        "    for j in range(1,9):\n",
        "        corresp[(i,j)]=(i-1)*8+j\n",
        "print(\"Correspondances : \",corresp)\n",
        "\n",
        "\n",
        "labyrinthe = {(1, 1): [(2, 1)], (1, 2): [], (1, 3): [(2, 3), (1, 4)], (1, 4): [(1, 3), (1, 5), (2, 4)], (1, 5): [(1, 4), (2, 5)],\\\n",
        " (1, 6): [(2, 6), (1, 7)], (1, 7): [(1, 6), (1, 8)], (1, 8): [(1, 7), (2, 8)], (2, 1): [(1, 1), (2, 2)],\\\n",
        " (2, 2): [(2, 1), (2, 3), (3, 2)], (2, 3): [(2, 2), (1, 3)], (2, 4): [(1, 4), (3, 4)], (2, 5): [(1, 5), (2, 6)],\\\n",
        " (2, 6): [(2, 5), (1, 6), (3, 6), (2, 7)], (2, 7): [(3, 7), (2, 6)], (2, 8): [(1, 8), (3, 8)], (3, 1): [],\\\n",
        " (3, 2): [(2, 2), (4, 2)], (3, 3): [], (3, 4): [(2, 4), (3, 5)], (3, 5): [(3, 4), (3, 6)], \\\n",
        " (3, 6): [(2, 6), (3, 5), (4, 6), (3, 7)], (3, 7): [(2, 7), (3, 6), (4, 7)], (3, 8): [(2, 8), (4, 8)], (4, 1): [],\\\n",
        " (4, 2): [(3, 2), (4, 3)], (4, 3): [(4, 2), (4, 4)], (4, 4): [(4, 3)], (4, 5): [(4, 6)], (4, 6): [(3, 6), (4, 5)],\\\n",
        " (4, 7): [(3, 7), (4, 8)], (4, 8): [(4, 7), (3, 8)]}\n",
        "graphe_allege = {}\n",
        "for noeud in labyrinthe:\n",
        "    graphe_allege[corresp[noeud]]=[corresp[tuple] for tuple in labyrinthe[noeud]]\n",
        "print(\"Nouveau dictionnaire : \",graphe_allege)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tqWWVTVB2yRe"
      },
      "source": [
        "Nous pouvons déjà visualiser succinctement ce ghraphe grâce au code ci-dessous.\n",
        "Remarque : vous pouvez exécuter plusieurs fois les lignes qui suivent, jusqu'à obtenir une représentation plus \"agréable\"\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "omMdWqLn2yRf"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "import networkx as nx\n",
        "def cree_graphe_non_oriente_nx(dictionnaire: dict) -> nx.Graph:\n",
        "    \"\"\"\n",
        "    Cette fonction premet de transformer une représentation en dictionnaire en\n",
        "    une représentation «complexe» d'un objet graphe orienté.\n",
        "\n",
        "    - Précondition : l'entrée est un dictionnaire\n",
        "    - Postcondition : la sortie est un graphe orienté (Graph) de Networkx\n",
        "    \"\"\"\n",
        "    Gnx = nx.Graph() \n",
        "    for sommets in dictionnaire.keys():\n",
        "        Gnx.add_node(sommets) # Creation des sommets\n",
        "    for sommet in dictionnaire.keys():\n",
        "        for sommets_adjacents in dictionnaire[sommet]:\n",
        "            Gnx.add_edge(sommet, sommets_adjacents,length=300) # Creation des arcs\n",
        "    return Gnx\n",
        "\n",
        "\n",
        "\n",
        "graphe={1: [9], 2: [], 3: [11, 4], 4: [3, 5, 12], 5: [4, 13], 6: [14, 7], 7: [6, 8], 8: [7, 16], 9: [1, 10],\\\n",
        "        10: [9, 11, 18], 11: [10, 3], 12: [4, 20], 13: [5, 14], 14: [13, 6, 22, 15], 15: [23, 14], 16: [8, 24],\\\n",
        "        17: [], 18: [10, 26], 19: [], 20: [12, 21], 21: [20, 22], 22: [14, 21, 30, 23], 23: [15, 22, 31],\\\n",
        "        24: [16, 32], 25: [], 26: [18, 27], 27: [26, 28], 28: [27], 29: [30], 30: [22, 29], 31: [23, 32], 32: [31, 24]}\n",
        "G=cree_graphe_non_oriente_nx(graphe)\n",
        "nx.draw(G,with_labels=True, node_color='white',width=3, node_size=100) # Pour une representation classique\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uBmr4GgR2yRh"
      },
      "source": [
        "3. Inversement, si on désire passer de la notation simplifiée d'un noeud, à la notation antérieure, comment doit-on procéder?  \n",
        "\n",
        "Ecrire une fonction `def numero_to_tuple(entier)` qui prend en argument un entier et renvoie le tuple correspondant. Compléter ci-dessous."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J9onTQAY2yRh"
      },
      "source": [
        "from doctest import testmod\n",
        "def numero_to_tuple(entier):\n",
        "    \"\"\"\n",
        "    precondition : entier est de type str\n",
        "    postcondition : la fonction renvoie un couple\n",
        "    Par exemple :\n",
        "    >>> numero_to_tuple(1)\n",
        "    (1, 1)\n",
        "    >>> numero_to_tuple(2)\n",
        "    (1, 2)\n",
        "    >>> numero_to_tuple(8)\n",
        "    (1, 8)\n",
        "    >>> numero_to_tuple(9)\n",
        "    (2, 1)\n",
        "    >>> numero_to_tuple(32)\n",
        "    (4, 8)\n",
        "\n",
        "    \"\"\"\n",
        "    if entier % 8 == 0:\n",
        "        return (entier//8 , 8)\n",
        "    else :\n",
        "        return (entier//8 + 1, entier%8)\n",
        "\n",
        "\n",
        "\n",
        "print(testmod())"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d8r_QmaN2yRj"
      },
      "source": [
        "## V. Autre représentation plus élégante : 😄"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "OJqasoSp2yRk"
      },
      "source": [
        "Cette représentation n'est quand même pas très belle. Nous pouvons procéder autrement :"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9hCOKSsd2yRk"
      },
      "source": [
        "Ici on met la technique de Jean-Louis, je n'ai pas bien compris laquelle ..."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GoeUQUaW2yRl"
      },
      "source": [
        "## VI. Votre problème :🤔"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I6pszHue2yRl"
      },
      "source": [
        "Ce labyrinthe est assez simple, et une fois sa représentation en graphe tracée, il semble assez facile de résoudre ce labyrinthe, c'est à dire de trouver un chemin  qui permette d'aller d'une case \"entrée\" à une case \"sortie\".  \n",
        "Nous voulons écrire un script Python qui permette de résoudre automatiquement, dans le cas où c'est possible, n'importe quel labyrinthe, même très compliqué.   \n",
        "Pour cela on peut penser parcourir le graphe en partant de l'entrée, en suivant différents chemins, jusqu'à atteindre le sommet de sortie.  \n",
        "Plusieurs algorithmes \"classiques\" permettent de parcourir les graphes. Nous allons commencer par les étudier, puis nous essaierons de résoudre ce problème en choisissant l'algorithme le plus adapté à cette situation."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1JpQfeDm2yRl"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}