19
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

CJam, 29 26 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.
\$\endgroup\$
5
\$\begingroup\$

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
 .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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.