gameofstones

Game of Stones est un projet Epitech (groupe, cursus avance) qui met en scene un Grand Maester devant proteger le trone en analysant, via la theorie des graphes, deux rapports d'espionnage : le Friendship Report (FR), qui liste les amities reciproques entre figures politiques, et le Conspiracy Report (CR), qui liste les complots (relation non reciproque, un individu pouvant comploter contre quelqu'un qui ne complote pas contre lui, y compris contre un ami). Le programme, ecrit dans le langage de son choix, expose deux modes : un mode Links qui affiche le degre de separation entre deux personnes du FR (ou -1 si elles ne sont pas connectees), et un mode Plots qui construit, pour un seuil de proximite n donne, la liste triee alphabetiquement des personnes, la matrice des plus courtes distances d'amitie bornees a n, et un rapport de complot.

Le coeur algorithmique du projet est la resolution recursive du 'plan de sauvegarde du trone' : a partir du CR, on extrait les ennemis directs de la Reine (ceux qui complotent directement contre elle), puis pour chacun on cherche un ami proche (friendship level <= n) qui complote egalement contre lui, formant une alliance directe. Si aucun ami proche ne complote contre un ennemi direct, on cherche un ami plus eloigne (far friend) qui complote contre l'un des ennemis de cet ennemi direct ; la personne qui complote alors contre ce far friend est appelee ennemi indirect, et le processus se poursuit recursivement de proche en proche jusqu'a neutraliser, directement ou indirectement, tous les ennemis directs.

Des regles de priorite strictes encadrent la resolution : quand plusieurs allies permettent de comploter contre un meme ennemi commun, on privilegie d'abord ceux qui ne complotent pas deja directement contre la Reine, puis les plus proches d'elle en niveau d'amitie, et enfin l'ordre alphabetique en dernier recours ; dans une meme chaine de complot, il est interdit de comploter deux fois avec ou contre la meme personne. Les chaines de complot trouvees doivent etre affichees triees de la plus courte a la plus longue, et par ordre alphabetique entre chaines de meme longueur.

Si le programme parvient a construire une chaine de complot neutralisant tous les ennemis directs, il affiche 'The stone is safe!' ; sinon, il affiche 'There is only one way out: treason!'. Toute personne presente dans le CR sans figurer dans le FR constitue une erreur de donnees. Le sujet interdit explicitement l'usage de bibliotheques ou fonctions externes de gestion de graphes ou de matrices, qualifiees de 'magie noire' : la structure de graphe, les parcours de plus courts chemins et la recherche recursive de complots doivent etre entierement codes a la main.