A rotation of a string is made by splitting a string into two pieces and reversing their order, for example "world! Hello," is a rotation of "Hello, world!". It is possible to create programs that can be rotated to form a different, but still valid program. Consider this example in python:

print ")import sys; sys.stdout.write("

It can be rotated to form

import sys; sys.stdout.write("print ")

Which is itself a valid python program.

Your challenge is to write a program that outputs a rotation of itself, which when run will output the original program. Bonus points to any entry with a cycle length greater than two!

This is code golf, the exact scoring will be: (length of code)/(cycle length - 1).

EDIT: We have a winner (unless someone else is able to beat a score of 4)! I'd still be very interested to see any other solutions, whether they're contenders or not.

  • 2
    Nice! You've excluded cheap concatenation with your (cycle length-1) weighting. – boothby Mar 8 '12 at 16:54
  • 3
    Try doing this in Befunge, with a literal rotation. – Mechanical snail Jan 1 '13 at 22:48
  • Using chicken and egg is also a good touch on this one. – meawoppl Mar 9 '14 at 9:29
up vote 21 down vote accepted

APL (158 characters, score = 4)

'''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 

I'm using Dyalog APL here. The number of cycles can be increased by one by adding (0 followed by a space) to the end of the expression and to the end of the string (before '''). The cycle length is (# 0's) + 1, and the length of the expression is 150 + 4*(cycle length)). Assuming we continue adding zeros forever, the score is Limit[(150 + 4*n)/(n - 1), n -> Infinity] = 4, where n is the cycle length.

Here's an example with cycle length=6:

      '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 
 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0

      0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0
 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0

      0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0
 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0

      0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0
 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0

      0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0
 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1

      0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1
'''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 0 0 0 0

192 characters, score = 2

'''{2≠⍴⍺:¯3⌽(2×1+⍴⍺)⍴(1+⍴⍺)⍴⍺ ⋄ a←⊃2⌷⍺ ⋄ ⍵=0:¯2⌽(2×1+⍴a)⍴(1+⍴a)⍴a⋄(-4+⌊10⍟⊃⍺)⌽(2×1+⍴a)⍴(1+⍴a)⍴a}01'''{2≠⍴⍺:¯3⌽(2×1+⍴⍺)⍴(1+⍴⍺)⍴⍺⋄a←⊃2⌷⍺⋄⍵=0:¯2⌽(2×1+⍴a)⍴(1+⍴a)⍴a⋄(-4+⌊10⍟⊃⍺)⌽(2×1+⍴a)⍴(1+⍴a)⍴a}01

Depending on the implementation, one point of failure could be when the integer prefixed to the string is too large. Theoretically, though, we can add a cycle by adding two characters - a 1 at the end of the string (before ''') and a 1 at the end of the entire line.

200 characters, score = 1

'''{a←{2=⍴⍵:⊃2⌷⍵⋄⍵}⍺⋄(⍺{⍵=9:⍬⋄⍕1+{2=⍴⍵:10×⊃⍵⋄0}⍺}⍵),(¯2⌽(2×1+⍴a)⍴(1+⍴a)⍴a),⍺{⍵=9:(⍕9),⍕⊃⍺⋄⍕⌊⍵÷10}⍵}'''{a←{2=⍴⍵:⊃2⌷⍵⋄⍵}⍺⋄(⍺{⍵=9:⍬⋄⍕1+{2=⍴⍵:10×⊃⍵⋄0}⍺}⍵),(¯2⌽(2×1+⍴a)⍴(1+⍴a)⍴a),⍺{⍵=9:(⍕9),⍕⊃⍺⋄⍕⌊⍵÷10}⍵}91

My APL implementation doesn't have unlimited precision integers by default, so the integer is converted to a float when it becomes too large, causing the output to be wrong. So this one is the most finicky, but theoretically (either by hand or with a different APL interpreter), it should have a score of 1. Just add a 1 to the end of the expression, and you get another cycle.

Overview (with a shorter quine)

I'm going to give an overview of the first version, because I think it's probably the easiest to comprehend. Before tackling that version, however, we're going to consider a simple quine in APL:

1⌽22⍴11⍴'''1⌽22⍴11⍴'''

I've found that one of the best ways to understand some APL expressions is to look at the output throughout the cascade of operators/functions. All operators and functions in APL are right-associative and have the same precedence, so here is is, from right to left:

  • '''1⌽22⍴11⍴''': This is just a string literal (a list of characters). '' is the APL way of escaping single quote marks. Output: '1⌽22⍴11⍴'.
  • 11⍴'''1⌽22⍴11⍴''': Here, we reshape () the string to be of length 11. Because the string's length is under 11, it is repeated (i.e., 5⍴'abc' would yield 'abcab'). Output: '1⌽22⍴11⍴''. So we now have two quotation marks at the end - we're getting somewhere!
  • 22⍴11⍴'''1⌽22⍴11⍴''': Similarly, we now reshape our previous output to be of length 22. Output: '1⌽22⍴11⍴'''1⌽22⍴11⍴''. We're almost there - we just need to move the first single quote to the end.
  • 1⌽22⍴11⍴'''1⌽22⍴11⍴''': Here, we rotate () the list of characters by 1. This moves the first character of the string to the end. As another example, 2⌽'abcdef' returns 'cdefab'. Output: 1⌽22⍴11⍴'''1⌽22⍴11⍴'''.

