Quine Acak

15

Tulis sebuah program yang mampu menghasilkan sendiri secara acak.

Itu harus melakukan ini berdasarkan token yang digunakan dalam kode sumbernya. Jika kode sumber program Anda terdiri dari 50 token unik dan panjangnya 60 token, maka program harus menampilkan 60 token di mana setiap token dipilih secara acak dari salah satu dari 50 token unik.

Sebagai contoh, program ini akan memiliki kesempatan satu dalam 50 ^ 60 untuk mereproduksi dirinya sendiri.

Apa itu token? Itu tergantung pada bahasanya. Misalnya, pengidentifikasi ( foo_bar), kata kunci ( while), dan angka ( 42) akan dihitung sebagai token dalam sebagian besar bahasa. Spasi tidak akan dihitung dalam sebagian besar bahasa.

Aturan tambahan:

  • Output hanya dapat berisi token yang ditemukan dalam kode sumber program, dipisahkan oleh pembatas yang sesuai
  • Output harus sama panjang dengan kode sumber program, dihitung dengan token
  • Hanya satu bahasa pemrograman yang dapat digunakan
  • Kode sumber harus memiliki setidaknya 3 token unik
  • Kecualikan komentar dari kode sumber
  • Program seharusnya hanya memiliki satu di U ^ L kesempatan untuk mereproduksi dirinya sendiri

Penilaian: Program yang memiliki peluang terbaik untuk mereproduksi dirinya sendiri, menang.

code-challenge quine Austin Henley
sumber
@MathieuRodic: Anda mengasumsikan bahwa program menarik token tanpa pengulangan.
user2357112 mendukung Monica
@MathieuRodic: Biarkan saya ulangi. Anda menganggap program secara acak mengacak multiset tokennya, daripada menggambar token L dengan pengulangan dari set token U yang digunakan dalam sumbernya.
user2357112 mendukung Monica
@ user2357112: Begitu. Kesalahan saya adalah menganggap masalah ini sebagai hasil imbang tanpa penggantian.
Mathieu Rodic
1
Aturan # 1 dan # 5 tampaknya bertentangan dengan saya.
Cruncher
4
Dapatkah Anda berasumsi bahwa fungsi acak yang dibangun adalah TRNG? Implementasi yang khas memiliki benih terlalu kecil untuk menghasilkan semua output dan dengan demikian mungkin tidak dapat benar-benar regenerasi sendiri.
CodesInChaos

Jawaban:

11

Python 2, 3 ^ -3 = 0,037

execpenyalahgunaan cukup berguna untuk mengurangi jumlah token. Sekarang diperbarui untuk tidak membaca file sumber!

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

Ekstra ''antara execdan string tiga kutip raksasa hanya untuk menambah jumlah token ke minimum yang diperlukan 3. Ia digabungkan ke dalam string kedua karena konkatasi literal string implisit.

Versi asli, membuka-sumber-file:

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

Sebenarnya, tata bahasa Python menempatkan token ENDMARKER di akhir file sumber, dan kami tidak dapat menghasilkan file sumber dengan ENDMARKER yang berserakan secara acak. Kami berpura-pura itu tidak ada.

