16
\$\begingroup\$

Your job is to create the longest period iterating quine, where the length of each program in the sequence is bounded by 500 bytes.

That is, if you repeat the following steps:

  1. Start with your initial program
  2. Run the current program
  3. Go back to step 2

You will eventually get back to your original program. The number of programs in the cycle is your score, which you are trying to maximize.

None of the programs may raise any errors. Each program must be run the same way as well (e.g. no different versions, implementations, compiler options, platforms, etc...) (EDIT: Yes, any external state such as that of a pseudo random number generator was included in the last statement. The external state must be "reset" after each run. If you use true random numbers, worst case is assumed.)

What separates this challenge from The longest period iterating quine (other than 100 v.s. 500) is that every program in the cycle must also be 500 bytes or less. This means that the longest possible cycle is (256^501 - 1)/255 or less. That of course is a big number, but not that big in terms of how much code it takes to calculate. So the challenge is about using as many of the (256^501 - 1)/255 possibilities as you can, not a busy beaver challenge.

The programs are not permitted to access its own source code. However an empty program is permitted if you want (as long as you follow the other rules).

Since checking the programs manually would be hard, you may figure out the score using theoretical methods. You must include an explanation of the score and correctness with your program. If you can not figure out the score, you may instead use a lower bound of the number of programs in the cycle as a defacto score. You are allowed to update this as you find better lower bounds, or if you find the exact actual score.

This is , so highest score wins!

EDIT: It is recommended that you write what your score is in scientific notation, so that answers are more easily comparable. It is perfectly fine to have other forms of the score as well, especially if they more clearly are connected to your program. Also, readers are encouraged to edit previous answers to comply with this.

\$\endgroup\$
  • 2
    \$\begingroup\$ "the longest possible cycle is (256^501 - 1)/255 or less" --- this isn't necessarily true, the program may pass through the same state multiple times before returning to the original if it manipulates an external object (such as the RNG state or seed) \$\endgroup\$ – JDL Feb 11 at 9:02
  • 2
    \$\begingroup\$ @JDL that should be against the rules, IMHO - if it stores state elsewhere than in the source code, then it's not an a proper iterating quine. \$\endgroup\$ – Nathaniel Feb 11 at 9:15
  • 1
    \$\begingroup\$ @Nathaniel I wouldn't categorise it as storing state elsewhere, it is simply using entry points which are a valid part of the programming language it's implemented in. Arguably, anything which calls another function in the programming language is accessing states which are held outside its own source code. \$\endgroup\$ – JDL Feb 11 at 9:17
  • 1
    \$\begingroup\$ @JDL no, those are different things. Any program in any language obviously has to rely on things that are implemented outside the source code, but storing state outside the source code is different. That would mean the output of the program is not a deterministic function of its source code, but instead depends on some other external context that has been changed by previous runs. That should not be allowed in a quine challenge, IMHO, and the OP's statement about the maximum cycle length indicates that it was intended to be disallowed here. \$\endgroup\$ – Nathaniel Feb 11 at 9:22
  • 3
    \$\begingroup\$ @JDL as I'm certain you're aware, in a deterministic language the instruction pointer only stores state during the execution of a program, and not between invocations of it. Your 5-state example isn't possible if the program's output is a deterministic function of its source. \$\endgroup\$ – Nathaniel Feb 11 at 14:21
12
\$\begingroup\$

Perl 6, \$126^{398} \approx 8.86 \times 10^{835}\$ iterations

$!=Q~~;<say "\$!=Q~{chrs(my@a=[R,] polymod :126[$!.ords]+1: 126 xx*)x?(@a-399)}~;<$_>~~.EVAL">~~.EVAL

Try it online!

This iterates through all the possible combinations of the first 126 bytes of length 398 and under (excluding strings with leading NUL bytes). If you want to see that it actually returns to the first iteration, you can reduce the length to 1 by changing the limit like so.

Explanation:

Each iteration increments the string, stored in base 126 form, and then converts it back to base 126. It does this until it reaches a string with length 399, and then resets the string back to empty again. If you're having trouble conceptualising the number, imagine it with ten bytes instead. Starting from 0, increment up to 4 digits, 1000 and reset. This is \$10^{4-1}\$ iterations (including 0 or empty string in my program's case).

