Menghasilkan Brainf *** NOP

26

Terkadang saat menulis kode brainfuck, Anda merasa perlu membuatnya lebih lama dari yang dibutuhkan untuk mendorong debugging. Anda bisa melakukannya dengan hanya memasukkannya ><ke sana, tetapi apa yang menyenangkan itu? Anda akan memerlukan sesuatu yang lebih lama dan lebih sedikit TIDAK untuk membingungkan siapa pun yang membaca kode Anda.

Pengantar cepat untuk Brainfuck

Brainfuck adalah bahasa pemrograman esoterik yang dibuat pada tahun 1993 oleh Urban Müller, dan terkenal karena minimalisnya yang ekstrem. (Wikipedia)

Brainfuck adalah bahasa berdasarkan delapan perintah: +-><,.[]. Kode dijalankan pada sesuatu seperti mesin Turing: rekaman tak terbatas yang nilainya dapat diubah. Dalam tantangan ini, kita akan fokus pada empat yang pertama:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

Brainfuck NOPs

NOP brainfuck adalah urutan karakter brainfuck yang, ketika dieksekusi dari negara bagian manapun, menyebabkan tidak ada perubahan di negara bagian. Mereka terdiri dari empat karakter yang disebutkan di atas.

Tantangan

Tantangannya adalah untuk menulis program atau fungsi yang, ketika dieksekusi, menghasilkan NOP brainfuck acak dari panjang yang diberikan.

Memasukkan

Anda akan menerima sebagai bilangan bulat genap nonnegatif n. (NOP tidak mungkin untuk aneh n.)

Keluaran

Anda akan menghasilkan NOP brainfuck acak panjangnya n.

Aturan

  • Definisi NOP: ketika output dari program dimasukkan pada titik mana pun dalam program brainfuck, perilaku program tersebut tidak boleh berubah dengan cara apa pun. Dengan kata lain, itu tidak boleh mengubah keadaan penerjemah.
    • Perhatikan bahwa misalnya +>-<tidak benar, karena mengubah nilai dari dua sel tanpa mengubahnya kembali. Silakan uji solusi Anda untuk ini sebelum memposting.
    • Perhatikan juga bahwa itu +>-<->+<adalah NOP yang tidak dapat direduksi menjadi tidak ada hanya dengan menghapus >< <> +- -+. Dengan demikian, Anda tidak dapat menggunakan algoritma yang hanya menyisipkan ini di dalam satu sama lain.
  • Setiap NOP yang valid dengan panjang nharus memiliki peluang nol muncul di output. Namun, distribusinya tidak harus seragam.
  • Penerjemah brainfuck yang dimaksud memiliki rekaman sel presisi arbitrer tak terbatas dua kali lipat. Artinya, Anda dapat pergi tanpa batas ke kedua arah, dan menambah / mengurangi setiap sel tanpa batas.
  • Program harus selesai dalam 1 menit untuk n= 100 pada mesin saya, jadi tidak menghasilkan semua NOP yang mungkin dan mengambilnya.
  • Jika diberi input yang tidak valid (non-integer, negatif, ganjil, dll.) Anda dapat melakukan apa saja yang Anda suka, termasuk crash.

Mencetak gol

Ini adalah , jadi jawaban tersingkat dalam byte menang.

Contohnya

Berikut ini semua output yang valid untuk n= 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Berikut adalah beberapa kemungkinan keluaran untuk n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
sumber
18
inilah NOP brainfuck yang tidak digunakan +-<>seperti yang Anda minta:a
undergroundmonorail
1
Saya rasa NOP non-sederhana ada, jadi Anda mungkin dapat menghapus kualifikasi itu. .memiliki efek samping, ,menimpa nilai yang tidak dapat dipulihkan tanpa penggunaan []. Tetapi []akhirnya akan menetapkan nilai ke nol. Ini juga menimpa nilai (jadi kita perlu yang lain []untuk memulihkannya) kecuali kita bisa yakin bahwa sel yang terpengaruh nol untuk memulai. Namun, kami harus mencari sel seperti [>]itu dengan sesuatu seperti , dan mustahil untuk kembali ke posisi asal kami.
Martin Ender
4
@Eumel "Penerjemah brainfuck yang dipermasalahkan memiliki sel tak beraturan ganda yang tak terbatas."
Martin Ender
2
Harap dicatat bahwa "Brainfuck" tidak lagi diizinkan dalam judul pertanyaan di tingkat sistem. Tampaknya Anda dapat menghindari pembatasan dengan menggunakan karakter non-ASCII. Di masa depan, harap patuhi pembatasan ini.
Alex A.
2
@undergroundmonorail Ya, ini Turing lengkap ... jadi secara teknis orang bisa menulis PRNG di dalamnya sama seperti bahasa lainnya. (Meskipun penyemaian mungkin sulit.)
PurkkaKoodari

Jawaban:

13

CJam, 62 59 byte

Terima kasih kepada nhahtdh karena telah menghemat 3 byte.

Karena tidak ada persyaratan untuk distribusi tertentu selama masing-masing no-op muncul dengan probabilitas terbatas, kita dapat menyederhanakan ini banyak dengan hanya menghasilkan string yang mengandung jumlah seimbang -+dan <>, masing-masing, menguji apakah itu NOP dan mengurutkannya jika bukan.

