24
\$\begingroup\$

Write a proper quine whose every rotation is itself a proper quine.

For example, if your source code is abcdef, then:

  • abcdef would output abcdef
  • bcdefa would output bcdefa
  • cdefab would output cdefab
  • defabc would output defabc
  • efabcd would output efabcd
  • fabcde would output fabcde

A rotation "is made by splitting a string into two pieces and reversing their order".

Scoring

This is . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
11
  • \$\begingroup\$ So I could have program aaabbb and I could say that the next rotation is bbbaaa? Or would the next rotation have to be baaabb? \$\endgroup\$
    – Beta Decay
    May 19, 2017 at 9:30
  • 1
    \$\begingroup\$ The next rotation is baaabb. \$\endgroup\$
    – Leaky Nun
    May 19, 2017 at 9:31
  • 2
    \$\begingroup\$ Side note, the standard Fission quine is a different quine of rotation-safe: no matter how you rotate it, it will always print the original source code. \$\endgroup\$ May 19, 2017 at 9:45
  • 2
    \$\begingroup\$ If a quine in a language is one byte, is that cheating? \$\endgroup\$
    – MD XF
    May 29, 2017 at 4:41
  • 1
    \$\begingroup\$ Is this a proper quine? \$\endgroup\$
    – tsh
    Sep 5, 2017 at 5:50

2 Answers 2

25
+200
\$\begingroup\$

Alice, 138 128 74 70 bytes

<pp&a0Ra*880R9Z640R8Z5e0R7*a70R6Z060R5Z9e0R4Z4R20R3*79Y3Zea0eZ1R51!Z73

Unfortunately, I had to fix a bug in the interpreter to make this work, so the current version doesn't work on TIO. But you can try the 128-byte solution online.

You can use this Python script to verify that it works for all rotations, but again you'll have to run it locally against an up-to-date interpreter for the latest version. (Thanks to Jo King for providing that.)

Explanation (for 74-byte solution)

(Link to an explanation of the original 138-byte solution.)

I was trying find a 2D language for Razetime's bounty where this might be possible and it turned out that it's actually very feasible in Alice. Unfortunately, the solution is a one-liner, not making much use of the two dimensions. That said, I'd be very impressed if this is possible with an actual 2D program (in any language), because almost every rotation would have one line broken into two pieces (one at the start and one at the end). I imagine a language would have to have a) multiple explicit entry points and b) a way to determine where on the grid an instruction pointer is to pick one that starts in a "safe" region of the grid. And then you'd still have to implement a quine for this that can work out what the actual current rotation is. So... uhhh...

Printing the quine