$!=Q~~;         # Start with an empty string
< ... >~~.EVAL  # Set a string to $_ and EVAL it
  say "\$!=Q~{...}~;<$_>~~.EVAL"   # Print the program with the string replaced by
                       :126[$!.ords]   # The string converted from base 126
                                    +1 # Incremented
          [R,] polymod                : 126 xx*  # Back to base 126
chrs(                                )  # Back to a string
     my@a=                            x?(@a-399)  # Only if it isn't 399 characters
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, you did that really fast, I'm almost done with mine, but I'll probably be finishing it tomorrow (mine is going to be in Gol><>) \$\endgroup\$ – KrystosTheOverlord Feb 11 at 4:02
  • \$\begingroup\$ This calculation suggests that you way over estimated your score. The numerator is how many strings of length 397 there are using 126 symbols. (I had to distribute the fraction into the sum since wolfram alpha was acting weird.) \$\endgroup\$ – PyRulez Feb 11 at 4:05
  • \$\begingroup\$ @PyRulez I think my number is correct, since it's basically iterating a base 126 number up to 399 digits... I think my explanation was off \$\endgroup\$ – Jo King Feb 11 at 4:28
  • \$\begingroup\$ @JoKing ah yes, I think the explanation was the problem. You changed 397 to 398, which makes your score no longer an overestimate. You might be underestimating it (since you only included strings of length exactly 398 in the score), but that's fine. \$\endgroup\$ – PyRulez Feb 11 at 5:26
2
\$\begingroup\$

Runic Enchantments, 64654106; 122387-1 ≈ 2.638 × 10807 iterations

"3X4+kSq'ƃZ,r{1?{1[:1Z%1+:a=+:d=+:3X4+=+:6X2+=+:'€(c*?~1-1kq}͍f1+0Bl1=6*?S1-Skql͗2=4*?{͍]}B͍l1=6*?kS1-Sq]}@

Try it online!

Alert: The is incorrectly displayed, it should be `` (0x80).

Rather than the stack, use a string and the stack operators modified with ͍ to modify a string rather than the stack (see prior revision). As such, each char is limited to 1 byte (0-127 range, minus the problematic characters), but with over 3 times as many of them (due to there being less processing boilerplate due to not having to skip Unicode combining characters, as well as some other byte savings) it achieves a higher number of iterations.

If encoding as a true big endian is allowed (that is, having byte values above 127 without interjecting 0x00 bytes) this can achieve 251387-1 ≈ 4.717 × 10928 iterations. However, TIO's Latin encoding prevents this as noted by Erik the Outgolfer in his Python 2 answer. I would need to check if it works locally before claiming this score.

Should be able to replace f1+0B with '0B (there's an unprinting 0x16 there), but it was fighting me (things didn't want to branch/skip/return correctly), so I left it alone. This would raise the big-endian structure from 387 to 388.

\$\endgroup\$
1
\$\begingroup\$

DOS COM, 49 bytes, period 2^3608

00000000  be 31 01 89 f7 b9 f4 02  f9 ac 14 00 aa 39 ce 72  |.1...........9.r|
00000010  f8 31 c9 b4 3c ba 2b 01  cd 21 89 c3 b4 40 b9 f4  |.1..<.+..!...@..|
00000020  01 ba 00 01 cd 21 b4 3e  cd 21 c3 71 2e 63 6f 6d  |.....!.>.!.q.com|
00000030  00                                                |.|

Original assembly to create:

 BITS 16
 ORG 0100h
   mov si, l
   mov di, si
   mov cx, 500 + 0100h
   stc
n: lodsb
   adc al, 0
   stosb
   cmp si, cx
   jb n
   xor cx, cx
   mov ah, 3ch
   mov dx, f
   int 21h
   mov bx, ax
   mov ah, 40h
   mov cx, 500
   mov dx, 0100h
   int 21h
   mov ah, 3eh
   int 21h
   ret
f: db "q.com", 0
l: db 0

This little jewel writes the next phase to q.com rather than standard output because of nulls and other stuff the terminal cannot handle. The root quine technique is equivalent to stringification and the payload room is used as a 3608 bit counter. Due to the way DOS works, the initial state of the counter contains debris from whatever was in memory prior to its first execution.

The original 49 byte input is unreachable, so if you want to score this as 500 bytes go ahead.

\$\endgroup\$
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), flags: /u:System.Numerics.BigInteger and /r:System.Numerics