Tentu saja, untuk input yang lebih panjang, ini hampir selalu akan menghasilkan output yang diurutkan, tetapi Anda dapat menguji kode dengan beberapa input ingin 8melihat bahwa pada prinsipnya dapat menghasilkan NOP dari panjang yang diberikan.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Cobalah online.

Martin Ender
sumber
1
Ya ... batas sewenang-wenang seharusnya n = 1000 di bawah 10 detik. Komputer hanyalah cara untuk berpuasa hari ini ^^ Karena jawaban algoritmik menyelesaikannya dalam waktu kurang dari satu detik bahkan untuk n = 1000
Falco
Untuk n yang lebih besar, saya pikir mungkin untuk hanya mengurutkan output jika string seimbang bukan NOP. Distribusi sangat miring, tetapi diizinkan oleh pertanyaan.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ itu ide yang bagus.
Martin Ender
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Terima kasih, itu sebenarnya menyimpan tiga byte di sini juga.
Martin Ender
16

CJam, 118 116 byte

Ini sedikit keluar dari tangan ... terutama paruh kedua sepertinya harus sangat golf.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Uji di sini.

Ini menangani N = 100hampir seketika. Saya tidak punya waktu untuk menulis uraian lengkap kode sekarang, jadi di sini adalah algoritma:

  • Hasilkan string seimbang acak dari <dan >dengan panjang acak (datar) antara 0dan Ninklusif.
  • Riffle posisi kepala kaset ke dalam array ini. Misalnya "<>><"menjadi [0 '< -1 '> 0 '> 1 '< 0].
  • Dapatkan daftar semua posisi yang dicapai dalam proses.
  • Untuk setiap posisi seperti inisialisasi string kosong. Juga tentukan berapa banyak pasangan karakter yang tersisa untuk mencapai serangkaian panjang N.
  • Untuk setiap pasangan yang tersisa tambahkan +-ke string posisi acak.
  • Kocok semua string itu.
  • Untuk setiap posisi, tentukan seberapa sering posisi itu terjadi dalam array yang di-riffled, dan pisahkan string yang sesuai menjadi banyak potongan (panjang acak).
  • Dalam array yang di-riffle, gantilah kemunculan posisi dengan potongan acaknya.

Selesai Ini berdasarkan pengamatan bahwa:

  • Setiap NOP harus memiliki jumlah <dan> untuk mengembalikan kepala kaset ke posisi semula.
  • Kode akan menjadi NOP selama masing-masing sel kaset bertambah sesering dikurangi.

Dengan mendistribusikan jumlah +s dan -s yang acak namun seimbang antara semua tempat di mana kepala pita berada pada sel tertentu, kami memastikan bahwa kami menemukan setiap NOP yang memungkinkan.

Martin Ender
sumber
4

Mathematica, 350 byte

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Terlalu lama? Iya nih. Apakah saya peduli? Tidak sampai orang lain memposting jawaban yang valid.

LegionMammal978
sumber
4
Maukah Anda menambahkan penjelasan, sehingga orang benar-benar dapat meyakinkan diri sendiri bahwa ini valid? :)
Martin Ender
Bagaimana tepatnya cara kerjanya? Jika saya memanggil fungsi dengan nomor itu hanya mengembalikan +.
Martin Ender
@ MartinBüttner Tetap ... Saat ini, itu hanya menghasilkan program acak dengan jumlah +- -dan <- >pasangan yang sama sampai satu menjadi NOP. Setengahnya diambil oleh juru bahasa BF sederhana.
LegionMammal978
apakah itu benar-benar menghasilkan no-op panjang 100 yang valid di bawah satu menit?
Martin Ender
@ MartinBüttner Ya. Rata-rata, saya akan mengatakan bahwa dibutuhkan sekitar 5 detik. Pada awalnya, saya mencoba program yang benar-benar acak, tetapi tidak pernah berakhir untuk panjang 100.
LegionMammal978
2

Python 3 , 177 byte

from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

Cobalah online!

Saya menggunakan kode dari jawaban Bubbler untuk simulasi BF.

Tyilo
sumber
2

Python 3 , 163 byte

from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

Cobalah online!

Program lengkap yang mencetak hasil ke STDOUT. Baris yang menjalankan kode BF mungkin golf.

Mengadopsi pendekatan Tyilo; jika kode BF yang dihasilkan bukan NOP, buang semuanya dan kembalikan ke '+-'berulang.

Bubbler
sumber
Batas waktu untuk n = 100
l4m2
@ l4m2 Tidak memperhatikan persyaratan itu. Tetap.
Bubbler
1

JavaScript (Node.js) , 160 byte

n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r

Cobalah online!

l4m2
sumber
1

Bahasa Wolfram (Mathematica) , 224 byte

(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

Cobalah online!

Berikut ini versi un-golfed (atau lebih tepatnya, pre-golfed):

Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]], 
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

Kami pertama-tama memilih jumlah acak dari <dan >untuk digunakan, dan menghasilkan daftar acak dengan masing-masing jumlah yang sama.

Untuk mengisi sisa karakter, kami memilih posisi untuk menambahkan +, kemudian menemukan posisi di mana penunjuk menunjuk ke lokasi yang sama dan menambahkan di -sana.

Ulangi sampai daftar memiliki panjang n, dan tegangkan hasilnya.

Misha Lavrov
sumber