# Koopa Shell Sequence

In various Super Mario games green and red Koopa Troopa shells can slide frictionlessly on flat surfaces and destroy brick blocks that are in their way. When a shell hits a brick block the block breaks, turning it into empty space, and the Koopa shell reverses direction. As an example, watch the red shell here.

Suppose a Super Mario level is just one block high and every grid cell is either a brick or empty space, except for the leftmost cell which contains a rightward moving shell. The level is also periodic, so if the shell exits the right or left edge of the level it will reenter on the opposite side. In this situation the shell will continue to bounce off of and break all the brick blocks in the level until there are no more. How far will the shell have traveled just after the last brick block is broken?

# Challenge

Write a program or function that takes in a non-negative decimal integer. This number, expressed in binary with no leading zeros (the only exception is 0 itself), encodes the one-block-high level layout. A 1 is a brick block and a 0 is empty space.

The Koopa Shell is inserted at the very left edge of the level and is initially moving right. For example, the level associated with input 39 is

>100111


because 100111 is 39 in binary, and > and < represent right and left moving shells respectively.

You need to print or return the total distance traveled by the shell once the very last brick block (a.k.a. 1) has been broken.

The output for 39 is 7 and the changes in the level look like this:

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


Similarly, the output for 6 is 1:

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


The shortest code in bytes wins.

For reference, here are the outputs for inputs 0 to 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


And here are the outputs up to input 1000.

# CJam, 2926 24 bytes

Thanks to Sp3000 for saving 3 bytes.

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


Test suite. (This prints all results from 0 to the integer given on STDIN.)

## Explanation

This turns the spec on its head a bit: instead of moving the shell through the binary string, we shift and reverse the binary string such that the shell is always at the front, pointing to the right:

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 bytes

&.WsH_XZeaYxZ1 0jQ2ssPBY


Try it online: Demonstration or Test Suite

The following 22 bytes code should also do the trick. It doesn't work currently, due to a bug in the Pyth compiler.

&u_XGeaYxG1ZjQ2)ssPBPY


edit: Bug fixed, but of course the solution doesn't count.

Try it online: Demonstration or Test Suite

### Explanation:

Alternating from the front and the back I do the following:

• I search for a 1
• Remember this index by putting it in a list
• Update this 1 to a 0

When there are no 1s left, I calculate the distance. Important is: The shell moves each distance in the list twice (forward and backward), except the last distance.

&.WsH_XZeaYxZ1 0jQ2ssPBY   implicit: Y = empty list
jQ2        convert input number to binary