Brainf *** subprogram dengan output unik

19

Anda harus menulis program 100 byte brainfuck panjang (BF).

Satu karakter akan dihapus dari itu dalam setiap cara yang mungkin 100 program baru (panjang 99 byte) yang dihasilkan. Misalnya untuk program ++.>.5 subprogram yang +.>., +.>., ++>., ++..dan ++.>.

Skor Anda akan menjadi jumlah output unik yang dihasilkan 100 program. Skor yang lebih tinggi lebih baik.

Detail

  • Program Anda akan dihentikan setelah mengeluarkan karakter pertama.
  • Program dan program yang tidak berhenti atau tidak berakhir yang menghasilkan output kosong tidak diperhitungkan dalam skor.
  • Sel BF adalah sel pembungkus 8 bit. (255 + 1 = 0, 0-1 = 255)
  • Program Anda tidak diberi input. Jika Anda menggunakan ,dalam kode itu mengatur sel saat ini menjadi 0.
  • Tidak ada sel di sisi kiri dari posisi awal. Misalnya <.tidak valid tetapi .<valid karena eksekusi dihentikan pada .. Rekaman itu tidak terikat ke arah lain.
  • Program dengan tanda kurung tidak seimbang ( [dan ]) tidak valid.
  • Program asli Anda bisa lebih pendek dari 100 byte karena mudah untuk memperpanjangnya menjadi 100 byte tanpa mengubah skor.
  • Program asli Anda tidak harus kode BF yang valid.

Anda dapat menggunakan program python3 ini (tautan ideone) untuk menentukan skor jawaban Anda. (Untuk program jangka panjang Anda mungkin perlu memodifikasi maxstepvariabel.)

Contoh

(Untuk kesederhanaan, program ini lebih pendek dari 100 byte.)

Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]    
Score is 3 for ++,+[-]+><.-,-. (length = 15)

Dalam hal seri, pemenangnya adalah yang memiliki kode pendek. (Program Anda bisa lebih pendek dari 100 byte seperti yang dinyatakan di bagian Detail.) Jika kode panjangnya sama, pemenangnya adalah poster sebelumnya.

Teka-teki bonus: tanpa batasan tebal dapatkah Anda menemukan program dengan skor 100?

randomra
sumber
Saya memecahkan puzzle bonus; jawabannya adalah (disensor).
AJMansfield
@AJMansfield Bisakah Anda mengedit komentar Anda sehingga orang lain bisa memikirkan teka-teki itu juga? Misalnya, ubah solusi Anda ke tautan pastebin.com yang berisi jawabannya.
randomra
3
Hmm. Saya menulis pengoptimal genetik untuk pertanyaan ini untuk mencoba menemukan perbaikan mikro untuk jawaban yang ada, tetapi sejauh ini tidak terlalu berhasil. Mereka terjebak di 79 dan 43 masing-masing. Ah well — itu layak dicoba!
wchargin

Jawaban:

12

Nilai: 35 41 69 78 79 83

(Hapus baris baru.)

-->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>-
>+>->+>->+>->+>->+>->+>->+>->+>++[>[-<+++>]<<++]>.

Cobalah online!

Saya tidak yakin persis mengapa itu bekerja ...

Nilai: 79

X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

Cobalah online!

Itu seharusnya jumlah 2 * mem [i] * i dan menambahkan jumlah sel (+ const) di mana alamat dihitung dari kanan ke kiri. Pengganda 2 dan jumlah sel dapat membuat penghapusan + dan> memiliki paritas yang berbeda.

Itu memang bekerja seperti itu di versi 69 poin. Tetapi versi terbaru memecahkannya dan mendapatkan sesuatu yang lain secara kebetulan. Ini menghitung jumlah (mem [i] * i + i + 1) dan menghapus + dan> melakukan hampir sama, kecuali untuk jumlah (i) yang memiliki perbedaan jumlah sel, yang juga merupakan jumlah output yang berbeda untuk menghapus + dan>.

Untuk bonus:

+. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +.

jimmy23013
sumber
Catatan: jika Anda menguji ini dengan program pencetak skor yang disediakan pastikan untuk meningkatkan maxstepnilai (dalam def evaluate(r,maxstep=20000):) karena beberapa subprogram berjalan untuk waktu yang lama.
randomra
1
Skor sebenarnya dapat ditingkatkan 79dengan mengganti ->+>+> ...dengan->,>+> ...
BrainSteel
@ Trainrain Saya baru saja mengubahnya ke no-op.
jimmy23013
9

Nilai: 37 43

+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

EDIT: Sekarang program saya memungkinkan beberapa tanda kurung. Tidak akan memenangkan hadiah apa pun dengan itu, tapi itulah yang saya dapatkan karena membuat beberapa RNG tertimbang melakukan pekerjaan yang sibuk untuk saya.

Ini dihasilkan oleh program yang saya tulis dalam C.

Untuk setiap Nkarakter yang dihapus, berikut adalah hasilnya:

N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

Ada total 37 output unik, yaitu (dalam urutan numerik):

0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188, 
196, 206, 207, 209, 211, 249, 251, 255

Saya 90% 100% yakin solusi ini tidak optimal , tetapi membuktikan bahwa itu mungkin sangat sulit . Ada beberapa hal yang jelas. Tidak memiliki .simbol sampai karakter terakhir tampaknya menjadi cara untuk pergi , dan tanda kurung siku ([] ) tampaknya agak tidak berguna . Saya sedikit berpikir di sini, yang ingin saya uraikan:

Membiarkan Lmenjadi panjang kode dalam byte (dalam tantangan, 100), dann menjadi jumlah output unik dari sub program.

Untuk L=3, ada beberapa solusi yang optimal dari bentuk +-., di mana n=2(dalam hal ini, output adalah 1 dan 255 untuk +.dan -.masing-masing.) Puts ini rasio terbaik untuk L = 3di n/L = 66.67%. Perhatikan bahwa rasio ini setidaknya tidak dapat dikalahkan L<10.

Sebab L=10, solusinya cukup sederhana untuk menguatkannya. Berikut ini semua solusi terbaik, di n = 6:

++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

Yang menghasilkan rasio skor n/L = 60%.

Seperti L->infinity, jelas bahwa rasio harus mendekati 0, karena hanya ada 255 kemungkinan output untuk potensi yang tak terbatas L.

Rasio BUKAN, namun, menurun secara seragam. Tidak mungkin untuk membuat solusi n=6, L=9, jadi rasio terbaik untuk itu L=9adalah 5/9 = 55.56% < 60%.

Ini menimbulkan pertanyaan, seberapa cepat , dan dalam hal apa, rasionya turun? Untuk L = 100, dan pada 10^9 checks/second, dibutuhkan beberapa kali lipat lebih lama dari umur alam semesta untuk memperkuat solusi yang optimal. Apakah ada cara yang elegan untuk melakukan ini? Saya sangat meragukan bahwa itu adalah ke 37%untuk L = 100.

Rasio ini benar-benar meningkat, hingga L=100. Lihat jawaban lain untuk mengonfirmasi.

Saya ingin mendengar evaluasi Anda di atas. Lagipula, aku bisa salah besar.

BrainSteel
sumber