Objectif : Lire et Analyser un sujet - Simuler un système qui évolue dans le temps - 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 Session4.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 Session4Test.java.

1 Programming Contest

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.

1.1 Un empilement de briques (inspiré de l’Advent of Code 2023, jour 22)

La Cité des Sables est une très ancienne cité, construite entièrement en briques et suspendue dans le ciel par magie. Un beau jour, des briques commencèrent à se détacher des bords des ruines célestes et à tomber sur la plaine en contrebas. Les habitants comprirent alors que la cité était en train de s’effondrer morceau par morceau. Ils réalisèrent aussi que les trésors de la cité pouvaient se trouver parmi les briques tombées. Afin d’organiser les fouilles, ils ont pris un instantané des briques pendant qu’elles étaient encore en train de tomber (votre entrée), ce qui devrait permettre de déterminer jusqu’à quelle hauteur ils devront grimper pour fouiller le tas de briques une fois qu’elles seront toutes tombées. Voici un exemple d’instantané contenant 3 briques :

4 2 4 H
0 3 2 H
4 0 2 V

Chaque ligne représente une brique au moment où l’instantané a été pris. Les deux première valeurs donne la position (x,y) de l’extrémité inférieure gauche de la brique. Chaque brique est constituée d’une seule ligne de cubes ; la troisième va leur est sa longueur indiquée en nombre de cubes ; enfin, la lettre H indique que la brique est horizontale, et la lettre V qu’elle est verticale. Par exemple, la ligne 0 3 2 H signifie qu’il y a une brique horizontale de longueur 2 dont l’extrémité gauche se trouve en position x = 0, y = 3. Les habitants ont pris soin de choisir un instant où toutes les briques en chute libre se trouvaient à des positions entières au-dessus du sol, de sorte que tout l’instantané est aligné sur une grille bidimensionnelle.

Comme l’instantané a été pris pendant que les briques étaient encore en train de tomber, certaines briques sont encore en l’air ; il faut donc déterminer où elles finiront par s’arrêter. Les briques sont stabilisées magiquement, donc elles ne tournent jamais, même dans des situations étranges où une longue brique horizontale n’est soutenue que par une seule extrémité. Deux briques ne peuvent pas occuper la même position ; ainsi, une brique en chute s’immobilise dès qu’elle rencontre la première autre brique sur sa trajectoire.

Votre mission est de déterminer la hauteur de la plus haute brique après que toutes les briques aient fini de tomber. Écrire la méthode bricks correspondante.

public static int bricks(Path path) throws IOException

Caractéristiques des fichiers d’entrée :

L’entrée est un fichier contenant une brique sur chaque ligne, au format indiqué ci-dessus.

DIFFICULTÉ Niv. 1
Nombre de briques max: 1000
Longueur de brique max: 1000
Valeur d'une coordonnée max: 10_000

DIFFICULTÉ Niv. 2
Nombre de briques max: 1_000_000
Longueur de brique max: 1000
Valeur d'une coordonnée max: Integer.MAX_VALUE

Exemple :

4 2 4 H
0 3 2 H
4 0 1 H
3 5 3 H
1 0 2 H  --> 3

4 2 4 H
0 3 2 H
4 0 2 V
3 5 3 H
1 0 2 H
6 4 8 V  --> 11

1.2 Les guirlandes lumineuses (Advent of Code 2025, jour 8)

Un groupe d’elfes travaille à la mise en place d’un ambitieux projet de décoration. Grâce à un ingénieux système de suspension, ils ont accroché un grand nombre de petites boîtes de jonction électriques.

Leur plan consiste à relier les boîtes de jonction avec de longues guirlandes lumineuses. La plupart des boîtes de jonction ne fournissent pas d’électricité ; cependant, lorsque deux boîtes de jonction sont reliées par une guirlande, l’électricité peut circuler entre ces deux boîtes.

Les elfes essaient de déterminer quelles boîtes de jonction connecter afin que l’électricité puisse atteindre chaque boîte de jonction. Ils disposent même d’une liste des positions de toutes les boîtes de jonction dans l’espace 3D (votre entrée).

Par exemple :

162,817,812
57,618,57
906,360,560
466,668,158
431,825,988
739,650,466
805,96,715
941,993,340
425,690,689

