Jordi Inglada

Posts tagged "python":

27 May 2022

Lottosup

Parcoursup est une machine à frustrations.

Les règles de classement des candidats par chaque formation sont opaques. Dans les formations sélectives, l'écart de notation entre les dossiers des admis et de ceux non admis peut être extrêmement faible. Du fait que les bulletins de notes ont un poids non négligeable, on peut se poser la question de l'équité entre élèves de classes et d'établissements différents.

À cela, il faut ajouter l'angoisse de devoir faire des choix dans un temps limité avant de perdre l'accès à des formations où le candidat est accepté.

Tout cela fait que Parcoursup est un Lotto géant où ceux qui sont mal conseillés risquent de perdre.

J'ai fait un petit programme qui permet de jouer à Parcoursup pour apprendre à gérer le stress auquel élèves et parents serons soumis.

L'interface utilisateur est rudimentaire, mais je ne sais pas faire aussi joli que les EdTech!

Attention!

C'est une simulation qui utilise le hasard pour générer des scénarios. Ce que vous obtiendrez, même si vous rentrez correctement les données correspondant à vos vœux Parcoursup, ce sont des résultats aléatoires. Cependant, ce n'est pas n'importe quoi!

Le simulateur utilise votre rang dans votre classe pour vous attribuer un rang dans chaque formation. Le taux d'acceptation de chaque formation est aussi utilisé. La simulation de l'évolution des listes d'attente essaie d'être plausible, mais j'ai fait des choix arbitraires. Si cela vous intéresse, regardez le code. J'ai essayé de le documenter avec des explications détaillées.

Entre 2 parties du jeu, même si vous gardez les mêmes données d'entrée, les résultats seront différents. L'idée est que vous puissiez faire plein de simulations pour être confrontés à des choix qui ressemblent à ceux que vous pourriez être amenés à faire.

Installation

Vous aurez besoin de Python 3.x. Autrement, il suffit de récupérer le fichier lottosup.py.

Vous devez adapter le programme à votre cas à votre cas particulier.

D'abord, vous devez modifier les valeurs suivantes :

# Votre rang dans votre classe
RANG_CLASSE = 15

# Nombre d'élèves dans votre classe
TAILLE_CLASSE = 35

Ensuite, vous devez rentrer vos vœux :

# Un voeux est un tuple ("nom", nb_places, rang_dernier_2021, taux_acceptation)
VOEUX = [
    (
        "MIT - Aerospace",
        60,
        296,
        0.1,
    ),
    (
        "Élite - Youtubeur ",
        25,
        79,
        0.1,
    ),
    (
        "Oxford - Maths",
        25,
        41,
        0.1,
    ),
    (
        "Stanford - Artificial Intelligence",
        42,
        322,
        0.1,
    ),
    (
        "HEC pour fils à Papa",
        20,
        58,
        0.1,
    ),
    ("Fac de truc qui sert à rien", 1500, 145300, 0.9999),
    ("Éleveur de chèvres dans les Pyrénées", 180, 652, 0.1),
]

Les informations nécessaires (nombre de places, rang du dernier accepté l'année précédente et taux d'acceptation) sont disponibles dans votre espace Parcoursup.

Tuto indispensable

Vous pouvez lancer le programme en ligne de commande comme ceci :

python lottosup.py

Si vous utilisez un éditeur comme Pyzo ou Spyder, vous pouvez simplement exécuter le programme depuis l'éditeur.

Une fois lancé, vous aurez ceci :

$ python lottosup.py 
Bienvenue dans LottoSup™.
Appuyez sur une touche pour jouer!

Appuyez sur une touche pour lancer la machine infernale et retrouver les résultats du premier jour. Vous pourriez avoir, par exemple, ce résultat :

################# Jour 1 #####################

        ======== Status.ACCEPT ========
6) Fac de truc qui sert à rien
        1500 places - rang 2021 : 145300
        votre rang : 655 - rang dernier : 4929
        date limite : jour 5
        Statut : Status.ACCEPT 🎉

        ======== Status.WAIT ========
