• 4 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 20/05/2019

Codez l'algorithme en Python

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Pour rappel, voici les règles de notre programme :

  • Chaque candidat a une mention entre "Excellent" et "À rejeter".

  • La mention majoritaire de chaque candidat est calculée sur une médiane et non sur une moyenne. 50 % au moins des votants trouvent cette mention valable.

  • En cas d’égalité de mentions majoritaires : celle ou celui ayant le pourcentage de mentions supérieures à la mention majoritaire le plus important est le mieux classé.

Et voici les mentions :

  • Excellent [0]

  • Très bien [1]

  • Bien [2]

  • Assez Bien [3]

  • Passable [4]

  • Insuffisant [5]

  • À rejeter [6]

Vous souhaitez coder en même temps que moi ? Youpi, vous avez entièrement raison ! Téléchargez ce code pour commencer. Il vous permettra de créer aléatoirement 100 000 votes.

Le fichier de départ inclut un dictionnaire et un tableau qui vous seront bien utiles. Le premier, CANDIDATES, contient le nom de chaque candidat associé à sa clé. Le second, MENTIONS, contient la liste de toutes les mentions dans un format agréable à lire.

CANDIDATES = {
    "hermione": "Hermione Granger",
    "balou": "Balou",
    "chuck-norris": "Chuck Norris",
    "elsa": "Elsa",
    "gandalf": "Gandalf",
    "beyonce": "Beyoncé"
}

MENTIONS = [
    "Excellent",
    "Très bien",
    "Bien",
    "Assez Bien",
    "Passable",
    "Insuffisant",
    "A rejeter"
]

Nous y reviendrons plus tard.

Format de données en entrée

Quelle structure de données choisir pour qu’elle soit le plus facilement interprétable ? Commençons par nous questionner sur les opérations que nous allons effectuer. Nous allons lire les données, les trier et trouver l’élément qui se situe à la moitié.

Regardons sur la Big O Cheat Sheet ce qui nous est conseillé. Il semblerait que ce soient la table de hachage (Hash table) et les tableaux (Array) qui l’emportent en ce qui concerne l’accès et la recherche. Vous souvenez-vous pourquoi ? Un tableau a un index qui le rend plus facile à parcourir pour en extraire des données. Quant à la table de hachage, vous retrouvez des données via des clés. Le tableau est moins flexible, mais ce n’est pas vraiment notre souci dans le cas présent, puisque nous ne le modifierons pas.

Je vous propose de créer un tableau pour regrouper tous nos votes.

Chaque vote sera représenté par une table de hachage dont les clés seront les différents candidats et leur valeur la mention sous forme de numéro. Par exemple :

{ "Hermione": 6 }

Voici un extrait de nos données en entrée :

[{"hermione": 1, "balou": 2, "chuck-norris": 3, "elsa": 4, "gandalf": 5, "beyonce": 6},
{"hermione": 2, "balou": 3, "chuck-norris": 4, "elsa": 5, "gandalf": 6, "beyonce": 0}
]

Format de données en sortie

Notre programme sera lancé en ligne de commandes et devra imprimer, dans notre terminal, une liste affichant ainsi :

Gagnant : Hermione avec 70% de mentions Bien
Suivants : 
- Balou avec 50% de mentions bien
- Chuck Norris avec 50% de mentions assez bien
- Elsa avec 70% de mentions passable
- Gandalf avec 60% de mentions passable
- Beyoncé avec 50% de mentions à rejeter

Algorithme

Créer un tableau intermédiaire

C’est parti !

Nous avons vu que notre tableau intermédiaire ressemblerait à ceci :

 

Balou

Hermione

Chuck Norris

Elsa

Gandalf

Beyonce

6 - À rejeter

 

 

 

 

 

 

5 - Insuffisant

 

 

 

 

 

 

4 - Passable

 

 

 

 

 

 

3 - Assez bien

 

 

 

 

 

 

