%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] %% nav-fin %% # Évaluation - Six degrés de Kevin Bacon > [!info] 🎯 Objectif > Calculer la distance entre deux acteurs dans le graphe des films, puis présenter le programme en soutenance. Cette page sert à la préparation de l'évaluation de la compétence [[Code et Développement/Programmation/Graphes/Graphes|Graphes]]. La validation se fait lors d'une soutenance individuelle. ## Le problème Deux acteurs sont reliés s'ils ont joué dans un même film. Le nombre de Bacon d'un acteur est la longueur du plus court chemin qui le relie à Kevin Bacon dans ce graphe. Kevin Bacon a le nombre 0. Un acteur qui a joué avec lui a le nombre 1. Un acteur qui a joué avec un acteur de nombre 1, sans avoir joué avec Kevin Bacon, a le nombre 2. Le graphe n'est pas pondéré. Le parcours en largeur donne donc les distances, comme dans la page [[Code et Développement/Programmation/Graphes/03_Parcours en largeur (BFS)|Parcours en largeur]]. ## Entrée et sortie - Ligne 1 : le nom de l'acteur étudié. - Ligne 2 : le nombre n de films. - n lignes : un film par ligne, sous la forme `Titre: acteur 1, acteur 2, …`. La sortie est le nombre de Bacon de l'acteur étudié. Dans tous les cas de test, l'acteur est relié à Kevin Bacon. ## Les cas de test ```sq-fichier nom: cas1.txt --- Kevin Bacon 1 Apollo 13: Kevin Bacon, Tom Hanks ``` ```sq-fichier nom: cas2.txt --- Elvis Presley 3 Change of Habit: Elvis Presley, Mary Tyler Moore Ordinary People: Mary Tyler Moore, Timothy Hutton Taps: Timothy Hutton, Sean Penn, Kevin Bacon ``` ```sq-fichier nom: cas3.txt --- Tom Hanks 2 Apollo 13: Kevin Bacon, Tom Hanks, Bill Paxton Cast Away: Tom Hanks, Helen Hunt ``` ```sq-fichier nom: cas4.txt --- Ada Lovelace 6 Film A: Ada Lovelace, Alan Turing Film B: Alan Turing, Grace Hopper Film C: Grace Hopper, Kevin Bacon Film D: Ada Lovelace, Linus Torvalds Film E: Linus Torvalds, Kevin Bacon, Guido van Rossum Film F: Guido van Rossum, Grace Hopper ``` ```sq-fichier nom: cas5.txt --- Marie Curie 5 Film 1: Marie Curie, Pierre Curie Film 2: Pierre Curie, Paul Langevin Film 3: Paul Langevin, Irène Joliot-Curie Film 4: Irène Joliot-Curie, Frédéric Joliot Film 5: Frédéric Joliot, Kevin Bacon ``` ## Votre programme Écrivez la fonction `resoudre(texte)`. Elle reçoit le contenu complet d'un cas de test et renvoie la sortie attendue sous forme de chaîne. ```sq-python def resoudre(texte): lignes = texte.strip("\n").split("\n") # À compléter : renvoyer la sortie attendue sous forme de chaîne return "" print(resoudre(open("cas1.txt").read())) #--- tests assert resoudre(open("cas1.txt").read()) == "0", "cas 1 : Kevin Bacon lui-même" assert resoudre(open("cas2.txt").read()) == "3", "cas 2 : chaîne de trois films" assert resoudre(open("cas3.txt").read()) == "1", "cas 3 : acteur de nombre 1" assert resoudre(open("cas4.txt").read()) == "2", "cas 4 : deux chemins de longueurs différentes" assert resoudre(open("cas5.txt").read()) == "5", "cas 5 : chaîne de cinq films" ``` ## Pour la soutenance - Expliquer comment le graphe est construit à partir des films. - Justifier le choix du parcours en largeur plutôt qu'en profondeur. - Présenter un cas de test ajouté par vous. Puzzle d'origine sur CodinGame : [Six Degrees of Kevin Bacon](https://www.codingame.com/training/easy/six-degrees-of-kevin-bacon). %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Graphes/Graphes|Accueil · Graphes]] %% nav-fin %%