Voyage pan-dimensionnel dans le Cœur-en-Or

Les voyages à bord du Cœur-en-Or, avec son moteur à improbabilité infinie, sont épuisants. Trillian est chargée d'établir les plans de vol, et pour cela, elle dispose de plusieurs cartes du ciel, qui lui permettent de choisir la succession de sauts à faire, en optimisant certains critères.

Les cartes fournies par l'ordinateur de bord Eddie sont de plusieurs types.

Une première carte indique les mouvements possibles. Par exemple :

La carte est toujours établie pour un voyage qui part du coin inférieur gauche au coin supérieur droit. Le Cœur-en-Or occupe initialement la case en bas à gauche. Deux choix sont possibles :

• partir sur la droite, d'un nombre de cases égal à la valeur située dans la partie droite de la case
• partir vers le haut, d'un nombre de cases égal à la valeur située dans la partie haute de la case.

Partant de la case en bas à gauche, le Cœur-en-Or peut donc se déplacer de 3 vers la droite ou de 2 vers le haut.

Le Cœur-en-Or ne peut pas sortir de la carte.

Avec le plan précédent, il peut par exemple joindre l'arrivée ainsi :

Le plan étant fixé, la succession des manœuvres consiste simplement à préciser si le vaisseau doit partir à droite ou en haut. La solution précédente est donc décrite par DHDH.

Une seconde carte indique en quoi seront changés les passagers du vaisseau lorsqu'il apparaîtra dans un lieu. Une telle carte ressemble à :

Voici la signification des lettres (toutes ne sont pas utilisées dans l'exemple -- Lisez bien, c'est important 😁) :

• 0 : Un banc de sardines chantant du jazz
• 1 : Un troupeau de chaises longues en train de débattre de philosophie existentialiste
• 2 : Une colonie de hamsters en rollers
• 3 : Des boîtes de biscuits qui refusent de s'ouvrir
• 4 : Une collection de chaussettes dépareillées qui complotent contre l'humanité
• 5 : Des tasses de thé conscientes et légèrement paniquées
• 6 : Un troupeau de licornes transparentes en train de jouer au poker
• 7 : Des bols de spaghettis vivants tentant d'écrire un roman
• 8 : Un essaim de papillons en origami qui chantent du heavy metal
• 9 : Des téléphones géants qui ne sonnent que lorsque personne ne les écoute
• 10 : Des habitants en marshmallow dans un décor en pâte à modeler
• 11 : Des bols de soupe à l'oignon récitant du Shakespeare

En suivant le trajet DHDH précédent, les passagers seront successivement transformés en :

• 1 : Un troupeau de chaises longues en train de débattre de philosophie existentialiste
• 2 : Une colonie de hamsters en rollers
• 0 : Un banc de sardines chantant du jazz
• 1 : Un troupeau de chaises longues en train de débattre de philosophie existentialiste

