8
\$\begingroup\$

In chaos theory, the horseshoe map is an example of how chaos arises in a simple process of folding and squashing. It goes like this: take an imaginary piece of dough, fold it, and finally squash it to its original size. Chaos arises in the pattern of how the pieces of dough end up in the final arrangement after n iterations.

Example of an invariant measure

In our case, we'll take a look at how a simple binary pattern behaves when we fold and squash it. Here are the steps with an 8-bit example (the binary representation of 201 or 11001001).

  1. Cut the bits in two pieces of equal length (add a '0' at the beginning if there is an odd number of bits).

    1100 | 1001

  2. Fold the first half over the second half. Note that the order of the first half is reversed, as we rotate it while folding.

    0011
    1001

  3. Squash to its original shape. While squashing, the upper bits are shifted left to the bits under their original position.

    01001011

If we repeat this for this example, we can see that after 4 iterations, we are back to the original bitstring:

Start  bits: 11001001
Iteration 1: 01001011
Iteration 2: 01001101
Iteration 3: 01011001
Iteration 4: 11001001

So, for the decimal value of 201, the number of cycles is 4.

The challenge

  • Write a full program that takes a decimal number as input and outputs the number of cycles it takes to repeat in the above described binary squash-and-fold process.
  • The (decimal) input must be taken from stdin (range: from 1 up to Googol or 10^100).
  • The (decimal) output must be written to stdout.
  • Your score is the number of bytes of your code.
  • Your answer must begin with [Programming language] - [Score in bytes]
  • Standard loopholes are not allowed.

Examples

7 --> 3
43 --> 5
178 --> 4
255 --> 1
65534 --> 1
65537 --> 12
1915195950546866338219593388801304344938837974777392666909760090332935537657862595345445466245217915 --> 329

Final note

What's interesting is that the number of cycles is related to the length of the binary representation, except for a few exceptions where the number of cycles is shorter because of the pattern in the bitstring (for example 111110 cycles after 1 iteration). This creates an interesting opportunity to optimize code length using the underlying pattern instead of calculating the number of cycles.

\$\endgroup\$
  • \$\begingroup\$ If the bit length of the number shortens during iteration, do we cut and fold using the original bit length, or the current one? \$\endgroup\$ – xnor Oct 13 '15 at 20:53
  • 2
    \$\begingroup\$ @xnor I would assume the original one, otherwise you would never complete cycle, right? \$\endgroup\$ – Martin Ender Oct 13 '15 at 21:06
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/48027/discrete-bakers-map/… \$\endgroup\$ – Digital Trauma Oct 13 '15 at 23:46
4
\$\begingroup\$

CJam, 34 bytes

q~2b_,2%,\+{__,2//~\W%.\_W$=!}g;],

Nothing fancy, it just applies the map until we get back to the input, and print the number of iterations that took.

Test it here.

\$\endgroup\$
  • \$\begingroup\$ First in! Look at you, shooting code faster than your shadow! \$\endgroup\$ – agtoever Oct 13 '15 at 20:29
3
\$\begingroup\$

Python 2, 175 154 149 bytes

i=bin(input())[2:]
i=o='0'+i if len(i)%2 else i
c=0
j=len(i)/2
while i!=o or c==0:
 a=''
 for x,y in zip(i[:j][::-1],i[j:]):a+=x+y
 i,c=a,c+1
print c

Ideone link

Thanks to agtoever for 27 bytes!

\$\endgroup\$
  • 1
    \$\begingroup\$ No need for the lambda. Once the length is even, it stays even. \$\endgroup\$ – agtoever Oct 13 '15 at 21:29
  • \$\begingroup\$ Excellent point, thanks! \$\endgroup\$ – Celeo Oct 13 '15 at 21:35
  • \$\begingroup\$ Change ` while 1` with while i!=o|c==0 and drop the if i==o:break. Saves 5. Maybe (note sure) you also don't need a. Just use i. Saves an assignment (4 bytes). Also the assignment of j can be put outside the loop. \$\endgroup\$ – agtoever Oct 14 '15 at 8:59
  • \$\begingroup\$ Thanks for the additional saves, @agtoever. I got a TypeError when attempting to implement the while i!=c|c==0 replacement, but still was able to save some bytes with a standard ` or `. \$\endgroup\$ – Celeo Oct 14 '15 at 16:21
2
\$\begingroup\$

Pyth, 21 bytes

I'm typing this on my phone, so please make sure to notify me of any mistakes.

fqu.i_hc2Gec2GTJ.BQJ1

Try it online.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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