user2357112 mendukung Monica
sumber
@Cruncher Itulah probabilitasnya. 3 ^ -3 == 1/3 ^ 3
Austin Henley
2
+1 untuk peretasan aturan yang brilian. Ide yang sama diterapkan di J: ".]';(?3 3 3){]`".;~({:,],{:,],6#{:)'';(?3 3 3){]`".;~({:,],{:,],6#{:)'''''''.
algoritme
5

Javascript, 102 token, 33 unik, 7,73 × 10 -154

Catatan, ini adalah quine yang sebenarnya. Itu tidak membaca file atau menggunakan evalatauFunction.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
sumber
4

Python: P (menghasilkan program dalam 1 percobaan) = 3.0317 * 10 ^ -123

34 token unik, 80 total token. Perhatikan bahwa ada spasi di akhir setiap baris.

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

Output sampel:

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

Berkat solusi Python lainnya oleh user2357112 untuk mengingatkan saya untuk membuang token terakhir dan menggunakan __file__yang sebelumnya saya tidak tahu.

Kaya
sumber
3

J - 1 dalam 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 memiliki banyak alat kecil yang berguna untuk menyelesaikan pekerjaan semacam ini.

  • Pertama-tama, setiap string angka yang dipisahkan spasi adalah satu token . Ini berarti array satu dimensi dari angka-angka itu. Inilah cara kerja lexer J. Omong-omong, itu tujuh belas 11, jika ada yang penasaran.

  • (,,,{:,{:)'QUINE'''adalah trik quine umum dalam J, dibuat untuk menggunakan token sesedikit mungkin: {:berarti Tail , sehingga menambahkan string ke dirinya sendiri, dan kemudian menambahkan dua salinan karakter terakhir ke akhir itu. Karena karakter terakhir adalah kutipan tunggal (J menggunakan string gaya Pascal), hasilnya adalah QUINE'QUINE'''.

  • ;:adalah tokenizer, dan memecah string input seolah-olah itu kode J, mengembalikan daftar kotak. Panjang hasil ini adalah 17.

  • ~.mengambil semua elemen unik dari array ini. Panjang hasil ini adalah 11.

  • ? disebut Roll . Untuk setiap bilangan bulat dalam argumennya, ia memilih angka positif acak lebih besar dari atau sama dengan nol, kurang dari angka itu. Jadi di sini J akan menghasilkan 17 angka dari 0 hingga 10 inklusif.

  • { menggunakan indeks acak untuk memilih item dari daftar token-in-box unik kami.

  • ; buka semua kotak ini dan jalankan hasilnya bersamaan.

Beberapa contoh mengikuti. Garis indentasi adalah prompt input, dan garis flush dengan sisi kiri adalah output interpreter.

   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
~.~.(?;;:11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''(){11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){(;:;
   ;(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''
{';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)''',?{:;:{:';(?11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11){~.;:(,,,{:,{:)'''11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11{:{;(;:{:,~.
algoritme hiu
sumber
2

Nota bene

Ini menyenangkan

/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

Ada 17 token unik dan 54 token total untuk sekitar 1 dalam kesempatan 3.6e-67.

Geoff Reedy
sumber
2

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

Ini adalah program Whitespace yang, ketika diunggulkan dengan karakter acak, memiliki peluang 1 banding 3 ^ 132 untuk mereproduksi dirinya sendiri (3 token berbeda, diulang 132 kali). Itu harus diunggulkan dengan setidaknya 132 karakter acak saat dijalankan, (Whitespace tidak memiliki fungsi tanggal atau acak bawaan untuk di-seed dengan) mis some_whitespace_interpreter my_quine.ws <some_random_source >quine_output.ws. Skor akan ditingkatkan jika program bisa golf lagi, tapi ini adalah program Whitespace "nyata" pertama saya, jadi saya akan meninggalkannya dengan jumlah golf yang sedikit.

Kode Ruang Kosong Biasa, atau lihat dijalankan : (untuk mencobanya, klik "edit", salin hal-hal di dalam tag <pre>; harus 132 karakter dengan EOL gaya Unix)

Kode dijelaskan dengan perintah apa adalah apa (tidak secara teknis quine, karena tidak akan mereproduksi komentar):

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 1 1 end
mengalir
make_label loop_begin  
stack push_number + 1 1 end
IO  
baca tumpukan karakter push_number + 1 1 ujung
heap ambil stack push_number + 1 1 end
modulo tumpukan heap mengambil IO  
cetak char stack push_number + 1 end
kurangi hitung tumpukan duplikat
 mengalir
jump_if_zero end_prog
mengalir
jump_to 
loop_begin  
mengalir
make_label end_prog
mengalir
end_program

Jika seed kebetulan sama (karakter diambil mod 3 untuk dikonversi ke token) untuk ini, itu akan berhasil:

CCCCACCCBCCBABBCCCCBACCCBCCCCCABBCCCCBCACCCBCBCBBCCCCBBCCCCBBCCACCBACCCBBABABCCCCBBABBBBBBBBBBBBBCCBBBBBBBBCCBBBBBBBBBCCBBBBBBBBBABBBBCCBCACABBAACABAAAAAAA

Ini adalah program yang sangat sederhana, kira-kira setara dengan program Ruby ini:

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

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

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

Edit terakhir: gunakan @ARGV=$0alih-alih open*ARGV,$0menyimpan token.

  • 15 token unik
  • 4 token muncul 2 kali ( =, /, @, $)
  • 1 token muncul 4 kali ( W)

Jadi saya pikir itu membuat probabilitas (pow (2,2 * 4) * pow (4,4)) / pow (27,27), sekitar 1,48E-34.

Jika kode sumber dalam file bernama ARGV, maka Anda dapat menggunakan solusi token 26 ini dengan P = ~ 2.193 x 10 -31 :

@ARGV=ARGV;print$ARGV[rand@ARGV]for@ARGV=split/(\W)/,readline
massa
sumber
Sebenarnya,, P = (4 * 2! + 4!) / 27!yaitu sekitar 1,7632684538487448 x 10 ^ -26
Mathieu Rodic
0

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

(Saya tahu ini bukan kode-golf, tapi ...)

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

Cobalah online!

Sama seperti jawaban Python, di mana token pertama adalah string literal yang dievaluasi. Tokennya adalah

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

Penjelasan:

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
sumber