The Random Quine

15

Écrivez un programme capable de se générer aléatoirement.

Il doit le faire en fonction des jetons utilisés dans son code source. Si le code source de votre programme est composé de 50 jetons uniques et a une longueur de 60 jetons, alors le programme devrait produire 60 jetons où chaque jeton est choisi au hasard parmi l'un des 50 jetons uniques.

Par exemple, ce programme aurait une chance sur 50 ^ 60 de se reproduire.

Qu'est-ce qu'un jeton? Cela dépend de la langue. Par exemple, les identifiants ( foo_bar), les mots-clés ( while) et les nombres ( 42) comptent comme des jetons dans la plupart des langues. Les espaces blancs ne comptent pas dans la plupart des langues.

Règles supplémentaires:

  • La sortie ne peut contenir que des jetons trouvés dans le code source du programme, séparés par le délimiteur approprié
  • La sortie doit être de la même longueur que le code source du programme, comptée par les jetons
  • Un seul langage de programmation peut être utilisé
  • Le code source doit avoir au moins 3 jetons uniques
  • Exclure des commentaires du code source
  • Le programme ne devrait avoir qu'une chance sur U ^ L de se reproduire

Notation: le programme qui a les meilleures chances de se reproduire gagne.

code-challenge quine Austin Henley
la source
@MathieuRodic: Vous supposez que le programme dessine des jetons sans répétition.
user2357112 prend en charge Monica
@MathieuRodic: Permettez-moi de reformuler. Vous supposez que le programme brouille au hasard le multiset de ses jetons, plutôt que de dessiner des jetons L avec répétition à partir de l'ensemble des jetons U utilisés dans sa source.
user2357112 prend en charge Monica
@ user2357112: Je vois. Mon erreur a été de considérer ce problème comme un match nul sans remplacement.
Mathieu Rodic
1
Les règles # 1 et # 5 me semblent en contradiction.
Cruncher
4
Pouvez-vous supposer que les fonctions aléatoires intégrées sont des TRNG? Les implémentations typiques ont des graines trop petites pour produire toutes les sorties et pourraient donc être incapables de se régénérer.
CodesInChaos

Réponses:

11

Python 2, 3 ^ -3 = 0,037

execl'abus est assez pratique pour réduire le nombre de jetons. Maintenant mis à jour pour ne pas lire le fichier source!

exec '' """
s = '''{a}
s = {b}
s = s.format(a='"'*3, b="'"*3+s+"'"*3)
import random
tokens = ['exec', "''", s]
print random.choice(tokens), random.choice(tokens), random.choice(tokens),
{a}'''
s = s.format(a='"'*3, b="'"*3+s+"'"*3)
import random
tokens = ['exec', "''", s]
print random.choice(tokens), random.choice(tokens), random.choice(tokens),
"""

Le supplément ''entre execet la chaîne géante entre guillemets triples consiste simplement à remplir le nombre de jetons au minimum requis de 3. Il est fusionné dans la deuxième chaîne en raison de la concaténation implicite littérale de la chaîne.

