Ce jour ci, il faut trouver son chemin dans un labyrinthe.
Le labyrinthe est composé de plusieurs types de tuile:
des chemins ".", des forêts "#" et des pentes dans une direction "", ">", "v", "<".
Dans la partie 1, on n'a pas le droit d'aller dans le forêt et on n'a pas le droit de remonter une pente.
Le but n'est pas ici de trouver un plus court chemin mais un plus long chemin dans le labyrinthe. Évidemment, on n'a pas le droit de repasser plusieurs fois par la même tuile (sinon on ferait des cycles infinis).
Exemple de labyrinthe:
#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#
La partie 2 est la même chose que la partie 1 sauf que l'on est autorisé à remonter les pentes.
Et mine de rien, ça complique pas mal le problème car l'espace d'exploration explose.
# Solution en Haskell
Posté par Guillaume.B . Évalué à 4.
100 ms pour la partie 1, 4s pour la partie 2.
J'ai trouvé le problème assez simple aujourd'hui. En tout cas plus simple que les jours précédents. Dommage que je me sois levé tard.
Tout d'abord, remarquons que le problème qu'on essaie de résoudre (Longest Path) est NP-difficile. Ce qui ne veut pas dire qu'on ne va réussir car il n'y a pas tellement de choix et donc de backtrack à faire.
La première partie est du backtracking classique. Dans la deuxième partie, l'espace d'exploration augmente considérablement. Mais on se rend qu'il y a de longs couloirs, c'est à dire une suite de sommets de degré 2.
On va dans compresser la grille de cette manière:
on dit qu'une tuile est intéressante si c'est la tuile de départ, d'arrivée ou si c'est une jonction, c'est à dire un sommet de degré au moins 3.
Et pour chaque tuile intéressante, on va chercher dans chaque direction la prochaine tuile intéssante ainsi que la distance qui les sépare.
On va appliquer notre algo de backtracking sur cette instance.
Voici le code:
comme d'habitude, on va essayer d'être le plus générique possible et on va définir une fonction
longestPath
qui prend en entrée un sommet de départ, un sommet d'arrivée et une fonction de voisinages. Elle s'applique donc à n'importe quelle strucutre et pas seulement aux grilles. On va la mettre dans ma librairie de fonctions de recherche dans un graphe.Ensuite, vient le code du problème à proprement parler.
Tout d'abord les types utilisés et le parsing. Rien de bien compliqué.
Ensuite, on définit une fonction de voisnage pour la partie 1.
Pour la partie 2, on définit une fonction de voisinage qui ne prend pas en compte les pentes.
et on définit la fonction de compression de grille.
# Brut force pour la partie 2
Posté par syj . Évalué à 1.
Pour la partie 1 , j'ai appliqué un bête parcours en profondeur.
Pour la partie 2, j'ai laissé tourner ma solution de partie 1 pour trouver la max de la partie 2.
Environ 1h de calcul.
J'aurai bien essayé de faire un truc plus intelligent mais je n'avais pas le temps.
Il faut quand même lancer ce code -Xss1g pour avoir une stack conséquence qui permet une récursivité aussi profonde.
# Les ennuis commencent...
Posté par Yth (Mastodon) . Évalué à 2.
Pour moi, les ennuis ont commencés : pas d'ordinateur, pas de clavier, juste mon petit téléphone qui ne permet pas vraiment de voir les données avec du recul, et l'extrême pénibilité de coder avec un clavier tactile, toujours à basculer pour chercher les chiffres, les opérations, les =, :, les (), [] et {}.
Bref, pénible, donc on code avec des variables à une ou deux lettres, on fait les algos les plus courts à écrire, et on tâtonne.
La première partie reste assez simple, je n'ai pas mis bien longtemps et le temps de calcul sur téléphone est assez ridicule.
Pour la seconde j'ai tenté de laisser tourner des heures avec l'algo brute-force bête et méchant, mais à part flinguer la batterie on n'arrive pas à grand chose, soyons honnêtes.
Donc être malins.
Et là je l'ai pas été, j'ai tout de suite tenté de réduire le problème aux nœuds d'exploration : les cases où il y a 3 ou 4 directions possibles, et je note les distances entre ces nœuds, puis j'explore le graphe réduit des nœuds.
Sauf que j'ai cru ce problème trop complexe pour mon téléphone, et cherché à simplifier : trouver des nœuds qui sont des passages obligés.
J'étais encouragé par le fait qu'il y en a dans les données de test.
Ça veut dire qu'on peut découper le graphe simplifié en plusieurs graphes qui s'enchaînent.
Donc je code, je débugge, ça marche, je lance sur les données réelles, il me laisse avec comme seul noeud intermédiaire le noeud d'arrivée, et tout ça n'a servi à rien.
Sauf que la réponse tombe malgré tout sans trop d'attente, le problème réduit est suffisamment simple pour que la force brute s'en empare.
Ça met ~10s sur mon PC (avec pypy bien sûr, pour le coup), pas loin de 2 minutes sur le téléphone.
Je n'ai pas cherché plus loin, et j'ai juste remis le code au propre, en virant l'exploration inutile des nœuds intermédiaires, avant de le poster.
La première passe, sur la carte complète, permet aussi de lister les nœuds et la distance les séparant. Techniquement, il pourrait en manquer, puisque l'exploration se fait avec les contraintes de glissement, ça n'est pas le cas, j'ai misé sur cette simplification parce que la denrée qui me manquait vraiment c'était du temps pour coder correctement les choses.
Je me rappelle cependant avoir tenté plein de trucs et finalement avoir été déçu de la simplicité du bidule qui fournit finalement la solution, bref.
Au passage, j'utilise une pile de chemins en cours d'exploration, un deque() bien utile pour ça, plutôt qu'une fonction récursive, on fait exploser la limite de récursivité bien trop vite sur le téléphone. Donc j'ai une boucle et une FIFO d'états à faire avancer, c'est pas trop violent sur la RAM, et on n'atteint pas les limites.
Donc je commence, et j'ai pas fini, les codes dont je n'ai aucune réelle certitude de l'exactitude en toutes circonstances, ça sera pire dans les jours qui viennent.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.