Dans divers jeux Super Mario , les coquilles vertes et rouges de Koopa Troopa peuvent glisser sans friction sur des surfaces planes et détruire les blocs de briques qui se trouvent sur leur chemin. Lorsqu'un obus heurte un bloc de briques, le bloc se casse, le transformant en espace vide, et l'obus Koopa change de direction. Par exemple, regardez la coquille rouge ici .

Supposons qu'un niveau Super Mario ne dépasse que d'un bloc et que chaque cellule de la grille soit soit une brique soit un espace vide, à l'exception de la cellule la plus à gauche qui contient une coque se déplaçant vers la droite. Le niveau est également périodique , donc si la coquille sort du bord droit ou gauche du niveau, elle rentrera du côté opposé. Dans cette situation, l'obus continuera de rebondir et de briser tous les blocs de briques du niveau jusqu'à ce qu'il n'y en ait plus. Jusqu'où la coque aura-t-elle voyagé juste après la rupture du dernier bloc de briques?

Défi

Écrivez un programme ou une fonction qui accepte un entier décimal non négatif. Ce nombre, exprimé en binaire sans zéros non significatifs (la seule exception est 0 lui-même), code la disposition de niveau élevé d'un bloc. A 1est un bloc de briques et un 0espace vide.

Le Koopa Shell est inséré à l'extrémité gauche du niveau et se déplace initialement vers la droite. Par exemple, le niveau associé à l'entrée 39est

>100111

car 100111est 39 en binaire, et >et <représentent droite et à gauche des obus se déplaçant respectivement.

Vous devez imprimer ou renvoyer la distance totale parcourue par la coque une fois que le tout dernier bloc de briques (aka 1) a été brisé.

La sortie de 39is 7et les changements de niveau ressemblent à ceci:

Level      Cumulative Distance
>100111    0
<000111    0
>000110    0
0>00110    1
00>0110    2
000>110    3
000<010    3
00<0010    4
0<00010    5
<000010    6
000001<    7
000000>    7  <-- output

De même, la sortie de 6est 1:

Level    Cumulative Distance
>110     0
<010     0
001<     1
000>     1  <-- output

Le code le plus court en octets gagne.

Pour référence, voici les sorties des entrées 0pour 20:

0 0
1 0
2 0
3 0
4 0
5 0
6 1
7 1
8 0
9 0
10 1
11 2
12 2
13 1
14 3
15 3
16 0
17 0
18 1
19 3
20 2

Et voici les sorties jusqu'à l'entrée 1000.

CJam, 29 26 24 octets

Merci à Sp3000 pour avoir économisé 3 octets.

q~2b{_1&}{W\({%}*0+}w],(

Suite de tests. (Cela affiche tous les résultats de 0 à l'entier donné sur STDIN.)

Explication

Cela tourne un peu la spécification sur sa tête: au lieu de déplacer le shell à travers la chaîne binaire, nous décalons et inversons la chaîne binaire de sorte que le shell soit toujours à l'avant, pointant vers la droite:

q~      e# Read and evaluate the input.
2b      e# Convert to base-2 to get the "level".
{_1&}{  e# While there is a 1 in the level...
  W\    e#   Put a -1 below the level.
  (     e#   Pull off the first digit, i.e. the cell the shell is pointing at.
  {     e#   If it's a 1 (i.e. a brick)...
    %   e#     Reverse the level, consuming the -1. This isequivalent to reversing the 
        e#     shell in place.
  }*
  0+    e#   Append a zero. If the cell was a brick, this just replaces it with an empty
        e#   cell. Otherwise, this rotates the level by one cell. This is equivalent 
        e#   to moving the shell one cell through the periodic level.
        e#   Note that if the leading cell was 0, the -1 remains on the stack.
}w
],(     e# Wrap the stack in an array, get its length and decrement.

Pyth, 24 octets

&.WsH_XZeaYxZ1 0jQ2ssPBY

Essayez-le en ligne: démonstration ou suite de tests

Le code de 22 octets suivant devrait également faire l'affaire. Cela ne fonctionne pas actuellement, en raison d'un bogue dans le compilateur Pyth.

&u_XGeaYxG1ZjQ2)ssPBPY

edit: Bug corrigé, mais bien sûr la solution ne compte pas.

Essayez-le en ligne: démonstration ou suite de tests

Explication:

En alternant de l'avant et de l'arrière, je fais ce qui suit:

• Je recherche un 1
• Rappelez-vous cet index en le mettant dans une liste
• Mettez ce 1 à 0

Lorsqu'il ne reste plus de 1, je calcule la distance. Important: le shell déplace deux fois chaque distance de la liste (avant et arrière), à ​​l'exception de la dernière distance.

&.WsH_XZeaYxZ1 0jQ2ssPBY   implicit: Y = empty list
                jQ2        convert input number to binary
 .WsH                      start with Z=^; 
                           while the sum(Z) > 0, apply the the following to Z:
           xZ1                index of 1 in Z
         aY                   append this to Y
        e                     take the last element of Y (=this index)
      XZ       0              set this 1 (at index ^) in Z to 0
     _                        and revert the order of Z
                           this returns a list of zeros
&                          don't print ^, print the next thing
                     PBY   creates the list [Y, Y[:-1]]
                    s      combine these lists
                   s       sum up the distances