Mais je peux me tromper, j’ai pas testé. L’intérêt de construire un cache par contre pour moi c’est de procéder dans le bon sens, de la dernière télécommande jusqu’à au digicode, plutôt que l’inverse.
Je fais des tables qui associent des transitions de touche (aller de T1 à T2) à un coût. Dans la première télécommande, celle que "je" manipule, le coût est toujours = 1 (appuyer sur la touche), donc cette table se construit à la main, ou avec defaultdict dans le langage de serpent. Ensuite… (1/2)
Pour la 1ère télécommande, celle que manipule le premier robot, je calcule les chemins de chaque touche à chaque touche, disons de A à ↓: j'en trouve 2: ←↓A et ↓←A. Comme on part toujours de A, la première solution me coûte le total des coûts des trans° A↓, ↓← et ←A = 3 (l'autre coûte idem) (2/2)
J'enregistre ça dans ma table 1, et j'applique récursivement 25 fois, puis une fois de plus pour le digicode, et c'est terminé. Le coût minimum pour taper le code WXYZA, c'est coûts[AW] + coûts[WX] + coûts[XY] + coûts[YZ] + coûts[ZA], ou coûts est la dernière table évidemment.
Comments