Posté par Guillaume.B .
En réponse au journal Advent of code 2024.
Évalué à 3.
Dernière modification le 09 décembre 2024 à 14:12.
Le neuvième jour n'était pas si simple mais c'est surtout que j'ai cherché à obtenir un algo linéaire pour les deux parties.
Pour la partie 1, j'ai obtenu un algorithme linéaire sans devoir allouer plus de mémoire que l'entrée.
L'idée est de maintenir un indice sur le bloc de fichier qu'on est en train de déplacer et un indice sur l'endroit où on est en train de le déplacer.
On va progressivement décrémenter le premier indice et incrémenter le second jusqu'à ce que le premier soit plus petit que le second.
Pour la partie 2, on va faire un peu la même chose. On va utiliser un indice sur le fichier qu'on est en train de déplacer et 10 indices, le i-ème indice pointant vers le prochain endroit où il y a au moins i blocs disponibles.
De même que pour la partie 1, on va progressivement décrémenter le premier indice et incrémenter les 10 indices ainsi que mettre à jour le nombre de blocs disponibles qu'on a fait un déplacement.
Contrairement à la partie 1, on a besoin de de mémoire supplémentaire pour indiquer à quel point une séquence de blocs vides a été remplie.
50 microsecondes pour la partie 1 and 380 microsecondes for la partie 2.
# 9ème jour
Posté par Guillaume.B . En réponse au journal Advent of code 2024. Évalué à 3. Dernière modification le 09 décembre 2024 à 14:12.
Le neuvième jour n'était pas si simple mais c'est surtout que j'ai cherché à obtenir un algo linéaire pour les deux parties.
Pour la partie 1, j'ai obtenu un algorithme linéaire sans devoir allouer plus de mémoire que l'entrée.
L'idée est de maintenir un indice sur le bloc de fichier qu'on est en train de déplacer et un indice sur l'endroit où on est en train de le déplacer.
On va progressivement décrémenter le premier indice et incrémenter le second jusqu'à ce que le premier soit plus petit que le second.
Pour la partie 2, on va faire un peu la même chose. On va utiliser un indice sur le fichier qu'on est en train de déplacer et 10 indices, le i-ème indice pointant vers le prochain endroit où il y a au moins i blocs disponibles.
De même que pour la partie 1, on va progressivement décrémenter le premier indice et incrémenter les 10 indices ainsi que mettre à jour le nombre de blocs disponibles qu'on a fait un déplacement.
Contrairement à la partie 1, on a besoin de de mémoire supplémentaire pour indiquer à quel point une séquence de blocs vides a été remplie.
50 microsecondes pour la partie 1 and 380 microsecondes for la partie 2.