2) Élite - Youtubeur 
        25 places - rang 2021 : 79
        votre rang : 82 - rang dernier : 27
        date limite : jour 45
        Statut : Status.WAIT ⏳

4) Stanford - Artificial Intelligence
        42 places - rang 2021 : 322
        votre rang : 182 - rang dernier : 64
        date limite : jour 45
        Statut : Status.WAIT ⏳

1) MIT - Aerospace
        60 places - rang 2021 : 296
        votre rang : 259 - rang dernier : 66
        date limite : jour 45
        Statut : Status.WAIT ⏳

7) Éleveur de chèvres dans les Pyrénées
        180 places - rang 2021 : 652
        votre rang : 782 - rang dernier : 191
        date limite : jour 45
        Statut : Status.WAIT ⏳

Acceptation définitive [idx ou 0] :     

On peut voir la liste des formations où vous êtes accepté et celles où vous êtes en liste d'attente. Pour chaque formation, vous avez les informations que Parcoursup est censé vous donner :

  • le nombre de places dans la formation
  • le rang (classement) du dernier qui a été accepté l'année précédente
  • votre rang pour cette formation
  • le rang du dernier à avoir été accepté cette année (si votre rang est inférieur, vous êtes accepté, sinon, vous êtes en liste d'attente)
  • la date limite de réponse pour cette formation avant que l'offre d'acceptation expire (si vous êtes en liste d'attente, cette date correspond au dernier jour de la phase principale, que j'ai fixé à 45)

Ensuite, vous devez faire vos choix. Il faut d'abord répondre si vous voulez accepter définitivement une formation où vous êtes accepté. Rentrez le numéro qui apparaît dans la liste, à gauche du nom de la formation (6 dans l'exemple ci-dessus). Pour ne pas faire de choix, rentrez 0. Si vous acceptez une formation, le jeu est fini.

On vous demande ensuite si vous voulez faire une acceptation temporaire :

Acceptation temporaire [idx ou 0] : 

Si vous faites une acceptation temporaire, vous refusez automatiquement toutes les autres où vous êtes accepté, mais cela n'a pas d'impact sur la liste d'attente.

La question suivante concerne les formations que vous voulez refuser :

Rejets [id1 id2 ... ou 0] : 

Ici, on peut donner une liste d'indices parmi ceux des formations où vous êtes accepté ou en liste d'attente. Elles disparaîtront de la liste le jour suivant. Si vous ne voulez rien refuser, rentrez 0.

Et on passe au jour suivant. Il se peut que rien ne change, mais probablement, le rang du dernier accepté dans les formations va évoluer. Ceci peut vous permettre d'être accepté à d'autres formations.

Quand on arrive au jour 5, c'est la date d'expiration des offres que vous avez reçu jusque là :

################# Jour 5 #####################

        ======== Status.ACCEPT ========
6) Fac de truc qui sert à rien
        1500 places - rang 2021 : 145300
        votre rang : 655 - rang dernier : 42447
        date limite : jour 5
        Statut : Status.ACCEPT 🎉

        ======== Status.WAIT ========
2) Élite - Youtubeur 
        25 places - rang 2021 : 79
        votre rang : 82 - rang dernier : 31
        date limite : jour 45
        Statut : Status.WAIT ⏳

4) Stanford - Artificial Intelligence
        42 places - rang 2021 : 322
        votre rang : 182 - rang dernier : 84
        date limite : jour 45
        Statut : Status.WAIT ⏳

1) MIT - Aerospace
        60 places - rang 2021 : 296
        votre rang : 259 - rang dernier : 91
        date limite : jour 45
        Statut : Status.WAIT ⏳

7) Éleveur de chèvres dans les Pyrénées
        180 places - rang 2021 : 652
        votre rang : 782 - rang dernier : 285
        date limite : jour 45
        Statut : Status.WAIT ⏳

Acceptation définitive [idx ou 0] :   

Ici, si je ne fais pas une acceptation temporaire de la formation no. 6, elle disparaîtra le jour suivant. Si je l'accepte temporairement, sa date limite de réponse est repoussée à la fin de la phase principale de Parcoursup. Voici mes réponses :

