# Counting cycles in a folding and squashing process

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.

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 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.

• If the bit length of the number shortens during iteration, do we cut and fold using the original bit length, or the current one?
– xnor
Commented Oct 13, 2015 at 20:53
• @xnor I would assume the original one, otherwise you would never complete cycle, right? Commented Oct 13, 2015 at 21:06
• Commented Oct 13, 2015 at 23:46

# 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.

• First in! Look at you, shooting code faster than your shadow! Commented Oct 13, 2015 at 20:29

# Python 2, 175154 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


Thanks to agtoever for 27 bytes!

• No need for the lambda. Once the length is even, it stays even. Commented Oct 13, 2015 at 21:29
• Excellent point, thanks! Commented Oct 13, 2015 at 21:35
• 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. Commented Oct 14, 2015 at 8:59
• 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 . Commented Oct 14, 2015 at 16:21

# 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.

# APL (Dyalog Extended), 37 bytes

≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕


Try it online!

A full program which takes a single number as input.

The traj function does a lot of heavy lifting here(thanks to Bubbler for suggesting it and helping ot golf this).

The (,,⍤0)/ idiom from APLcart is used to interleave lists together, but instead this uses ,/↓⍉⌽ since it is a matrix.

## Explanation

≢{⊃,/↓⍉⌽@1⊢2 ¯1⍴{2|≢⍵:0,⍵⋄⍵}⍵}⌂traj⊤⎕
⊤⎕ convert input to base-2
{                           }⌂traj   calculate trajectory when the following function is applied repeatedly:
{2|≢⍵:0,⍵⋄⍵}⍵         prepend a 0 if there are an odd number of bits
2 ¯1⍴                     cut into two rows
⌽@1⊢                          apply reverse to first row
,/↓⍉                              transpose, concatenate into a vector
⊃                                  unenclose
≢                                    get length of the resulting list