Tiré d'Advent of Code 2020 : https://adventofcode.com/2020/day/15
Chacun son tour, les joueurs disent un nombre. Ils commencent par une liste prédéfinie (input).
Puis les règles suivantes s'appliquent:
en considérant le nombre qui vient d'être cité,
si c'est la première fois que le nombre a été cité, le joueur dit 0,
sinon le joueur annonce il y a combien de tours que le nombre a été cité pour la dernière fois.
Autrement dit, après la liste initiale, chaque tour consiste en un joueur qui dit 0 si le nombre précédent était nouveau ou un âge (si le nombre précédent avait déjà été cité)
Input: 0, 3, 6 Puis :
- Tour 4 : 0 (car 6 était nouveau)
- Tour 5 : 3 (car 0 avait été dit au tour 1, donc son âge était 4-1 = 3)
- Tour 6 : 3 (car 3 avait été dit au tour 2, donc son âge était 5-2 = 3)
- Tour 7 : 1 (car 3 avait été dit au tour 5, donc son âge était 6-5 = 1)
- Tour 8 : 0 (car 1 était nouveau)
- Tour 9 : 4 (car 0 avait été dit au tour 4, donc son âge était 8-4 = 4)
- Tour 10 : 0 (car 4 était nouveau)
Le code attendu doit donner pour l'input (0, 3, 6) le 2020e élément : 436.
Or pour le calcul du 2020e élément, on met environ 180ms.
Cela pose problème si on veut calculer le 30 000 000e élément qui doit être 175594.
Comment optimiser le code ?
Indices : https://docs.scala-lang.org/overviews/collections/overview.html https://www.lihaoyi.com/post/BenchmarkingScalaCollections.html