Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

You are to write a program that will output source code that is

  1. Larger than the original program (character wise)
  2. Itself an acceptable answer

Any obviously useless code doesn't count towards the character count, i.e. pass or doing an if False: print "Useless. This is code-golf, so shortest answer wins.

share|improve this question
1  
@Kevin, The definition is recursive. The output should be a program whose output is larger than itself, and an answer to this question. So the output's output should be larger than the output, and the output's output's output should be even larger, etc. –  ugoren Feb 23 at 10:55
3  
I think you should clarify your rules. On one hand, any additional code output by such a program is "obviously useless"; on the other hand, all additional code in the output is "useful" in that it furthers the goal of answering this challenge. –  Jason C Feb 23 at 22:29
3  
Sorry for destroying your challenge. :^) –  Quincunx Feb 24 at 5:03
1  
I think this challenge would be much better as a popularity contest than a code golf. It would allow for a lot more creativity! –  corsiKa Feb 24 at 23:44
2  
Naturally, such a program should be known as a quinine. –  Jonathan Van Matre Feb 25 at 5:05

24 Answers 24

up vote 129 down vote accepted

H9+ : 1 char

9

That's right. One character. Outputs the lyrics to 99 bottles of beer, which is a valid program. All the extraneous data does not count, but there are plenty of 9s in there.

The output of the outputted program is the lyrics to 99 bottles of beer 59 times.

This function gives the number of times the lyrics are outputted if you run the program n times (if my calculation is correct):

f(n) = 59n-1
share|improve this answer
16  
+1 I think that this is unbeatable. –  Victor Feb 23 at 6:10
3  
@Victor I did it! A 0 char program with the right characteristics! –  Quincunx Feb 23 at 6:29
12  
A 0 char program in a given language, given that it's valid, will likely output 0 characters. And since 0*x=0 for any finite value x, I can claim that my outputted program is actually 9999999999999999 times bigger than the source code. –  nitro2k01 Feb 23 at 18:33
12  
@JohannesH. For all(solvable) problems there exists a programming language that solves the problem in 0 chars. –  Cruncher Feb 24 at 18:48
4  
I still move that we name that "Cruncher's Theorem", unless it's already been discovered. –  Erty Feb 25 at 18:31

GolfScript, 9 chars

{.'.~'}.~

This code outputs:

{.'.~'}{.'.~'}.~

which outputs:

{.'.~'}{.'.~'}{.'.~'}.~

which outputs:

{.'.~'}{.'.~'}{.'.~'}{.'.~'}.~

and so on.

I believe this is the shortest answer in a "real" Turing-complete programming language so far.

Explanation:

Basically, the original code above is a "quine-layer": it outputs a normal quine followed by itself.

In GolfScript, any code block literal (e.g. {foo}), if left undisturbed on the stack, is a quine. Thus, on its own, {.'.~'} simply outputs itself, just like any other code block would.

The .~ at the end of the code takes the last code block on the stack, duplicates it, and executes the copy. When executed, the code .'.~' inside the code block duplicates the topmost item on the stack (i.e. the copy of itself) and appends the string .~.

At the end of the program, the GolfScript interpreter stringifies and outputs everything on the stack, which, in this case, consists of one more {.'.~'} block than in the input, plus the string .~.

Bonus:

Adding a ] before the first . (to collect all the code blocks on the stack into an array before they're duplicated) makes it grow exponentially:

{].'.~'}.~

outputs:

{].'.~'}{].'.~'}.~

which outputs:

{].'.~'}{].'.~'}{].'.~'}{].'.~'}.~

which outputs:

{].'.~'}{].'.~'}{].'.~'}{].'.~'}{].'.~'}{].'.~'}{].'.~'}{].'.~'}.~

and so on.

share|improve this answer
86  
{].'.~'}.~︵ ┻━┻ –  nitro2k01 Feb 23 at 18:34
5  
+1 for turing complete –  Cruncher Feb 24 at 18:51
1  
bit.ly/1cQXJyA –  Jason C Feb 26 at 20:33
1  
@nitro2k01 my first thoughts exactly :D –  Songo Feb 27 at 12:50
    
