Lettres_manquantes.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lettres manquantes.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyPZ8YK9HKvwcIVcrChSIo12",
      "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/Lettres_manquantes.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": [
        "## **Lettres manquantes ★★★**\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*Exercice disponible sur la plateforme TOSA : Battle Dev Hello Works - Mars 2019 : https://www.isograd.com/FR/solutionconcours.php*\n",
        "\n",
        "\n",
        "\n",
        "**Enoncé**\n",
        "\n",
        "Récemment, votre clavier s'est mis à souffrir d'un fâcheux défaut : il arrive que des appuis sur des touches ne soient pas enregistrés. Par conséquent, vous qui aviez pris l'habitude de taper à toute vitesse sans vous relire, vous constatez maintenant quelques lettres manquantes dans vos textes.\n",
        "\n",
        "Heureusement, la plupart du temps, le contexte permet de retrouver quel mot était censé se trouver là. Vous vous demandez donc quelles ambiguïtés sont susceptibles d'apparaître. Étant donnée une liste de mots, vous cherchez à savoir s'il est possible de tous les confondre en supprimant des lettres au milieu.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "**Objectif**\n",
        "\n",
        "L'objectif de ce challenge est donc de trouver une suite de lettres qui se retrouvent, dans le même ordre, dans tous mots de la liste en entrée. On voudrait que cette suite soit la plus longue possible, autrement dit que l'obtenir à partir des mots donnés implique le moins de suppressions de lettres possible. (Pour simplifier, dans cet exercice, les mots de la liste seront tous de longueur 10.)\n",
        "\n",
        "Indication : vous pouvez procéder par énumération exhaustive (force brute).\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "**Format des données**\n",
        "\n",
        "*Entrée*\n",
        "\n",
        "\n",
        "Ligne 1 : un entier N entre 2 et 100, le nombre de mots différents.\n",
        "\n",
        "Lignes 2 à N+1 : sur chaque ligne, une chaîne de 10 caractères constituée uniquement des 26 lettres de l'alphabet en minuscule.\n",
        "\n",
        "\n",
        "\n",
        "*Sortie*\n",
        "\n",
        "Une suite de caractères de longueur maximale qui pourrait être obtenue à partir des mots en entrée par suppression de caractères.\n",
        "Si les mots n'ont aucune lettre commune, affichez KO.\n",
        "\n",
        "*Exemple*\n",
        "\n",
        "Sur l'entrée suivante :\n",
        "\n",
        "3\n",
        "\n",
        "artificiel\n",
        "\n",
        "algorithme\n",
        "\n",
        "algebrique\n",
        "\n",
        "Tous les 3 mots ci-dessus peuvent donner arie en supprimant 6 caractères. En supprimant 5 caractères ou moins, on ne pourrait pas obtenir une suite de lettres commune aux trois mots. C'est donc arie qu'il faut afficher.\n",
        "\n",
        "Si l'entrée avait été :\n",
        "\n",
        "2\n",
        "\n",
        "artificiel\n",
        "\n",
        "algorithme\n",
        "\n",
        "Alors les réponses arie et arte auraient toutes les deux été acceptées.\n",
        "\n",
        "Enfin, sur l'entrée suivante :\n",
        "\n",
        "2\n",
        "\n",
        "algorithme\n",
        "\n",
        "algebrique\n",
        "\n",
        "La réponse attendue est algrie."
      ]
    },
    {
      "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": "a27fd1ec-3b6d-4dc2-9ae1-f70941857d9e"
      },
      "source": [
        "import csv\n",
        "filedir = ('https://cours.unilasalle.fr/courses/SG4007/document/Exercices_Python/Lettres_manquantes/')\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,5):\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 : ['2', 'algebrique', 'algorithme']\n",
            "Sortie 1 : algrie \n",
            "\n",
            "Entrée 2 : ['3', 'artificiel', 'algebrique', 'algorithme']\n",
            "Sortie 2 : arie \n",
            "\n",
            "Entrée 3 : ['2', 'abcdefghij', 'klmnopqrst']\n",
            "Sortie 3 : KO \n",
            "\n",
            "Entrée 4 : ['8', 'jfnjnfjjnn', 'nfjfnfnfnf', 'ffnnnjffnj', 'ffnfjjjnjf', 'fffnnnnffn', 'fjjjfjjnjf', 'ffnfnjjjjn', 'nffnjnffnf']\n",
            "Sortie 4 : fnf \n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}