Cette liste décrit 9 boîtes de jonction, une par ligne. Chaque position est donnée sous la forme de coordonnées X, Y, Z. Ainsi, la première boîte de jonction de la liste se trouve en X = 162, Y = 817, Z = 812.

Afin d’économiser les guirlandes, les elfes veulent privilégier la connexion de paires de boîtes de jonction aussi proches que possible (distance euclidienne). Dans cet exemple, les deux boîtes les plus proches sont 162, 817, 812 et 425, 690, 689. En reliant ces deux boîtes, l’électricité peut circuler entre elles, elles font désormais partie du même circuit. Il y a maintenant un unique circuit contenant ces deux boîtes et les 18 boîtes restantes demeurent chacune dans leur propre circuit individuel.

Ensuite, les deux boîtes les plus proches qui ne sont pas déjà directement reliées sont 162, 817, 812 et 431, 825, 988. Après les avoir connectées, puisque 162, 817, 812 est déjà reliée à une autre boîte, on a un circuit contenant trois boîtes et 17 autres avec chacun une seule boîte. Les deux boîtes de jonction suivantes à connecter sont 906, 360, 560 et 805, 96, 715. Après les avoir reliées, il y a un circuit contenant 3 boîtes, un circuit contenant 2 boîtes, et 15 circuits solitaires. Les deux boîtes suivantes sont 431, 825, 988 et 425, 690, 689. Comme elles sont déjà dans le même circuit, il ne se passe rien !

Afin que la décoration fonctionne, les elfes doivent continuer à connecter les boîtes de jonction jusqu’à ce qu’elles forment toutes un unique grand circuit. Après 9 étapes, les deux dernières boîtes connectées sont 57, 618, 57 et 466, 668, 158.

Écrivez une fonction junctionBoxes qui permet de prévoir quelles seront les deux dernières boîtes connectées, quelle que soit la liste de boîtes initiale.

public static Set<Box> junctionBoxes(Path path) throws IOException

La fonction renvoie un ensemble de 2 Box qui sont les deux dernières connectées pour former un unique circuit.

Caractéristiques des fichiers d’entrée :

L’entrée est un fichier contenant sur chaque ligne les coordonnées d’une boîte, séparées par des virgules.

DIFFICULTÉ Niv. 1
Nombre de boîtes max: 100
Valeur d'une coordonnée max: 500

DIFFICULTÉ Niv. 2
Nombre de boîtes max: 2_000
Valeur d'une coordonnée max: 926800

Source: https://adventofcode.com/2025/day/8

1.3 Profondeur d’imbrication (Google Code Jam 2020 - Qualification - Problème B)

Étant donnée une chaîne de chiffres S, il faut insérer un nombre minimal de parenthèses ouvrantes et fermantes de sorte que :

1. la chaîne obtenue est correctement parenthésée ;
2. si l’on supprime toutes les parenthèses, on retrouve exactement S ;
3. chaque chiffre d apparaît à une profondeur d’imbrication d ;
4. la chaîne finale est de longueur minimale. 

La profondeur d’imbrication d’une position est le nombre de paires de parenthèses appariées qui l’entourent. Par exemple, les chaînes suivantes respectent la contrainte “chiffre = profondeur” :

• 0((2)1)
• (((3))1(2))
• ((((4))))
• ((2))((2))(1)  

Cependant, toutes ne sont pas minimales. Par exemple, pour les chiffres 221, la chaîne ((22)1) est plus courte que ((2))((2))(1). Écrire la fonction nestingDepth qui, étant donnée une séquence de chiffres calcule la séquence parenthésée définie ci-dessus.

public static String nestingDepth(String sequence)

0000    --> 0000
1011     --> (1)0(11)
111020  --> (111)0((2))0
2       --> ((2))

