Contexte de l'exercice
L'exercice en question est celui du jour 3 de l'Advent of code 2019. L'objectif de cet exercice est d'aider le père noël et son vaisseau spatial à parcourir la galaxie sereinement, et pour ça nous devons optimiser son moteur. Des câbles sortent d'un même trou, se croisent X fois et se branchent chacun à un endroit différent. Afin d'aider les lutins lors de la maintenance de l'appareil, nous devons trouver les intersections de ces câbles. Cela revient à trouver sur un repère cartésien des intersections de tracés (ici nos câbles). Parmis ces intersections nous devrons trouver celle qui est la plus proche du point [0,0] (là ou sortent les câbles) via une Distance de Manhattan et également celle qui est la plus proche du début de chaque tracé. Pour déterminer cette deuxième partie de l'exercice nous compterons, pour chacun des câbles, le nombre total de mouvements fait pour arriver à cette intersection. Ceux-ci sont décrits selon une suite d'instructions composés d'une lettre et d'un nombre, chaque instruction séparée par une virgule.
Dans le schéma ci-dessus, le câble bleu peut être écrit comme ceci : R4,D2,R3,D7,L5,U6
On distingue dans ce schéma deux intersections : une en [5,2] et une en [2,8]. La plus proche est la première car 5+2=7 (et 8+2=10). C'est aussi l'intersection la plus proche du début de chaque tracé car elle se trouve en 30 étapes alors que la seconde se trouve en 34.
Résolution de l'exercice
Pour trouver les réponses, j'utilise Javascript. Je fais simplement un fichier index.js que j'éxécute avec NodeJS et qui m'output en console le résultat attendu. Mon idée est la suivante : je vais créer une liste de chaque points de chaque câble et je vais regarder les points en communs des deux câbles : ce seront mes intersections. Ensuite, pour calculer la distance je ferai la somme des valeurs absolues de l'absisse et de l'ordonnée (car les valeurs peuvent être négatives). Let's code.
Array solution
Pour la solution tableau je vais boucler sur chaque câble et passer celui-ci dans une fonction qui va me retourner un tableau avec tous les points du câble passé en paramètre. Ensuite j'irai chercher l'intersection de ces deux tableaux avec un simple filter. Attention les yeux, ça va piquer :
const generatePoints = (wire) => {
wire.split(',').reduce(
(acc, val) => {
const coords = acc[acc.length - 1].split(',')
const oldX = parseInt(coords[0])
const oldY = parseInt(coords[1])
const moveType = val.split('').splice(0, 1)[0]
const distance = parseInt(val.replace(moveType, ''))
for (let i = 1; i <= distance; i++) {
if (moveType === 'R') {
acc.push(`${oldX + i},${oldY}`)
} else if (moveType === 'L') {
acc.push(`${oldX - i},${oldY}`)
} else if (moveType === 'D') {
acc.push(`${oldX},${oldY + i}`)
} else if (moveType === 'U') {
acc.push(`${oldX},${oldY - i}`)
}
}
return acc
},
['0,0']
)
}Ce petit morceau de code me donne un tableau de String qui contient les coordonnées x,y de chaque point. Par exemple ['0,0', '0,1', '0,2'] etc... Vous avez déviné la suite, pour déterminer les intersections, on va boucler sur ce tableau et voir si chacun des points est contenu dans l'autre tableau. Attention les yeux bis :
const findIntersections = (array1, array2) => {
return array1.filter((value) => array2.includes(value))
}Ici, nous bouclons sur le premier tableau en utilisant la fonction filter. Pour chaque item, nous appliquons la fonction de callback value => array2.includes(value) qui permet de vérifier si cet item est aussi présent dans le deuxième tableau. Si la valeur retournée est true alors l'élément est conservé sinon il est filtré. Vous voyez venir le problème ? Non ? Sur des tableaux d'une taille convenable, ça passe tranquillou, mais sur un tableau de 200 000 éléments, ça commence à faire long 🤓 Imaginez une boucle qui parcours 40 000 000 000 d'éléments... Notre temps d'éxécution oscille entre 70 et 80 secondes (au début je pensais même avoir fait planter mon PC tellement c'était long). Conclusion : Odile d'array, c'est pas pour nous.
Map solution
Ici nous allons comme dans l'autre cas de figure, construire un tableau contenant tous les points et vérifier les points en commun. La solution proposée n'est surement pas la plus belle et optimale mais l'objectif que je me suis fixé pour cet advent of code est de résoudre les exercices assez vite, quitte à les refactoriser plus tard. Toujours est-il que cette solution est beaucoup plus performante que la première et pour une raison assez simple, elle ne parcours pas tout le deuxième tableau à chaque itération du premier mais se contente de vérifier, par sa clé, que l'item est présent. Mieux, beaucoup mieux.
La base est la même mais plutôt que de créer un Array, on pousse dans une Map nos coordonnées. Celles-ci seront les clés et les valeurs seront le nombre de mouvement nécessaire pour arriver à ce point. La valeur nous servira pour résoudre la partie 2 de l'exercice.
const generatePoints = (wire) => {
const instructions = wire.split(',')
const points = new Map()
let oldX = 0,
oldY = 0,
moves = 1
instructions.map((val) => {
const moveType = val.split('').splice(0, 1)[0]
const distance = parseInt(val.replace(moveType, ''))
for (let i = 0; i < distance; i++) {
switch (moveType) {
case 'R':
oldX++
break
case 'L':
oldX--
break
case 'D':
oldY++
break
case 'U':
oldY--
break
}
points.set(`${oldX},${oldY}`, moves++)
}
})
return points
}Le code est simple, on créé une Map vide, on initialise des compteurs pour les coordonnées et le nombre de mouvement total, puis on récupère comme avant le type de mouvement et la distance à parcourir. Ensuite on incrémente ce qu'il faut et on pousse dans notre Map le résultat.
La fonction d'intersection va être elle beaucoup plus performante pour une bonne raison, la méthode .has() qui permet de vérifier si pour une clé donnée l'item est présent. Voyez plutôt :
const findIntersections = (map1, map2) => {
return Array.from(map1.keys()).reduce((acc, key) => {
if (map2.has(key)) {
acc.push(key)
}
return acc
}, [])
}C'est plus beau et plus rapide, alors pourquoi se priver ? Ici le temps d'éxécution est d'environ 130ms.
Conclusion
Pour conclure cet article, on voit bien que dans notre cas de figure, une Map est beaucoup plus pertinente qu'un Array. Nous aurions pu le faire également avec un Object et faire appel à object[key] mais la Map sert spécifiquement à ce cas de figure. Je vous invite à lire la documentation disponible pour les Map afin de découvrir les possibilités offertes par cette beauté du monde.
La première solution met environ 75 secondes à s'éxécuter, la deuxième environ 130ms. Soit un gain de 99,82%. Pas mal.
Merci de votre attention, à bientôt !