@nitro2k01: Flip back that table /(@.@)/ –  DebugErr Apr 22 at 12:13

Java 7: 0 chars



Save as file Blank.java. If you save it as any other file, replace any instance of Blank with the appropriate file name.

Then, run in command line via first compiling, then running. If compiling fails, stop.

I list this as Java 7 because it might output differently for different versions of Java.

First few outputs (outputted to stderr):

Error: Could not find or load main class Blank
Blank.java:1: error: class, interface, or enum expected
Error: Could not find or load main class Blank
^
Blank.java:1: error: reached end of file while parsing
Error: Could not find or load main class Blank
                                              ^
2 errors
Blank.java:1: error: class, interface, or enum expected
Blank.java:1: error: class, interface, or enum expected
^
Blank.java:1: error:  expected
Blank.java:1: error: class, interface, or enum expected
                          ^
Blank.java:1: error:  expected
Blank.java:1: error: class, interface, or enum expected
                                     ^
Blank.java:1: error: as of release 5, 'enum' is a keyword, and may not be used as an identifier
Blank.java:1: error: class, interface, or enum expected
                                          ^
  (use -source 1.4 or lower to use 'enum' as an identifier)
Blank.java:1: error: = expected
Blank.java:1: error: class, interface, or enum expected
                                               ^
Blank.java:2: error:  expected
Error: Could not find or load main class Blank
     ^
Blank.java:2: error: ';' expected
Error: Could not find or load main class Blank
      ^
Blank.java:2: error: = expected
Error: Could not find or load main class Blank
                      ^
Blank.java:2: error: = expected
Error: Could not find or load main class Blank
                                   ^
Blank.java:2: error:  expected
Error: Could not find or load main class Blank
                                              ^
Blank.java:3: error: = expected
^
^
Blank.java:3: error: ';' expected
^
 ^
Blank.java:4: error: illegal start of type
Blank.java:1: error: reached end of file while parsing
     ^
Blank.java:4: error: = expected
Blank.java:1: error: reached end of file while parsing
          ^
Blank.java:4: error: illegal start of type
Blank.java:1: error: reached end of file while parsing
           ^
Blank.java:4: error:  expected
Blank.java:1: error: reached end of file while parsing
            ^
Blank.java:4: error: = expected
Blank.java:1: error: reached end of file while parsing
          ^
Blank.java:4: error: illegal start of type
Blank.java:1: error: reached end of file while parsing
           ^
Blank.java:4: error:  expected
Blank.java:1: error: reached end of file while parsing
            ^
Blank.java:4: error: = expected
Blank.java:1: error: reached end of file while parsing
              ^
Blank.java:4: error: ';' expected
Blank.java:1: error: reached end of file while parsing
                   ^
Blank.java:4: error: = expected
Blank.java:1: error: reached end of file while parsing
                                 ^
Blank.java:4: error:  expected
Blank.java:1: error: reached end of file while parsing
                                        ^
Blank.java:4: error: = expected
Blank.java:1: error: reached end of file while parsing
                                         ^
Blank.java:4: error: ';' expected
Blank.java:1: error: reached end of file while parsing
                                              ^
Blank.java:5: error:  expected
Error: Could not find or load main class Blank
     ^
Blank.java:5: error: ';' expected
Error: Could not find or load main class Blank
      ^
Blank.java:5: error: = expected
Error: Could not find or load main class Blank
                      ^
Blank.java:5: error: = expected
Error: Could not find or load main class Blank
                                   ^
Blank.java:5: error:  expected
Error: Could not find or load main class Blank
                                              ^
Blank.java:6: error: = expected
                                              ^
                                              ^
Blank.java:6: error: ';' expected
                                              ^
                                               ^
Blank.java:7: error: reached end of file while parsing
2 errors
        ^