Les chaînes (1)0((()1) et (1)0(1)(1) ne sont pas valides parce qu’elles ne sont pas de longueur minimale. De plus, 1)( et )(1 ne sont pas des solutions valides car elles contiennent des parenthèses non appariées.

Source: https://dmoj.ca/problem/gcj20qrb

1.4 Saving The Universe (Google Code Jam 2018 – Qualification – Problème A)

Un robot extra-terrestre menace l’univers à l’aide d’un rayon laser ultra puissant qui peut tout détruire. Il faut l’arrêter !

Heureusement, le fonctionnement du robot est connu. Il commence avec un rayon de puissance 1, puis exécute un programme constitué d’une suite d’instructions, traitées une par une, de gauche à droite. Chaque instruction est :

• soit C (pour charge) : double la puissance du rayon ;
• soit S (pour shoot) : tire avec le rayon, en infligeant des dégâts égaux à la puissance actuelle du rayon.

Par exemple, si le programme du robot est SCCSSC, alors le robot effectue les actions suivantes :

• il tire avec le rayon et inflige 1 dégât ;
• il charge le rayon, ce qui double sa puissance à 2 ;
• il charge le rayon, ce qui double sa puissance à 4 ;
• il tire avec le rayon et inflige 4 dégâts ;
• il tire avec le rayon et inflige 4 dégâts ;
• il charge le rayon, ce qui augmente sa puissance à 8.

Dans ce cas, le programme inflige donc un total de 9 dégâts.

Les meilleurs scientifiques de l’univers ont développé un bouclier capable de résister à un total maximal de D dégâts. Mais le programme actuel du robot peut infliger davantage de dégâts lorsqu’il sera exécuté.

Vous vous êtes porté volontaire pour aller dans l’espace pirater le programme du robot avant son exécution. La seule manière de le pirater (sans que le robot ne s’en aperçoive) consiste à échanger deux instructions adjacentes. Par exemple, vous pourriez pirater une fois le programme ci-dessus en échangeant les troisième et quatrième instructions pour obtenir SCSCSC. Cela réduirait le total des dégâts à 7.

Ensuite, par exemple, vous pourriez pirater à nouveau le programme pour obtenir SCSSCC, réduisant les dégâts à 5, et ainsi de suite.

Afin de ne pas éveiller les soupçons du robot, il ne faut pas effectuer trop de piratages. Quel est le plus petit nombre possible de piratages permettant de garantir que le programme n’inflige pas plus de D dégâts au total, si cela est possible ? Écrire la fonction saveTheUniverse qui, étant donnés la valeur de dégâts maximale et le programme du robot, calcule ce nombre de piratages.

public static int saveTheUniverse(long damage, String program)

La valeur renvoyée est soit le nombre minimal de piratages nécessaires pour atteindre l’objectif, soit -1 si cela ne peut pas être fait.

Caractéristiques des fichiers de test :

La première ligne de l’entrée contient le nombre de cas de test, T.
Les T cas de test suivent. Chacun est constitué d’une ligne contenant le nombre maximal de dégâts que le bouclier peut encaisser, suivi du programme du robot.

DIFFICULTÉ Niv. 1
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot contient soit zéro, soit un seul caractère 'C'.

DIFFICULTÉ Niv. 2
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot peut contenir plusieurs caractères 'C'.

DIFFICULTÉ Niv. 3
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot peut contenir plusieurs caractères 'C'.

Exemple :

6
1 CS       --> 1
2 CS       --> 0
1 SS       --> -1
6 SCCSSC   --> 2
2 CC       --> 0
3 CSCSS    --> 5

Dans le cas n°1, on peut échanger les deux instructions pour réduire les dégâts totaux à 1, ce que le bouclier peut supporter.

Dans le cas n°2, on n’a pas besoin de pirater le programme du tout, puisque le bouclier peut déjà résister aux 2 dégâts totaux qu’il provoquera.

Dans le cas n°3, le programme infligera plus de dégâts que le bouclier ne peut en supporter, et le piratage ne changera rien à cela. L’univers est condamné.

Le cas n°4 utilise le programme décrit dans l’énoncé. Celui-ci montre une manière de réduire les dégâts à 5 en utilisant deux piratages. Il n’est pas possible de réduire les dégâts à 6 ou moins avec un seul piratage ; rappelons que l’on ne peut échanger que des instructions adjacentes.

Dans le cas n°5, le robot ne tirera jamais, et n’infligera donc jamais aucun dégât. Aucun piratage n’est nécessaire.

Dans le cas n°6, cinq piratages sont requis. Remarquez que même si deux piratages échangent les instructions aux mêmes deux positions, ils comptent tout de même comme deux piratages distincts.

Source: https://dmoj.ca/problem/gcj18qra

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.