2 - Bien

 

 

 

 

 

 

1 - Très bien

 

 

 

 

 

 

0 - Excellent

 

 

 

 

 

 

Comment le créer en Python ? En créant un tableau à l’intérieur d’un hash. Comme ceci :

candidates = {
    'hermione': [0, 0, 0, 0, 0, 0, 0],
    'balou': [0, 0, 0, 0, 0, 0, 0],
    'chuck-norris': [0, 0, 0, 0, 0, 0, 0],
    'elsa': [0, 0, 0, 0, 0, 0, 0],
    'gandalf': [0, 0, 0, 0, 0, 0, 0],
    'beyonce': [0, 0, 0, 0, 0, 0, 0]
}

Créons une fonction qui prendra en entrée une liste de votes et renverra, en sortie, un dictionnaire contenant le résultat des candidats :

def results_hash(votes):
    candidates_results = {
        candidate: [0]*len(MENTIONS)
        for candidate in CANDIDATES.keys()
    }
    for vote in votes:
        for candidate, mention in vote.items():
            candidates_results[candidate][mention] += 1
    return candidates_results

Et ajoutons dans la fonction  main  son exécution :

def main():
    votes = create_votes()
    results = results_hash(votes)

Décomposons-le :

candidates_results = {
    candidate: [0]*len(MENTIONS)
    for candidate in CANDIDATES.keys()
}

Je commence par créer un premier tableau dont toutes les valeurs sont à zéro. C’est normal : pour l’instant, chaque candidat a zéro vote ! Exactement de la même manière que nous l’avons fait à la main précédemment !

Cette fonction crée le dictionnaire suivant :

{
    "hermione": [0, 0, 0, 0, 0, 0, 0], 
    "balou": [0, 0, 0, 0, 0, 0, 0], 
    "chuck-norris": [0, 0, 0, 0, 0, 0, 0], 
    "elsa": [0, 0, 0, 0, 0, 0, 0], 
    "gandalf": [0, 0, 0, 0, 0, 0, 0], 
    "beyonce": [0, 0, 0, 0, 0, 0, 0]
}

Puis, je vais parcourir chaque vote et ajouter 1 quand un candidat recevra une mention :

for vote in votes:
    for candidate, mention in vote.items():
        candidates_results[candidate][mention] += 1
return candidates_results

Cela va générer un dictionnaire similaire à celui-ci :

{
    'hermione': [0, 0, 0, 25333, 24796, 24871, 25000], 
    'balou': [14404, 14311, 14305, 14250, 14195, 14231, 14304], 
    'chuck-norris': [33320, 33436, 33244, 0, 0, 0, 0], 
    'elsa': [0, 49969, 50031, 0, 0, 0, 0], 
    'gandalf': [0, 0, 0, 25023, 25033, 25039, 24905], 
    'beyonce': [0, 0, 19926, 20099, 19835, 20214, 19926]
}

Nous allons maintenant calculer la mention médiane !

Calculer la mention médiane de chaque candidat

Commencez par regarder cette vidéo :

Nous atteignons la médiane lorsque 50 % des votes pour un candidat sont représentés. Prenons un exemple.

Considérons les résultats d’Hermione : [0, 0, 0, 25333, 24796, 24871, 25000]

Nous allons calculer les résultats cumulés afin d’atteindre 50 000 votes (100 000 / 2).

  • Mention 0 : 0 + 0 = 0 => atteint-on 50 000 ? Non. Alors on continue avec la mention suivante.

  • Mention 1 : 0 + 0 = 0 => atteint-on 50 000 ? Non. Alors on continue avec la mention suivante.

  • Mention 2 : 0 + 0 = 0 => atteint-on 50 000 ? Non. Alors on continue avec la mention suivante.

  • Mention 3 : 0 + 25333 = 25333 => atteint-on 50 000 ? Non. Alors on continue avec la mention suivante.

  • Mention 4 : 25333 + 24796 = 50129 => atteint-on 50 000 ? Oui ! La boucle s’arrête.

