Calendrier de l'avent 🎄 (mais sans chocolats)

[Grenat2]

Une journée de repos aura fait le plus grand bien à mes neurones. Non seulement j’ai réussi à comprendre la partie 2 de ce jour, mais j’ai repris de zéro le jour 12, j’ai fait simple et ça passe en moins d’ une seconde

[deneb]

Une journée 16 également sans difficulté particulière. C’est surprenant, en général les problèmes du week-end lors des deux dernières semaines sont plutôt corsés.
Bon ben week-end à tous alors

[arzhuras]

Oui, pas de piège sur ce jour 16. Va-t-on prendre cher demain ?

[Xerto]

Pas eu de soucis si ce n’est une erreur entre un + et un - qui m’a retardé. C’est bien du brute force qu’il faut faire pour la partie 2 (ça me prend 11s ) ?

[deneb]

Le brute force marche très bien oui. Juste une grosse seconde pour moi pour la partie 2 à essayer chaque entrée, sans ajouter d’optimisation particulière par rapport à la partie 1.
J’ai aussi tendance à n’utiliser que des structures « lourdes » (genre je préfère une Map<Pair<Int, Int>, Char> plutôt qu’un tableau 2D de Char, faut pas chercher), mais comme je fais ça en Kotlin c’est beaucoup moins punitif que le Python niveau perf.

[arzhuras]

Moi aussi, parcours systématique de toutes les entrées, pas d’optimisation sur un cache des chemins.
Et utilisation d’un bon vieux dict. 2.6s en python sur proc de 5 ans.
→ part 1 (0.006s): 7632
→ part 2 (2.591s): 8023
Day 16

edit
→ part 2 (1.548s): 8023 : j’avais laissé des deepcopy qui ne servent a rien. 1s de gagné!

[Xerto]

Pour le coup je stock un set de (int, int, str) (i,j, direction) les parties visitées. Je vais voir si je peux faire mieux si j’ai le temps.

Edit: en changeant une queue.Queue pour une collection.deque ça va 10x plus vite j’ai l’impression. Je ne vais pas chercher plus

[Grenat2]

Oui Jour 16 ça se brute force bien, idem entre 1 et 2 secondes sur mon vénérable pc portabe de 2015.

Jour 17 pas de problème particulier. J’avais peur au début la partie 1 ramait beaucoup, mais je testais plusieurs fois les mêmes possibilité.
Pour la partie 2 ça tourne en 2-3 sec, et pas besoin de retoucher à beaucoup de code pour y arriver. Bref pas de piège aujourd’hui

[Xerto]

Hmm moi je bloque sur 1 : je tente un Dijkstra, en ajoutant une condition sur les voisins non visités. Quand j’arrive sur une position, je regarde les 3 prédécesseurs. S’ils sont tous sur la même colonne ou ligne, alors je suis obligé de tourner. Sur l’exemple, j’obtiens 127 comme résultat, donc pas bon.

[deneb]

Je bloque aussi sur la partie 1.

J’ai essayé un algo maison au début, mais sans grande surprise ça part vite en sucette.

Ce qui me gêne c’est que sur l’example le chemin ne se recoupe jamais, alors que je pense qu’en théorie il devrait être possible d’avoir un trajet optimal qui passe plusieurs fois sur une même case - et je n’ose pas partir sur un Dijsktra « standard » (ou modifié comme le tient) qui ne prendrait a priori pas en compte cette possibilité.

[deneb]

@Xerto

j’obtiens 127 comme résultat, donc pas bon

Je pense que ça vient du fait que si tu gardes les 3 derniers trajets d’un node « optimal », tu vas te couper des routes alors qu’une arrivée sur le même node avec un moins bon score (déjà éliminé chez toi) permettrait de continuer tout droit par un chemin meilleur au final.
Peut-être qu’il faudrait exploser chaque node du graphe en sous-node différente selon la direction d’arrivée et le nombre de pas dans cette direction précédents.

.

[Grenat2]

Oui j’ai fait ça. Je garde un état qui est la position, la direction en cours et le nombre de fois successives que je suis cette direction. Et ça aide pour la partie 2.

Et oui, il ne faut pas se couper d’une arrivée sur un noeud en gardant uniquement l’arrivée optimale.
Un pattern fréquent est qu’on veut aller tout droit, mais la limite de 3 impose de faire un pas de côté, d’avancer d’un cran et de revenir sur la trajectoire initiale.

Et pas de boucle constaté dans mon cas. D’ailleurs je ne vois pas comment ça pourrait se produire. Sur la partie 2 à la rigueur, mais le coût de faire la boucle sera trop grand je pense par rapport à une autre solution.

[Xerto]

