Session 1 : Échauffement.

Objectif : Choisir les bonnes structures de données pour des problèmes simples - Analyser les besoins en temps et en mémoire.

Compétences :
Écrire des algorithmes simples en Java - Utiliser des tests unitaires - Parser un fichier formaté

Pour tous les exercices de cette session, on vous fournit un fichier squelette Session1.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 Session1Test.java.

Partie 1 : quelques méthodes simples

On commence par quelques méthodes statiques très simples qui prennent en entrée une liste générique. Pour tester, vous pouvez ajouter un main avec vos propres tests et utiliser les tests unitaires fournis.

Dans cette partie, vous ne devez pas utiliser de Stream.

Exercice 1 : Compter les occurrences d’un élément

Écrivez une méthode numberOfOccurrences qui prend en paramètre une liste et un élément, et renvoie le nombre de fois que cet élément apparaît dans la liste.

public static <E> long numberOfOccurrences(List<E> list, E element)

Exemples :

list = [A, B, A, C], element = A, résultat: 2
list = [A, B, C],    element = Z, résultat: 0

Exercice 2 : Vérifier l’unicité

Écrivez une méthode allDistinct qui renvoie true si tous les éléments de la liste sont différents (aucun doublon), et false sinon.

public static <E> boolean allDistinct(List<E> list)

Exemples :

list = [1, 2, 3, 4], résultat: true
list = [1, 2, 1, 3], résultat: false

Exercice 3 : Conversion en chaîne de caractères

Écrivez une méthode listToString qui convertit une liste en une chaîne de caractères où chaque élément est séparé par un point-virgule (;).

public static <E> String listToString(List<E> list)

Exemples :

list = [10, 20, 30],  résultat: "10;20;30"
list = ["Java", "C"], résultat: "Java;C"

Exercice 4 : L’élément le plus fréquent

Écrivez une méthode mostFrequent qui renvoie l’élément qui apparaît le plus souvent dans la liste. Si la liste est vide, l’Optional renvoyé est vide. En cas d’égalité, n’importe lequel des éléments gagnants peut être renvoyé.

public static <E> Optional<E> mostFrequent(List<? extends E> list)

Exemples :

list = [1, 2, 1, 3], résultat: Optional[1]
list = [],           résultat: Optional.empty

Exercice 5 : Supprimer les doublons

Écrivez une méthode withoutDuplicates qui renvoie une nouvelle liste contenant les éléments de la liste d’origine sans aucun doublon. L’ordre de première apparition des éléments doit être conservé.

public static <E> List<E> withoutDuplicates(List<? extends E> list)

Exemples :

list = [1, 2, 1, 3, 2], résultat: [1, 2, 3]
list = [A, A, A],       résultat: [A]

Exercice 6 : Identifier les éléments dupliqués (une seule fois)

Écrivez une méthode oneOfEachDuplicate qui renvoie une liste des éléments qui apparaissent au moins deux fois dans la liste d’origine. Chaque valeur dupliquée ne doit apparaître qu’une seule fois dans le résultat.

public static <E> List<E> oneOfEachDuplicate(List<? extends E> list)

Exemples :

list = [1, 2, 1, 3, 2, 1], résultat: [1, 2]
list = [A, A, A, A],       résultat: [A]

Exercice 7 : Les éléments aux positions paires

Écrivez une méthode onlyEvenPosition qui renvoie un ensemble contenant uniquement les éléments qui n’apparaissent qu’aux positions paires dans la liste d’origine.

public static <E> Set<E> onlyEvenPosition(List<? extends E> list)

Exemples :

list = [1, 2, 1, 3, 4, 4, 5], résultat: [1, 5]
list = [A, A, B],             résultat: [B]

Exercice 8 : Les éléments uniques (singletons)

Écrivez une méthode singles qui renvoie un ensemble contenant uniquement les éléments qui apparaissent exactement une fois dans la liste d’origine.

public static <E> Set<E> singles(List<? extends E> list)

Exemples :

list = [1, 2, 1, 3, 4, 2], résultat: [3, 4]
list = [A, A, B],          résultat: [B]

Partie 2 : l’entrée est un fichier de nombres

À partir de maintenant, pour chaque problème, l’entrée sera donnée dans un fichier. Voici quelques exercices pour s’entraîner à ce format.

