--- Jour 10: Labyrinthe de tuyaux ---
Vous utilisez le deltaplane pour monter sur l'air chaud de l'île du Désert jusqu'à l'île flottante en métal. Cette île est étonnamment froide et il n'y a certainement pas de thermiques sur lesquels planer, donc vous laissez votre deltaplane derrière vous.
Vous vous promenez pendant un moment, mais vous ne trouvez ni personnes ni animaux. Cependant, vous trouvez parfois des panneaux indiquant "Sources chaudes" pointant dans une direction apparemment cohérente ; peut-être pourrez-vous trouver quelqu'un aux sources chaudes et leur demander où sont fabriquées les pièces de la machine du désert.
Le paysage ici est étranger ; même les fleurs et les arbres sont en métal. Alors que vous vous arrêtez pour admirer de l'herbe en métal, vous remarquez quelque chose de métallique qui se précipite hors de votre champ de vision périphérique et saute dans un grand tuyau ! Ça ne ressemblait à aucun animal que vous ayez jamais vu ; si vous voulez mieux le voir, vous devrez le devancer.
En scannant la zone, vous découvrez que le champ entier sur lequel vous vous tenez est densément rempli de tuyaux ; c'était difficile à dire au début car ils ont la même couleur argentée métallique que le "sol". Vous faites un rapide croquis de tous les tuyaux de surface que vous pouvez voir (votre entrée de puzzle).
Les tuyaux sont disposés dans une grille bidimensionnelle de tuiles :
- | est un tuyau vertical reliant le nord et le sud.
- - est un tuyau horizontal reliant l'est et l'ouest.
- L est un coude à 90 degrés reliant le nord et l'est.
- J est un coude à 90 degrés reliant le nord et l'ouest.
- 7 est un coude à 90 degrés reliant le sud et l'ouest.
- F est un coude à 90 degrés reliant le sud et l'est.
- . est le sol ; il n'y a pas de tuyau sur cette tuile.
- S est la position de départ de l'animal ; il y a un tuyau sur cette tuile, mais votre croquis ne montre pas la forme du tuyau.
En fonction de l'acoustique du bruit de l'animal qui se précipite, vous êtes sûr que le tuyau qui contient l'animal est une grande boucle continue.
Par exemple, voici une boucle carrée de tuyaux :
.....
.F-7.
.|.|.
.L-J.
.....
Si l'animal était entré dans cette boucle dans le coin nord-ouest, le croquis ressemblerait plutôt à ceci :
.....
.S-7.
.|.|.
.L-J.
.....
Dans le diagramme ci-dessus, la tuile S est toujours un coude F à 90 degrés : vous pouvez le dire à cause de la façon dont les tuyaux adjacents s'y connectent.
Malheureusement, il y a aussi de nombreux tuyaux qui ne sont pas connectés à la boucle ! Ce croquis montre la même boucle que ci-dessus :
-L|F7
7S-7|
L|7||
-L-J|
L|-JF
Dans le diagramme ci-dessus, vous pouvez toujours déterminer quels tuyaux forment la boucle principale : ce sont ceux qui sont connectés à S, les tuyaux auxquels ces tuyaux se connectent, les tuyaux auxquels ces tuyaux se connectent, et ainsi de suite. Chaque tuyau de la boucle principale se connecte à ses deux voisins (y compris S, qui aura exactement deux tuyaux se connectant à lui, et qui est supposé se reconnecter à ces deux tuyaux).
Voici un croquis qui contient une boucle principale légèrement plus complexe :
..F7.
.FJ|.
SJ.L7
|F--J
LJ...
Voici le même croquis d'exemple avec les tuiles de tuyaux supplémentaires, qui ne font pas partie de la boucle principale, également affichées :
7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ
Si vous voulez devancer l'animal, vous devriez trouver la tuile de la boucle qui est la plus éloignée de la position de départ. Comme l'animal est dans le tuyau, il n'est pas logique de mesurer cela par distance directe. Au lieu de cela, vous devez trouver la tuile qui prendrait le plus grand nombre d'étapes le long de la boucle pour atteindre à partir du point de départ - peu importe dans quel sens l'animal a parcouru la boucle.
Dans le premier exemple avec la boucle carrée :
.....
.S-7.
.|.|.
.L-J.
.....
Vous pouvez compter la distance de chaque tuile de la boucle par rapport au point de départ de cette manière :
.....
.012.
.1.3.
.234.
.....
Dans cet exemple, le point le plus éloigné du départ est à 4 étapes de distance.
Voici la boucle plus complexe à nouveau :
..F7.
.FJ|.
SJ.L7
|F--J
LJ...
Voici les distances pour chaque tuile de cette boucle :
..45.
.236.
01.78
14567
23...
Trouvez la seule grande boucle commençant à S. Combien d'étapes le long de la boucle faut-il pour aller de la position de départ au point le plus éloigné de la position de départ ?
# j'ai adoré
Posté par steph1978 . Évalué à 2.
Le labyrinthe de tuyaux change des labyrinthe classique.
Cela m'a pris un peu (trop) de temps d'encoder les déplacements. Mais au final, ça se fait.
Par contre la partie 2, je ne vois pas du tout comment procéder.
[^] # Re: j'ai adoré
Posté par Pierre . Évalué à 1.
Pour la partie 2, cela m'a rappelé un problème que j'avais résolu sur CodingGame par remplissage de zones, mais ce n’était pas très efficace, le plus simple est de considérer uniquement les traversées de tuyaux :
À chaque ligne on commence à l'extérieur de la boucle
Si on traverse un tuyau | de la boucle on entre à l’intérieur de la boucle jusqu’à la prochaine traversée.
le point un peu délicat est de considérer les autres type de traversée de tuyaux
[^] # Re: j'ai adoré
Posté par steph1978 . Évalué à 2. Dernière modification le 10 décembre 2023 à 15:17.
Avec un lib de gestion des polygone, j'ai fini par trouver pour la partie 2.
Mais un peu l'impression de tricher et de sortir le bazooka.
Le code pour la partie 1:
Sinon, c'est joli
# Un grand classique, mais toujour aussi long à résoudre
Posté par alberic89 🐧 . Évalué à 2. Dernière modification le 10 décembre 2023 à 14:41.
Quand j'ai vu que l'énoncé nous demandait de définir une boucle fermée, j'ai tout de suite senti qu'on allait devoir en calculer l'aire dans la partie suivante.
Je ne me suis pas trompé.
Dans la partie une, une récursion sur toute la boucle suffit (en augmentant la limite de récursion).
Ma logique pour la partie deux est que certains motifs nous font entrer ou sortir de la boucle, il suffit de les repérer en parcourant toute la carte.
Et beaucoup de gestion d'erreur pour repérer les erreurs de logique quand on code ou pour ne pas avoir à tester les longueurs des chaînes.
Voici mon code :
L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès
[^] # Re: Un grand classique, mais toujour aussi long à résoudre
Posté par Pierre . Évalué à 1.
J'avais aussi commencé par une fonction récursive, mais elle ne dépassait la limite de recursion, je l'ai remplacé par une simple boucle while.
# Une solution assez élégante, je trouve.
Posté par Yth (Mastodon) . Évalué à 2.
Attention, spoiler pour ceux qui luttent sur la partie 2 !
Partie 1
Pour la première c'est pas très difficile, on parcours le bidule.
J'ai très mal dormi, je me suis pris la tête à partir dans les deux directions à la fois et à trouver le moment de la rencontre, alors qu'il suffit de parcourir une seule boucle et de diviser la longueur par deux, voici un algorithme assez efficace, même si probablement trop modélisé.
Au passage, j'ai aplati la carte pour qu'elle soit en 1 dimension, c'est plus facile, mais pas autant pour la partie 2 :
Pour la suite, j'ai dû voir les choses et donc représenter mon bidule plus visuellement, on remplace
|-LJ7Fpar│─└┘┐┌. J'ai totalement triché en remplaçantSpar son symbole, après avoir observé les données, mais c'est pas si difficile de déterminer ça, et le rendu sur les données de test.Partie 2, et maintenant pour le spoiler !
J'ai doublé la carte et reconstruit les tuyaux manquants. Ensuite il suffit d'explorer la zone vide à l'extérieur, on peut se faufiler partout vu qu'on a créé de l'espace entre les tuyaux.
On transforme une case en quatre cases, on garde celle d'origine, et on étend logiquement à droite et en dessous, la 4è en bas à droite étant forcément vide.
Les cartes d'exemple doublées donnent ça :
On « recompresse » ensuite en prenant les cases dont les coordonnées sont paires : (0, 0), (0, 2), (2, 2) etc.
Le reste c'est un décompte et hop, fini.
Le code est plutôt moche, je le posterai plus tard quand je l'aurai rendu plus lisible.
[^] # Re: Une solution assez élégante, je trouve.
Posté par steph1978 . Évalué à 2. Dernière modification le 10 décembre 2023 à 15:40.
Chapeau pour l'astuce du doublement
[^] # Re: Une solution assez élégante, je trouve.
Posté par Yth (Mastodon) . Évalué à 2.
Vous verrez ici le rendu exploratoire de ma carte doublée, on voit très bien les zones :
https://ythogtha.org/advent_of_code/aoc-2023-10.html
# Première partie
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 3.
C'est pour moi l'occasion d'utiliser
enum.Flagqui correspond très bien à des trucs qui peuvent avoir une superposition d'états, ici des tuyaux connectés dans différentes directions.Et la carte maintenant :
La solution est donnée par la méthode
Map.farthest(). C'est un parcours itératif de proche en proche :[^] # Re: Première partie
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à 3.
Et pour la deuxième partie, résolue grâce à l'idée de Pierre :
Première étape, simplifier la carte en virant tous les tuyaux inutiles. Comme pour la première partie, c'est basé sur un parcours de proche en proche pour identifier les tuyaux connectés au point de départ. Ensuite, on parcours tout, puis on met à zéro les tuiles qui contenaient des tuyaux non connectés.
En fait, on parcours chaque ligne en gardant en mémoire si on est à l'intérieur de la boucle de tuyaux ou non. Seulement, à l'intérieur ou à l'extérieur, c'est ambigu lorsqu'on est justement sur un tuyau qui fait partie du réseau. Donc, pour être plus précis, on s'intéresse au fait que la zone en haut à gauche de chaque tuile est à l'intérieur ou non. Et vous pouvez faire tous les schémas que vous voulez, la seule chose qui fait changer l'état intérieur/extérieur de la zone en haut à gauche de la tuile suivante, c'est la présente d'un tuyau connecté au nord.
Quant à l'aire, les tuiles qui y contribuent sont celles qui sont à l'intérieur et qui sont vides (après élimination de tuyaux inutiles). Voilà !
[^] # Re: Première partie
Posté par Yth (Mastodon) . Évalué à 2.
T'aime bien faire plus générique que l'énoncé, parce qu'on sait sans regarder les données que les tuyaux sont à deux entrées, jamais de bifurcations, alors joli travail hyper générique, et proprement modélisé :)
J'aime bien les enum.Flags, ça peut être vraiment utile.
J'ai conçu une super machine à états avec un enum.Flags dans mon projet professionnel actuel, c'est tout propre et tout le monde comprend le code !
Et je constate aussi que je suis finalement le seul bourrin à avoir zoomé sur la carte pour la voir plus en détail, c'est bien propre comme résolution de la partie 2. Et plus rapide que ma solution aussi, mais que je n'ai pas optimisée du tout (du tout (elle prend toute une longue seconde à s'exécuter !!)).
# Solution en Haskell
Posté par Guillaume.B . Évalué à 1. Dernière modification le 11 décembre 2023 à 17:29.
Voici ma solution en Haskell.
La partie 1 utilise un BFS mais c'est un peu overkill.
La partie 2 repose sur des idées similaires à ce qu'a proposé Pierre.
Une partie non négligeable du code (la fonction getNiceInput) chercher à determiner quelle est la tuile adéquate pour remplacer la tuile Start.
# Ma solution
Posté par syj . Évalué à 1.
Pour la deuxième partie, j'ai opté pour une solution où je remplace les tuiles de base par des tuiles de 3x3
Je remplie ensuite en faisant les cellules en bordure de la map.
Note: Ce code doit être utilisée --Xms2G pour avoir une stack plus grande que celle par défaut.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.