30 errors
share|improve this answer
14  
"You are to write a program that will output source code that is" The output is arguably not source code. And furthermore, depending on the definition of output (whether output must come specifically from stdout) nothing is actually output. –  nitro2k01 Feb 23 at 18:48
18  
@nitro2k01 I quote the same: "You are to write a program that will output source code". Anything is source code. But only some things are valid source code. Additionally, it was not specified what is considered output, so I am allowed freedom there. –  Quincunx Feb 23 at 18:50
7  
@PyRulez That's right. I exploited your rules. You don't need to accept this answer. When I posted this, I knew that a controversy would follow, complete with many up and down votes. I decided that it would be worth it, though. –  Quincunx Feb 23 at 21:40
13  
Are you sure that the program itself printed the output? Wasn't that only the compiler? The program gets never compiled and itself is not interpreted nor executed, thus it wasn't able to produce any output. –  V-X Feb 24 at 8:25
4  
@blabla999 I disagree - people don't try these challenges because someone else does something crazy. We just challenge ourselves to do it some other way. As Mark Rosewater says, "Restrictions breed creativity" –  corsiKa Feb 24 at 23:40

HQ9+, HQ9++ and similars, 2 characters

QQ

This is the output:

QQQQ
share|improve this answer
13  
I saw this and thought "Oh no, nothing can beat this." I started trying to come up with something, then it hit me. So I posted an answer. –  Quincunx Feb 23 at 6:09
1  
@Quincunx Bravo, upvoted your answer. –  Victor Feb 23 at 6:10
2  
@Quincunx No, I think it's 2^2^n, where the initial program is generation 0. The length recurses m -> m^2. –  Vortico Feb 23 at 20:11
1  
@Vortico Good point. Even though I said it wrong, I meant: At code-length n, the output becomes n^n. However, that is false; when the code-length is n, the output's length is n^2 –  Quincunx Feb 23 at 21:00
2  
It is funny though because even the first two iterations are possible contenders for this question. –  PyRulez Feb 23 at 21:47

Ruby 27

A very slightly modified version of this (via):

puts <<3*3,3
puts <<3*3,3
3

The number of times that puts-line is printed grows exponentially.

$ ruby quine.rb | ruby | ruby
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
puts <<3*3,3
3

$ ruby quine.rb | ruby | ruby | ruby | ruby | ruby | ruby | ruby | wc -l
    3283
share|improve this answer
8  
Answer inspired by the Kaiser Chiefs –  Ben Jackson Feb 23 at 20:06

SH script, 9

cat $0 $0

Grows at exponential rate.

Either run as sh whatever.sh or set it as executable.

Windows version is here.

share|improve this answer

Lambda Calculus - 29

A simple lambda term

(λu.(u u)(u u))(λu.(u u)(u u))

Reducing this term by one beta reduction yields

((λu.(u u)(u u))(λu.(u u)(u u)))((λu.(u u)(u u))(λu.(u u)(u u)))

And so on and so on. It's a simple variant on the classic (λu.u u)(λu.u u) which is a quine in lambda calculus, double self application here means we get twice the output.

share|improve this answer
2  
I'd argue that in lambda calculus, "running" a lambda term means computing its normal form, not performing a single beta reduction. Also, a term can contain multiple redexes, therefore "reducing a single redex" is an ambiguous operation. –  Petr Pudlák Feb 24 at 19:17
1  
You're right, but since this term has no normal form it makes sense to talk about this in terms of small step reduction. Since lambda calculus lacks any inherent set evaluation, I can just define "running" it to be reducing a single redex top level redex with call-by-name semantics no? –  jozefg Feb 24 at 19:54
    
Well, terms with no normal form correspond to non-terminating programs. And the problem with top level redex is that a term can have two redexes, neither one being a sub-term of another. You could pick some criterion which one to reduce, but I'd say that then you're getting very far from the standard lambda calculus semantics. (Anyway I appreciate your novel idea.) –  Petr Pudlák Feb 24 at 19:56
2  
(λx.x x x)(λx.x x x) :20 –  Fabio F. Feb 24 at 22:10
1  
(λx. x x)(λx. x x x) reduces to that in a single step –  Ben Millwood Feb 26 at 21:56

dc 11

Quite simple:

6579792
dfP

The first line is repeated once every generation:

