Exercice 3 - Graphes · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2025 (jour 2)

Exercice 3 [8 points]

Cet exercice porte sur les structures de données, la programmation, les graphes.

Partie A

Le siteswap est une notation mathématique pour codifier les figures de jonglerie. Elle est aujourd'hui utilisée par des jongleurs et jongleuses dans le monde entier. Beaucoup de figures sont alors simplement désignées par leur siteswap, comme par exemple 441, 7531 ou encore 453.

On modélise le jonglage de la manière suivante: au lieu de calculer des trajectoires complexes, on considère simplement un rythme régulier sur lequel on jongle, et une balle est lancée à chacun de ses « temps ».

Les lancers sont caractérisés par un nombre entier positif, représentant simplement le nombre de « temps » au bout duquel la balle revient dans la main du jongleur et peut être relancée.

À un instant donné, on peut représenter ce qu'on appelle un état, c'est-à-dire une sorte de photographie des balles « en l'air ». On notera ces états sous forme de tableaux Python, contenant des 0 et des 1. Un 0 représente un espace vide et un 1 représente une balle.

Si on considère l'état e1 = [1, 0, 0, 1, 1, 0]: son premier élément, e1[0] vaut 1, et représente donc la balle prête à être relancée. Si e1[0] valait 0, aucune balle à relancer ne serait présente. Ensuite chaque e1[i] représente la présence ou non d'une balle qui atterrira dans la main de la jongleuse au bout de i temps.

L'état e1 ci-dessus représente donc un instant d'une figure à 3 balles, l'une est dans la main de la jongleuse, et deux autres balles sont plus haut, et retomberont dans la main dans respectivement 3 et 4 temps puisque e1[3] et e1[4] sont égaux à 1 et les autres à 0.

Comme l'indice maximal est de 5 dans le tableau, on dira que la hauteur maximale est 5.

Lorsque la jongleuse attrape la balle, elle va la relancer, dans un emplacement en l'air qui est « libre », car elle ne souhaite pas recevoir à un moment donné deux balles en même temps.

Dans l'exemple e1 = [1, 0, 0, 1, 1, 0], la jongleuse peut effectuer un lancer de 1, un lancer de 2 ou un lancer de 5, car les emplacements e1[1], e1[2] et e1[5] sont à 0, donc « libres ». Elle ne peut pas lancer un 3 ou un 4.

Si le premier élément de l'état est à 0, cela signifie que la jongleuse n'a aucune balle dans sa main à cet instant. Elle ne peut donc pas lancer de balle, et on appellera ça, par convention, un lancer « 0 ». Un lancer « 0 » n'est possible que dans cette situation.

Lorsqu'on lance une balle, elle vient se placer là où on l'a prévu, puis la gravité fait son effet et toutes les balles redescendent d'un cran.

Ainsi, si depuis l'état e1 = [1, 0, 0, 1, 1, 0] on lance un 2, on obtient l'état [0, 0, 1, 1, 1, 0] puis l'état [0, 1, 1, 1, 0, 0] après effet de la gravité:

Partie C

Plutôt que de calculer l'ensemble des séquences possibles à partir d'un état donné, on préfère calculer d'un coup, dès le début, l'ensemble des états et des lancers possibles.

On représentera ces données par un graphe orienté, dont les sommets sont les états, et on a un arc d'un état $e$ à un état $f$ si le lancer $n$ permet de passer de l'état $e$ à l'état $f$. Dans ce cas on inscrit le $n$ à proximité de l'arc entre $e$ et $f$ et on dit que c'est l'étiquette de l'arc.

On travaille donc avec un graphe orienté étiqueté. Ce graphe est également appelé automate des états.

Voici par exemple l'automate des états des jonglages à deux balles, de hauteur maximale 4:

On a choisi de représenter les états par des chaînes de caractères: '11000' représente l'état [1, 1, 0, 0, 0] dans les parties précédentes.

On souhaite stocker ce graphe sous forme de dictionnaire de listes d'adjacences: les clés sont les états, et les valeurs sont des listes de tuple: le premier élément est un entier, le numéro du lancer possible, et le second est l'état qu'on obtient lorsqu'on applique ce lancer.

10.

Recopier et compléter le code Python permettant de représenter l'automate de la figure 4 dans une variable automate:

11.

Écrire le code de la fonction lancer_balle_automate qui prend en arguments un automate automate comme décrit plus haut, un état etat et un entier lancer représentant un lancer et qui renvoie l'état obtenu lorsqu'on lance lancer depuis l'état etat. On renvoie la chaîne vide si le lancer n'est pas possible.

Exemples:

>>> lancer_balle_automate(automate, '10010', 2) renvoie '01100'

>>> lancer_balle_automate(automate, '11000', 1) renvoie ''

Un siteswap est une suite de lancers qui correspond à un cycle dans l'automate: autrement dit cela correspond à des lancers qu'on peut répéter en boucle: c'est une « figure » de jonglage.

Par exemple dans le graphe de la Figure 4, la séquence 3, 1 est un siteswap: on part de l'état '11000' puis le lancer de 3 nous amène dans l'état '10100', le lancer de 1 nous ramène dans l'état '11000' et on peut recommencer cette figure.

La séquence 1, 2, 3, 4, 0 est également un siteswap (partant de l'état '10100', les lancers successifs sont possibles et on revient bien à l'état de départ).

La séquence 2 est également un siteswap (reste dans l'état '11000').

On souhaite écrire une fonction parcours_sequence_depart qui prend en argument un automate, un état de départ, et une liste de lancers, et qui renvoie l'état dans lequel on arrive en suivant la séquence de lancers, ou bien None si l'un des lancers était impossible.

12.

Écrire le code de la fonction parcours_sequence_depart. On peut utiliser la fonction lancer_balle_automate.

Grâce à la fonction précédente, il est possible de vérifier qu'un siteswap est valide, c'est-à-dire qu'il existe un état à partir duquel réaliser la figure de jonglage.

On souhaite à présent écrire une fonction departs_siteswap qui prend en argument un automate et une liste de lancers (un potentiel siteswap), et renvoie la liste des états de l'automate qui valide le siteswap.

13.

Écrire la fonction departs_siteswap. On peut utiliser la fonction parcours_sequence_depart, et vérifier si le siteswap est possible à partir de chaque état de l'automate.