Score: 10332

Thanks to JoKing who increased my score from 10255 * 2 - 1 to now!

var i=Parse("0");var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";Write(s,(char)34,s,(++i).ToString().Length<333?i:0);

Try it online!

Explanation

Increments a BigInteger every iteration, until it's length becomes too large, which in that case we instantly revert back to the original quine.

//The BigInteger that will be incremented
var i=Parse("0");
//The string that encodes the quine
var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";
//Print out the string, with every {0} replaced with quotes and the {1} replaced with the original string
Write(s,(char)34,s,
//And the {2} is replaced to the BigInteger+1 if the BigInteger wouldn't be too long, else 0
(++i).ToString().Length<333?i:0);
\$\endgroup\$
1
\$\begingroup\$

Python 2, 500 bytes, \$252^{219}\$

#coding=L1
s=""""""
for i in range(220-len(s.lstrip("ÿ")))[:219]:s=s[:i]+chr(ord(s[i])%255-~(s[i]in"!$&"))+s[i+1:]
S='#coding=L1\ns="""%s"""\nfor i in range(220-len(s.lstrip("\xff")))[:219]:s=s[:i]+chr(ord(s[i])%%%%255-~(s[i]in"!$&"))+s[i+1:]\nS=%%r;print S%%%%s%%%%S';print S%s%S

Note that there is a trailing newline. It might get removed above if the syntax highlighter forces its way in.

Unfortunately, you can't execute this program in TIO, as it's encoded in Latin-1.

