On a mélangé les bits

Il semblerait qu'il y ait un petit problème avec le dispositif ASVA. En effet, après une récente mise à jour, les loupiotes indiquant les stations affichent n'importe quoi !

Habituellement, pour allumer les points du parcours, on construit un nombre binaire où chaque bit correspond à une LED. Ainsi, on aura le nombre 0b111 s'il reste trois stations à desservir dans un sens. Dans l'autre sens, on aurait un nombre finissant par des zéros : 0b1110000000000000000000000. Malheureusement, ici, il est clair que tous les bits ont été mélangés.

Sur les réseaux sociaux, on voit paraître plein de moqueries, photos à l'appui, illustrant ce curieux dysfonctionnement. On a compilé un certain nombre de ces images et on a pris soin d'encoder en binaire ce qui s'affiche. Seulement, on ignore de quelle station elles proviennent et dans quelle direction allait la rame. À part une, sur laquelle on distingue derrière les portes ouvertes la station et la direction. Après un rapide coup d'œil, on en déduit que, des deux terminus de la ligne, celui affiché par le bit au poids le plus faible est celui qui devrait être au bit d'indice zéro.

On voudrait retrouver la permutation à effectuer pour corriger l'affichage. Si on a 0b101 et 0b100 au lieu de 0b011 et 0b001, c'est que le bit qui devrait être à l'indice 0 a été câblé à l'indice 2, le bit qui devrait être à l'indice 1 a été câblé à l'indice 0, et le bit qui devrait être à l'indice 2 a été câblé à l'indice 1. Ainsi, la liste représentant la permutation serait [2, 0, 1].

Recâbler chaque LED serait fastidieux, donc on ne fera qu'appliquer logiciellement la permutation. Les limitations techniques ont mené à ce que le numéro en numération factorielle de la permutation soit renseigné dans la configuration.

Afin de calculer ce numéro, on reprend la liste représentant la permutation. Pour chaque élément, on compte combien de valeurs situées après lui dans la liste sont plus petites que la sienne. Dans [2, 0, 1], 2 est suivi de 0 et 1, qui sont deux valeurs inférieures ; 0 n'est suivi d'aucune valeur inférieure et 1 non plus. À partir de cette nouvelle liste, on calcule la somme des valeurs multipliées par la factorielle de leur position depuis la fin de la liste. Avec [2, 0, 0], on a le calcul suivant : 2 * 2! + 0 * 1! + 0 * 0! = 4.

Exemple

Imaginons une ligne de métro de 5 stations. Les photos prises auraient pu être encodées en binaire et données en hexadécimal comme suit :

0x5
0x12
0x1
0x1d

Après conversion en binaire, on a :

• 0b00101
• 0b10010
• 0b00001
• 0b11101

On peut alors voir l'emplacement des deux terminus avec 0b00001 et 0b11101, sur le bit d'indice 0 et 1. Puisqu'on sait que le bit de poids le plus faible devrait être au bit d'indice 0, on déduit que le bit à l'indice 0 n'a pas été permuté. Avec 0b00101, on déduit que le bit d'indice 2 devrait être à l'indice 1. Avec 0b10010, on déduit que le bit d'indice 3 devrait être à l'indice 2. Avec 0b11101, on déduit que le bit d'indice 4 devrait être à l'indice 3. Enfin, le bit d'indice 1 devrait être à l'indice 4.

La permutation à effectuer est donc donnée par la liste [0, 2, 3, 4, 1].

Le numéro peut être calculé à partir de cette liste. La valeur 0 n'est suivie d'aucune valeur inférieure. La valeur 2 est suivie d'une valeur inférieure (1). La valeur 3 est suivie d'une valeur inférieure (1). La valeur 4 est suivie d'une valeur inférieure (1). La valeur 1 n'est suivie d'aucune valeur inférieure.

La nouvelle liste [0, 1, 1, 1, 0] nous donne le calcul :

0 * 4! + 1 * 3! + 1 * 2! + 1 * 1! + 0 * 0! = 9

On devra configurer la permutation numéro 9.

Vous pouvez récupérer votre input en cliquant ici.

Votre réponse :