Pour tous les exercices de cette session, on vous fournit un fichier squelette SessionR26.java.

Les objectifs sont, dans l’ordre, que le code soit correct, que le code soit efficace et que le code soit lisible. Des tests unitaires sont fournis dans SessionR26Test.java.

Vous devez être attentifs à la quantité de mémoire nécessaire à votre programme et vous avez le droit d’utiliser toutes les caractéristiques de l’entrée (elles sont indiquées pour chaque exercice) pour concevoir un code efficace.

JavaDoc 25.

1 - Plus petite différence, en valeur absolue.

La différence absolue entre deux entiers x et y peut être calculée en Java à l’aide de l’appel de méthode : Math.abs(x - y).

On souhaite déterminer la plus petite différence absolue entre deux valeurs distinctes d’une liste. Par exemple, dans la liste [8, -1, 3, 12, -9], la plus petite différence absolue est 4. Elle est obtenue entre 8 et 12, mais aussi entre  − 1 et 3.

Écrire la méthode minimumAbsoluteDifference qui, étant donnée une liste d’entiers, renvoie la plus petite différence absolue entre deux de ses valeurs.

public static int minimumAbsoluteDifference(List<Integer> list) 

Caractéristiques des listes testées :

Les listes peuvent contenir des doublons et des valeurs négatives.

DIFFICULTÉ Niv. 1
Taille de liste max: 100
Valeur min: -500
Valeur max: 500

DIFFICULTÉ Niv. 2
Taille de liste max: 1_000
Valeur min: -10_000
Valeur max: 10_000

DIFFICULTÉ Niv. 3
Taille de liste max: 1_000_000
Valeur min: -Integer.MAX_VALUE
Valeur max: Integer.MAX_VALUE

2 - Robots

Des étudiants en robotique souhaitent tester leurs nouveaux robots. Pour cela, ils leur font réaliser plusieurs épreuves. L’une d’elles consiste à faire coopérer deux robots afin d’allumer des lampes placées dans un couloir, selon un ordre déterminé.

Le couloir comporte 11 lampes, numérotées de 0 à 10 de gauche à droite. Deux lampes consécutives sont espacées d’un mètre. Chaque lampe possède un interrupteur placé devant elle.

Initialement, le robot orange se trouve devant l’interrupteur 0 et commence à se déplacer vers la droite à une vitesse d’un mètre par seconde. Le robot bleu se trouve devant l’interrupteur 10 et commence à se déplacer vers la gauche à la même vitesse.

Lorsqu’un robot atteint une extrémité du couloir, il fait instantanément demi-tour. Ainsi, lorsqu’il atteint l’interrupteur 0, il repart vers la droite et, lorsqu’il atteint l’interrupteur 10, il repart vers la gauche. Les deux robots effectuent donc continuellement des allers-retours dans le couloir.

Avant leur départ, les robots reçoivent une liste d’interrupteurs. Ces interrupteurs doivent être actionnés dans l’ordre de la liste. Dès que l’un des deux robots passe devant le prochain interrupteur de la liste, il l’actionne instantanément et la lampe correspondante s’allume brièvement. Les deux robots se déplacent simultanément et ne s’arrêtent pas lorsqu’un interrupteur est actionné.

On cherche à déterminer le temps nécessaire aux deux robots pour actionner tous les interrupteurs de la liste. Lorsque le même interrupteur apparaît plusieurs fois consécutivement, toutes les activations correspondantes sont considérées comme instantanées.

La liste des numéros des interrupteurs est fournie sous la forme d’une chaîne de caractères dans laquelle les numéros sont séparés par des espaces. Écrire la méthode twoSimpleBots qui calcule le temps nécessaire aux deux robots pour actionner tous les interrupteurs de la liste.

public static int twoSimpleBots(String line)

Caractéristiques des lignes d’entrée :

Nombre de valeurs max sur une ligne: 100_000

Exemple :

"8 2 4 5 0 8 8 9" --> 49

Au départ, le robot orange se trouve devant l’interrupteur 0 et se déplace vers la droite. Le robot bleu se trouve devant l’interrupteur 10 et se déplace vers la gauche.

• Après 2 secondes, le robot bleu atteint la position 8 et actionne l’interrupteur 8. Au même instant, le robot orange atteint la position 2 et actionne immédiatement l’interrupteur 2.
• Le robot orange poursuit vers la droite et atteint la position 4 en 2 secondes (le robot bleu est en position 6).
• Il atteint ensuite la position 5 en 1 seconde (le robot bleu est également à la position 5).
• Puis, le robot bleu continue vers la gauche et atteint la position 0 en 5 secondes.
• Le robot orange, qui a atteint la position 10, fait demi-tour. Il atteint la position 8 en 2 secondes et actionne deux fois cet interrupteur instantanément (le robot bleu est en position 2).
• Enfin, le robot bleu atteint la position 9 en 7 secondes.