$ dc growing_quine.dc
6579792
6579792
dfP

$ dc growing_quine.dc | dc | dc 
6579792
6579792
6579792
6579792
dfP

The last line consists of the following instructions: d duplicates the last value put on the stack (6579792) (so that we get one more copy each time we run it), f prints the whole stack (which is a bunch of that same number) and P prints the number out as a byte stream, which displays as dfP.

share|improve this answer

Python 3 - 55

print(open(__file__).read())
f=lambda:print('f()')
f()

This could be made shorter by replacing __ file__ with a single character filename and saving the file as that, but I felt this answer was more in the spirit of the question. After one iteration it outputs:

print(open(__file__).read())
f=lambda:print('f()')
f()
f()
share|improve this answer
1  
This isn't a quine. See the definition. –  Petr Pudlák Feb 24 at 19:13
6  
@PetrPudlák Nor are any programs in this question. This is a quine-variant problem, not strict quining. –  AJMansfield Feb 25 at 2:22

Javascript

function a(){
     for(;;)
 console.log(a.toString(), "a()");
}
a()

Keeps on printing its source code

share|improve this answer

Smalltalk, 125 61 57

The golf version looks almost unreadable so I'll explain first (and use real identifiers).

This is a variant of the "weirdest-way-to-produce-a-stack-overflow" self modifying method.

The method prints out a hello message, and its current source (for the demonstration only). Then, the code is modified to output a longer string and installed. Finally, the new code is called recursively.

In order to protect myself from an immediate runaway, it lets the user confirm in each cycle.

compile in Object:

eatMe_alice
   |msg mySource|

   mySource := thisContext method source.

   '**** Hello Alice' printCR.
   '  ---- my current code is:' printCR.
   mySource printCR.
   '  ---------------' printCR.

   (UserConfirmation confirm:'Again? ') ifTrue:[
       Object compile:
            (mySource
                copyReplaceString:'Hello ','Alice'
                withString:'Hello ','Alice !').
       self eatMe_alice
   ]

start the show by sending "eatMe_alice" to any Object; nil will do:

nil eatMe_alice

A nice variant is to not call the new code recursively, but instead iteratively, by unwindig the call stack and reentering into the new method. This has the advantage of not leading to a recursion exception. To do this, replace the recursive call ("self eatMe_alice") by:

thisContext resend

Golfing:

Obviously, printing and self calling was not asked for, so the shortest (for golf) is to simply append a comment to my own source and return it. As a side effect, it also gets installed for the next call...

x|s|Object compile:(s:=thisContext method source,'""').^s
share|improve this answer

SH script, 12 8 7

Store a file with

sed p *

in its own, empty directory and run from this directory using sh [file] or set executable.


Old alternative with 8 characters, but doesn't need its own directory. Store a file with

sed p $0

and run using sh [file] or set executable.

Old alternative with 12 characters:

sed -i- p $0

This will actually output to the program file itself, but where to output was not specified. Replicates itself at an exponential rate.

share|improve this answer
    
+1 Aw you beat my SH by 1! –  Jason C Feb 24 at 2:43
1  
You might still have chance using ed, didn't want to look through its man page... –  Jens Erat Feb 24 at 10:49

C, 95

b="";main(a){printf(a="b=%c%s %c;main(a){printf(a=%c%s%c,34,b,34,34,a,34);}",34,b,34,34,a,34);} 

based on main(a){printf(a="main(a){printf(a=%c%s%c,34,a,34);}",34,a,34);}

it has additional variable b, which contains string of spaces (empty string at the beginning). Each generation adds one additional space.

share|improve this answer
    
Original (non-growing): geeksforgeeks.org/quine-a-self-reproducing-program –  Jason C Feb 23 at 22:47

Windows .BAT, 25

@COPY %~nx0+%~nx0 CON>NUL

Grows at exponential rate.

Equivalent SH version here.

share|improve this answer

redcode (recursive solution)

This is the code of the easiest warrior writable in redcode, the famous Imp:

MOV 0, 1

When executed, the code writes a copy of its single instruction at the next address in memory; then executes it, etc.