(Notez bien que le vaisseau n'apparaît pas dans la case en bas à gauche, il y est déjà. C'est la case d'arrivée du déplacement qui indique en quoi le vaisseau sera changé.)

Par ailleurs, le fait de s'écarter de la diagonale qui joint directement le point de départ du point d'arrivée a un coût. En numérotant les diagonales ainsi :

on relève pour chaque voyage le plus grand numéro de diagonale visitée, et le plus petit numéro de diagonale visitée.

Ainsi, toujours pour le même trajet DHDH, le numéro de diagonale minimum sera 0 et le numéro maximum sera 3.

Finalement, le coût d'un voyage est estimé ainsi : (num_diag_maxi - num_diag_mini) x (nb_transformations_différentes)

Le trajet DHDH a donc pour coût (3 - 0) * 3 = 9, puisque la diagonale de plus haut numéro visitée est la 3, la diagonale de plus bas numéro visitée est la 0, et les 4 transformations 1, 2, 0, 1 concernent seulement 3 objets différents.

L'objectif est de trouver un voyage qui minimise ce coût. Et s'il y en a plusieurs, on choisira forcément un des trajets qui occasionne le nombre minimal de sauts.

Plutôt facile non ?

Mais ce n'est pas tout... le Cœur-en-Or peut voyager pan-dimensionnellement. Ses coordonnées restent les mêmes, mais le vaisseau se retrouve sur une autre carte. Le vaisseau commence son périple dans la première pan-dimension, et l'objectif est de terminer dans la case en haut à droite, dans n'importe quelle pan-dimension.

Voici un exemple avec 3 cartes seulement :

À chaque instant, le Cœur-en-Or peut donc aller à droite, en haut, ou dans la dimension suivante, sachant que les dimensions sont cycliques et qu'après la dernière carte, on revient sur la première.

Un trajet est donc complètement décrit par la donnée des cartes et une succession de déplacements : D (droit), H (haut), P (changement de pan-dimension).

Voici quelques exemples de trajets possibles en utilisant le mode pan-dimensionnel du vaisseau, ainsi que leurs coûts associés, et le descriptif des trajets.

• description du trajet : HPHDPD
• diagonale mini : -4
• diagonale maxi : 0
• nombre d'objets : 3 (0, 4 et 1)
• coût : 12 ((0 - (-4)) x 3)

• description du trajet : PPHDPPHDPPHPHD
• diagonale mini : -2
• diagonale maxi : 0
• nombre d'objets : 4
• coût : 8 ((0 - (-2)) x 4)

Dans le cas des cartes fournies en exemple, on ne peut pas espérer un coût plus faible que 4. Les deux parcours les plus courts qui ont ce coût sont : PPHPDPHDPPHDHPPD et PPHDPPHDPPHDHPPD.

Les cartes sont fournies au format JSON. L'exemple qui précède est décrit ainsi :

{"transformations": 
    [
        [[3, 0, 0, 1, 1], 
         [0, 4, 4, 4, 0], 
         [0, 0, 1, 4, 4], 
         [0, 3, 0, 2, 0], 
         [0, 4, 0, 1, 1]], 
        [[0, 3, 1, 0, 0],
         [4, 3, 4, 0, 2],
         [0, 1, 0, 2, 2],
         [3, 1, 0, 4, 3],
         [0, 4, 0, 3, 1]], 
        [[2, 2, 3, 4, 1],
         [1, 0, 1, 1, 2],
         [4, 2, 0, 4, 3],
         [1, 0, 3, 3, 4],
         [4, 2, 2, 3, 2]]
     ], 
"directions": 
    [
        [[[2, 2], [1, 2], [3, 2], [2, 2], [2, 2]],
         [[3, 1], [3, 1], [2, 1], [1, 3], [2, 3]], 
         [[3, 3], [1, 2], [1, 3], [1, 3], [2, 2]], 
         [[3, 1], [2, 2], [2, 3], [3, 1], [3, 2]], 
         [[2, 3], [2, 1], [3, 1], [1, 3], [2, 3]]], 
        [[[3, 3], [1, 3], [2, 2], [2, 3], [2, 3]], 
         [[1, 1], [3, 1], [1, 1], [3, 2], [1, 3]], 
         [[2, 3], [2, 1], [2, 3], [2, 3], [1, 3]], 
         [[2, 3], [1, 3], [3, 3], [2, 2], [1, 3]], 
         [[2, 2], [3, 1], [2, 1], [1, 1], [1, 3]]], 
        [[[3, 2], [2, 1], [1, 3], [1, 1], [1, 1]], 
         [[3, 3], [3, 2], [3, 3], [2, 3], [1, 1]], 
         [[3, 3], [2, 3], [2, 2], [2, 3], [3, 3]], 
         [[2, 1], [2, 3], [1, 2], [3, 3], [2, 1]], 
         [[1, 1], [3, 2], [1, 3], [1, 2], [1, 2]]]
    ]
}

Enfin, le Cœur-en-Or ne peut pas aller au delà de 35 déplacements, toutes catégories confondues. Les deux exemples ci-dessus comportent par exemple 16 déplacements.

En utilisant les données fournies en entrée (pas celles de l'exemple...), et tout en restant dans la limite de 35 déplacement au maximum, proposez un trajet à moindre coût et de longueur minimale pour le Cœur-en-Or (sous la forme DHDHP...).