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 Pré-traitement des données.

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, maintenue par une ancienne magie oubliée. Un matin, après un violent grondement venu des nuages, 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é ancestrale é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. La position est donnée par les coordonnées (x,y) de l’extrémité inférieure gauche de la brique. Chaque brique est constituée d’une seule ligne de cubes ; sa longueur est indiquée en nombre de cubes ; enfin, la lettre H indique que la brique est horizontale, et la lettre V qu’elle est verticale. 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.

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.

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

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.