Posté par Guillaume.B .
En réponse au journal Advent of code 2024.
Évalué à 3.
Dernière modification le 21 décembre 2024 à 19:29.
Le jour le plus compliqué pour moi jusqu'à présent. J'ai mis beaucoup de temps à comprendre l'énoncé.
L'idée pour résoudre le problème est de remarquer que la complexité (la valeur qu'on cherche) ne dépend que des paires consécutives de lettres dans une séquence.
L'ordre de ces paires n'importe où.
Donc au lieu de représenter la séquence par une chaîne à caractères, on va le représenter par un tableau qui a une paire donnée associe son nombre d’occurrences dans la séquence.
Cela fait un tableau de 11x11 pour les séquences du clavier numérique et 5x5 pour les séquences du clavier analogique.
Ensuite il faut écrire deux fonctions numpad_step et dirpad_step qui a une paire de touches (x, y) donnée respectivement par le clavier numérique et le clavier de direction, associe la séquence de lettres pour passer de x à y à la profondeur +1.
Étant donné un tableau d'occurrences pour la profondeur p, on peut trouver le tableau d’occurrences pour la profondeur suivante de la manière suivante.
Soit current le tableau d'occurrences pour la profondeur p
créer un tableau next de 25 éléments initialisés à 0
pour x dans ['<', '>', 'v', '>', A']
pour y dans ['<', '>', 'v', '>', A']
pour chaque paire consécutive (x2, y2) de dirpad_step(x, y):
next[(x2, y2)] += current[(x, y)]
renvoyer next
En optimisant un peu, je suis arrivé à 6 microsecondes de temps d'exécution.
J'ai essayé d'aller plus loin en remarquant qu'on pouvait précalculer à la compilation un tableau qui à chaque paire du clavier numérique associe la longueur pour obtenir cette paire à profondeur 2 et à profondeur 25.
Avec cette approche, je suis arrivé à 70 nanosecondes de temps d'exécution, sans utiliser de code unsafe et en restant générique sur l'input (je ne suppose par exemple pas que chaque ligne fait exactement 4 caractères).
# 21ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 3. Dernière modification le 21 décembre 2024 à 19:29.
Le jour le plus compliqué pour moi jusqu'à présent. J'ai mis beaucoup de temps à comprendre l'énoncé.
L'idée pour résoudre le problème est de remarquer que la complexité (la valeur qu'on cherche) ne dépend que des paires consécutives de lettres dans une séquence.
L'ordre de ces paires n'importe où.
Donc au lieu de représenter la séquence par une chaîne à caractères, on va le représenter par un tableau qui a une paire donnée associe son nombre d’occurrences dans la séquence.
Cela fait un tableau de 11x11 pour les séquences du clavier numérique et 5x5 pour les séquences du clavier analogique.
Ensuite il faut écrire deux fonctions
numpad_stepetdirpad_stepqui a une paire de touches(x, y)donnée respectivement par le clavier numérique et le clavier de direction, associe la séquence de lettres pour passer de x à y à la profondeur +1.Étant donné un tableau d'occurrences pour la profondeur p, on peut trouver le tableau d’occurrences pour la profondeur suivante de la manière suivante.
En optimisant un peu, je suis arrivé à 6 microsecondes de temps d'exécution.
J'ai essayé d'aller plus loin en remarquant qu'on pouvait précalculer à la compilation un tableau qui à chaque paire du clavier numérique associe la longueur pour obtenir cette paire à profondeur 2 et à profondeur 25.
Avec cette approche, je suis arrivé à 70 nanosecondes de temps d'exécution, sans utiliser de code unsafe et en restant générique sur l'input (je ne suppose par exemple pas que chaque ligne fait exactement 4 caractères).