Aux objectifs précédents, on ajoute celui de savoir parser un fichier simplement formaté. 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.

Dans cette partie, vous ne devez pas utiliser de Stream.

Exercice 1 : Vérifier l’unicité des entiers

L’entrée est un fichier contenant un ou plusieurs entiers (int) par ligne, séparés par des espaces.

Écrivez une méthode allDistinctInFile qui renvoie true si tous les entiers du fichiers sont différents (aucun doublon), et false sinon.

public static boolean allDistinctInFile(Path path) throws IOException

Caractéristiques des fichiers :

DIFFICULTÉ Niv. 1
Nombre de lignes max: 1000
Nombre d'entiers par lignes max: 100
Valeur d'un entier max: 2^31-1

DIFFICULTÉ Niv. 2
Nombre de lignes max: 1_000_000
Nombre d'entiers par lignes max: 1_000
Valeur d'un entier max: 100_000

Exemples :

1
2
3 --> true
1 
2 3
3 4 5 --> false

Exercice 2 : Compter les entiers distincts

L’entrée est un fichier contenant un ou plusieurs entiers (int) par ligne, séparés par des espaces.

Écrivez une méthode numberOfDistinctsNumbersInFile qui renvoie d’entiers différents dans le fichier.

public static int numberOfDistinctsNumbersInFile(Path path) throws IOException

Caractéristiques des fichiers:

DIFFICULTÉ Niv. 1
Nombre de lignes max: 1_000
Nombre d'entiers par lignes max: 100
Valeur d'un entier max: 2^31-1

DIFFICULTÉ Niv. 2
Nombre de lignes max: 1_000_000
Nombre d'entiers par lignes max: 1_000
Valeur d'un entier max: 100_000

DIFFICULTÉ Niv. 3
Nombre de lignes max: 1_000_000
Nombre d'entiers par lignes max: 1_000
Valeur d'un entier max: 2^31-1

Exemples :

1
2 3
3 --> true
1 
2 3 3
3 4 5 --> false

Exercice 3 : Calculer la moyenne

L’entrée est un fichier contenant contenant deux entiers (int) par ligne, un id et une valeur, séparés par un espace.

Écrivez une méthode averageInFile qui renvoie la moyenne (arrondie à l’entier inférieur) des valeurs contenues dans le fichier.

public static long averageInFile(Path path) throws IOException

Caractéristiques des fichiers:

Nombre de lignes max: 1_000_000
Valeur d'un id max: 2^31-1
Valeur associée max: 100

Exemples :

1 1
2 3 
3 4 --> 2
38 38
38 62
38 71
93 93
63 63
63 75
21 21
18 21
63 95
63 95 --> 60

Exercice 4 : Minimum et maximum, par id, à la volée.

L’entrée est un fichier dont chaque ligne contient deux entiers (int) séparés par un espace : un identifiant id et la valeur qui lui est associée. L’objectif est de déterminer, pour chaque id, le minimum et le maximum des valeurs déjà rencontrées pour cet identifiant, au fur et à mesure de la lecture du fichier.

Par exemple, après lecture de la ligne 1 42, on a pour l’id 1 : minimum = 42 et maximum = 42. Si la ligne suivante est 1 7, alors pour l’id 1 : minimum = 7 et maximum = 42. Si l’on lit ensuite 2 99, alors pour l’id 2 : minimum = 99 et maximum = 99. Et ainsi de suite.

Écrivez une méthode minMaxInFile qui renvoie une liste de couples (MinMax) telle que le i-ème élément de la liste correspond au minimum et au maximum courants pour l’id figurant sur la i-ème ligne du fichier.

public record MinMax(int min, int max) {}

public static List<MinMax> minMaxInFile(Path path) throws OException

Caractéristiques des fichiers:

Nombre de lignes max: 1_000_000
Valeur d'un id max: 2^31-1
Valeur associée max: 100

Exemples :

3 38 --> 38 38   
3 62 --> 38 62 
8 63 --> 63 63 
8 75 --> 63 75 
2 21 --> 21 21 
8 95 --> 63 95

Partie 3 (optionnelle): same same but different

Exercice : avec des Stream

Pour chaque exercice des deux premières parties, lorsque c’est possible et si la complexité est la même (en temps et en mémoire), réécrire le code en utilisant des Stream.