Objectif : Lire et Analyser un sujet - Apprendre à ne pas tout recalculer si ce n’est pas nécessaire - Choisir les bonnes structures de données pour des problèmes simples.
Pour tous les exercices de cette session, on vous fournit un fichier
squelette Session5.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 Session5Test.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.
Dans cette partie, vous ne devez pas utiliser de
Stream.
Dans un ancien temple, une porte magique protège l’accès de la bibliothèque oubliée. Pour l’ouvrir, il faut retrouver un mot secret gravé en lettres d’or sur la pierre. Malheureusement, au fil du temps, ces lettres sont devenues invisibles.
Un mécanisme permet cependant de proposer des lettres, une par une. Chaque fois qu’une lettre est proposée, si cette lettre apparaît dans le mot secret, toutes ses occurrences réapparaissent immédiatement sur la porte. Sinon, rien ne se passe.
La porte s’ouvre dès que toutes les lettres du mot sont visibles.
On dispose :
word, composée de lettres minuscules, qui
représente le mot secret ;proposed, qui représente, dans l’ordre,
les lettres essayées par l’aventurier.L’objectif est d’écrire la méthode discoverWord qui
calcule après combien de propositions la porte s’ouvre. Si toutes les
lettres de proposed sont utilisées sans réussir à révéler tout le mot,
la méthode renvoie -1.
public static int discoverWord(String word, String proposed)Exemple :
discoverWord("banana", "xyzabn") --> 6Pour ‘x’, ‘y’, ‘z’, il ne se passe rien. Avec ‘a’, les 3 positions contenant ‘a’ sont révélées ; avec ‘b’, une position est révélée ; avec ‘n’ : les dernières positions sont révélées, à ce moment toutes les lettres sont visibles. Donc la méthode renvoie 6.
discoverWord("mirror", "abcimr") --> -1Il manque encore le ‘o’, donc la méthode renvoie -1,.
La bibliothèque du temple est bien plus précieuse que le temple lui même, elle est donc protégée par un mécanisme plus complexe : sur la porte de la bibliothèque, ce n’est plus juste un mot secret, mais toute une phrase gravée dans la pierre qu’il faut découvrir. Ici aussi, cette inscription a été effacée par le temps, et seules quelques traces visibles (les espaces et la ponctuation) subsistent encore dans la roche.
Les érudits avaient prévu un dispositif pour révéler peu à peu l’inscription. Ils ont laissé derrière eux une série de fragments. Chaque fragment est une petite chaîne de un, deux ou trois caractères. Lorsqu’un fragment est proposé, toutes ses occurrences dans le texte secret apparaissent immédiatement.
Le texte à révéler ainsi que la liste des fragments sont stockés dans un fichier texte, la première ligne contient le texte secret et chaque ligne suivante contient un fragment, dans l’ordre où ils sont proposés.
L’objectif est de déterminer combien de fragments sont nécessaires
pour rendre visible l’intégralité du texte. Écrivez la méthode
discoverText correspondante. Seuls les caractères
alphabétiques ont besoin d’être découverts et la casse est indifférente.
Si tous les fragments du fichier sont utilisés sans réussir à révéler
complètement le texte, la méthode doit renvoyer -1.
public static long discoverText(Path path) throws IOException Caractéristiques des fichiers d’entrée :
L’entrée est un fichier contenant le texte sur la première ligne et chaque fragment de longueur entre 1 et 3 sur les lignes suivantes.
DIFFICULTÉ Niv. 1
Nombre de caractères dans le texte: 15_000
Nombre de fragments: 300_000
DIFFICULTÉ Niv. 2
Nombre de caractères dans le texte: 1_000_000
Nombre de fragments: 100_000Exemple :
The Dragon sleeps.
rag
sl
dra
goo
one
ee
ps
the
on
fooLe texte secret est “The Dragon sleeps.” Il faut attendre d’avoir vu le neuvième fragment “on” pour que le texte soit complètement révélé, donc la méthode renvoie 9.
La bibliothèque du temple possède une porte secrète derrière laquelle se trouve son plus précieux trésor : un somptueux grimoire magique. Bien entendu, la porte est fermée par un mécanisme à débloquer.
Une fois n’est pas coutume, il faut trouver un mot secret, mais il faut faire vite : le temple menace de s’effondrer. Le mot secret est affiché sur la porte, mais une de ses lettres a été effacée. Il faut essayer de deviner le mot complet et le prononcer à voix haute. Par chance, dans la bibliothèque se trouve un manuscrit qui contient tous les mots de la langue utilisées par les anciens érudits. Il suffit donc de trouver tous les mots qui peuvent correspondre au mot affiché sur la porte pour les réciter à voix haute.
Écrivez la méthode guessWord correspondante. Elle prend en paramètre
un mot en minuscules dont l’un des caractères est une * (le
caractère effacé), ainsi qu’un fichier contenant une liste de mots en
minuscules (le manuscrit), et elle renvoie la liste, dans l’ordre
alphabétique, des mots pouvant correspondre.
public static List<String> guessWord(String wordToGuess, Path wordList) throws IOException Malheureusement, le mécanisme est un peu grippé et il faut parfois
recommencer l’opération plusieurs fois. Écrivez la méthode guessWords
qui prend comme premier paramètre un fichier contenant les différents
mots (avec une *) qui s’affichent sur la porte, et comme
deuxième paramètre le même fichier que précédemment. Elle renvoie la
liste des listes de mots à prononcer à voix haute pour chaque mot de
wordsToGuess. Chaque liste de mots est donnée comme une chaîne de la
forme [mot1, mot2, ...].
public static List<String> guessWords(Path wordsToGuess, Path wordList) throws IOException Caractéristiques des fichiers d’entrée :
Le fichier words.data contient 144_544 mots.
Nombre de mots max: 1_200_000Exemple :
wordList :
chat
chut
char
wordsToGuess :
*hat --> chat
c*at --> chat
ch*t --> chat, chut
cha* --> char, chat
Une dernière énigme vous attend avant de pouvoir accéder au grimoire tant convoité : il y a une combinaison sur le coffre. Sur le couvercle se trouve un mécanisme rotatif sur lequel est gravé une grille de caractères en minuscules. Un petit levier permet de décaler toutes les lignes d’un cran horizontalement à chaque fois qu’on l’actionne : la première ligne devient la seconde, et ainsi de suite jusqu’à la dernière ligne, qui devient la première. Par exemple, si les lignes sont “abcd” et “efgh” et “ijkl”, actionner le levier les décale en “ijkl” sur la première ligne, suivie “abcd” et enfin “efgh”.
Les anciens érudits ont laissé des instructions qui permettent de calculer la valeur d’une combinaison : elle est obtenue en additionnant, pour chaque lettre, sa position dans l’alphabet multipliée par son numéro de colonne et son numéro de la ligne (les lignes et les colonnes ont numérotées à partir de 1).
Par exemple, la combinaison :
dz
bcvaut 4 × 1 × 1 + 26 × 2 × 1 + 2 × 1 × 2 + 3 × 2 × 2 = 72.
Pour ouvrir le coffre, il faut trouver la rotation qui donne la
combinaison de score maximal. Écrivez la méthode rotate qui
prend en paramètre le chemin vers un fichier contenant les lignes du
mécanisme, et qui renvoie le nombre de fois qu’il faut actionner le
levier pour obtenir le score maximal. Si plusieurs rotations donnent le
même score maximal, on renvoie celle qui fait actionner le levier le
moins de fois.
public static long rotate(Path path) throws IOException Caractéristiques des fichiers d’entrée :
Le fichier une ligne de caractères (toutes de même longueur) par ligne.
DIFFICULTÉ Niv. 1
Nombre de lignes max: 1000
Nombre de caractères par ligne max: 100
DIFFICULTÉ Niv. 2
Nombre de lignes max: 100_000
Nombre de caractères par ligne max: 100Exemple :
dz
bc --> 1En actionnant le levier 0 fois, on obtient 72 comme calculé ci-dessus, et en l’actionnant une fois, on obtient 120.
StreamPour 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.