Anyway, let's talk about this solution. I'm using grid manipulation (or self-modifying) command p to write our actual program into the grid. The main trick for letting me get below 100 bytes is to write that code outside the initial grid, specifically to the left of it (at negative x indices). This self-modification works regardless of the applied rotation (we'll get into why later), and prepends the following snippet to the code:

@o&J'h%p't"

This code will be executed from right to left. By the time we get here:

  • there might be some rubbish left on the stack (depending on the rotation) - in one case, there might be an iterator in the queue (more about that later)
  • in two cases (specifically those starting with a p) the first character of the original source code has been replaced with a null
  • otherwise the original source always remains unchanged.

Before we get into how and why this self-modification works consistently, let's look at what the new code does.

"   Toggle string mode. While in string mode, Alice records every
    codepoint the IP travels over (with some caveats that don't
    matter). Since there's only one " on the grid, we'll record 
    every other cell, wrap around, and eventually hit " again.
    When we leave string mode again, all of the codepoints get 
    pushed to the stack. 
    There'll be a bunch of useless stuff at the bottom of the stack
    now but what's important is that the top 74 values are the
    original source code in reverse order.
    However, the leading 'p' might have been replaced with a null.
    Let's fix that.
t   Decrement.
'p% Modulo 112. Since 'p' is the biggest codepoint in the original
    source, this won't affect any value that corresponds to an 
    actual character. But if we had a 0, -1 % 112 becomes 111.
h   Increment. We've now mapped 0 to 112 and left all values from 1
    to 112 unchanged.
'J  Push 74, which happens to be the length of the source code.
&o  Pop and print that many characters from the top of the stack.
@   Terminate the program.

Generating the printing code

On to the question of how we apply this source modification in the first place. Let's go back to half of the initial code:

<pp&ha0Na*880RaZ640R9Z5e0R8Z620R7Z060R6Z9e0R5Z4R20R4Z730R3Z060R2Zea0eZ1R51

We start on a < which makes the instruction pointer (IP) move west instead of east. The IP wraps around the edges, so we really start executing the code from the end and should once again read this code in reverse.

This makes use of p, which pops y, x, v and writes value/codepoint v to the location (x, y). We use ah& to execute p 11 times, though the second p will add a 12th invocation. It's important for those to happen only in one place in the code for all rotations to work. All the other stuff before that just prepares the stack with inputs for these twelve invocations of p. Breaking the code down into v, x, y triples:

v     x   y

          ​1
5R1Z  e   0
aeZ   2R  0
60Z   3R  0
37Z   4R  0
2R4Z  5R  0
e9Z   6R  0
60Z   7R  0
26Z   8R  0
e5Z   9R  0
46Z   aR  0
88*   aN  0

Apart from pushing individual digits, there are only a few commands of note here. e pushes -1. a pushes 10. R multiplies the top of the stack by -1. N computes the bitwise NOT. And then there's Z. You'll notice that most of them make use of it, the zip command. This command computes a bijection from a pair of integers to a single integer. The intended usage is to encode lists or other collections of numbers in a single number (to make it easier to store on the tape or the grid, for example), but it happens to be very useful for generating larger numbers in few characters. You can use this Alice program to figure out which two numbers you need to get the desired result.

Also note that there's an additional 1 at the bottom of the stack. This is the only relevant input for the 12th invocation of p. Since this is the y this writes some garbage somewhere on the second line of the program, which we'll never encounter.

Rotating the source

Finally, let's look at how various rotations of the source code behave. I'm going to shorten our "unrotated" source code to <pp&haZYX where ZYX represents the code that pushes all the constants. Let's go through the various possibilities:

pp&haZYX<

Here, we start on a p, which immediately reads three implicit zeros from the empty stack and replaces itself with a null. This is the reason any solution will need two ps, because the rotation which starts with p immediately loses it before it can do anything useful. For this particular rotation, we immediately run into another p, which does nothing and then &haZYX pushes a ton of random numbers we're never going to use. Finally < moves us left and we basically move through the exact same code as in the unrotated source, except we don't have the additional p any more (but that only wrote a useless character to the second line anyway).

p&haZYX<p

This one behaves a bit differently. The initial p still removes itself, so the behaviour isn't really different until we hit < move back and push all the constants. However, now when reach the left end of the code, our actual p hasn't been executed yet, so the quine-printing code doesn't exist yet. The IP wraps around and we finally modify the source with the p at the end. Then the IP moves through ZYX again, uselessly pushing the constants again. Finally, we end on &ha just before the ".

String mode works such that it makes use of the iterator queue when leaving string mode. So what this does is that we end up pushing all of the grid codepoints to the stack 11 times instead of once. But since we're only working with the top 74 stack values anyway, we don't care about the other 10 copies at all and this rotation ends up working as well.

Next:

&haZYX<pp

This is basically the same, except we don't replace a p with null (but do write a rubbish character to the second line).

And finally, putting the rotation anywhere inside the code that pushes constants:

YX<pp&haZ

This isn't fundamentally different, we just push a smaller amount of rubbish to the stack before hitting the < and executing the proper code.

\$\endgroup\$
3
  • 11
    \$\begingroup\$ Welcome back!!! \$\endgroup\$
    – Adám
    May 12, 2021 at 21:39
  • 1
    \$\begingroup\$ The return of the legend, and with a huge answer like this, no less. \$\endgroup\$ May 13, 2021 at 7:35
  • \$\begingroup\$ I'm flattered, but don't get your hopes up. ;) \$\endgroup\$ May 13, 2021 at 19:47
16
\$\begingroup\$

Motorola MC14500B Machine Code, 1 byte

The 1 byte score is derived from two 4-bit instructions:

0000 0010

Explanation

The Motorola MC145008 is a single chip, one-bit, static CMOS processor optimized for decision-oriented tasks. The processor is housed in a 16-pin package and features 16 four-bit instructions. The instructions perform logical operations on data appearing on a one-bit bidirectional data line and data in a one-bit accumulating Result Register within the ICU. All operations are performed at the bit level.

The pins of the processor are numbered:

Pin assignment

Instructions are presented to the chip on the 4 instruction pins, (I0, I1, I2, I3), and are latched into the Instruction Register, (IR), on the negative-going edge of X1.

In layman's terms, pins 4 through 7, are used to present the Instruction Register with an instruction, but the bits are interpreted in the reverse order. For example, the instruction 0001 would have pin #7 in the high state and pins 6 through 4 in the low state.

The instructions, are decoded in the Control Logic (CTL), sending the appropriate logic commands to the LU. Further decoding is also performed in the CTL to send a number of output flags (JMP, RTN, FLGO, FLGF) to pins 9 through 12. These are used as external control signals and remain active for a full clock period after the negative-going edge of X1.

Or, put simply, pins 9 through 12 are the output flags FLGF, FLGO, RTN, and JMP, respectively. Note that data is typically multiplexed to the WRITE pin (pin #2). The output flag pins are similar to other language's exit codes.

Each of the ICU's instructions execute in a single clock period.

Rotations

Initial position

0000    NOPO
0010    LDC

The clock periods:

  1. The NOPO instruction puts pin #10 (FLGO) in the high state. Before the next clock period, the output flag pins are put back into the low state.
  2. The LDC instruction loads the complement of the Data Bus' value to the Result Register, without affecting the output flag pins.

So, during the program's two clock periods, the output flag pins have represented 0100 0000, which, read in reverse (like the input pins), is 0000 0010, or the original instructions.

First rotation

0010    LDC
0000    NOPO

The clock periods:

  1. The complement of the Data Bus is loaded to the Result Register, with no effect of the output flag pins.
  2. Pin #10 in switched to the high state.

During these two clock periods, the output flag pins have represented 0000 0100, which, when reversed, are the instructions 0010 0000.

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