{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3c2317b2",
   "metadata": {},
   "source": [
    "# Feuille d'exercices 3 -- avancé\n",
    "\n",
    "\n",
    "```{warning} \n",
    "Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d'exercices \"classiques\".\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Exercice 8 : anagrammes\n",
    "\n",
    "Deux mots sont appelés des **anagrammes** s'ils sont composés d'exactement les mêmes lettres (comptées avec leur multiplicité). Par exemple :\n",
    "- \"juste\" et \"sujet\" sont des anagrammes\n",
    "- \"cannes\" et \"encas\" ne sont pas des anagrammes, car la lettre \"n\" apparaît 2 fois dans \"cannes\" et seulement une fois dans \"encas\".\n",
    "\n",
    "**Question 1.** Écrire une fonction `anagramme(mot1, mot2)` qui prend en entrée deux mots sous la forme de chaînes de caractères, et qui teste si ces deux mots sont l'anagramme l'un de l'autre.\n",
    "\n",
    "\n",
    "Voici une solution **sans utiliser de dictionnaire**. L'idée est la suivante : on crée la liste des caractères de chaque mot, puis tant que c'est possible,  on élimine des caractères simultanément dans les deux listes. Si on n'aboutit pas à deux listes vides, c'est que les deux mots ne sont pas des anagrammes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1f465b76",
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagramme(mot1, mot2):\n",
    "\n",
    "    # on vérifie si les mots ont la même longueur\n",
    "    n = len(mot1)\n",
    "    if n != len(mot2):\n",
    "        return False\n",
    "    \n",
    "    # on crée la liste des caractères\n",
    "    caracteres1 = [ c for c in mot1 ]\n",
    "    caracteres2 = [ c for c in mot2 ]\n",
    "    \n",
    "    # on parcourt les caractères de la première liste\n",
    "    for i in range(n):\n",
    "        c = caracteres1.pop()\n",
    "        \n",
    "        # on cherche le caractère dans la seconde liste\n",
    "        trouve = False\n",
    "        j = 0\n",
    "        while j < n-i and not(trouve):\n",
    "            if caracteres2[j] == c:\n",
    "                caracteres2.pop(j)\n",
    "                trouve = True\n",
    "            else:\n",
    "                j += 1\n",
    "    \n",
    "        # si on ne le trouve pas, alors \n",
    "        # les deux mots ne sont pas des anagrammes\n",
    "        if not(trouve):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b97b5187",
   "metadata": {},
   "source": [
    "Voici une autre solution, avec le dictionnaire créé dans un exercice de la feuille \"classique\" :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1eea41be",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compte_caracteres(texte):\n",
    "    D = {}\n",
    "    for c in texte:\n",
    "        if c in D:\n",
    "            D[c] += 1\n",
    "        else:\n",
    "            D[c] = 1\n",
    "    return D\n",
    "    \n",
    "def anagramme_dictionnaire(mot1, mot2):\n",
    "    return compte_caracteres(mot1) == compte_caracteres(mot2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9771a23",
   "metadata": {},
   "source": [
    "**Question 2.** Testez votre fonction avec les paires de mots suivantes :\n",
    "1. \"niche\" et \"chien\"\n",
    "1. \"calcul\" et \"formel\"\n",
    "1. \"anna\" et \"naan\"\n",
    "1. \"sagemath\" et \"sagemath\"\n",
    "1. \"garage\" et \"rage\"\n",
    "1. \"doree\" et \"dorer\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c43bde51",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(anagramme(\"niche\", \"chien\"))\n",
    "print(anagramme(\"calcul\", \"formel\"))\n",
    "print(anagramme(\"anna\", \"naan\"))\n",
    "print(anagramme(\"sagemath\", \"sagemath\"))\n",
    "print(anagramme(\"garage\", \"rage\"))\n",
    "print(anagramme(\"doree\", \"dorer\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5f46e3e",
   "metadata": {},
   "source": [
    "La relation \"être l'anagramme l'un de l'autre\" est une **relation d'équivalence** (vous pouvez le vérifier mathématiquement si vous le souhaitez). On peut donc essayer **d'identifier les différentes \"classes d'anagrammes\"** dans une liste de mots.\n",
    "\n",
    "**Question 3.** Écrire une fonction `classe_anagrammes(liste)` qui prend en entrée une liste de mots `liste`, et qui retourne une liste des classes d'anagrammes de `liste`.\n",
    "\n",
    "Puis, tester sur la liste :\n",
    "```\n",
    "L = [\"niche\", \"casser\", \"carnet\", \"crasse\", \"ressac\", \"sagemath\", \"nectar\", \"chien\"]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e422585",
   "metadata": {},
   "outputs": [],
   "source": [
    "def classe_anagramme(liste):\n",
    "    classes = []\n",
    "    nb_classes = 0\n",
    "    for mot in liste:\n",
    "        i = 0\n",
    "        trouve = False\n",
    "        while i < nb_classes and not(trouve):\n",
    "            if anagramme(mot, classes[i][0]):\n",
    "                classes[i].append(mot)\n",
    "                trouve = True\n",
    "            i += 1\n",
    "        if not(trouve):\n",
    "            classes.append([mot])\n",
    "            nb_classes += 1\n",
    "    return classes\n",
    "    \n",
    "classe_anagramme([\"niche\", \"casser\", \"carnet\", \"crasse\", \"ressac\", \"sagemath\", \"nectar\", \"chien\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f951e40",
   "metadata": {},
   "source": [
    "## Exercice 9 : chiffrement ROT13\n",
    "\n",
    "Le chiffrement **ROT13** est un chiffrement \"jouet\" (c'est-à-dire, à ne pas utiliser sérieusement) qui fonctionne sur des textes contenant uniquement des lettres de l'alphabet en majuscules. Ce chiffrement s'effectue **par substitution** : on remplace les lettres du message clair en des lettres du message chiffré selon la règle suivante :\n",
    "\n",
    "```\n",
    "caractère \"clair\"   : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z\n",
    "caractère \"chiffré\" : N O P Q R S T U V W X Y Z A B C D E F G H I J K L M\n",
    "```\n",
    "\n",
    "Par exemple, le caractère `J` est remplacé par le caractère `W`.\n",
    "\n",
    "**Question 1 :** Écrire le dictionnaire de substitution de **ROT13**, c'est-à-dire le **dictionnaire** `SUB` qui a pour clés les caractères \"clairs\" allant de A à Z, et qui a pour valeur correspondant à un caractère clair, le caractère chiffré correspondant. Par exemple, il faut que `SUB['J']` soit égal à `W`.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Solution 1 :**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38864e4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "SUB = {'A': 'N', 'B': 'O', 'C': 'P', 'D': 'Q', 'E': 'R',\n",
    "       'F': 'S', 'G': 'T', 'H': 'U', 'I': 'V', 'J': 'W',\n",
    "       'K': 'X', 'L': 'Y', 'M': 'Z', 'N': 'A', 'O': 'B',\n",
    "       'P': 'C', 'Q': 'D', 'R': 'E', 'S': 'F', 'T': 'G',\n",
    "       'U': 'H', 'V': 'I', 'W': 'J', 'X': 'K', 'Y': 'L',\n",
    "       'Z': 'M'}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6e734f7",
   "metadata": {},
   "source": [
    "**Solution 2**, en utilisant les fonctions de conversion ASCII **`ord`** (pur passer du caractère au code ASCII) et **`chr`** (pour passer du code au caractère) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20d14ef6",
   "metadata": {},
   "outputs": [],
   "source": [
    "SUB = { chr(ord('A') + x): chr(ord('A') + ((x + 13) % 26)) for x in range(26) }\n",
    "SUB"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba8f5b8b",
   "metadata": {},
   "source": [
    "**Question 2 :** Écrire une fonction `chiffre_rot13(texte)` qui prend en entrée un texte formé uniquement de caractères allant de A et Z, et qui retourne le chiffré correspondant par **ROT13**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16f03173",
   "metadata": {},
   "outputs": [],
   "source": [
    "def chiffre_rot13(texte):\n",
    "    res = \"\"\n",
    "    for t in texte:\n",
    "        res += SUB[t]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb652e52",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(chiffre_rot13(\"SAGEMATH\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7d4464e",
   "metadata": {},
   "source": [
    "**Question 3 :** Écrire la fonction de déchiffrement `dechiffre_rot13(chiffre)` qui \"inverse\" le chiffrement, c'est-à-dire qui prend en entrée un texte chiffré par **ROT13**, et qui retourne le texte clair correspondant. Puis, vérifier que le déciffrement d'un chiffré donne le message d'origine.\n",
    "\n",
    "\n",
    "On note que le chiffrement est \"involutif\", c'est-à-dire qu'en chiffant deux fois on retrouve le texte d'origine. On peut donc \"copier\" les fonctions :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7bf55a0d",
   "metadata": {},
   "outputs": [],
   "source": [
    "dechiffre_rot13 = chiffre_rot13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "31d52375",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(dechiffre_rot13('FNTRZNGU'))\n",
    "print(dechiffre_rot13(chiffre_rot13(\"LOGICIELDECALCULFORMEL\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea16ae33",
   "metadata": {},
   "source": [
    "**Question 4 :** Déchiffrer le cryptogramme `SRYVPVGNGVBAF`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9094b619",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(dechiffre_rot13(\"SRYVPVGNGVBAF\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1649f6d9",
   "metadata": {},
   "source": [
    "## Exercice 10 : questions avancées sur les listes\n",
    "\n",
    "**Question 1.** Écrire une fonction `plus_grande_plage(L)` qui prend en entrée une liste d'éléments `L`, et qui retourne la **taille** de la plus grande série d'éléments identiques consécutifs (une telle série est appelée une **plage**). Par exemple, pour la liste `L = [0, 1, 1, 1, 3, 3, 2, 3, 3, 3, 3, 4, 0]`, la fonction retournera $4$, car la plus grande série d'éléments identiques consécutifs est de taille $4$ (c'est une série d'entiers qui valent $3$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7bcb6926",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plus_grande_plage(L):\n",
    "    n = len(L)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    \n",
    "    i = 0\n",
    "    valeur = L[0]\n",
    "    longueur_max = 0\n",
    "    longueur = 0\n",
    "    \n",
    "    while i < n:\n",
    "        longueur = 0\n",
    "        while (i < n and L[i] == valeur):\n",
    "            longueur += 1\n",
    "            i += 1\n",
    "        if (longueur > longueur_max):\n",
    "            longueur_max = longueur\n",
    "        i += 1\n",
    "        if i < n:\n",
    "            valeur = L[i]\n",
    "    return longueur_max\n",
    "\n",
    "L = [0, 1, 1, 1, 3, 3, 2, 3, 3, 3, 3, 4, 0]\n",
    "print(plus_grande_plage(L))\n",
    "        \n",
    "L = [0]*17 \n",
    "print(plus_grande_plage(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bebe4fe4",
   "metadata": {},
   "source": [
    "**Question 2.** Écrire une fonction `troisieme_plus_petit(L)` qui prend en entrée une liste d'entiers `L`, et qui retourne le troisième plus petit entier de la liste. Par exemple, pour la liste `L = [1, -8, -4, 5, 0, 6, -8, 2]`, la fonction retournera $-4$. Si la liste a strictement moins de $3$ éléments, retourner un message d'erreur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e53264ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "def troisieme_plus_petit(L):\n",
    "    if len(L) < 3:\n",
    "        return \"Erreur\"\n",
    "    petits = [ L[0] ]\n",
    "    \n",
    "    if L[1] < petits[0]:\n",
    "        petits.insert(0, L[1])\n",
    "    else:\n",
    "        petits.insert(1, L[1])\n",
    "    \n",
    "    if L[2] < petits[0]:\n",
    "        petits.insert(0, L[2])\n",
    "    elif L[2] < petits[1]:\n",
    "        petits.insert(1, L[2])\n",
    "    else:\n",
    "        petits.insert(2, L[2])\n",
    "    \n",
    "    for i in range(3, len(L)):\n",
    "        x = L[i]\n",
    "        if x < petits[0]:\n",
    "            petits.insert(0, x)\n",
    "        elif x < petits[1]:\n",
    "            petits.insert(1, x)\n",
    "        elif x < petits[2]:\n",
    "            petits.insert(2, x)\n",
    "    \n",
    "    return petits[2]\n",
    "    \n",
    "L = [1, -8, -4, 5, 0, 6, -8, 2]\n",
    "print(troisieme_plus_petit(L))\n",
    "\n",
    "M = [2, 3, 6, 0, 0, 0, 0, -1, 0]\n",
    "print(troisieme_plus_petit(M))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python",
   "language": "python",
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}