13
\$\begingroup\$

Challenge

Your goal is to write a program that prints another program. That printed program should print another program, and the new program should print another program, until the end.

Rules

  1. Each program must less than 256 bytes. (If this needs to be changed, leave a comment)
  2. The last program must be an empty program.
  3. There must be a finite number of programs, so the program cannot be a quine.
  4. The programs must all run in the same language.
  5. No input is allowed.
  6. The winning program is the program that prints as many programs as possible, counting itself.

Good Luck!

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ The maximum score is 2^2048, or 3.2317e616. \$\endgroup\$
    – orlp
    Sep 10, 2015 at 4:46
  • \$\begingroup\$ For making it easier to compare big scores, please include an approximation to your score in the form a*10^b where 1<=a<10 and b is a natural number. \$\endgroup\$
    – flawr
    Sep 10, 2015 at 10:08
  • 2
    \$\begingroup\$ Actually, my previous calculation was wrong. Assuming the program must be in bytes the maximum possible score is <number too long for comment> or 1.2673e614. \$\endgroup\$
    – orlp
    Sep 10, 2015 at 10:56

11 Answers 11

Reset to default
20
\$\begingroup\$

CJam, 4.56 × 10526 programs

2D#2b{"\256b_(256b:c'\s`_:(er`":T~{;38'ÿ*`{:T~{;63'ÿ*`{:T~{;88'ÿ*`{:T~{;114'ÿ*`{:T~{;140'ÿ*`{:T~{;166'ÿ*`{:T~{;192'ÿ*`{:T~{;219'ÿ*`{Q?\"_~"}s(\T}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}s(\T`}?\"_~"}_~

Exact score: 254219 + 254192 + 254166 + 254140 + 254114 + 25488 + 25463 + 25438 + 25413 + 3

All programs have to be saved using the ISO-8859-1 encoding to comply with the file size limit.

Thanks to @ChrisDrost who pointed out a bug and suggested the nesting approach.

Try it online in the CJam interpreter.

254219 + 2 ≈ 4.56 × 10526 programs

The line share of the score can be achieved by the following, much simpler program1.

"ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ"
{\256b_(256b:c'\s`_:(er`Q?\"_~"}_~

Running this program produces the program

"ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþ"
{\256b_(256b:c'\s`_:(er`Q?\"_~"}_~

and after 254219 - 1 more iterations, the program

{\256b_(256b:c'\s`_:(er`Q?\"_~"}_~

This last non-empty program exits with an error2 and prints nothing (the empty program).

How it works

Assume the string is already on the stack.

{      e# Push a code block.
  \    e# Swap the string on top of the code block.
       e# This will cause a runtime error if there is no string on the stack.
  256b e# Convert the string (treated as a base-256 number) to integer (I).
  _(   e# Copy the integer and decrement the copy.
  256b e# Convert the integer into the array of its base-256 digits.
  :c   e# Cast each base-256 digit to character. Converts from array to string.
  '\s  e# Push a string that contains a single backslash.
  `    e# Push its string representation, i.e., the array ['" '\ '\ '"].
  _:(  e# Push a copy and decrement each character. Pushes ['! '[ '[ '!].
  er   e# Perform transliteration to replace "s with !s and \s with [s.
       e# This skips characters that require escaping.
  `    e# Push its string representation, i.e., surround it with double quotes.
  Q    e# Push an empty string.
  ?    e# Select the first string if I is non-zero, the empty string otherwise.
  \    e# Swap the selected string with the code block.
  "_~" e# Push that string on the stack.
}      e#
_~     e# Push a copy of the code block and execute it.
       e# The stack now contains the modified string, the original code block
       e# and the string "_~", producing an almost exact copy of the source.

254192 ≈ 5.35 × 10461 more programs

This is where things get a little crazy.

The first program is highly compressible. By writing a similar program that, instead of the empty program, eventually produces the first program from the above section, we can improve the score by 254192 programs3.

The program

"ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ"
{"\256b_(256b:c'\s`_:(er`":T~{;219'ÿ*`{Q?\"_~"}s(\T}?\"_~"}_~

is similar to the first program of the previous section, and running the former and its output for 254192 iterations produces the latter.

Assume the string is already on the stack:

{                           e# Push a code block.
  "\256b_(256b:c'\s`_:(er`" e# Push that string on the stack.
                            e# The characters inside it behave exactly as
                            e# they did in the previous section.
  :T~                       e# Save the string in T and evaluate it.
  {                         e# If the integer I is non-zero, keep the generated
                            e# string; else:
    ;                       e#   Pop the code block from the stack.
    219'ÿ*`                 e#   Push a string of 219 ÿ's (with double quotes).
    {Q?\"_~"}               e#   Push that block on the stack.
    s                       e#   Push its string representation.
    (\                      e#   Shift out the { and swap it with the tail.
    T                       e#   Push T.
  }?                        e#
  \                         e# Swap the selected string with the code block
                            e# or T with the tail of the code block.
  "_~"                      e# Push that string on the stack.
}                           e#
_~                          e# Push a copy of the code block and execute it.

Moar programs

The first program of the previous section is still highly compressible, so we can apply a similar method and write a program that, after 254166 iterations, produces the aforementioned program.

Repeating this technique over and over again until we hit the 255 byte limit, we can add a total of 254166 + 254140 + 254114 + 25488 + 25463 + 25438 + 25413 + 1 ≈ 1.59 × 10399 programs to those of the previous sections.

1 Newline added for clarity.
2 Per consensus on Meta, this is allowed by default.
3 or 0.0000000000000000000000000000000000000000000000000000000000000012 %

Improve this answer
\$\endgroup\$
1
5
\$\begingroup\$

JavaScript, 1000 programs

x=999;
q=";alert(x=999?`q=${JSON.stringify(q)+q}`.split(x).join(x-1):``)";
alert(
    x ? `x=999;q=${JSON.stringify(q)+q}`.split(x).join(x-1) // basically .replaceAll(x, x-1)
      : ``
)

Whether this is valid depends on precisely how to understand the third rule.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ It isn't technically a quine, since it prints out a modified version of its own source code rather than an identical copy. It does use quine-like techniques, obviously. I think we'll need clarification from @TheTurtle. \$\endgroup\$
    – JohnE
    Sep 9, 2015 at 22:49
  • 5
    \$\begingroup\$ @JohnE and Ypnypn This is something like I envisioned. This works. \$\endgroup\$
    – The Turtle
    Sep 9, 2015 at 23:05
  • 6
    \$\begingroup\$ You still are well below the code length limit. Why don't you change 999 to something bigger? \$\endgroup\$
    – DankMemes
    Sep 10, 2015 at 1:58
4
\$\begingroup\$

Ruby, 1.628 × 10^237 programs

a=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;_="a=%#x-1;_=%p;puts _%%[a,_]if a";puts _%[a,_]if a

Same approach as my Perl answer, but because Ruby handles big ints already, it's easier to store as hex.

Ruby, 9.277 × 10^90 programs

a=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;b=0xf;(b<1)&&(a-=1)&&b=eval('0x'+'f'*(74-("%x"%a).length));_="a=%#x;b=%#x;(b<1)&&(a-=1)&&b=eval('0x'+'f'*(74-('%%x'%%a).length));_=%p;puts _%%[a,b-1,_]if a";puts _%[a,b-1,_]if a

So this attempt is a slightly different variation on the previous quine-like, but because of all the extra functions I'm not getting the number anywhere near as high as the other one... Was interesting to try another approach though!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python 2, 9.7*10^229 programs

O=0
if len(hex(O))<191:print"O=0x%x"%(O+1)+open(__file__).read()[-68:]
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice, didn't think of string repetition! \$\endgroup\$
    – Dom Hastings
    Sep 10, 2015 at 13:02
2
\$\begingroup\$

C, 2.2 * 10^177 programs

#define S(s)char*q=#s,n[]="#####################################################################################################";i;s
S(main(){while(n[i]==91)n[i++]=35;i==101?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})

It's not perfect, but pretty good. I mean it's exactly 255 bytes long and generates programs of the same length. You could probably fiddle arround some more to gain some more programs, but I'll leave it as it is for now.

The program is based of a simple C quine. Additionally there's a quite simple counting algorithm which counts through all possible values of the char array n. We have as many programs as permutations of the string n.

The char range is limmited to a range from # (=35) to [ = (91). That's because I don't want any " or \ in the string, because they need to be escaped.

The program generation ends when all values in the char array n are [. Then it outputs a simple dummy program main(){}, which itself outputs nothing.

#define  S(s) char *q = #s; /* have the source as a string */ \
char n[] = "#####################################################################################################"; \ 
int i; \
s /* the source itself */
S(main() {
    while(n[i]=='[') /* clear out highest value, so next array element be incremented */
        n[i++]='#'; 
    i==101 /* end of array reached? output dummy program */
        ? q = "main(){}"
        : n[i]++; /* count one up in the whole array */
    printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)", n, q);
})

As a demonstration that it should work I just changed the limits, so only characters between ASCII-Code 35 and 36 are used and only 4 array elements.

The resulting programs are

% echo > delim; find -iname 'program_*.c' | xargs -n1 cat delim

#define S(s)char*q=#s,n[]="####";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$###";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="#$##";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$$##";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="##$#";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$#$#";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="#$$#";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$$$#";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="###$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$##$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="#$#$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$$#$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="##$$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$#$$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="#$$$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="$$$$";i;s
S(main(){while(n[i]==36)n[i++]=35;i==4?q="main(){}":n[i]++;printf("#define S(s)char*q=#s,n[]=\"%s\";i;s\nS(%s)",n,q);})
#define S(s)char*q=#s,n[]="####";i;s
S(main(){})

This outputs 2^4 + 1 = 17 different programs.

So the program above outputs ((91-35)+1)^101 + 1 = 57^101 + 1 ~= 2.2 * 10^177 different programs. I'm not entierly sure if this counts, or if my calculation is even correct

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Could you please include that this is about 2.2 * 10^177 (for those who want to compare)? \$\endgroup\$
    – flawr
    Sep 10, 2015 at 10:07
  • \$\begingroup\$ Didn't know how to calculate this one, but I included it ;-) \$\endgroup\$
    – MarcDefiant
    Sep 10, 2015 at 10:59
  • \$\begingroup\$ wolframalpha.com =) \$\endgroup\$
    – flawr
    Sep 10, 2015 at 11:17
1
\$\begingroup\$

Perl, 1 × 10^163

Otherwise this is a pretty basic quine, shrunk down to as few chars as possible, that only runs whilst the counter isn't 0.

use bigint;$i=9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999||die;$_=<<'e';eval
print"use bigint;\$i=$i-1||die;\$_=<<'e';eval
${_}e
"
e
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Common Lisp, 10113-1

(LET ((X
       99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999))
  (WHEN #1=(PLUSP X)
    #2=(SETF *PRINT-CIRCLE* T)
    #3=(PRINT (LIST 'LET `((X ,(1- X))) (LIST 'WHEN '#1# '#2# '#3#)))))
  • There are 113 nines.
  • The next program has 112 nines followed by a 8
  • The next program has 112 nines followed by a 7
  • ...

The number of nines is limited by the maximum size of code, 256, taking into account the spaces introduced by the printer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl, 1.4*10^225

use bignum;open$F,__FILE__;$_=<$F>;s/0x\w+/($&-1)->as_hex/e;0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff&&print

Similar approach to python; same result!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python, 1 × 10^194 programs

n=99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
if n:print open(__file__).read().replace(str(n),str(n-1))

This must be run from a file, not an interactive repl. It is not a quine.

Thanks to @The Turtle for helping me save 3 bytes, which is more room for nines!
Thanks to @poke for helping me save 2 bytes, which is more room for nines!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ @ Cheese Lover The if n!=0 is redundant. You can just write if n. \$\endgroup\$
    – The Turtle
    Sep 11, 2015 at 23:20
  • \$\begingroup\$ You can get rid of two spaces too; after the if n: and between the replace arguments. \$\endgroup\$
    – poke
    Sep 14, 2015 at 6:38
0
\$\begingroup\$

><>, 65534 (?) Programs

I've added a question mark next to 65533 since I have yet to verify that it can print 65533 (although I have reason to believe it should). Once I have a bit more time, I'm going to figure out a way to test it.

":?!;1-r00gol?!;a0.�

You can try it online here.

The gist of this program is that it changes the output of the character at the very end and then decrements its numerical value before printing. I got 65534 programs because the ascii value of the character at the end of the code is 65533, so counting the first program we have 65534 (if you count the empty program 65535, I guess). The last program "returned" is nothing; it simply ends when the character value is 0.

I'm quite sure it will be able to print a character for all iterations: I couldn't find a definitive source for how many characters ><> can print, but there are characters directly below 65533, numerically.

Let me know if there are any problems with this implementation; I'm a little unsure about the validity of my entry.

Explanation

I have shamelessly stolen the idea of using a single quotation mark to create a pseudo-quine from the ><> wiki and a comment I saw here once.

":?!;1-r00gol?!;a0.�
"                     begins string parsing
 :?!;                 terminates program if final character is 0, numerically
     1-               decrements final character by 1
       r              reverses stack
        00g           grabs quotation mark (fancy way of putting " ")
           ol?!;      prints and terminates if stack is empty
                a0.   jumps back to o to loop

What it does is parse everything after the quotation mark as characters, then decrement the last one. From there it just reverses the stack (so as to print in the right order), pushes a quotation mark onto the stack, and then prints until the stack is empty.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Bash, 52 programs

Utterly uninspired, and (hopefully) solidly in last place.

echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo echo
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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