La mention médiane d’Hermione sera "Passable", car au moins 50 % des votants lui ont accordé cette mention ou une supérieure.

Commençons par coder cette première boucle :

def majoritary_mentions_hash(candidates_results):
    cumulated_votes = 0
    for mention, vote_count in enumerate(candidates_results["hermione"]):
        cumulated_votes += vote_count
        if MEDIAN < cumulated_votes:
                # add a key in a dictionary
            break
    print(cumulated_votes)

Et ajoutons son exécution dans la fonction  main().

def main():
    votes = create_votes()
    results = results_hash(votes)
    majoritary_mentions = majoritary_mentions_hash(results)

Résultat :

50129

Ajoutons maintenant un dictionnaire dans lequel nous garderons la mention et les votes cumulés, sous cette forme :

{'hermione': {'mention': 4, 'score': 50129}}
def majoritary_mentions_hash(candidates_results):
  r = {}
  cumulated_votes = 0
  for mention, vote_count in enumerate(candidates_results["hermione"]):
      cumulated_votes += vote_count
      if MEDIAN < cumulated_votes:
          r["hermione"] = {
              "mention": mention,
              "score": cumulated_votes
          }
          break
  print(r)

Ajoutons désormais une boucle pour réaliser cette opération pour tous nos candidats :

def majoritary_mentions_hash(candidates_results):
    r = {}
    for candidate, candidate_result in candidates_results.items():
        cumulated_votes = 0
        for mention, vote_count in enumerate(candidate_result):
            cumulated_votes += vote_count
            if MEDIAN < cumulated_votes:
                r[candidate] = {
                    "mention": mention,
                    "score": cumulated_votes
                }
                break
    print(r)

Résultat :

{
    'hermione': {'mention': 4, 'score': 50129}, 
    'balou': {'mention': 3, 'score': 57270}, 
    'chuck-norris': {'mention': 1, 'score': 66756}, 
    'elsa': {'mention': 2, 'score': 100000}, 
    'gandalf': {'mention': 4, 'score': 50056}, 
    'beyonce': {'mention': 4, 'score': 59860}
}

Enfin, remplaçons notre print final (uniquement utilisé à des fins de débug) par un return :

def majoritary_mentions_hash(candidates_results):
    r = {}
    for candidate, candidate_result in candidates_results.items():
        cumulated_votes = 0
        for mention, vote_count in enumerate(candidate_result):
            cumulated_votes += vote_count
            if MEDIAN < cumulated_votes:
                r[candidate] = {
                    "mention": mention,
                    "score": cumulated_votes
                }
                break
    return r

Trier les candidats par mention

Bien. Maintenant que nous savons comment trouver la mention médiane d’un candidat, je vous propose de les trier par mention ! Celui ayant la meilleure mention devra arriver en haut de la liste et celui ayant la mention la plus basse (À rejeter) en bas.

Cela tombe bien, nous avons justement déjà vu un algorithme de tri : le tri par bulles !

Notre fonction prend en paramètre un dictionnaire. Or, le tri par bulles n’est possible que sur un tableau, car vous avez besoin des index pour réordonner les items. La première étape va donc être de recréer un tableau comprenant les informations suivantes : le nom du candidat (cela nous sera utile, plus tard, pour retrouver ses résultats) et sa mention.

def sort_candidates_by(mention):
    unsorted = [(key, (mention["mention"], mention["score"])) for key, mention in mentions.items()]

À présent, nous allons utiliser la forme du tri à bulles que nous avons vue précédemment. Attention, détail important : vous comparez les valeurs des mentions et non de l’élément en lui-même !

def sort_candidates_by(mentions):
    ## bubble sort here we go!
    unsorted = [(key, (mention["mention"], mention["score"])) for key, mention in mentions.items()]
    swapped = True
    while swapped:
        swapped = False
        for j in range(0, len(unsorted) - 1):
            ## but we need REVERSE bubble sort ;-)
            # (note that here we compare tuples, which is pretty neat)
            if unsorted[j + 1][1] < unsorted[j][1]:
                unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
                swapped = True

