Je vais essayer de faire la preuve mathématiques que si quand on part de xxA pour aller à xxZ, on fait o_a + C steps, et si on part de yyA pour aller à yyZ, on fait o_b + C steps (avec C le nombe de steps pour boucler entre le Z), alors pour arriver en même temps sur un Z, c’est ppcm(o_a + C, o_b + C).
Edit: j’ai compris pourquoi ça marche. Les cycles A->Z ont chacun une longueur similaire au cycle Z->Z. Donc il faut faire assez de cycles pour que ça matche (du style a + b + c = c + b + a). J’ai pas vérifié, mais j’imagine que ça fait un cercle et c’est pour ça que ça marche. Mais c’est donc que l’input est bien calibré…
Edit bis :
Explication plus détaillée
starts = ['JQA', 'NHA', 'AAA', 'FSA', 'LLA', 'MNA'] steps = [13939, 11309, 20777, 15517, 17621, 18673]
Il faut un certain nombre de steps pour arriver à une fin en Z.
Ensuite les fins Z cyclent sur elles-même, sans passer par un autre Z:
Cycle SCZ → SCZ in 13939 steps
Cycle DDZ → DDZ in 11309 steps
Cycle ZZZ → ZZZ in 20777 steps
Cycle PTZ → PTZ in 15517 steps
Cycle NQZ → NQZ in 17621 steps
Cycle GVZ → GVZ in 18673 steps
(dans l’ordre des positions starts)
On constate que les longueurs des cycles A->Z et Z->Z sont les mêmes, et sont appareillées. Donc on cherche effectivement le PPCM de [13939, 11309, 20777, 15517, 17621, 18673], Clairement le type qui a eu les 2 étoiles en moins de 5 minutes a dû intuiter le bazar sans trop vérifier
Alors c’est effectivement pas dit dans le texte comment est construit l’input, mais intuitivement j’ai de suite été vérifier que:
la sortie rebouclait sur l’entrée, et que le nombre d’étape était bien un multiple entier de la longueur des RL. Ca se fait directement en fait en appliquant la partie 1
Hop, jours 8 fini. Effectivement la premiere partie se fait en quelques minutes.
Pour la seconde partie :
J’ai, bien évidemment, commencé par programmer l’exécution des boucles en parallèle avec la condition de fin égale à « quand tout le monde est sur un Z », et j’ai écouté mon PC turbiné
Ensuite, je suis partie sur une solution de détection de boucle et de ppcm, comme tout le monde
Après plusieurs années de aoc, j’aurai pu m’en douter dès le départ, mais c’est toujours marrant de coder l’exercice naivement d’abord
Bon clairement, il faut que l’input soit bien construit.
D’ailleurs les conditions de l’étoile 1 et l’étoile 2 ne sont pas exactement les mêmes. Dans l’étoile 1, on s’arrête sur ‹ ZZZ ›, alors que sur l’étoile 2, on s’arrête sur ‹ …Z ›
Ensuite dans la détection des boucles, pour bien faire, il aurait fallu vérifier que le premier ‹ …Z › atteint reboucle bien sur le début. Je ne l’ai pas fait, j’ai considéré que ça serait le cas, et c’est bien le cas
En tout cas, très sympa. Et pas trop de parsing aussi, c’est agréable.
@arzhuras : pour le ppcm et le pgcd, les deux fonctions sont inclus dans python, pas besoin de libraire : math. gcd() et math.lcm()
Alors effectivement gcd et lcm sont dans la lib math ! Merci pour le tuyau aussi
Tip pour les pythoneux: lcm et gcd ne sont présent qu’a partir du python 3.9, et « match » en 3.10…
J’étais toujours en 3.8 de mon côté. J’avais jamais pris le temps d’upgrader mon python… donc la, je suis passé en 3.12! je suis au top pour la suite
Tip2: pour utiliser math.lcm(nb1, nb2,…nbn) sur plusieurs nombres depuis une liste il suffit d’utiliser l’opérateur « * » pour désérialiser la liste: math.lcm(*myNumberList)
Jour 8 fait.
Comme tout le monde, j’ai essayé de détecter des cycles, et pour détecter le cycle je devais calculer (et afficher) n° étape modulo la taille de la liste des directions LR, et j’ai bien vu que j’avais toujours 0!
Et une petite vérif rapid m’a permis aussi de vérifier que dans chaque boucle on avait un seul Z et du coup le ppcm assurait le résultat
Donc oui, on reste dans le cas idéal, on est encore que le jour 8. En regardant en 2020 jour 13 il y avait un problème similaire mais sans avoir l’input idéale.
Clairement, pas de soucis aujourd’hui. Pour la partie 2 j’ai d’abord fait un calcul « à la main » puis après j’ai trouvé l’astuce. Mais clairement rien de bien sorcier pour un jour 9. Code
Je sais pas pourquoi j’ai séché un moment devant le jour 9 avant de me décider à faire une version simple au moins pour tester. Et finalement c’est passé direct. Comparé à celui hier qui a fait décoller ma machine sur le premier essai.
Jour 9, RAS. Hyper simple, codé en 20min. La deuxième partie en 2 min, vu que ma structure de donnée permettait de faire la gauche avec le meme code en rajoutant une ligne.
Étonnant d’avoir un jour aussi simple un samedi après la difficulté des jours précédents !
J’ai réussi la partie 2 après avoir dû bien cogiter. Mon algo:
Pour commencer, je construis un Set avec tous les points qui forment la boucle.
Également, je remplace le S par le caractère qui va bien pour fermer la boucle - ça permet d’éviter d’avoir à le gérer par la suite.
Ensuite, je lis ligne par ligne et caractère par caractère, en regardant pour chaque caractère qui fait partie de la boucle si je traverse la frontière ou pas. Pour ça, j’ai 3 variables d’état:
Suis-je à l’intérieur ou à l’extérieur de la boucle
Suis-je en train de chevaucher la frontière
Si je suis en train de chevaucher la frontière, suis-je arrivé sur la frontière par le Sud (« F ») ou par le Nord (« L »)
Si le caractère est un « | », je ne peux pas être en train de chevaucher la frontière, j’inverse donc l’état « interieur/exterieur ».
Si le caractère est un F ou un L, je commence à chevaucher la frontière
Si le caractère est un « - », je continue à chevaucher la frontière
Si le caractère est un "J ou un « 7 », alors je finis de chevaucher la frontière, et je change l’état « interieur/extérieur » en fonction de la direction par laquelle je suire rentré de celle par où je sors. En gros, ai-je juste longé un boucle (pas de changement) ou ai-je traversé la frontière (changement)
Et si le caractère lu ne fait pas partie de la boucle, je le compte ou pas en fonction de la variable d’état « interieur/exterieur ».
Au final j’essayais de faire ça, mais je me suis planté à un moment j’imagine. Donc j’essayais de faire des trucs plus dur mais qui ne marchaient pas. Là en reprenant après le repas je m’en suis sorti. Mais clairement c’était pas simple, 4h entre mes deux étoiles et pourtant je gagne 2000 place en l’étoile 1 et 2. Code
Jour 10 done! Bon, c’était pas simple mais super sympa.
une parti1 propre et un grosse astuce pour la part2.
J’ai galéré a essayer de trouver ce qui est à l’intérieur/l’extérieur en franchissant les frontières. il faudra que je regarde au calme ta proposition @deneb!
J’ai donc fait plus basique! Comme les passages en mode squeeze sont galères à gérer, j’ai juste écarté toutes les colonnes et les lignes en ajoutant une colonne et une ligne intercalaire a chaque fois. Sur ces colonnes/lignes intercalaire, j’ai juste rempli avec des ‹ - › et des ‹ | › pour garder la continuité du parcours. Il n’y a plus de cellule/zone isolée d’une autre. plus de squeeze!. Il ne reste plus qu’a faire un parcours de proche en proche pour avoir les extérieur. Ce qui reste, c’est les intérieurs!
Salut, même méthode pour moi pour la partie 2.
J’ai juste fait une petite erreur au départ car j’ai oublié de remplacer S par le caractère qui va bien pour fermer la boucle. et je n’avais pas vérifié mon code sur tous les exemples, juste le dernier.
Pour chaque point qui est situé dans un rectangle défini par la localisation de la boucle principale (histoire de pas checker toute la map) :
On regarde si le point est sur la boucle, si oui, skip
On regarde si le point est au bord de la map, si oui, skip
Sinon :
on récupère l’ensemble des points qui sont à l’Ouest / Est / Nord / Sud du point considéré et sur la boucle.
Pour chacun de ces 4 ensembles, on considère la string créée par les points considérés, puis on applique des regex pour réduire + remplacer les suites de ‹ - › et ‹ | › qui vont bien et compter la longueur de la string finale, qui donne le nombre de passages de frontière.
Si la longueur est impaire, le noeud est dans la boucle et c’est gagné.
Exemple de transformation en considérant des noeuds à gauche/droite du noeud courant: ||F-7L7FJ|| => ||||||
car F-7 n’est pas un passage de frontière, mais L7 et FJ oui
Très content d’en avoir terminé avec celui-ci, la part 2 m’a donné bien du fil à retordre dans l’implémentation.
Pas de soucis aujourd’hui, surtout que j’ai codé ma partie 1 de façon maline et que j’ai quasiment pu la réutiliser pour la partie 2 telle quelle. Le code
