Professeur_populaire_corrige.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Professeur populaire corrige.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOC8pFq2t6yiD3vCnrSQESM",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/GeoLabUniLaSalle/Python/blob/main/Professeur_populaire_corrige.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R8kQ2CJh9aDY"
      },
      "source": [
        "## **Professeur populaire ★★☆**\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*Exercice disponible sur la plateforme TOSA : Battle Dev Hello Works - Novembre 2018 : https://www.isograd.com/FR/solutionconcours.php*\n",
        "\n",
        "\n",
        "\n",
        "**Enoncé**\n",
        "\n",
        "\n",
        "Vous vous êtes enfin décidé à monétiser vos connaissances en algorithmique en proposant des cours particuliers à des parents remplis d'espoirs injustifiés. Vous devenez rapidement très populaire, trop populaire, vous n'êtes plus sûr de pouvoir assurer tous vos cours. Pour avoir plus de chance d'acquérir votre savoir, tous vos élèves vous proposent deux créneaux de 60 minutes pendant lesquels ils sont disponibles, vous ne pourrez leur donner cours que sur un seul de ces deux créneaux (si vous avez le temps).\n",
        "\n",
        "Sachant que vous ne pouvez donner cours qu'à un seul élève en même temps et que vous ne pouvez pas commencer un cours et en terminer un autre à la même minute, combien d'élèves différents pouvez-vous prendre au maximum ?\n",
        "\n",
        "Indication : vous pouvez procéder par énumération exhaustive (force brute).\n",
        "\n",
        "**Format des données**\n",
        "\n",
        "*Entrée*\n",
        "\n",
        "\n",
        "Ligne 1 : un entier N entre 3 et 8 inclus, le nombre d'étudiants.\n",
        "\n",
        "Lignes 2 à N+1 : deux entiers entre 0 et 1000 inclus, les deux débuts de créneaux (en minutes) auxquels un étudiant est disponible, chaque créneau a une durée de 60 minutes à partir des débuts indiqués.\n",
        "\n",
        "\n",
        "\n",
        "*Sortie*\n",
        "\n",
        "Le nombre maximum d'étudiant différents qu'il est possible de prendre.\n",
        "\n",
        "*Exemple*\n",
        "\n",
        "Pour l'entrée suivante :\n",
        "\n",
        "\n",
        "5\n",
        "\n",
        "205 300\n",
        "\n",
        "210 370\n",
        "\n",
        "290 380\n",
        "\n",
        "120 305\n",
        "\n",
        "390 110\n",
        "\n",
        "La réponse attendue est 4. Vous pourrez par exemple prendre les 4 étudiants suivants :\n",
        "- L'étudiant 1 sur son premier créneau de 205 à 265\n",
        "- L'étudiant 2 sur son second créneau de 370 à 430\n",
        "- L'étudiant 3 sur son premier créneau de 290 à 350\n",
        "- L'étudiant 4 sur son premier créneau de 120 à 180\n",
        "Il est possible de prendre d'autres combinaisons de 4 étudiants sur différents créneaux, mais il n'en existe aucune à 5 étudiants."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LaFrvPhE-Ezb"
      },
      "source": [
        "## **Données**\n",
        "\n",
        "*Accès aux données*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2HlpCu_r-aqr",
        "outputId": "dd8b1858-bedc-4b4c-e09f-7ee26d2367b0"
      },
      "source": [
        "import csv\n",
        "filedir = ('https://cours.unilasalle.fr/courses/SG4007/document/Exercices_Python/Professeur_populaire/')\n",
        "\n",
        "import ssl\n",
        "ssl._create_default_https_context = ssl._create_unverified_context\n",
        "\n",
        "import urllib.request\n",
        "\n",
        "for x in range(1,6):\n",
        "  f = urllib.request.urlopen(str(filedir+\"input\"+str(x)+\".txt\"))\n",
        "\n",
        "  data=[]\n",
        "  for i in f:\n",
        "      line=i.decode('utf-8').strip()\n",
        "      data.append(line)\n",
        "  print('Entrée',x,':',data)\n",
        "\n",
        "  f = urllib.request.urlopen(str(filedir+\"output\"+str(x)+\".txt\"))\n",
        "  for i in f:\n",
        "      line=i.decode('utf-8').strip()\n",
        "  print('Sortie',x,':',line,'\\n')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Entrée 1 : ['3', '60 400', '120 340', '120 400']\n",
            "Sortie 1 : 2 \n",
            "\n",
            "Entrée 2 : ['5', '205 300', '210 370', '290 380', '120 305', '390 110']\n",
            "Sortie 2 : 4 \n",
            "\n",
            "Entrée 3 : ['6', '69 150', '65 166', '67 13', '199 116', '33 8', '27 82']\n",
            "Sortie 3 : 3 \n",
            "\n",
            "Entrée 4 : ['6', '347 94', '256 500', '335 480', '479 57', '135 300', '247 388']\n",
            "Sortie 4 : 5 \n",
            "\n",
            "Entrée 5 : ['8', '799 978', '180 600', '907 852', '967 576', '697 37', '682 391', '364 214', '220 833']\n",
            "Sortie 5 : 8 \n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yKMr4hZ0UIQy"
      },
      "source": [
        "Commençons par convertir le contenu de lines en une liste de tuples entiers :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XzvirjlS2Ipm",
        "outputId": "a868891c-beac-4000-c971-6fbd87645f88"
      },
      "source": [
        "lines = ['3', '60 400', '120 340', '120 400']\n",
        "N=int(lines[0])\n",
        "T = []\n",
        "for i in lines[1:]:\n",
        "  T.append((int(i.split()[0]),int(i.split()[1])))\n",
        "print(T)"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[(60, 400), (120, 340), (120, 400)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LLE935faUWlQ"
      },
      "source": [
        "Il s'agit ici de traiter le problème par force, brute, c'est à dire, d'envisager toutes les combinaisons possibles.\n",
        "\n",
        "Le nombre de combinaisons est de 2^N puisque pour chaque étudiant, il y a deux créneaux possibles.\n",
        "\n",
        "Voici quelques exemples de combinaisons :\n",
        "On prend le premier choix (indice 0) de chaque étudiant : 0, 0, 0\n",
        "On prend de second choix (indice 1) pour le 1er et le 3ème étudiant, et le premier choix pour le second étudiant : 1, 0, 1\n",
        "\n",
        "La liste des combinaisons peut être obtenue en comptant en base 2 :\n",
        "\n",
        "000\n",
        "\n",
        "001\n",
        "\n",
        "010\n",
        "\n",
        "011\n",
        "\n",
        "100\n",
        "\n",
        "101\n",
        "\n",
        "110\n",
        "\n",
        "111\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rd0uAL3YVPBo",
        "outputId": "cc9d4bcd-6f31-4272-9a5c-c0af755251e8"
      },
      "source": [
        "for i in range(2**N):\n",
        "  b = format(i,'0'+str(N)+'b')\n",
        "  print(b)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "000\n",
            "001\n",
            "010\n",
            "011\n",
            "100\n",
            "101\n",
            "110\n",
            "111\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EPmWnalgVXIt"
      },
      "source": [
        "On obtient les combinaisons correspondantes ainsi :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_RziVJWyVfpK",
        "outputId": "981f1f59-79fc-4837-b369-0eca6e4f2b94"
      },
      "source": [
        "for i in range(2**N):\n",
        "  b = format(i,'0'+str(N)+'b')\n",
        "  print((T[0][int(b[0])],T[1][int(b[1])],T[2][int(b[2])]))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(60, 120, 120)\n",
            "(60, 120, 400)\n",
            "(60, 340, 120)\n",
            "(60, 340, 400)\n",
            "(400, 120, 120)\n",
            "(400, 120, 400)\n",
            "(400, 340, 120)\n",
            "(400, 340, 400)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0deZjUOyVrEc"
      },
      "source": [
        "Nous allons maintenant généraliser pour que cela fonctionne quelque soit la valeur de N :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "e9zJZkDTVweP",
        "outputId": "883760a2-99d0-4ae5-ab3f-1e63406232c3"
      },
      "source": [
        "c=[]\n",
        "for i in range(2**N):\n",
        "  b = format(i,'0'+str(N)+'b')\n",
        "  v=[]\n",
        "  for j in range(N):\n",
        "    v.append(T[j][int(b[j])])\n",
        "  print(v)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[60, 120, 120]\n",
            "[60, 120, 400]\n",
            "[60, 340, 120]\n",
            "[60, 340, 400]\n",
            "[400, 120, 120]\n",
            "[400, 120, 400]\n",
            "[400, 340, 120]\n",
            "[400, 340, 400]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QciQ3ntxV_kJ"
      },
      "source": [
        "Stockons ces valeurs dans une liste qui contient donc toutes les combinaisons possibles, et trions les combinaisons d'horaires en ordre croissant :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kJQrWq7aWCI1",
        "outputId": "a9e7ce4d-b9fe-40bc-eae5-02b944fc5db8"
      },
      "source": [
        "c=[]\n",
        "for i in range(2**N):\n",
        "  b = format(i,'0'+str(N)+'b')\n",
        "  v=[]\n",
        "  for j in range(N):\n",
        "    v.append(T[j][int(b[j])])\n",
        "  c.append(sorted(v))\n",
        "print(c)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[60, 120, 120], [60, 120, 400], [60, 120, 340], [60, 340, 400], [120, 120, 400], [120, 400, 400], [120, 340, 400], [340, 400, 400]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZX6DchcjWLSB"
      },
      "source": [
        "Il ne nous reste plus qu'à rechercher le nombre de rendez-vous que peut honorer le professeur pour chaque combinaison, et à retenir la plus grande valeur :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sm11I7f72c01",
        "outputId": "de46d682-6bc1-4b9b-eabf-6c1eefc315ff"
      },
      "source": [
        "max=1\n",
        "for i in range(len(c)):\n",
        "  maxi = 1\n",
        "  debut=c[i][0]\n",
        "  for j in range(N):\n",
        "    if debut+60<c[i][j]:\n",
        "      maxi+=1\n",
        "      debut=c[i][j]\n",
        "  if maxi>max:\n",
        "    max=maxi\n",
        "print(max)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}