Et ajoutons un bout de code dans la fonction  main()  pour l’exécuter :

def main():
    votes = create_votes()
    results = results_hash(votes)
    majoritary_mentions = majoritary_mentions_hash(results)
    sorted_candidates = sort_candidates_by(majoritary_mentions)

Cela fonctionne, sauf que la mention la plus haute se trouve ainsi à la fin de la liste, or nous voulions qu’elle apparaisse au début ! Changeons la comparaison en ligne 3 : nous dirons que, si l’élément suivant est plus grand, il doit être interverti !

def sort_candidates_by(mentions):
    unsorted = [(key, (mention["mention"], mention["score"])) for key, mention in mentions.items()]
    swapped = True
    while swapped:
        swapped = False
        for j in range(0, len(unsorted) - 1):
            if unsorted[j + 1][1] > unsorted[j][1]:
                unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
                swapped = True
    print(unsorted)

Voici le résultat :

[('hermione', (0, 50044)), ('beyonce', (1, 66748)), ('balou', (3, 66575)), ('elsa', (4, 100000)), ('chuck-norris', (5, 66648)), ('gandalf', (6, 100000))]

Nos candidats sont bien classés !

Ajoutons un petit peu de code pour renvoyer un tableau tout joli tout beau :

def sort_candidates_by(mentions):
    ## bubble sort here we go!
    unsorted = [(key, (mention["mention"], mention["score"])) for key, mention in mentions.items()]
    swapped = True
    while swapped:
        swapped = False
        for j in range(0, len(unsorted) - 1):
            ## but we need REVERSE bubble sort ;-)
            # (note that here we compare tuples, which is pretty neat)
            if unsorted[j + 1][1] > unsorted[j][1]:
                unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
                swapped = True
    print(unsorted)

    return [
        {
            "name": candidate[0],
            "mention": candidate[1][0],
            "score": candidate[1][1],
        }
        for candidate in unsorted
    ]

Afficher les résultats dans la console

Créons une nouvelle fonction qui tranformera nos résultats en plusieurs chaînes de caractères agréables à lire.

Utilisons le dictionnaire  CANDIDATES  afin de retrouver le nom du candidat grâce à sa clé. Quant à chaque mention, il est assez simple d’afficher son nom "humain" grâce à son index.

def print_results(results):
    for i, result in enumerate(results):
        name = CANDIDATES[result["name"]]
        mention = MENTIONS[result["mention"]]
        score = result["score"] * 100. / VOTES
        print("- {} avec {:.2f}% de mentions {}".format(
            name, score, mention
        ))

Puisque je souhaite mettre à l’honneur notre vainqueur, j’ajoute une structure conditionnelle pour créer une chaîne de caractères différente :

def print_results(results):
    for i, result in enumerate(results):
        name = CANDIDATES[result["name"]]
        mention = MENTIONS[result["mention"]]
        score = result["score"] * 100. / VOTES
        if i == 0:
            print("Gagnant: {} avec {:.2f}% de mentions {}".format(
                name, score, mention
            ))
            continue
        else:
            print("- {} avec {:.2f}% de mentions {}".format(
                name, score, mention
            ))

Enfin, mettons à jour notre fonction  main  pour qu’elle exécute cette dernière fonction :

def main():
    votes = create_votes()
    results = results_hash(votes)
    majoritary_mentions = majoritary_mentions_hash(results)
    sorted_candidates = sort_candidates_by(majoritary_mentions)
    print_results(sorted_candidates)

Alors, qui gagne l’élection ? 

Bonne question ! Chez moi, c’est Hermione (youpi !), mais chez vous, le résultat est certainement différent !

Exemple de certificat de réussite
Exemple de certificat de réussite