Session 6 - Énumérer les solutions

Objectif : Lire et Analyser un sujet - Proposer une solution “brute-force” à in problème d’optimisation - 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 Session6.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 Session6Test.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.

1 Force Brute

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

1.1 Allumez les lumières (Advent of Code 2025, jour 10)

1.1.1 Pour commencer

Avant de se lancer dans les exercice, et parce que nous pensons que ce sera utile pour la suite, écrivez la méthode suivante qui renvoie tous les sous-ensembles de [0..n−1]. Chaque sous ensemble est représenté par un BitSet tel que si l’entier i appartient au sous-ensemble, alors le bita d’indice i est set. Il est possible de la faire récursivement, mais il y a plus efficace. Pour vous aiguiller, on vous demande de commencer par écrire une méthode of qui transforme un entier en un BitSet qui correspond à sa représentation binaire. Et d’ailleurs, avant d’écrire la méthode, pouvez-vous dire combien de sous-ensemble elle va renvoyer, en fonction de n?

public static BitSet of(int value) 

public static List<BitSet> allSubsets(int n)

Énumérer les sous-ensembles de [0..n−1] revient à énumérer les mots binaires de longueur n… donc les entiers de 0 à 2ⁿ − 1

1.1.2 Ré-initialisation des machines

Juste de l’autre côté du couloir, se trouve une grande usine. Malheureusement, toutes les machines de l’usine sont hors service, et les ouvriers ne connaissent pas la procédure d’initialisation. Vous allez les aider.

Il existe un manuel des machines, mais la section qui détaillait la procédure d’initialisation a été arrachée. Tout ce qu’il reste du manuel, ce sont quelques schémas de voyants lumineux et des schémas de câblage des boutons (votre entrée).

Le manuel décrit une machine par ligne. Chaque ligne contient un unique schéma de voyants composés de # et de ., suivi d’un ou plusieurs schémas de câblage de boutons. Les différents schémas sont séparés par des espaces.

Pour démarrer une machine, ses voyants doivent correspondre à ceux indiqués dans le schéma, où . signifie éteint et # signifie allumé. La machine possède le nombre de voyants indiqué, mais tous sont initialement éteints. Sur une machine, les voyants sont numérotés de droite à gauche en partant de 0. Par exemple, le schéma de voyants #.###. signifie que la machine possède 6 voyants initialement éteints et que l’objectif est de configurer simultanément les voyant 0 et 4 sur éteint et les voyants 1, 2, 3 et 5 sur allumé.

Il est possible de changer l’état des voyants en appuyant sur n’importe lequel des boutons listés. Chaque bouton indique quels voyants il inverse. Lorsqu’un bouton est pressé, chacun des voyants indiqués change d’état : il s’allume s’il était éteint, et s’éteint s’il était allumé. Par exemple, le schéma de câblage comme 0-3-4 signifie que chaque fois que ce bouton est pressé, les premier, quatrième et cinquième voyants changent tous d’état. Si les voyants étaient dans l’état .....#, appuyer sur ce bouton les ferait passer à l’état .##....

Il est possible d’appuyer sur chaque bouton autant de fois que souhaité. Cependant, pour gagner du temps, il faut déterminer le nombre total minimal de pressions nécessaires pour configurer correctement tous les voyants de toutes les machines de la liste. Si les schémas de câblages ne permettent pas d’allumer tous les voyants, la machine est reste éteinte.

Analyser le schéma de voyants et les schémas de câblage des boutons de chaque machine et écrivez la méthode factory qui renvoie le nombre minimal de pressions nécessaires pour configurer correctement les voyants de toutes les machines.

public static long factory(Path path) throws IOException {

L’entrée est un fichier contenant une machine par ligne, au format indiqué ci-dessus.

Mais le nombre minimal de pressions est 2, en appuyant une fois sur les deux derniers boutons 0-2 et 0-1.

La deuxième machine peut être configurée avec 3 pressions : une fois sur les trois derniers boutons 0-4, 0-1-2 et 1-2-3-4.

La troisième machine possède 6 voyants. Le nombre minimal de pressions est 2 : une fois sur les boutons 0-3-4 et 0-1-2-4-5.

Donc, le nombre minimal de pressions pour configurer correctement les voyants de toutes les machines est 2 + 3 + 2 = 7.

Tous les schémas (voyants et boutons) peuvent être représentés par des BitSet.

1.2 Tout est une question d’équilibre (Advent of Code 2015, jour 24)

Vous effectuer des livraisons à vélo et vous être est en train de charger les 2 sacoches et votre sac à dos. Vous avez la liste des poids de tous les colis que vous devez faire tenir dedans. Les colis doivent être répartis en trois groupes de poids, de telle façon que le poids des 2 sacoches soit le double du poids du sac à dos (sinon, vous ne serez pas stable sur le vélo), et chaque colis doit être utilisé. Le premier groupe va dans le sac à dos, et les deux autres dans les sacoches.

Bien sûr, la stabilité n’est pas le seul problème. Le premier groupe doit tenir dans le sac à dos, donc il doit contenir le moins de colis possibles. Le nombre de colis dans les deux autres groupes n’a pas d’importance, tant que tous les groupes ont le même poids.

De plus, s’il existe plusieurs façons de répartir les colis de sorte que le premier groupe contienne le nombre minimal possible de colis, il faut choisir celle où le premier groupe a le plus petit enchevêtrement quantique afin de réduire le risque d’accidents (allez savoir pourquoi…). L’enchevêtrement quantique d’un groupe de colis est le produit de leurs poids, c’est-à-dire la valeur obtenue en multipliant tous leurs poids entre eux.

Par exemple, supposons qu’il y ait dix colis de poids 1 à 5, puis 7 à 11. Dans ce cas, certains premiers groupes possibles, leur enchevêtrement quantique, ainsi qu’une manière de répartir les colis restants, sont les suivants (ici les groupes 2 et 3 ont le mieme poids, mais ce n’est pas une obligation) :

Parmi ces possibilités, bien que 10 9 1 ait l’enchevêtrement quantique le plus faible (90), la configuration avec seulement deux colis, 11 9, dans le sac à dos est celle qui l’emporte. Dans cette situation, l’enchevêtrement quantique de la configuration idéale est donc 99.

Écrivez la méthode itHangsInTheBalance qui renvoie l’enchevêtrement quantique du premier groupe de colis dans la configuration idéale.

public static long itHangsInTheBalance(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 6 - Énumérer les solutions

1 Force Brute

1.1 Allumez les lumières (Advent of Code 2025, jour 10)

1.1.1 Pour commencer

1.1.2 Ré-initialisation des machines

1.2 Tout est une question d’équilibre (Advent of Code 2015, jour 24)

2 Same same but different (optionnel)

2.1 Avec des `Stream`

1 Force Brute

1.1 Allumez les lumières (Advent of Code 2025, jour 10)

1.1.1 Pour commencer

1.1.2 Ré-initialisation des machines

1.2 Tout est une question d’équilibre (Advent of Code 2015, jour 24)

2 Same same but different (optionnel)

2.1 Avec des Stream

2.1 Avec des `Stream`