{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TP — Draft d'Arène : un algorithme glouton en action\n",
    "\n",
    "Dans le mode **Arène** d'un jeu de cartes, on ne joue pas avec sa collection : on **drafte** son deck.\n",
    "On t'ouvre un booster de 3 cartes, tu en gardes **une seule**, et on passe au booster suivant.\n",
    "\n",
    "**Une carte écartée est perdue pour toujours. On ne revient jamais en arrière.**\n",
    "\n",
    "Cette règle du jeu est *exactement* la définition d'un algorithme glouton :\n",
    "\n",
    "- on procède par étapes (un booster à la fois) ;\n",
    "- à chaque étape on fait le meilleur choix possible ;\n",
    "- on ne revient jamais sur un choix déjà fait.\n",
    "\n",
    "Ce TP a un seul but : voir de nos propres yeux **ce que le glouton fait bien, et ce qu'il rate**.\n",
    "\n",
    "---\n",
    "\n",
    "## Les données\n",
    "\n",
    "Une carte est un tuple `(nom, puissance, cout)` :\n",
    "\n",
    "- la **puissance** mesure la force de la carte (plus c'est haut, mieux c'est) ;\n",
    "- le **coût** est le nombre de manas nécessaires pour la poser sur le plateau.\n",
    "\n",
    "> **Règle de jouabilité.** Une carte est dite **chère** si elle coûte **5 manas ou plus**.\n",
    "> Un deck n'est **jouable** que s'il contient **au plus 3 cartes chères**.\n",
    "> Sinon, on n'a rien à jouer pendant les premiers tours : on perd la partie avant même\n",
    "> d'avoir pu poser ses grosses cartes.\n",
    "\n",
    "**Objectif : obtenir le deck jouable de puissance totale maximale.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ---------------------------------------------------------------\n",
    "# Données du TP — ne pas modifier\n",
    "# ---------------------------------------------------------------\n",
    "\n",
    "# Une carte = (nom, puissance, cout)\n",
    "BOOSTERS = [\n",
    "    [(\"Gnome bricoleur\", 3, 1), (\"Yéti des roches\", 5, 4), (\"Golem de siège\", 6, 5)],\n",
    "    [(\"Écuyer fidèle\", 2, 1), (\"Loup argenté\", 4, 3), (\"Chevalier du néant\", 5, 5)],\n",
    "    [(\"Apprenti mage\", 3, 2), (\"Sorcière du marais\", 4, 4), (\"Dragon de bronze\", 5, 5)],\n",
    "    [(\"Recrue de la garde\", 2, 1), (\"Berserker orc\", 4, 3), (\"Titan de pierre\", 9, 7)],\n",
    "    [(\"Novice de l'ombre\", 1, 1), (\"Archer elfe\", 3, 2), (\"Léviathan des abysses\", 10, 8)],\n",
    "    [(\"Sanglier tenace\", 2, 2), (\"Garde royal\", 5, 4), (\"Ogre lourdaud\", 4, 6)],\n",
    "    [(\"Voleur agile\", 3, 2), (\"Prêtresse de la lune\", 4, 3), (\"Colosse runique\", 7, 6)],\n",
    "    [(\"Gobelin ferrailleur\", 2, 1), (\"Chaman du totem\", 4, 4), (\"Hydre des marais\", 6, 6)],\n",
    "    [(\"Éclaireur nain\", 3, 2), (\"Paladin d'argent\", 5, 4), (\"Behemoth ancien\", 6, 7)],\n",
    "    [(\"Rat des égouts\", 1, 1), (\"Duelliste vétéran\", 5, 3), (\"Ver des sables\", 6, 5)],\n",
    "]\n",
    "\n",
    "COUT_CHER = 5        # une carte est \"chère\" à partir de 5 manas\n",
    "MAX_CHERES = 3       # au plus 3 cartes chères dans un deck jouable\n",
    "\n",
    "\n",
    "def afficher_deck(deck):\n",
    "    \"\"\"Affiche un deck sous forme de tableau.\"\"\"\n",
    "    for nom, puissance, cout in deck:\n",
    "        marque = \" (chère)\" if cout >= COUT_CHER else \"\"\n",
    "        print(f\"  {nom:<24} puissance {puissance:>2}   coût {cout}{marque}\")\n",
    "\n",
    "\n",
    "print(f\"{len(BOOSTERS)} boosters de 3 cartes.\")\n",
    "print(\"Booster 1 :\")\n",
    "afficher_deck(BOOSTERS[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Partie 1 — Savoir juger un deck\n",
    "\n",
    "Avant de drafter, il faut savoir répondre à deux questions sur un deck :\n",
    "**combien vaut-il ?** et **est-il seulement jouable ?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 1\n",
    "# Écrire une fonction qui renvoie la somme des puissances des cartes d'un deck.\n",
    "\n",
    "def puissance_totale(deck):\n",
    "    \"\"\"Renvoie la somme des puissances des cartes du deck.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "# Vérification\n",
    "test = [(\"A\", 3, 1), (\"B\", 5, 6), (\"C\", 2, 2)]\n",
    "assert puissance_totale(test) == 10\n",
    "assert puissance_totale([]) == 0\n",
    "print(\"Exercice 1 : OK\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 2\n",
    "# a) Compter les cartes chères (coût >= COUT_CHER) d'un deck.\n",
    "# b) En déduire si le deck est jouable (au plus MAX_CHERES cartes chères).\n",
    "\n",
    "def nb_cartes_cheres(deck):\n",
    "    \"\"\"Renvoie le nombre de cartes coûtant COUT_CHER manas ou plus.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "def deck_jouable(deck):\n",
    "    \"\"\"Renvoie True si le deck respecte la règle de jouabilité.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "# Vérification\n",
    "test = [(\"A\", 3, 1), (\"B\", 5, 6), (\"C\", 2, 7), (\"D\", 4, 5), (\"E\", 1, 8)]\n",
    "assert nb_cartes_cheres(test) == 4\n",
    "assert deck_jouable(test) is False\n",
    "assert deck_jouable(test[:3]) is True\n",
    "print(\"Exercice 2 : OK\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Partie 2 — Le glouton naïf\n",
    "\n",
    "La stratégie qui vient spontanément à l'esprit :\n",
    "\n",
    "> **À chaque booster, je prends la carte la plus puissante.**\n",
    "\n",
    "C'est bien un algorithme glouton : un choix par étape, le meilleur sur le moment,\n",
    "jamais de retour en arrière. Codons-la."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 3\n",
    "# Renvoyer la carte de plus grande puissance d'un booster.\n",
    "# (Ne pas utiliser max() : on veut voir la boucle de recherche du maximum.)\n",
    "\n",
    "def carte_la_plus_puissante(booster):\n",
    "    \"\"\"Renvoie la carte de plus grande puissance du booster.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "# Vérification\n",
    "assert carte_la_plus_puissante(BOOSTERS[0]) == (\"Golem de siège\", 6, 5)\n",
    "assert carte_la_plus_puissante(BOOSTERS[4]) == (\"Léviathan des abysses\", 10, 8)\n",
    "print(\"Exercice 3 : OK\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 4\n",
    "# Drafter un deck complet : pour chaque booster, prendre la carte la plus puissante.\n",
    "\n",
    "def draft_naif(boosters):\n",
    "    \"\"\"Renvoie le deck obtenu en prenant à chaque fois la carte la plus puissante.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "deck_naif = draft_naif(BOOSTERS)\n",
    "afficher_deck(deck_naif)\n",
    "print()\n",
    "print(\"Puissance totale :\", puissance_totale(deck_naif))\n",
    "print(\"Cartes chères    :\", nb_cartes_cheres(deck_naif), \"( maximum autorisé :\", MAX_CHERES, \")\")\n",
    "print(\"Deck jouable ?   :\", deck_jouable(deck_naif))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 1\n",
    "\n",
    "Le deck obtenu a une puissance totale de **65**, la plus haute qu'on puisse imaginer...\n",
    "et il est **injouable** : 9 cartes chères pour 3 autorisées.\n",
    "\n",
    "Remarque bien ce qui vient de se passer : le glouton n'a pas donné un résultat\n",
    "« un peu moins bon que l'optimal ». Il a donné un résultat **inutilisable**.\n",
    "\n",
    "**À toi.** Explique en une phrase pourquoi cet algorithme produit un deck injouable.\n",
    "Qu'a-t-il regardé, et surtout qu'a-t-il *ignoré* ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Partie 3 — Le glouton contraint\n",
    "\n",
    "Réparons l'algorithme sans changer sa nature. Il reste glouton — un choix par étape,\n",
    "pas de retour en arrière — mais il compte au fur et à mesure les cartes chères déjà prises :\n",
    "\n",
    "> **À chaque booster, je prends la carte la plus puissante _parmi celles que j'ai encore le droit de prendre_.**\n",
    "\n",
    "Tant que le quota de cartes chères n'est pas atteint, toutes les cartes sont autorisées.\n",
    "Une fois le quota plein, seules les cartes à moins de `COUT_CHER` manas le sont.\n",
    "\n",
    "*(Les boosters sont construits pour qu'il y ait toujours au moins une carte à moins de 5 manas :\n",
    "l'algorithme ne peut donc jamais se retrouver bloqué.)*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercice 5\n",
    "# Drafter en respectant le quota de cartes chères.\n",
    "#\n",
    "# Indication : garder un compteur du nombre de cartes chères déjà prises.\n",
    "# Pour chaque booster, construire la liste des cartes autorisées, puis prendre\n",
    "# la plus puissante de cette liste.\n",
    "\n",
    "def draft_contraint(boosters):\n",
    "    \"\"\"Renvoie le deck obtenu par un glouton qui respecte le quota de cartes chères.\"\"\"\n",
    "    # À COMPLÉTER\n",
    "    ...\n",
    "\n",
    "\n",
    "deck_glouton = draft_contraint(BOOSTERS)\n",
    "afficher_deck(deck_glouton)\n",
    "print()\n",
    "print(\"Puissance totale :\", puissance_totale(deck_glouton))\n",
    "print(\"Deck jouable ?   :\", deck_jouable(deck_glouton))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2\n",
    "\n",
    "Cette fois le deck est jouable, pour une puissance de **46**.\n",
    "\n",
    "Notre algorithme fonctionne. Mais une question reste ouverte, et c'est *la* question\n",
    "du chapitre : **46, est-ce le maximum ?**\n",
    "\n",
    "Le glouton, lui, en est incapable de le dire — il n'a jamais comparé son deck à un autre."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Partie 4 — La force brute : quel était le vrai maximum ?\n",
    "\n",
    "Pour le savoir, il n'y a qu'une méthode certaine : **essayer tous les decks possibles**\n",
    "et garder le meilleur deck jouable.\n",
    "\n",
    "À chaque booster on a 3 choix, et il y a 10 boosters : cela fait\n",
    "\n",
    "$$3^{10} = 59\\,049 \\text{ decks possibles.}$$\n",
    "\n",
    "C'est beaucoup pour un humain, très peu pour une machine. Le code ci-dessous est **fourni** :\n",
    "`product(*boosters)` fabrique toutes les combinaisons possibles, une par une.\n",
    "\n",
    "Lis-le, exécute-le, mais ne cherche pas à le réécrire : ce n'est pas l'objet du TP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ---------------------------------------------------------------\n",
    "# Force brute — code fourni\n",
    "# ---------------------------------------------------------------\n",
    "from itertools import product\n",
    "from time import perf_counter\n",
    "\n",
    "\n",
    "def meilleur_deck_force_brute(boosters):\n",
    "    \"\"\"Essaie TOUS les decks possibles et renvoie le meilleur deck jouable.\"\"\"\n",
    "    meilleur = None\n",
    "    meilleure_puissance = -1\n",
    "    for deck in product(*boosters):\n",
    "        if deck_jouable(deck) and puissance_totale(deck) > meilleure_puissance:\n",
    "            meilleur = list(deck)\n",
    "            meilleure_puissance = puissance_totale(deck)\n",
    "    return meilleur, meilleure_puissance\n",
    "\n",
    "\n",
    "debut = perf_counter()\n",
    "deck_optimal, puissance_optimale = meilleur_deck_force_brute(BOOSTERS)\n",
    "duree = perf_counter() - debut\n",
    "\n",
    "afficher_deck(deck_optimal)\n",
    "print()\n",
    "print(\"Puissance optimale :\", puissance_optimale)\n",
    "print(f\"Calculé en {duree:.2f} s après avoir testé {3 ** len(BOOSTERS)} decks.\")\n",
    "print()\n",
    "print(\"Glouton :\", puissance_totale(deck_glouton), \" |  Optimal :\", puissance_optimale)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 3\n",
    "\n",
    "Le glouton obtient **46**, l'optimum est **58**. Il s'est fait piéger — reste à comprendre où.\n",
    "\n",
    "Regarde les 3 cartes chères que chacun a retenues :\n",
    "\n",
    "- **glouton** : Golem de siège, Chevalier du néant, Dragon de bronze (les boosters 1, 2 et 3) ;\n",
    "- **optimum** : Titan de pierre, Léviathan des abysses, Colosse runique (les boosters 4, 5 et 7).\n",
    "\n",
    "Le tableau ci-dessous calcule, pour chaque booster, ce que rapporte le fait d'y « dépenser »\n",
    "une place de carte chère plutôt que de prendre la meilleure carte bon marché.\n",
    "\n",
    "Exécute-le, puis explique en quelques lignes l'erreur du glouton."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ce que rapporte réellement chaque carte chère, comparée à la meilleure carte pas chère du même booster\n",
    "print(f\"{'Booster':<9}{'meilleure pas chère':<27}{'meilleure chère':<29}{'gain'}\")\n",
    "for i, booster in enumerate(BOOSTERS):\n",
    "    pas_cheres = [c for c in booster if c[2] < COUT_CHER]\n",
    "    cheres = [c for c in booster if c[2] >= COUT_CHER]\n",
    "    if cheres == []:\n",
    "        continue\n",
    "    meilleure_pas_chere = carte_la_plus_puissante(pas_cheres)\n",
    "    meilleure_chere = carte_la_plus_puissante(cheres)\n",
    "    gain = meilleure_chere[1] - meilleure_pas_chere[1]\n",
    "    print(f\"{i + 1:<9}{meilleure_pas_chere[0] + f' ({meilleure_pas_chere[1]})':<27}\"\n",
    "          f\"{meilleure_chere[0] + f' ({meilleure_chere[1]})':<29}{gain:+d}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Partie 5 — Alors pourquoi ne pas toujours faire de la force brute ?\n",
    "\n",
    "Puisque la force brute donne toujours le bon résultat, autant l'utiliser partout, non ?\n",
    "\n",
    "La cellule suivante mesure le temps de calcul de la force brute pour un nombre croissant\n",
    "de boosters. Observe la colonne « temps »."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"{'boosters':<11}{'decks testés':<16}{'temps (s)'}\")\n",
    "for n in range(4, len(BOOSTERS) + 1):\n",
    "    debut = perf_counter()\n",
    "    meilleur_deck_force_brute(BOOSTERS[:n])\n",
    "    duree_n = perf_counter() - debut\n",
    "    print(f\"{n:<11}{3 ** n:<16}{duree_n:.3f}\")\n",
    "\n",
    "# Extrapolation à un vrai draft d'Arène (30 boosters), à partir du temps mesuré ci-dessus\n",
    "vitesse = 3 ** len(BOOSTERS) / duree_n          # decks testés par seconde\n",
    "secondes = 3 ** 30 / vitesse\n",
    "print()\n",
    "print(f\"Vitesse mesurée : environ {vitesse:.0f} decks testés par seconde.\")\n",
    "print(f\"Pour 30 boosters : {3 ** 30} decks à tester,\")\n",
    "print(f\"soit environ {secondes / (365 * 24 * 3600):.0f} années de calcul.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 4\n",
    "\n",
    "1. Quand on ajoute **un seul** booster, par combien le nombre de decks à tester est-il multiplié ?\n",
    "   Et le temps de calcul ?\n",
    "2. Un vrai draft d'Arène compte **30 boosters**. Combien de decks faudrait-il tester ?\n",
    "   En te servant du temps mesuré pour 10 boosters, estime la durée du calcul.\n",
    "3. Conclusion : dans quelle situation l'algorithme glouton est-il **le bon choix**,\n",
    "   même s'il ne garantit pas l'optimum ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "## Ce qu'il faut retenir\n",
    "\n",
    "| | Glouton | Force brute |\n",
    "|---|---|---|\n",
    "| Résultat | 46 (pas l'optimum) | 58 (l'optimum) |\n",
    "| Nombre d'opérations | 10 (une par booster) | 59 049 |\n",
    "| Avec 30 boosters | 30 opérations | plusieurs années |\n",
    "| Garantie | aucune | optimum certain |\n",
    "\n",
    "Un **algorithme glouton** construit une solution par étapes, en faisant à chaque étape\n",
    "le meilleur choix selon un critère local, et **sans jamais revenir en arrière**.\n",
    "\n",
    "Il est rapide. Il n'est pas toujours optimal. Quand ce n'est pas le cas, on parle\n",
    "d'**heuristique**.\n",
    "\n",
    "---\n",
    "\n",
    "## Pour aller plus loin\n",
    "\n",
    "Reprends le tableau des gains de la partie 4. Un autre algorithme glouton est possible :\n",
    "calculer le gain de chaque booster, puis dépenser ses 3 places de cartes chères sur les\n",
    "**3 plus gros gains**.\n",
    "\n",
    "1. Vérifie sur les données du TP que cette stratégie donne bien 58, c'est-à-dire l'optimum.\n",
    "2. Pourtant, cette stratégie est **impossible à appliquer dans un vrai draft**. Pourquoi ?\n",
    "\n",
    "<details>\n",
    "<summary><strong>Indice</strong></summary>\n",
    "\n",
    "De quelle information a-t-on besoin pour calculer le tableau des gains ? Et à quel moment\n",
    "un joueur en Arène dispose-t-il de cette information ?\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Auteur : Florian Mathieu\n",
    "\n",
    "Licence CC BY-SA\n",
    "\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-sa/4.0/\"><img alt=\"Licence Creative Commons\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-sa/4.0/88x31.png\" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-sa/4.0/\">Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International</a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}