Above, s contains 219 0x01 bytes. After the program runs, its source is printed, except for one difference: s has been incremented like a base-252 big-endian number, so its leftmost character has been "incremented" to 0x02. The bytes 0x00, 0x22, 0x25 and 0x5C are avoided, so, if any character of the string becomes one of those after the incrementation, the character itself is incremented again.

  • 0x00 (null): A Python source file can't contain null characters.
  • 0x22 ("): There's a danger of three 0x22 bytes forming in a row, that is, """, or the last character of the string becoming ", so the string would be closed prematurely.
  • 0x25 (%): printf-like string formatting is used before completion of the quine skeleton, so a % not adjacent to another % in s will cause trouble. Unfortunately, it's not possible to reorder the formatting to avoid this caveat.
  • 0x5C (\): There's a possibility that the \ is used as an escape mark in the string, instead of verbatim, so it's avoided.

Therefore, 252 out of 256 bytes are usable. If s contains 219 0xFF (ÿ) bytes, it's simply reverted to 219 0x01 bytes, hence completing the cycle.

Given the above, we have \$252^{219}\$ possible strings, hence as many programs overall.

\$252^{219}=8067118401622543607173815381864126969021321378412714150085501148172\\081568355283332551767558738710128769977220628694979838777041634307806013053\\042518663967641130129748108465109552157004184441957823830340121790768004370\\530578658229253323149648902557120331892465175873053680188287802536817909195\\292338112618632542000472094347226540339409672851252596442228662174845397731\\175044304251123874046626291460659909127172435776359148724655575878680270692\\451120531744950544969860952702932354413767504109600742385916705785109741289\\800204288\$

\$\endgroup\$
1
\$\begingroup\$

Clean, \$251^{226} \approx 2.1 \times 10^{542}\$

  • 25139 removed dependency on Text
  • 251122 golfed incrementing function
  • 251128 combined prefix and suffix source strings
  • 251188 removed dependency on Gast.GenLibTest

Presented in xxd format due to nonprintables / invalid UTF-8:

00000000: 6d6f 6475 6c65 2071 3b69 6d70 6f72 7420  module q;import 
00000010: 5374 6445 6e76 3b53 7461 7274 3d28 7325  StdEnv;Start=(s%
00000020: 2830 2c34 3129 2c3f 5b27 0101 0101 0101  (0,41),?['......
00000030: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000040: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000050: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000060: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000070: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000080: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000090: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000a0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000b0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000c0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000d0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000e0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000f0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000100: 0101 0101 0101 0101 0101 0101 275d 2c73  ............'],s
00000110: 2528 3432 2c39 3939 292c 712c 732c 7129  %(42,999),q,s,q)
00000120: 3b71 3d69 6e63 2721 273b 3f5b 683a 745d  ;q=inc'!';?[h:t]
00000130: 2363 3d68 2b69 6628 616e 7928 283d 3d29  #c=h+if(any((==)
00000140: 6829 5b27 ff09 0c26 5b27 5d29 2702 2727  h)['...&['])'.''
00000150: 0127 3d5b 633a 6966 2863 3e68 2969 643f  .'=[c:if(c>h)id?
00000160: 745d 3b3f 653d 653b 733d 226d 6f64 756c  t];?e=e;s="modul
00000170: 6520 713b 696d 706f 7274 2053 7464 456e  e q;import StdEn
00000180: 763b 5374 6172 743d 2873 2528 302c 3431  v;Start=(s%(0,41
00000190: 292c 3f5b 2727 5d2c 7325 2834 322c 3939  ),?[''],s%(42,99
000001a0: 3929 2c71 2c73 2c71 293b 713d 696e 6327  9),q,s,q);q=inc'
000001b0: 2127 3b3f 5b68 3a74 5d23 633d 682b 6966  !';?[h:t]#c=h+if
000001c0: 2861 6e79 2828 3d3d 2968 295b 27ff 090c  (any((==)h)['...
000001d0: 265b 275d 2927 0227 2701 273d 5b63 3a69  &['])'.''.'=[c:i
000001e0: 6628 633e 6829 6964 3f74 5d3b 3f65 3d65  f(c>h)id?t];?e=e
000001f0: 3b73 3d22                                ;s="

Try it online!

Increments a 226-byte string through all byte values excluding \0, \n, \r, ' and \.

The reason we avoid these characters is:

  • \0 makes the compiler angry
  • \n and \r can't appear in charlists
  • ' would end the charlist
  • \ could cause problems if it comes before an escapable character

Once the string is all \377s it wraps around to all \001s, giving the original program.

\$\endgroup\$
  • \$\begingroup\$ The output (at least on TIO) is the character with ordinal value 128, but composed of the two bytes C2 80. Is this the same as the behaviour on your local machine? \$\endgroup\$ – Jo King Feb 12 at 7:41
  • 1
    \$\begingroup\$ @JoKing Oh, no, I get a single byte on my machine. TIO mangles output when it isn't valid UTF-8 (and input files too). \$\endgroup\$ – Οurous Feb 12 at 8:47
  • 1
    \$\begingroup\$ @JoKing I've changed the answer to a new format which makes it possible to see the correct behaviour on TIO. \$\endgroup\$ – Οurous Feb 12 at 22:31
0
\$\begingroup\$

Gol><>, 70 bytes, 39039000 iterations

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPaa*5*=?1:1=Q$~$~|:1)lPaa*5*(Q?:|r2ssH##

Wow, that is a lot lower than I thought it would be... Next step! Making it have more iterations!!!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ it doesn't seem to delete anything once it reaches 500, just appends a NUL byte \$\endgroup\$ – Jo King Feb 11 at 4:45
  • \$\begingroup\$ Does this even work at all? I can't get the "increment the last char" to work \$\endgroup\$ – ASCII-only Feb 11 at 6:09
  • \$\begingroup\$ @ASCII-only Now this works, sorry about before, I had messed up a section while working on fixing the whole thing. It works now, sorry for the inconvenience!!! \$\endgroup\$ – KrystosTheOverlord Feb 11 at 13:04
  • \$\begingroup\$ @JoKing The NUL byte is the deleting process, now the program should delete until it is almost gone, then delete the NUL and increment the last char, if it is a ~, then it will be converted to a '#', returning back to normal!!! \$\endgroup\$ – KrystosTheOverlord Feb 11 at 13:09

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.