Jérémy PagèsA partir d'aujourd'hui, et jusqu'au 25 juin, je vais résoudre les problèmes de l'Advent of Code 2018 (le seul que je n'aie pas encore fait), à raison d'un par jour.
Partie 1 : 10:46
Partie 2 : 31:22
Pas de difficulté particulière pour ce premier problème.
Ma solution de la partie 1 tient sur une ligne.
Pour la partie 2, il suffisait d'utiliser un Set pour garder en mémoire les fréquences déjà atteintes.
Partie 1 : 20:05
Partie 2 : 44:29
Encore un problème facile (normal, pour un deuxième jour).
Pour la partie 2, j'ai utilisé une petite optimisation : ne pas compter le nombre de différences entre deux chaînes de caractères, mais arrêter le décompte lorsque ce nombre dépasse 1.
Partie 1 : 29:49
Partie 2 : 2:14:22
Pour la partie 1, j'ai simplement compté, pour chaque pixel d'une grille de taille 1000x1000, à combien de pièces il appartenait.
La partie 2 m'a posé beaucoup plus de problèmes. J'ai eu du mal à trouver une formule, finalement très simple, permettant de déterminer si deux rectangles sont disjoints.
Partie 1 : 1:35:44
Partie 2 : 1:44:38
Le parsing et le tri des données ont été pour moi la principale difficulté de ce problème. La partie purement "algorithmique" était relativement simple.
Partie 1 : 34:21
Partie 2 : 53:26
Sur la partie 1, je n'ai pas vu l'algorithme optimal, qui consistait en l'utilisation d'une pile, et permettait de simuler la réaction en une seule fois.
Pour la partie 2, j'ai utilsé une petite optimisation : simuler la réaction, enlever les unités requises, puis terminer la réaction avec le polymère résultant. Cela m'a permis de réduire le temps de calcul de 350 ms à 90 ms.
Partie 1 : 1:54:26
Partie 2 : 2:29:38
La partie 1 demandait de construiire une sorte de diagramme de Voronoi, avec la distance de Manhattan à la place de la norme euclidienne. La principale difficulté était de déterminer quelles aires d'influences étaient infinies.
Pour la partie 2, j'ai calculé la somme des distances de Manhattan sur chaque point d'un rectangle englobant tous les points donnés en entrée.
Partie 1 : 58:53
Partie 2 : 2:20:50
Le problème portait sur un tri topologique dans la première partie, et sur un ordonnancement de processus dans la seconde.
Les deux parties s'exécutent en 2 millisecondes.
Partie 1 : 30:00
Partie 2 : 54:57
C'est le premier problème de l'année 2018 que j'ai résolu avec des méthodes récursives.
Par contre, je n'ai pas utilisé de structure arborescente pour les données. J'ai choisi d'utiliser un Array immutable avec un pointeur qui est incrémenté au fur et à mesure de l'avancement des calculs.
Partie 1 : 58:55
Partie 2 : 1:59:21
Un problème où choisir la bonne structure de données est crucial pour avoir un temps de calcul acceptable.
Ici, il fallait utiliser une liste doublement chaînée. J'ai pu obtenir ainsi un temps de calcul de 1ms pour la partie 1, et de 100 ms pour la partie 2.
Partie 1 : 2:20:29
Partie 2 : 2:27:38
J'ai commencé ce matin avec une heure de retard sur l'horaire prévu.
Pour résoudre ce problème, j'ai construit le plus petit rectangle contenant tous les points, à chaque étape. J'ai ensuite cherché à quel instant la taille de ce rectangle atteint un minimum. Enfin, j'ai bricolé un petit OCR pour lire le résultat.
Pour la partie 2, j'avais déjà trouvé le résultat demandé en travaillant sur la partie 1.
Partie 1 : 27:38
Partie 2 : 5:05:48
Un problème de complexité algorithmique.
La partie 1 s'exécute en O(n^2), et 2 ms pour n = 300, et la partie 2 s'exécute en O(n^3) et 350 ms.
La première version de mon code de la partie 2 était en O(n⁴), et prenait plus de 10 secondes pour retourner le résultat.
Partie 1 : 4:41:28
Partie 2 : 6:54:26
Il s'agissait d'un automate cellulaire en 1 dimension.
Pour la partie 1, il fallait trouver l'état de l'automate au bout de 20 étapes, et pour la partie 2, au bout de... 50 milliards d'étapes !
J'ai remarqué assez vite que cet automate se comportait comme un glisseur. J'ai donc pu trouver une relation linéaire entre le nombre d'étapes et l'état de l'automate.
Partie 1 : 3:59:55
Partie 2 : 4:48:17
Un problème de simulation, où il fallait modéliser le parcours de véhicules sur un circuit (assez complexe), déterminer le lieu de la première collision (partie 1) et la position finale du dernier véhicule restant (partie 2).
Finalement, c'est la construction du circuit, à partir des données d'entrée, qui m'aura donné le plus de mal.
Partie 1 : 24:25
Partie 2 : 1:02:51
Ce problème était plus facile, et je suis arrivé très facilement à la solution de la partie 1.
Pour la partie 2, j'ai dû ruser un peu pour obtenir un temps de calcul inférieur à 1 seconde. J'ai utilisé un ArrayDeque pour sauvegarder, à mesure de l'exécution de l'algorithme, les scores des 6 dernières recettes.
Partie 1 : 11:25:55
Partie 2 : 11:52:39
Pour l'instant, c'est le problème le plus difficile de l'Advent of Code 2018, qui a nécessité le plus de code pour être résolu (mon code, en Scala, fait 150 lignes).
La difficulté se trouvait principalement dans la partie 1, où il fallait simuler un combat aux règles complexes entre Elfes et Gobelins. La partie 2 s'appuyait entièrement sur le code de la partie 1.
Partie 1 : 2:37:10
Partie 2 : 3:15:18
Un problème d'émulation d'une microarchitecture, avec 16 instructions différentes.
Il fallait d'abord trouver à quelle instruction correspondait chaque opcode de 0 à 15, puis exécuter le programme décrit dans la deuxième partie du fichier de données.
Partie 1 : 15:39:14
Partie 2 : 15:46:49
La partie 1 était vraiment difficile. Il fallait simuler l'écoulement de l'eau à travers un sol argileux. Pour cela, j'ai utilisé une fonction récursive avec mémoisation, et j'ai sauvegardé la liste des cellules contenant de l'eau dans une HashMap.
J'ai pris beaucoup de temps pour trouver un algorithme et des structures de données efficaces. Le code s'exécute en 20 ms.
La partie 2, par contre, était triviale.
Partie 1 : 2:04:04
Partie 2 : 9:25:00
Encore un automate cellulaire, comme pour le jour 12, mais en 2 dimensions.
Je suis allé assez vite sur la partie 1 (une demi-heure de travail réel, pusique j'ai commencé à 7h30), mais j'ai vraiment eu du mal sur la partie 2, croyant à tort qu'il n'y avait pas de cycle, ou un cycle très long, sur le déroulement de cet automate cellulaire.
Partie 1 : 1:10:49
Partie 2 : 9:45:14
Ce problème est la suite du jour 16, avec un pointeur d'instructions en plus.
Pas à grand chose à dire sur la partie 1, assez simple.
La partie 2 nécessitait de comprendre le programme donné en entrée. Il s'agissait d'un calcul (très inefficace, en O(n^2)) de la somme des diviseurs d'un entier. J'ai donc écrit un équivalent en Scala de ce programme, avec un meilleur algorithme, qui s'exécute en O(sqrt(n)).
Partie 1 : > 24h
Partie 2 : > 24h
J'ai seulement validé il y a une heure la première partie de ce problème. J'avais la bonne solution hier, mais le code était trop lent et trop complexe. Je l'ai refait aujourd'hui, divisant le temps de calcul par 200 (10 ms au lieu de 2 secondes).
La partie 2 ne présentaitt quand à elle aucune difficulté, tous les calculs nécessaires étant déjà faits dans la partie 1. Il ne m'a fallu que 6 minutes pour la valider.
Partie 1 : 21:46:21 (2 essais)
Partie 2 : 21:58:38
Encore un problème d'émulation, faisant suite aux jours 16 et 19.
Encore une fois, il fallait comprendre le fonctionnement d'un programme en assembleur, et déterminer pour quelles valeurs initiales du registre 0 il finissait par s'arrêter.
Partie 1 : 5:14:19 (2 essais)
Partie 2 : 22:07:46
La partie 1 était assez facile, mais j'ai commis une erreur stupide qui m'a fait perdre pas mal de temps.
Pour la partie 2, j'ai beaucoup tâtonné pour trouver le meilleur algorithme de pathfinding, et j'ai finalement opté pour un A*. Avec une petite optimisation, j'ai réussi à réduire le temps dee calcul à 600ms.
Partie 1 : 16:14
Partie 2 : > 24 h
Après une première partie très simple, venait une deuxième partie beaucoup plus difficile, combinant géométrie dans l'espace et théorie des graphes (intersection d'octaèdres et clique maximum).
Je ne suis pas sûr que mon algorithme fonctionne dans tous les cas de figure possibles et imaginables, mais il doit marcher pour tous les fichiers de données soumis dans le cadre de l'Advent of Code.
Partie 1 : > 24h
Partie 2 : > 24h
Un problème qui est un peu dans l'esprit du jour 15. Il faut d'abord simuler un combat dans la partie 1, et trouver ensuite dans la partie 2 la valeur d'un paramètre qui permet de remporter le combat.
Le point le plus difficile pour moi a été l'écriture et le test d'expressions régulières pour l'analyse des données d'entrée.