Je vois la limite de mon approche, sur un exemple simple

11111
21191

ça ne marche pas…

Formalisme

En réfléchissant, est-ce que les noeuds devraient donc être (i, j, dir, k), tous initialisés avec une distance max (avec dir entre 0 et 3) ? Et ensuite, pour chaque noeud, je trouve celui de distance min pas encore visité, et je mets à jour les voisins potentiels ? J’ai pas l’impression que ça va marcher

Edit: je m’en suis sorti : il faut changer un peu l’algo de Dijkstra pour en remettre dans la boucle si nécessaire. Une fois que j’ai compris ça, le reste déroule simplement. Et la partie 2 se fait bien si on stock la direction et le nombre de pas déjà fait.

[deneb]

@Xerto

En réfléchissant, est-ce que les noeuds devraient donc être (i, j, dir, k), tous initialisés avec une distance max (avec dir entre 0 et 3) ?

Oui, mais chez moi chaque noeud doit être dupliqué avec la distance k entre 1 et 3 (pas 0 et 3) vu que c’est le nombre de cases parcourues dans cette distance sans tourner, et ce pour chacunes de 4 directions. Du coup quand tu vas insérer un nouveau noeud, il aura toujours déjà parcouru une case dans cette direction. Ça donne donc 12 noeuds pour chaque case dans le graphe éclaté sur lequel on fait ensuite tourner Dijkstra.

Et pas de souci concernant ma réserve sur le fait que Dijkstra ne couvre pas les chemins se coupant: Ça marche tout à fait, car un chemin optimal se recoupera forcément selon des directions perpendiculaires - et comme les directions sont différentes, ce sont donc 2 noeuds différents dans le graphe « éclaté », donc pas de souci, aucun noeud du graphe éclaté ne doit être parcouru 2 fois par le chemin optimal.

Sinon pour la partie 2 j’ai galéré un peu en oubliant le fait que le wagon ne peut pas s’arrêter sur la case finale sans avoir parcouru au moins 4 cases dans la même direction. Heureusment que le deuxième exemple m’a aidé à identifier le problème !

[deneb]

@Grenat2

Et pas de boucle constatée dans mon cas. D’ailleurs je ne vois pas comment ça pourrait se produire.

En effet je n’ai pas trouvé de cas avec une boucle pour ces règles du problème. J’ai été un peu trop précautionneux car je m’attendais à une partie 2 du genre « maintenant les wagons doivent toujours tourner du même côté », ce qui aurait rendu possible les cycles sur le chemin optimal.

[Xerto]

Et donc le code que j’ai oublié de poster. Pour ceux que ça intéresse, j’ai mis pas mal de commentaires si vous bloquez et que vous cherchez à comprendre.

[Xerto]

17.1 faite en s’inspirant du jour 10 pour intérieur/extérieur, par contre j’ai peur que le brute force ne fonctionne pas pour la partie 2. Il va falloir réfléchir…

[deneb]

Je me prend grave la tête sur la partie 2 du jour 18. Je suis sûr qu’il doit y avoir un moyen plus simple que ce que je tente, quitte à faire un peu de brute force, mais j’hésite à tout reprendre de zéro… Dans tous les cas c’est très intéressant comme problème !

[Xerto]

J’ai une idée que je n’arrive pas à mettre en oeuvre:

Idée

On récupère les segments horizontaux et verticaux séparément. On récupère aussi tous les corners, on met les x dans abs, et les y dans ord. Ensuite, on teste chaque rectangle possible avec les x dans abs et ord. Pour chaque rectangle, on calcule son centre, et on regarde combien de segments horizontaux il intersecte en haut, si impair on regarde combien de verticaux à gauche, si impair on ajoute l’air du rectangle. Mais je dois me planter dans des indices

[deneb]

C’est vraiment la galère avec les indices. J’ai choisi une approche encore moins simple:

Idée

• Je stocke tous les coins (points) dans une liste.
• Je cherche le point le plus en haut puis le plus à gauche de la forme
• J’écrase cette excroissance jusquà arriver au prochain coins, je calcule l’aire du rectangle ainsi écrasé. Faut faire gaffe à bien tout calculer quand ça fait une ligne qui sort de la forme en bas de l’écrasement.
• Rebelotte jusqu’à arriver à un rectangle.
• C’est plus corsé si il y a une boucle à l’intérieur du rectangle que j’écrase - dans ce cas, après avoir ajouté l’aire du rectangle écrasé, ça va me faire deux circuits fermés de part et d’autre de la boucle, et j’utilise le même algo pour calculer l’aire de chacun

Là j’en suis au cas où je tombe sur une boucle en écrasant le rectangle, je m’embrouille de partout mais j’avance petit à petit !