Le temps total est donc : 2 + 0 + 2 + 1 + 5 + 2 + 7 = 19 secondes.

Variante des robots (bonus) :

Écrire une variante de la méthode de l’exercice précédent telle que le numéro du dernier interrupteur soit donné en paramètre. Elle doit passer les tests twoSimpleBotsBonus. La valeur maximale de lastNumber est 10_000_000.

public static int twoSimpleBots(int lastNumber, String line)

3 - Course à vélo

La Fédération Cycliste Gustave Eiffel organise une course de vélo par équipes.

Avant le départ, les cyclistes se présentent avec un dossard sur lequel est inscrit le numéro de leur équipe. Chaque équipe comporte le même nombre de coureurs. Au moment du départ, les cyclistes se positionnent dans l’ordre dans lequel ils se sont présentés. Lorsque tous les participants sont présents, la course commence.

Le commissaire de course est chargé de vérifier qu’aucune irrégularité ne se produit. Pour cela, il note chaque fois qu’un cycliste accélère et dépasse le coureur qui le précède immédiatement dans la course. Si le cycliste qui accélère est déjà en tête, l’ordre des coureurs ne change pas.

Après chaque accélération, l’information est transmise au régisseur, qui doit afficher le score de l’équipe à laquelle appartient le cycliste qui a accéléré.

Le score d’un cycliste correspond à sa position dans la course : le premier a un score de 0, le deuxième un score de 1, et ainsi de suite. Le score d’une équipe est égal à la somme des scores de tous ses coureurs. Votre objectif est d’écrire un programme pour le régisseur qui calcule, après chaque accélération, le score de l’équipe concernée. Un exemple est fourni à la fin de l’énoncé.

Le nombre de cyclistes, leur nom et leur numéro d’équipe dans l’ordre d’arrivée ainsi que les accélérations sont indiqués dans un fichier constituant l’entrée du programme. Vous devez écrire la méthode race, qui renvoie une liste d’entiers correspondant aux scores que le régisseur doit afficher.

public static List<Long> race(Path path) throws IOException

Caractéristiques des fichiers d’entrée :

L’entrée est un fichier contenant le nombre n de cyclistes sur la première ligne, ensuite, un nom de cycliste, suivi d’un espace, suivi de son numéro d’équipe sur chacune des n lignes suivantes. L’ordre de ces lignes détermine l’ordre de départ. Toutes les lignes restantes contiennent chacune le nom d’un cycliste qui accélère.

DIFFICULTÉ Niv. 1
Nombre de cyclistes max: 3_000
Nombre de d'équipes max: 100
Nombre d'accélérations max: 10_000

DIFFICULTÉ Niv. 2
Nombre de cyclistes max: 1_000_000
Nombre de d'équipes max: 1_000
Nombre d'accélérations max: 10_000

Exemple :

4
Ali 1
Bob 1
Chani 2
Drew 2
Bob
Drew
Chani
Ali
Chani
Ali
Bob   --> [1, 5, 5, 1, 4, 2, 1]

L’ordre de départ est [Ali, Bob, Chani, Drew]. Chaque ligne à partir de la 5e correspond à l’accélération d’un cycliste.

• ligne 5, Bob accélère, dépasse Ali, l’ordre est [Bob, Ali, Chani, Drew]. Le score de l’équipe de Bob est 0 + 1 = 1.
• ligne 6, Drew accélère, dépasse Chani, l’ordre est [Bob, Ali, Drew, Chani]. Le score de l’équipe de Drew est 2 + 3 = 5.
• ligne 7, Chani accélère, dépasse Drew, l’ordre est [Bob, Ali, Chani, Drew]. Le score de l’équipe de Chani est 2 + 3 = 5.
• ligne 8, Ali accélère, dépasse Bob, l’ordre est [Ali, Bob, Chani, Drew]. Le score de l’équipe d’Ali est 0 + 1 = 1.
• ligne 9, Chani accélère, dépasse Bob, l’ordre est [Ali, Chani, Bob, Drew]. Le score de l’équipe de Chani est 1 + 3 = 4.
• ligne 10, Ali accélère, comme il est en tête, il ne se passe rien, l’ordre ne change pas. Le score de l’équipe d’Ali est 0 + 2 = 2.
• ligne 11, Bob accélère, dépasse Chani, l’ordre est [Ali, Bob, Chani, Drew]. Le score de l’équipe de Bob est 0 + 1 = 1.