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.

Write a program that is capable of randomly generating itself.

It must do this based on the tokens used in its source code. If your program's source code is composed of 50 unique tokens and is 60 tokens long, then the program should output 60 tokens where each token is randomly chosen from one of the 50 unique tokens.

For example, this program would have a one in 50^60 chance to reproduce itself.

What is a token? That depends on the language. For example, identifiers (foo_bar), keywords (while), and numbers (42) would count as tokens in most languages. Whitespace would not count in most languages.

Additional rules:

  • Output may only contain tokens found in the programs source code, separated by the appropriate delimiter
  • Output must be the same length as the program's source code, counted by tokens
  • Only one programming language may be used
  • Source code must have at least 3 unique tokens
  • Exclude comments from the source code
  • Program should only have a one in U^L chance to reproduce itself

Scoring: The program that has the best chance to reproduce itself, wins.

share|improve this question
    
@MathieuRodic: You're assuming that the program draws tokens without repetition. –  user2357112 Mar 25 at 9:48
    
@MathieuRodic: Let me rephrase. You're assuming the program randomly scrambles the multiset of its tokens, rather than drawing L tokens with repetition from the set of U tokens used in its source. –  user2357112 Mar 25 at 9:52
    
@user2357112: I see. My mistake was to consider this problem as a draw without replacement. –  Mathieu Rodic Mar 25 at 10:02
1  
Rule #1 and #5 appear to be in contradiction to me. –  Cruncher Mar 25 at 13:46
4  
Can you assume that built in random functions are TRNGs? Typical implementations have too small seeds to produce all outputs and thus might be unable to actually regenerate itself. –  CodesInChaos Mar 25 at 15:20

7 Answers 7

up vote 10 down vote accepted

Python 2, 3^-3 = 0.037

exec abuse is quite handy for reducing the token count.

exec '''
# String literals are one token!
import random
import tokenize

with open(__file__) as f:
    tokens = [x[1] for x in tokenize.generate_tokens(f.readline)][:-1]

''' '''
# Splitting the string into two strings pads the token count to the minimum of 3.

print random.choice(tokens), random.choice(tokens), random.choice(tokens),
'''

Strictly speaking, the Python grammar places an ENDMARKER token at the end of the source file, and we can't produce a source file with ENDMARKERs randomly strewn about. We pretend it doesn't exist.

share|improve this answer
    