Acceptation définitive [idx ou 0] : 0 
Acceptation temporaire [idx ou 0] : 6
Rejets [id1 id2 ... ou 0] : 0

Et donc le jour suivant j'ai ça :

################# Jour 6 #####################

        ======== Status.ACCEPT ========
6) Fac de truc qui sert à rien
        1500 places - rang 2021 : 145300
        votre rang : 655 - rang dernier : 45414
        date limite : jour 45
        Statut : Status.ACCEPT 🎉

        ======== Status.WAIT ========
2) Élite - Youtubeur 
        25 places - rang 2021 : 79
        votre rang : 82 - rang dernier : 31
        date limite : jour 45
        Statut : Status.WAIT ⏳

4) Stanford - Artificial Intelligence
        42 places - rang 2021 : 322
        votre rang : 182 - rang dernier : 84
        date limite : jour 45
        Statut : Status.WAIT ⏳

1) MIT - Aerospace
        60 places - rang 2021 : 296
        votre rang : 259 - rang dernier : 97
        date limite : jour 45
        Statut : Status.WAIT ⏳

7) Éleveur de chèvres dans les Pyrénées
        180 places - rang 2021 : 652
        votre rang : 782 - rang dernier : 307
        date limite : jour 45
        Statut : Status.WAIT ⏳

J'ai donc assuré une formation et je peux attendre de remonter dans la liste d'attente. Il ne me reste que 51 places pour apprendre à devenir Youtubeur.

Quelques détails de mise en œuvre

J'ai seulement utilisé des modules disponibles dans la bibliothèque standard Python. J'avais fait une première version qui utilisait Numpy pour les tirages aléatoires, mais finalement le module math contient tout, y compris le tirage avec une loi exponentielle.

import math
import random
import sys
from enum import Enum, auto