The rotating quine

That short quine is the main basis for our rotating quine. Now, with that in mind, let's take a look at our quine:

'''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 

{ ... } defines an unnamed function, which is where we'll be doing the work. Note that functions in APL take a right argument, denoted by , and an optional left argument, denoted by (think infix). We want to feed this function both our quine string and something to aid us in creating an arbitrary number of cycles. To make things easier on ourselves (and anyone wanting to add cycles), we make the quine string the left argument. The right argument, then, is where we put our list of cycles. 2 or more items separated by a space creates a list, so in this example, we have 2-element list consisting of a 1 and a 0.

We can see that the function looks similar to the quine from before. We have the same ...⌽...⍴...⍴... form from before. So that's good - we at least understand that much! Let's delve deeper into the ellipses, starting with everything after the last : ⊃,/(~^/¨⍺=0)/⍺.

  • As you can see by looking at the example above, we prefix the string with the 0's from the right-hand side, adding one with each iteration; but we don't care about those right now. We just want the string!
  • First, consider what's in the parentheses. (They group like in most other languages, by the way.)
    • ⍺=0 returns a list, in this case, with the same shape as , where each element in is replaced by a 1 if it is equal to 0, and a 0 otherwise. This is performed recursively; so if we have a list of a list of a list of characters, the individual characters will be tested against 0, and you will get back a list of a list of a list of binary values.
    • So if consists of just our string, we get back a list of 0's. Otherwise, our left argument has some 0's prefixed to it (e.g., 0 0 0 'quinestring'), so it is a list consisting of 0's and another list, our string. Then our output looks like 1 1 1 <sub-list of zeros>.
    • ^/¨⍺=0: We apply the derived function ^/, which reduces (/) using the logical AND (^) function, to each (¨) element of ⍺=0. This is to flatten the sub-list of zeros so that we can consider the quine string to be one binary value. Considering the previous example, the output would be 1 1 1 0.
    • ~: We binary NOT each of the values from before (e.g., returning 0 0 0 1).
  • (~^/¨⍺=0)/⍺: For each element in , we replicate (/) it the number of times given by the corresponding element in the left argument. This eliminates all of the 0's, leaving us only with our quine string.
  • ⊃,/ is some necessary paperwork to ensure that we get back a flattened list of characters, by reducing the result with the concatenation function (,). If the input is already a flattened list (i.e., the left argument to our main function is only the string), we get a 1-element list containing that list. In the other case, when we have a list consisting of a sub-list for the string, we get the same thing back (a list with a sub-list). We then unpack this (), giving us only the first element of the list (i.e., the sub-list of characters). This might seem unnecessary, but otherwise we would then be trying to reshape a 1-element list!

Next, we look at the length given for the first reshape, within the parentheses:

  • ⍺,⍵: We concatenate the right argument to the first argument
  • ⊃,/⍺,⍵: Same as before - flatten the list.
  • +/0=⊃,/⍺,⍵: Add up the number of zeros in the list by reducing (/) using the addition (+) function.
  • 2×+/0=⊃,/⍺,⍵: Multiply that number by two.
  • z←2×+/0=⊃,/⍺,⍵: Assign () the result to a variable, z. To recap, z is now twice the number of zeros found in both the left and right arguments.
  • 77+z←2×+/0=⊃,/⍺,⍵: We then add 77, for the characters in the quine string, ignoring everything after the space following 1. Like in the initial quine example, we add 1 to the length of the string to get another single quote.
  • The output of this reshape, in this example, is: '{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''

The argument to the reshape that follows is simple and mirrors the short quine (2 times the length for the first reshape). Our output now is:

'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 '''{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''

Now for the final step, where we calculate how much to rotate the output string:

  • As you can see by looking at the previous output, we want to rotate it back (a negative amount) to bring the 2 final quotes to the beginning. Because we want a 0 (and another space) to move to the beginning as well, we want to rotate it an additional 3 characters back.
  • +/+/¨⍺=0: Add up the number of zeros in the left argument. The first (from the right) +/¨ sums each element's count (i.e., a sublist or just an integer), and the second +/ gives us the sum of that resulting list.
  • 5+2×+/+/¨⍺=0: Multiply by two (to rotate the spaces as well), and add 5 (the result we came up with before).
  • Now, we subtract the previous value from the left argument to - to handle the case when we hit the end of our cycle:
    • (3+z)×^/⍵: AND all of the elements in the right argument together to see if we've reached our end (1), and multiply that by 3+z.

And we're done!

  • Wow, very cool, I didn't expect anything like this when I wrote the original question! I don't speak APL at all, is there any chance you could give an overview of how this works? – Gordon Bailey Mar 9 '12 at 15:18
  • Sure! I've got a couple more versions to post (with theoretically lower scores), so I'll add an overview with those sometime tomorrow. – Dillon Cower Mar 13 '12 at 4:53
  • Thanks very much for your extremely thorough documentation, you're using some neat tricks here. I especially like the use of the operator(?). I think I'll have to read through the whole thing a couple more times before I fully digest it! – Gordon Bailey Mar 16 '12 at 22:20

GolfScript, 10046 / 9999 ≈ 1.0047 (asymptotic score 1)

OK, I'm going to try and beat D C's APL entry with this:

{\''+.,{(;\'.~1'}{'1'9999*@'.~']puts:puts}if}.~

The code above is not the actual quine — I felt that posting a 10kB one-liner would not be a very good idea. Rather, running the code above once produces the actual 10046-char GolfScript program, which, when iterated as specified in the question, generates 9999 rotations of itself and, finally, itself again.

The length of the cycle (and the program) can be adjusted by changing the constant 9999. For brevity and convenience, I'll show what the iterated output looks like if the constant is reduced to 9:

111111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~
11111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~1
1111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~11
111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~111
11111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~1111
1111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~11111
111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~111111
11{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~1111111
1{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~11111111
{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~111111111
111111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~
11111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~1
1111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~11
111111{\''+.,{(;\'.~1'}{'1'9*@'.~']puts:puts}if}.~111
etc.

As the constant 9999 is increased, the ratio of the program length and cycle length (minus one) tends to one. I'm pretty sure that this solution can't be beaten, at least not asymptotically. ;-)

How does it work?

GolfScript is a pretty easy language to write quines in, since basically any number literal acts as a quine: for example, the GolfScript program 12345 outputs — you guessed it — 12345. Also, concatenating multiple quines typically produces a quine. Thus, I could use a simple number like 11111...111 as the repetitive part of my cyclic quine.

However, to get the quine to actually cycle, we need to carry and execute a non-trivial "payload". The simplest GolfScript quine I could think of that can do that is the following:

{PAYLOAD'.~'}.~

So my plan was to prefix a quine like that with a repetitive numeric constant, and use a payload that chops one digit off the number and moves it to the end of the program. If the program detects that there is no numeric constant in front of it (in which case the value below it on the stack will be an empty string, assuming there no input), it will instead prepend a fixed-length numeric constant in front of itself.

There's one additional wrinkle, though — when "wrapping around", the payload must also suppress the output of the number after itself. Normally, when a GolfScript program ends, all values on the stack are automatically printed, which would be a problem here.

However, there turns out to be an (AFAIK) undocumented way to avoid that: the interpreter actually calls the predefined function puts to do the printing, so redefining that function as a no-op suppresses the automatic output. Of course, this also means that we must first call puts ourselves to print the part of the stack we want printed.

The final code looks pretty messy (even for GolfScript), but at least it works. I suspect there may be some clever ways I haven't yet thought of to shave a few chars off the payload, but for this version I was mainly just focusing on the asymptotic score.

  • Seems to work for me without the puts{}:puts, although I could see an argument for {print}:puts on the grounds that a newline in the output would mean that it isn't strictly cycling. – Peter Taylor Mar 15 '12 at 7:53
  • @Peter: The ]puts{}:puts is needed for the wrap-around from {STUFF}.~111111111 to 111111111{STUFF}.~, otherwise the number of 1s at the end of the program just keeps growing and growing. (The {} seems to be unnecessary, though; apparently, the GolfScript interpreter allows assignment from an empty stack.) – Ilmari Karonen Mar 15 '12 at 12:50
  • Very nice, although it looks like D C has also posted a solution with an asymptotic score of 1, so we might have a tie. – Gordon Bailey Mar 16 '12 at 22:26

HTML, minus infinity (almost)

-2

AA

-10

AAAAAAAAAA

And so on... If someone tells that it is cheating, we can argue about it, but I have found a hole in question :)

So I guess everyone understand that code does, it has no loops, so longest loop is 0 and considering program length is n, score is n / (0 - 1) or -n, I can write program which has n as big positive integer, but it is useless, because everyone understand it.

  • 7
    Sorry to say, but your cycle length is 1, not 0. So your score is n/0 which is neither negative nor small. – Paul Thomann Apr 26 '14 at 18:43

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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