@Cruncher That is the probability. 3^-3 == 1/3^3 –  Austin Henley Mar 25 at 16:03
1  
+1 for brilliant hack of the rules. The same idea implemented in J: ".]';(?3 3 3){]`".;~({:,],{:,],6#{:)'';(?3 3 3){]`".;~({:,],{:,],6#{:)'''''''. –  algorithmshark Mar 25 at 18:17

Javascript, 102 tokens, 33 unique, 7.73×10-154

Note, this is a true quine. It doesn't read the file or use eval or Function.toString

meta = "meta = ; out = '' ; tokens = meta . split ( '\\u0020' ) ; tokens . push ( '\"' + meta + '\"' ) ; length = tokens . length ; tmp = length ; unique = { } ; while ( tmp -- ) unique [ tokens [ tmp ] ] = unique ; unique = Object . keys ( unique ) ; tmp = unique . length ; while ( length -- ) out += tokens [ ~~ ( Math . random ( ) * tmp ) ] + '\\u0020' ; console . log ( out )"; 
out = '';
tokens = meta.split('\u0020');
tokens.push('"' + meta + '"');
//console.log(tokens);
length = tokens.length;
tmp = length;
unique = { };
while(tmp--) unique[tokens[tmp]] = unique;
unique = Object.keys(unique);
//console.log(unique);
tmp = unique.length;
while(length--)
    out += unique[~~(Math.random() * tmp)] + '\u0020';
console.log(out)
share|improve this answer

Python: P(generating program in 1 trial) = 3.0317 * 10^-123

34 unique tokens, 80 total tokens. Note that there is a space at the end of each line.

import tokenize , random 
tokens = [ x [ 1 ] for x in tokenize . generate_tokens ( open ( __file__ , 'r' ) . readline ) ] [ : -1 ] 
s = '' 
for x in tokens : s += random . choice ( list ( set ( tokens ) ) ) ; s += [ ' ' , '' ] [ s [ -1 ] == '\n' ] 
print s 

Sample output:

' ' random len set 'r' , for ( list , import ] ] tokens : random [ for '\n' import readline readline 'r' tokens [ len 'r' import '' choice '' '' for in ( readline ( = open readline , list 1 list s += for s 1 , '' : 1 += list len - __file__ ; open __file__ print . - ] 'r' for import [ print . , 

; . [ [ print print __file__ generate_tokens ] ; open ] , readline 

Thanks to the other Python solution by user2357112 for reminding me to discard the last token and use __file__ which I was previously ignorant of.

share|improve this answer

J - 1 in 1117 = 1.978 x 10-18

;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''

J has a bunch of handy little tools for getting these kinds of jobs done.

  • First of all, any space separated string of numbers is one token. It means a one-dimensional array of those numbers. This is how J's lexer works. By the way, that's seventeen 11s, if anyone is curious.

  • (,,,{:,{:)'QUINE''' is a common quine trick in J, made to use as few tokens as possible: {: means Tail, so it appends the string to itself, and then adds two copies of the last character to the end of that. Since the last character is a single quote (J uses Pascal-style strings), the result is QUINE'QUINE'''.

  • ;: is a tokenizer, and breaks up an input string as though it was J code, returning a list of boxes. The length of this result is 17.

  • ~. takes all the unique elements of this array. The length of this result is 11.

  • ? is called Roll. For each integer in its argument, it selects a random positive number greater than or equal to zero, less than that number. So here J will generate 17 numbers from 0 to 10 inclusive.

  • { uses the random indices to select items out of our list of unique-tokens-in-boxes.

  • ; opens all these boxes and runs the result together.

Some examples follow. The indented lines are the input prompts, and the lines flush with the left side are the interpreter's output.

   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
~.~.(?;;:11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''(){11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){(;:;
   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
{';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)''',?{:;:{:';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11{:{;(;:{:,~.
share|improve this answer

Postscript

This was a fun one

/cvx /cvx cvx /exec /exec cvx /dup /rand /mod /get /== /array /astore /realtime
/srand /repeat 6 17 54 17 /array cvx exec /astore cvx exec 54 /dup cvx /rand
cvx 17 /mod cvx /get cvx /== cvx 6 /array cvx exec /astore cvx exec cvx /realtime
cvx exec /srand cvx exec /repeat cvx exec

There are 17 unique tokens and 54 tokens total for approx 1 in 3.6e-67 chance.

share|improve this answer

Perl, 27 tokens, P = 1.4779 x 10-34

@ARGV=$0;print$W[rand@W]for@W=split/(\W)/,readline

Last edit: use @ARGV=$0 instead of open*ARGV,$0 to save a token.

  • 15 unique tokens
  • 4 tokens appear 2 times (=, /, @, $)
  • 1 token appears 4 times (W)

So I think that makes the probability (pow(2,2*4) * pow(4,4))/pow(27,27), about 1.48E-34.

If the source code is in a file called ARGV, then you can use this 26 token solution with P =~ 2.193 x 10-31:

@ARGV=ARGV;print$ARGV[rand@ARGV]for@ARGV=split/(\W)/,readline
share|improve this answer
    
Actually, P = (4 * 2! + 4!) / 27!, which is around 1.7632684538487448 x 10^-26 –  Mathieu Rodic Mar 25 at 8:47

Whitespace, 3^-205 3^-189 3^-181 3^-132 ~= 10^-63

This is a Whitespace program that, when seeded with random characters, has a 1 in 3^132 chance of reproducing itself (3 distinct tokens, repeated 132 times). It must be seeded with at least 132 random characters when run, (Whitespace has no built-in random or date function to seed with) e.g. some_whitespace_interpreter my_quine.ws <some_random_source >quine_output.ws. The score would be improved if the program could be golfed any more, but this is my first "real" Whitespace program, so I'll just leave it with my meager amount of golfing.

Plain Whitespace code, or see it run: (to try it, click "edit", copy the stuff inside the <pre> tags; should be 132 characters with Unix-style EOL)

    

























Code annotated with what command is what (not technically a quine, as it won't reproduce the comments):

stack push_number + 0 end
stack push_number + 1   0 0 1   end
heap        store stack push_number + 1 end
stack push_number + 1   0 0 0 0 0 end
heap        store stack push_number + 1 0 end
stack push_number + 1   0 1 0 end
heap        store stack push_number + 1 0 0 0 0 0 1 1   end
flow
make_label  loop_begin  
stack push_number + 1   1   end
IO  
read    character stack push_number + 1 1   end
heap        retrieve    stack push_number + 1   1   end
arithmetic   modulo     heap        retrieve    IO  
print char stack push_number + 1    end
arithmetic   subtract   stack duplicate
 flow
jump_if_zero        end_prog
flow
jump_to 
loop_begin  
flow
make_label  end_prog
flow
end_program

If the seed just happens to be equivalent (the characters are taken mod 3 to be converted to the tokens) to this, it will succeed:

CCCCACCCBCCBABBCCCCBACCCBCCCCCABBCCCCBCACCCBCBCABBCCCCBCCCCCBBAACCBACCCBBABABCCCCBBABBBCCCBBABCBBBBBBACCCCCBABCCBCACABBAACABAACCAAAA

It's a pretty simple program, roughly equivalent to this Ruby program:

i = 131
while true
    print '\t \n'[STDIN.getc.ord % 3]
    i = i - 1
    break if i < 0
end
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.