Chaque formation a un état différent (acceptation, liste d'attente, etc.). Je modélise ça avec des énumérations. Ce sont des ensembles de valeurs restreintes :

class Status(Enum):
    ACCEPT = "🎉"  # la formation a accepté
    WAIT = "⏳"
    REJECT = "☠️"  # la formation a rejeté
    DROP = "💪"  # le candidat a rejeté
    EXPIRED = "⌛"  # date limite dépassée
    CHECK = "☑️"  # le candidat a accepté définitivement

Les réponses des candidats aux propositions d'acceptation ou de liste d'attente, sont modélisées de la même façon :

class Choix(Enum):
    WAIT = auto()  # le candidat maintient l'attente
    DROP = auto()  # le candidat a rejeté
    CHECK = auto()  # le candidat a accepté définitvement
    ACCEPT = auto()  # acceptation non définitive

Cela peut sembler redondant, mais les valeurs ne sont pas les mêmes et, surtout, elles n'ont pas la même signification. Par exemple, ACCEPT de la part du candidat veut dire qu'il réserve une place, tandis qu'un ACCEPT de la part d'une formation, ne veut pas dire que le candidat accepte.

Ensuite, je modélise chaque formation par une classe. Le candidat a un rang dans la formation et les acceptations se font en fonction du nombre de places disponibles et le rang du candidat. On gère une liste d'attente qui s'actualise chaque jour en fonction des refus des autres candidats.

class Formation:
    def __init__(self, idx, nom, places, rang_dernier_2021, taux_accept):
        self.nom = nom
        self.idx = idx
        self.total_places = places
        self.rang_dernier_2021 = rang_dernier_2021
        self.rang_dernier = self.total_places
        self.taux_acceptation = taux_accept
        self.votre_rang = self.compute_rang()
        self.date_limite = DUREE_PS  # jour limite pour répondre
        self.places_disponibles = self.total_places
        self.status = None  # statut du candidat dans la formation

La méthode __init__ est le constructeur de la classe. Elle initialise la formation à partir des paramètres suivants :

idx
un indice unique pour chaque formation qui nous permettra de gérer les réponses de l'utilisateur
nom
le nom de la formation (pour l'affichage)
places
nombre de places disponibles
rang_dernier_2021
rang du dernier candidat admis l'année précédente
taux_accept
le taux d'acceptation de la formation

Afin de pouvoir afficher une formation avec print(), nous définissons la méthode =__repr__= :

    def __repr__(self):
        """ Pour un affichage avec print()"""
        return (
            f"{self.idx}) {self.nom}\n"
            f"\t{self.total_places} places -"
            f" rang 2021 : {self.rang_dernier_2021}\n"
            f"\tvotre rang : {self.votre_rang} -"
            f" rang dernier : {self.rang_dernier}\n"
            f"\tdate limite : jour {self.date_limite}\n"
            f"\tStatut : {self.status} {self.status.value}\n"
        )

Plus intéressante est la façon de définir le rang du candidat (son classement) dans la formation. Avec le nombre de places et le taux d'acceptation, on calcule le nombre de candidats. Le rang du candidat parmi tous les autres est calculé à partir du rang dans sa classe par une simple règle de trois. Pour donner un peu de réalisme, on fait un tirage aléatoire avec une loi gaussienne de moyenne égale à ce rang et un écart type de 10 (parce que!). La gaussienne étant à support non borné, on coupe entre 0 et le nombre de candidats.

    def compute_rang(self):
        nombre_candidats = self.total_places / self.taux_acceptation
        rang_moyen = RANG_CLASSE / TAILLE_CLASSE * nombre_candidats
        tirage = random.gauss(rang_moyen, 10)
        rang = int(min(nombre_candidats, max(tirage, 0)))
        return rang

Cette méthode est appelée par le constructeur lors de l'initialisation de la formation.

À chaque fois que le candidat reçoit une offre de formation, elle est accompagnée d'une date limite de réponse :

    def update_date_limite(self, jour):
        if jour < 5:
            self.date_limite = 5
        else:
            self.date_limite = jour + 1

Pour simuler l'évolution de la liste d'attente chaque jour, on calcule simplement le rang du dernier accepté dans la formation. Cela nous évite de devoir simuler les refus de candidats (c'est des adolescents, ils sont imprévisibles).

La position du dernier admis avance avec selon une densité de probabilité exponentielle (il est plus probable que la position du dernier avance de peu de places que de beaucoup) :

\[p(x) = \lambda e^{-\lambda x}\]

La moyenne de cette loi (λ), décroît avec les jours qui passent (davantage de candidats se désistent les premiers jours que par la suite).

Pour fixer λ, on part du 99è quantile (la valeur de la variable pour laquelle on a 99% de chances d'être en dessous). Pour la distribution exponentielle, la fonction quantile est : \[q = -\ln(1-p)/\lambda\]

De façon arbitraire, on prend q égal à un dixième de la longueur de la liste d'attente.

    def update_rang_dernier(self, jour):
        longueur_attente = max(
            self.rang_dernier_2021 - self.rang_dernier + 1, 1
        )
        jours_restants = DUREE_PS - jour + 1
        q = longueur_attente / 10
        p = min(
            0.999, float(jours_restants / DUREE_PS) * 0.99
        )  # on fixe le max à 0.999 pour éviter des exceptions dans le log
        lam = max(-(math.log(1 - p) / q), 1e-15)
        tirage = random.expovariate(lam)
        self.rang_dernier += int(tirage)

Le statut du candidat dans la formation est actualisé chaque jour. On utilise la méthode suivante dans 2 cas :

  1. la mise à jour automatique du système chaque nuit,
  2. la mise à jour après choix du candidat.

La mise à jour du lotto Parcoursup est faite de la façon suivante. Au départ, un candidat est accepté par une formation si son rang est inférieur ou égal au nombre de places de la formation. Les jours suivants, il est accepté si son rang est inférieur au dernier admis cette année. Un candidat est refusé par une formation si son rang es de 20% supérieur à celui du dernier admis l'année dernière (je ne pense pas que ce soit la règle utilisée par les formations, mais j'aime bien être sévère avec ces jeunes …). On gère aussi l'expiration des délais d'attente de réponse. Si le délai est dépassé, l'offre expire.

La gestion des choix du candidat consiste à mettre à jour le statut de la formation en fonction de sa réponse.

    def update_status(self, jour, choix: Choix = None):
        if choix is None:
            self.update_rang_dernier(jour)
            if self.votre_rang <= self.rang_dernier and (
                self.status == Status.WAIT or self.status == Status.ACCEPT
            ):
                if self.status != Status.ACCEPT:
                    self.update_date_limite(jour)
                    self.status = Status.ACCEPT
            elif self.votre_rang >= self.rang_dernier_2021 * 1.2:
                self.status = Status.REJECT
            else:
                self.status = Status.WAIT
            if self.status == Status.ACCEPT and jour > self.date_limite:
                self.status = Status.EXPIRED
        elif choix == Choix.CHECK:
            self.status = Status.CHECK
        elif choix == Choix.DROP:
            self.status = Status.DROP
        elif choix == Choix.WAIT:
            self.status = Status.WAIT

Et c'est tout pour les formations.

On passe ensuite à la simulation des actualisation journalières du système. On crée aussi une classe pour cela.

class Parcoursup:
    def __init__(self, voeux):
        self.voeux = voeux
        self.jour = 0
        for v in self.voeux:
            v.update_status(self.jour)

La classe est construite avec les vœux du candidat le jour 0. Pour chaque vœux, on fait une mise à jour définies par les formations.

Ensuite, on a une méthode pour l'itération journalière du système. C'est simple :

  • on commence par mettre à jour en chaque formation pour le jour courant,
  • on affiche les résultats de l'algo PS®,
  • on demande au candidat de faire ses choix et
  • on élimine les formations refusées par le candidat.
    def iteration(self):
        """Itération 
        """

        self.jour += 1
        for v in self.voeux:
            v.update_status(self.jour)
        self.print()
        self.choice()
        self.clean()

Pour faire tout ça, on aura besoin de quelques petites méthodes. D'abord, il nous faut pouvoir récupérer un voeu à partir de son identifiant unique :

    def get_voeu(self, idx):
        for v in self.voeux:
            if v.idx == idx:
                return v

Si le candidat accepte temporairement une formation, il refuse automatiquement toutes les autres où il a été accepté. That's life. Bienvenue au monde des adultes …

    def drop_all_accept_except(self, accept_tmp):
        for v in self.voeux:
            if v.idx != accept_tmp and v.status == Status.ACCEPT:
                v.update_status(self.jour, Choix.DROP)

Une petite fonction pour poser une question à l'utilisateur et récupérer sa réponse :

    def get_input(self, message, single_value=False):
        print(message, end=" ")
        resp = input()
        if single_value:
            try:
                val = int(resp)
                return val
            except ValueError:
                self.get_input(message, True)
        else:
            return resp.split()

Ici, on fait l'interaction avec l'utilisateur pour gérer les choix. On commence par lui demander s'il veut accepter définitivement une formation, on passe ensuite à l'acceptation temporaire et on finit par récupérer les formations refusées. En cas d'acceptation (définitive ou temporaire) on vérifie qu'il choisit des formations pour lesquelles il a été accepté! Si vous avez des ados à la maison, vous comprendrez que c'est une bonne précaution à prendre …

    def choice(self):
        accept_def = self.get_input(
            "Acceptation définitive [idx ou 0] :", True
        )
        while accept_def != 0:
            v_accept = self.get_voeu(accept_def)
            if v_accept.status == Status.ACCEPT:
                v_accept.update_status(self.jour, Choix.CHECK)
                print(
                    "Félicitations, vous avez accepté définitivement"
                    " la formation\n"
                )
                print(v_accept.nom)
                sys.exit(0)
            else:
                print(
                    "Vous n'avez pas été accepté dans la formation\n"
                    f"{v_accept.nom}\n"
                )
                accept_def = self.get_input(
                    "Acceptation définitive [idx ou 0] :", True
                )

        accept_tmp = self.get_input(
            "Acceptation temporaire [idx ou 0] :", True
        )
        while accept_tmp != 0:
            v_accept = self.get_voeu(accept_tmp)
            if v_accept.status == Status.ACCEPT:
                self.drop_all_accept_except(accept_tmp)
                v_accept.date_limite = DUREE_PS
                break
            else:
                print(
                    "Vous n'avez pas été accepté dans la formation\n"
                    f"{v_accept.nom}\n"
                )
                accept_tmp = self.get_input(
                    "Acceptation temporaire [idx ou 0] :", True
                )
        rejets = self.get_input("Rejets [id1 id2 ... ou 0] :", False)
        if rejets[0] == "0":
            return None
        for rejet in rejets:
            v_rejet = self.get_voeu(int(rejet))
            if v_rejet is not None:
                v_rejet.update_status(self.jour, Choix.DROP)

Il y a quelques doublons dans le code qui auraient pu être factorisés dans une autre méthode, mais ça fait l'affaire.

Voici la méthode pour éliminer les formations qui ne sont ni acceptées ni en liste d'attente :

    def clean(self):
        self.voeux = {
            v
            for v in self.voeux
            if (v.status == Status.ACCEPT or v.status == Status.WAIT)
        }

Et finalement, une fonction pour afficher les résultats du lotto journalier. Seulement les formations où le candidat est accepté ou en liste d'attente sont affichées. Il ne faut pas remuer le couteau dans la plaie!

    def print(self):
        print(f"################# Jour {self.jour} #####################\n")
        for s in [Status.ACCEPT, Status.WAIT]:
            print(f"\t======== {s} ========")
            for v in self.voeux:
                if v.status == s:
                    print(v)

Nous avons terminé avec la classe Parcoursup.

La fonction principale pour faire tourner la simulation. On lit les veux du candidat et on initialise la simulation. On simule (DUREE_PS = 45 par défaut) jours d'agonie et de stress.

def main():
    voeux = {
        Formation(idx, n, p, r, tr)
        for idx, (n, p, r, tr) in enumerate(VOEUX, start=1)
    }
    ps = Parcoursup(voeux)
    print("Bienvenue dans LottoSup™.\n" "Appuyez sur une touche pour jouer!\n")
    input()
    for it in range(DUREE_PS):
        ps.iteration()

Le code est relativement simple et court, ce qui permet d'en changer le comportement relativement facilement.

Tags: fr programming python education politics
19 Apr 2011

Functional Python

Small things can make you smile when you have the Aha! moment. It seems that these few days of 7li7w are starting to have real effects in the way I think when programming. Today, I was faced to a simple but annoying problem. I had about 60 Formosat 2 acquisitions that I needed to use. These images have been pre-processed (thank Olivier!) and, because of historical reasons they are presented like this:

    Sudouest_20060206_MS_fmsat_ortho_surf_8m.B1
    Sudouest_20060206_MS_fmsat_ortho_surf_8m.B2
    Sudouest_20060206_MS_fmsat_ortho_surf_8m.B3
    Sudouest_20060206_MS_fmsat_ortho_surf_8m.B4
    Sudouest_20060206_MS_fmsat_ortho_surf_8m.hdr

That is, a single ENVI header file and the 4 bands in one file each. And the same thing for every single acquisition date. I wanted to have the list of all the acquisition dates (the 20060206 above). Since this was not a one shot operation, I wanted something a little bit more generic than opening the directory containing the images in an Emacs Dired buffer and copying and pasting the dates, so I have used Python. The thing is solved in a single line of code:

    dates = [fil.split('_')[1] for fil in os.listdir(imageDir) 
                                if(fil.split('.')[-1]=="hdr")]

I use a list comprehension, where for each file in the imageDir directory (os.listdir), if the extension is hdr I keep the second chunk of the name of the file when _ is used as a separator.

Tags: programming python
Other posts
Creative Commons License
jordiinglada.net by Jordi Inglada is licensed under a Creative Commons Attribution-ShareAlike 4.0 Unported License. RSS. Feedback: info /at/ jordiinglada.net