Pour tous les exercices de cette session, on vous fournit un fichier squelette SessionE26.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 SessionE26Test.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 long intervalle d’entiers consécutifs

Un intervalle d’entiers consécutifs est une suite de valeurs de la forme a, a + 1, a + 2, ..., b

Par exemple, dans la liste [8, 3, 5, 4, 10, 6], les valeurs 3, 4, 5 et 6 forment un intervalle d’entiers consécutifs de longueur 4, et c’est le plus long possible pour cette liste. Vous pouvez remarquer que les valeurs de l’intervalle ne sont pas forcément adjacentes dans la liste.

Écrire la méthode longestInterval qui, étant donnée une liste d’entiers, renvoie la longueur du plus long intervalle d’entiers consécutifs présents dans cette liste.

public static int longestInterval(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 max: 500

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

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

2 Two Sum

Étant donné un tableau d’entiers et une valeur cible, on souhaite trouver toutes les paires d’indices telles que les entiers à ces indices ont pour somme la valeur cible.

On ne considère que les paires d’indices (i,j) telles que i < j. Par exemple, pour le tableau [1, 4, 2, 3, 0, -1, 0] et la valeur cible 3, les paires d’indices valides sont (0,2), (1,5), (3,4) et (3,6).

Une paire d’indices est encodée par le record suivant :

public record Indices(int i, int j) {}

Écrire la méthode twoSum qui renvoie l’ensemble des paires valides pour le tableau values et la valeur cible target.

public static Set<Indices> twoSum(int[] values, int target)

Caractéristiques des tableaux testés :

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

DIFFICULTÉ Niv. 1
Taille de tableau max: 100
Valeur max: 500

DIFFICULTÉ Niv. 2
Taille de tableau max: 1_000
Valeur max: 10_000

DIFFICULTÉ Niv. 3
Taille de tableau max: 1_000_000
Valeur max: Integer.MAX_VALUE

3 Bingo

Un groupe de girafes éparpillées dans le monde entier a décidé d’organiser une grande partie de bingo en ligne. Elles communiquent sur un serveur Discord. Les règles de leur bingo sont un peu étranges, mais on veut bien leur pardonner : elles ne sont pas très douées en conception de jeu. Le jeu fonctionne ainsi : l’une des girafes est maître du jeu et choisit un nombre n à atteindre. Ensuite, toutes les secondes, elle effectue un tirage au sort : elle attribue un nombre compris entre 0 et n − 1 à une girafe choisie au hasard. L’objectif de chaque girafe est d’obtenir toutes les valeurs entre 0 et n − 1 le plus rapidement possible.

Pour suivre l’évolution du jeu, les girafes veulent un bot qui affiche l’information suivante à chaque tirage :

• 0 si la girafe tirée au sort n’a pas encore obtenu toutes ses valeurs ;
• sinon, le nombre de girafes qui ont déjà obtenu toutes leurs valeurs (elle comprise) au moment où la girafe tirée au sort a obtenu la dernière qui lui manquait. Remarque : une fois que cette valeur est déterminée pour une girafe, elle ne change plus.

Votre objectif est de programmer ce bot.

Les tirages du maître du jeu sont enregistrés dans un fichier, qui constitue votre entrée. Vous devez écrire la méthode bingo, qui renvoie une liste d’entiers correspondant aux valeurs que le bot doit afficher.

public static List<Integer> bingo(Path path) throws IOException

Exemple :

3
Alice 2
Alice 0
Bob 2
Carl 0
Alice 1
Bob 1
Alice 2
Bob 0
Alice 0   --> [0, 0, 0, 0, 1, 0, 1, 2, 1]

Chaque girafe doit obtenir les valeurs 0, 1 et 2.

• Au 5e tirage, Alice a obtenu toutes ses valeurs : l’affichage vaut donc 1.
• Au 6e tirage, Bob n’a pas encore fini : l’affichage vaut 0.
• Au 7e tirage, c’est à nouveau Alice : l’affichage vaut toujours 1.
• Au 8e tirage, Bob a terminé après Alice : l’affichage vaut donc 2.
• Au dernier tirage, l’affichage pour Alice vaut toujours 1.

Caractéristiques des fichiers d’entrée :

L’entrée est un fichier contenant le nombre n de valeurs à atteindre sur la première ligne et ensuite, un tirage par ligne, c’est-à-dire le nom de la girafe et la valeur qui lui est attribuée, séparés par un espace, au format indiqué ci-dessus. Les noms des girafes ne contiennent pas d’espace.

DIFFICULTÉ Niv. 1
Nombre de lignes max: 10_000
Nombre de valeurs max: 100
Nombre de girafes max: 10

DIFFICULTÉ Niv. 2
Nombre de lignes max: 1_000_000
Nombre de valeurs max: 100_000
Nombre de girafes max: 3

DIFFICULTÉ Niv. 2b
Nombre de lignes max: 10_000_000
Nombre de valeurs max: 2
Nombre de girafes max: 1_000_000