Version originale, ouverture du fichier source:

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),
'''

À proprement parler, la grammaire Python place un jeton ENDMARKER à la fin du fichier source, et nous ne pouvons pas produire un fichier source avec ENDMARKERs aléatoirement éparpillés. Nous prétendons que cela n'existe pas.

user2357112 prend en charge Monica
la source
@Cruncher C'est la probabilité. 3 ^ -3 == 1/3 ^ 3
Austin Henley
2
+1 pour un hack brillant des règles. La même idée mise en œuvre en J: ".]';(?3 3 3){]`".;~({:,],{:,],6#{:)'';(?3 3 3){]`".;~({:,],{:,],6#{:)'''''''.
algorithmshark
5

Javascript, 102 jetons, 33 uniques, 7,73 × 10-154

Remarque, ceci est une vraie quine. Il ne lit pas le fichier ni n'utilise evalouFunction.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)
aebabis
la source
4

Python: P (programme de génération en 1 essai) = 3.0317 * 10 ^ -123

34 jetons uniques, 80 jetons au total. Notez qu'il y a un espace à la fin de chaque ligne.

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

Exemple de sortie:

' ' 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

Merci à l'autre solution Python de user2357112 pour m'avoir rappelé de jeter le dernier jeton et d'utiliser __file__ce que j'ignorais auparavant.

Kaya
la source
3

J - 1 à 11 17 = 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 a un tas de petits outils pratiques pour faire ce genre de travail.

  • Tout d'abord, toute chaîne de nombres séparés par des espaces est un jeton . Cela signifie un tableau unidimensionnel de ces nombres. C'est ainsi que fonctionne le lexer de J. Soit dit en passant, c'est dix-sept 11, si quelqu'un est curieux.

  • (,,,{:,{:)'QUINE'''est une astuce courante en J, conçue pour utiliser le moins de jetons possible: {:signifie Tail , donc il ajoute la chaîne à lui-même, puis ajoute deux copies du dernier caractère à la fin de cela. Puisque le dernier caractère est un guillemet simple (J utilise des chaînes de style Pascal), le résultat est QUINE'QUINE'''.

  • ;:est un tokenizer, et décompose une chaîne d'entrée comme si c'était du code J, renvoyant une liste de cases. La longueur de ce résultat est de 17.

  • ~.prend tous les éléments uniques de ce tableau. La longueur de ce résultat est de 11.

  • ?s'appelle Roll . Pour chaque entier de son argument, il sélectionne un nombre positif aléatoire supérieur ou égal à zéro, inférieur à ce nombre. Donc ici, J va générer 17 nombres de 0 à 10 inclus.

  • { utilise les indices aléatoires pour sélectionner des éléments de notre liste de jetons uniques dans des boîtes.

  • ; ouvre toutes ces boîtes et exécute le résultat ensemble.

Quelques exemples suivent. Les lignes en retrait sont les invites d'entrée et les lignes alignées avec le côté gauche sont la sortie de l'interpréteur.

   ;(?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{:{;(;:{:,~.
algorithmshark
la source
2

Postscript

C'était amusant

/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

Il y a 17 jetons uniques et 54 jetons au total pour environ 1 chance sur 3,6e-67.

Geoff Reedy
la source
2

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

Il s'agit d'un programme Whitespace qui, lorsqu'il est semé de caractères aléatoires, a une chance de 1 sur 3 ^ 132 de se reproduire (3 jetons distincts, répétés 132 fois). Il doit être ensemencé avec au moins 132 caractères aléatoires lors de son exécution (l'espace blanc n'a pas de fonction aléatoire ou de date intégrée pour l'amorçage), par exemple some_whitespace_interpreter my_quine.ws <some_random_source >quine_output.ws. Le score serait amélioré si le programme pouvait être joué au golf plus longtemps, mais c'est mon premier "vrai" programme Whitespace, donc je vais le laisser avec ma maigre quantité de golf.

Code d'espace blanc clair, ou voyez-le s'exécuter : (pour l'essayer, cliquez sur "modifier", copiez le contenu à l'intérieur des balises <pre>; devrait être 132 caractères avec EOL de style Unix)

Code annoté avec quelle commande est quoi (pas techniquement un quine, car il ne reproduira pas les commentaires):

pile push_number + 0 end
stack push_number + 1 0 0 1 end
tas de magasin de tas push_number + 1 end
pile push_number + 1 0 0 0 0 0 end
tas de magasin de tas push_number + 1 0 end
pile push_number + 1 0 1 0 end
pile de magasin de tas push_number + 1 0 0 0 0 0 1 1 end
couler
make_label loop_begin  
stack push_number + 1 1 end
IO  
lire la pile de caractères push_number + 1 1 end
tas récupérer la pile push_number + 1 1 end
tas modulo arithmétique récupérer IO  
imprimer la pile de caractères push_number + 1 end
arithmétique soustraire la pile en double
 couler
jump_if_zero end_prog
couler
sauter à 
loop_begin  
couler
make_label end_prog
couler
end_program

Si la graine se trouve être équivalente (les personnages sont pris mod 3 pour être convertis en jetons), cela réussira:

CCCCACCCBCCBABBCCCCBACCCBCCCCCABBCCCCBCACCCBCBCABBCCCCBCCCCCBBAACCBACCCBBABABCCCCBBABBBCCCBBABCBBBBBACCCCCBABCCBCACABBAACABAACCAAAA

C'est un programme assez simple, à peu près équivalent à ce programme Ruby:

i = 131
while true
    print '\t \n'[STDIN.getc.ord % 3]
    i = i - 1
    break if i < 0
end
Tim S.
la source
1

Perl, 27 jetons, P = 1,4779 x 10 -34

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

Dernière modification: utilisez @ARGV=$0au lieu de open*ARGV,$0pour enregistrer un jeton.

  • 15 jetons uniques
  • 4 jetons apparaissent 2 fois ( =, /, @, $)
  • 1 jeton apparaît 4 fois ( W)

Je pense donc que cela rend la probabilité (pow (2,2 * 4) * pow (4,4)) / pow (27,27), environ 1,48E-34.

Si le code source se trouve dans un fichier appelé ARGV, vous pouvez utiliser cette solution à 26 jetons avec P = ~ 2.193 x 10 -31 :

@ARGV=ARGV;print$ARGV[rand@ARGV]for@ARGV=split/(\W)/,readline
foule
la source
En fait, P = (4 * 2! + 4!) / 27!qui se situe aux alentours de 1,7632684538487448 x 10 ^ -26
Mathieu Rodic
0

Perl 6 ,1 dans 33 = 0,037037 ...

(Je sais que ce n'est pas du golf de code, mais ...)

q[say |roll <<~~"q[$_]".EVAL>>: 3]~~.EVAL

Essayez-le en ligne!

Tout comme la réponse Python, où le premier jeton est un littéral de chaîne évalué. Les jetons sont

q[say |roll <<~~"q[$_]".EVAL>>: 3]   String literal
~~                                   Smartmatch operator
.EVAL                                Function call

Explication:

q[say |roll <<~~"q[$_]".EVAL>>: 3]         # Push as string literal
                                  ~~       # Smartmatch by setting $_ to the string literal
                                    .EVAL  # Eval the string
            <<~~"q[$_]".EVAL>>             # From the list of tokens
       roll                   : 3          # Pick 3 times with replacement
  say |                                    # Join and print
Jo King
la source