Session 2 - Premiers problèmes

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

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

1 All animals are equal, but some animals are more equal than others

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.

1.1 La rivière magique

Un groupe de lémuriens cherche à traverser une rivière en passant sur une corde tendue entre les deux rives. La corde a une longueur fixe N > 0, et l’on considère qu’il y a N positions différentes sur la corde, numérotées de 0 à N − 1. La corde peut accueillir au plus N lémuriens en même temps, chacun à une position distincte (il ne peut pas y avoir deux lémuriens à la même position). Un lémurien peut avancer d’une seule position à la fois sur la corde, et seulement à condition qu’il n’y ait pas de lémurien juste devant lui. Tous les lémuriens avancent dans le même sens. Lorsqu’un lémurien entre sur la corde, il occupe la position 0 et, lorsqu’il se trouve à la dernière position et qu’il avance, il sort de la corde et se retrouve sur l’autre rive. Comme il s’agit d’une rivière magique, dès que le lémurien touche la rive après avoir traversé sur la corde, il est téléporté instantanément sur l’autre rive (celle de départ), et peut à nouveau tenter de traverser.

Beaucoup de lémuriens cherchent à traverser en même temps, et le processus semble désorganisé, mais vous remarquez que les lémuriens communiquent : à chaque fois que l’un d’entre eux souhaite avancer (ou entrer sur la corde), il crie son nom. Afin d’étudier le processus, vous enregistrez les noms criés par les lémuriens pendant quelques heures et vous les transcrivez dans un fichier (votre entrée). Au moment d’analyser vos données, vous réalisez que vous avez oublié de compter combien de lémuriens ont réussi à effectuer une traversée complète. Ce n’est pas très grave, vous pensez pouvoir écrire un programme permettant de retrouver le compte. Écrivez la fonction lemurs correspondante.

public static int lemurs(Path path) throws IOException

L’entrée est un fichier contenant sur la première ligne, la longueur N de la corde, et ensuite un nom de lémurien par ligne.

1.2 La boîte à fromage

Les souris qui vivent dans votre immeuble font des provisions pour l’hiver en stockant du fromage dans une boîte. La boîte a une taille fixe N > 0, et les souris peuvent stocker au maximum N morceaux de fromage en même temps. Quand une souris ajoute un morceau de fromage, elle le dépose au fond de la boîte, après tous les autres, avec une petite étiquette à son nom.Lorsqu’une souris a un petit creux, elle vient prendre le premier fromage de la boîte, quelle que soit l’étiquette qu’il porte. Si la boîte est vide, la souris repart sans fromage.

Quand une souris arrive pour déposer un morceau de fromage, si la boîte est pleine, elle doit attendre que la boîte se vide un peu pour le déposer. Comme les souris sont très bien organisées, elles ont décidé de nommer un contrôleur de la file d’attente pour déposer les fromages. La dépose s’effectue dans un ordre dicté par une note (entre 1 et une valeur max K) attribuée à chaque souris quand elle arrive devant la boîte. La souris en attente ayant la plus haute note sera celle qui pourra déposer son fromage en premier. Et si deux souris ont la même note, c’est celle qui est arrivée le plus tôt qui peut déposer. Afin de vérifier que son système fonctionne bien, le contrôleur note toutes les actions des souris dans son carnet (votre entrée) : le nom de chaque souris quand elle arrive pour déposer un fromage, ainsi que la note qu’on lui a attribuée, et aussi tous les moments où une souris prend un fromage. Il remarque au passage que certaines souris essaient de tricher en revenant avec une autre note alors qu’elles sont déjà en attente. Dans ce cas, il les gronde un peu et ne tient pas compte de leur nouvelle demande.

Le contrôleur a du mal à tout gérer tout seul et il décide de prendre un apprenti (vous). Pour vérifier que vous avez bien compris son système, il vous donne ses notes et vous demande d’écrire la liste des étiquettes des fromages qui ont été retirés de la boîte, dans l’ordre. Écrivez la fonction mice correspondante.

public static List<String> mice(Path path) throws IOException

L’entrée est un fichier contenant sur la première ligne la taille N de la boîte, et ensuite sur chaque ligne, soit un nom de souris suivi de sa note (séparés par un espace), soit le caractère # pour indiquer qu’une souris essaie de prendre un fromage.

1.3 Une pluie de grenouilles

Pour vous détendre après une longue journée de cours, vous aimez bien faire la grille de mots mêlés du journal : il s’agit de trouver tous les mots d’une liste donnée dans une grille de lettres. Dans cette grille, les mots peuvent être écrits horizontalement, verticalement, en diagonale, à l’envers, et ils peuvent même se chevaucher avec d’autres occurrences. Quand vous ouvrez le journal d’aujourd’hui, une surprise vous attend… Un petit malin a remplacé tous les mots de la liste par un unique mot : FROG, et vous devez compter toutes les occurrences de FROG dans la grille du journal (votre entrée). Vous n’avez aucune envie de faire cela à la main, vous dégainez votre clavier et vous écrivez une fonction frogs pour résoudre le problème.

public static int frogs(Path path) throws IOException

2 Same same but different (optionnel)

2.1 Avec des Stream

Pour chaque exercice de la premières partie, 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.

Session 2 - Premiers problèmes

1 All animals are equal, but some animals are more equal than others

1.1 La rivière magique

1.2 La boîte à fromage

1.3 Une pluie de grenouilles

2 Same same but different (optionnel)

2.1 Avec des `Stream`

1 All animals are equal, but some animals are more equal than others

1.1 La rivière magique

1.2 La boîte à fromage

1.3 Une pluie de grenouilles

2 Same same but different (optionnel)

2.1 Avec des Stream

2.1 Avec des `Stream`