share|improve this answer

JavaScript, 41 chars

function f(){console.log(f+"f();f()")}f()

The first time you run it it outputs itself with another ;f() at the end. Subsequent runs of the output results in each "input" source printed twice.

alert would be shorter than console.log but I don't consider multiple alert dialogs to be "the" output while it seems reasonable to call multiple lines in the console as an output.

share|improve this answer

Common Lisp, 16 Characters

(print `(or ,-))

Granted, it's interactive-only, but being able to reference the current top-level form is probably the single best way to minimize a non-trivial program that meets the specification.

What would be really interesting is what blows up the fastest. Maybe something like

(print `(progn ,@(loop repeat (length -) collect -)))

share|improve this answer
    
+1 For Common Lisp. Looks to me like you can skip ` and ,? –  daniero Feb 26 at 13:55
    
@daniero Without the quotation, it just prints the original program, never growing. At that point, you may as well omit the or, too: (print -) –  Stuart Olsen Feb 26 at 20:14

PHP, 38

<?echo fgets(fopen(__FILE__,'r')).';';

It will add a semicolon at each run.

share|improve this answer
    
Are the semicolons useless code? –  Quincunx Feb 23 at 18:00
2  
@Quincunx They are, you are right. However, what would you consider useful code? –  ComFreek Feb 23 at 18:03
    
Maybe you could put in in the ';'. Then you'd get longer outputs. –  Quincunx Feb 23 at 18:03
1  
why not <?=fgets(fopen(__FILE__,'r')).';';? –  Ismael Miguel Feb 24 at 23:54
    
;<?echo fgets(fopen(__FILE__,'r')); –  user23013 Oct 15 at 8:59

ECMAScript 6 (38 Characters)

(f=_=>'(f='+f+')();(f='+f+')();')();

Which outputs:

(f=_=>'(f='+f+')();(f='+f+')();')();(f=_=>'(f='+f+')();(f='+f+')();')();

Edit

You could do (28 characters):

(f=_=>'(f='+f+')();'+f())();

However it will recurse infinitely and never return anything... but this can be solved by doing something like this (42 characters):

(f=_=>_?'(f='+f+')('+_+');'+f(_-1):'')(3);

Which will output:

(f=_=>_?'(f='+f+')('+_+');'+f(_-1):'')(3);(f=_=>_?'(f='+f+')('+_+');'+f(_-1):'')(2);(f=_=>_?'(f='+f+')('+_+');'+f(_-1):'')(1);
share|improve this answer

EcmaScript 6 (51 bytes):

(_=x=>'(_='+_+Array(x++).join(','+_)+')('+x+')')(2)

It produces a longer version of itself, which can produce a longer version of itself, which can produce a longer version of itself, etc. ...

share|improve this answer

BATCH, 26

Place this code in any .bat file and it will continue to execute (in an infinite loop) and the file will grow as well.

echo echo %0 ^>^> %0 >> %0
share|improve this answer
    
This doesn't quite work, %0 is the command used to invoke the script, which may not have a .BAT extension. You can use %~nx0 to get the full filename of the batch file. –  Jason C Feb 24 at 0:06
    
@JasonC AFAIK, it doesn't need the .bat to be executed. If the filename is execute.bat, you can enter either execute or execute.bat. Both will work. –  ub3rst4r Feb 24 at 1:59
    
The file itself needs to have a .bat extension to execute but you can leave the extension off when you execute it (when you type a command with no extension, Windows tries .com, .exe, then .bat in that order). If the filename is hello.bat, then >> %0 will write a file named hello, which isn't the original hello.bat (and can't be executed). –  Jason C Feb 24 at 2:40

Javascript - 46

(function $(){console.log('('+$+'());$()')}())
share|improve this answer

PYG (6)

P(Q,Q)

Prints it's own source code, separated by newlines. The second generation would be

P(Q,Q)
P(Q,Q)

and so forth.

share|improve this answer

Batch

set d=time  
copy c:\>loop.bat /B loop%d%.bat  
call c:\>loop.bat
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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