Golunar / Unary adalah cara untuk menyandikan semua program Brainfuck yang valid , tetapi ini bukan enumerasi, karena sebagian besar bilangan alami tidak sesuai dengan program yang valid.

Untuk tujuan tantangan ini, asumsikan rekaman ganda tak terbatas dan tidak ada komentar, yaitu, program Brainfuck valid jika dan hanya jika itu hanya terdiri dari karakter <>+-.,[]dan semua tanda kurung kiri dan kanan cocok.

Misalnya, program kosong ,[+][-].,, [>+<[--].]dan +[+[+][+[+]+]+]+.merupakan program Brainfuck yang valid, sementara ][, dan a[]tidak.

Tugas

Tulis program atau fungsi yang menerima program Brainfuck yang valid sebagai input dan kembalikan nomor alami ( 1 , 2 , 3 , ...), dengan batasan-batasan berikut:

• Output yang dihasilkan harus berbeda untuk semua program Brainfuck yang valid.

• Untuk setiap bilangan alami n , harus ada program Brainfuck yang valid yang, ketika diberikan sebagai input, menghasilkan output n .

Aturan tambahan

• Diberi program Brainfuck 100 atau kurang byte, program atau fungsi Anda harus selesai dalam satu menit.

  Ini berarti bahwa Anda tidak dapat mengulangi semua program Brainfuck yang valid hingga Anda mencocokkan input.

• Aturan standar kode-golf berlaku.

Python 3, 443 158 155 154 134 131 128 124 117 116 115 byte

c=d=C=D=0
for e in input():v='[<>,.-+]'.find(e);d=d*8+v;c+=c<0<6<v;c-=d>1>v;C,D=(c,C+1,d,D)[v>6::2]
print(-~D*8**C)

Beberapa byte berkat Sp3000 dan Mitch Schwartz: D

Bagaimana ini bekerja:

Ini memetakan semua program BF yang valid ke dalam semua program BF yang mungkin, valid, atau tidak valid, yang tidak dimulai dengan [rasio satu banding satu. Setelah itu, program baru diubah menjadi oktal.

Berikut adalah rumus pemetaannya:

1. Pisahkan program BF menjadi 3 bagian. Bagian pertama adalah awalan terbesar yang hanya terdiri dari [karakter. Bagian ketiga adalah postfix terbesar yang hanya terdiri dari ]karakter. Bagian kedua adalah tengah.
2. Buang bagian pertama. Ini dapat dihitung ulang nanti.
3. Hapus semua ]tanda kurung di bagian ketiga yang cocok dengan [tanda kurung di bagian kedua. Ini juga dapat dihitung ulang nanti.
4. Menggabungkan bagian kedua dan ketiga bersama-sama.

Jika Anda tidak mengerti penjelasan ini, Anda dapat menemukan penjelasan tambahan dalam obrolan yang dimulai di sini .

Untuk referensi, berikut adalah 20 program pertama:

1 : 
2 : <
3 : >
4 : ,
5 : .
6 : -
7 : +
8 : []
9 : <[]
10 : <<
11 : <>
12 : <,
13 : <.
14 : <-
15 : <+
16 : [<]
17 : >[]
18 : ><
19 : >>
20 : >,

Berikut adalah 1000 program pertama: http://pastebin.com/qykBWhmD
Ini adalah program yang saya gunakan untuk menghasilkannya: http://ideone.com/e8oTVl

Ini adalah Hello, World!:

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

Python 2, 157 byte

def f(s,o=0,d=0,D={}):T=s,o,d;x=D[T]=D[T]if T in D else~o and 0**o+sum(f(s[1:],cmp(c,"[")%-3-~o,d or cmp(c,s[0]))for c in"+,-.<>[]")if s else~d<0==o;return+x

Masih terlihat cukup golf, tapi saya memposting ini untuk saat ini. Ini menggunakan rekursi dengan sedikit caching. Yang menjengkelkan, D.gettidak ada hubungan pendek untuk caching, jadi saya tidak bisa menyimpan 9 byte seperti itu ...

Pemetaan memprioritaskan panjang pertama, kemudian urutan leksikografis atas pemesanan "][><.-,+"(lihat contoh output di bawah). Gagasan utamanya adalah membandingkan awalan.

Variabel omelacak jumlah [kurung masih terbuka untuk awalan saat ini, sementara variabel dmengambil salah satu dari tiga nilai yang menunjukkan:

• d = 1: Awalan saat ini secara leksikografis lebih awal dari s. Tambahkan semua program dengan awalan dan panjang ini <= s,
• d = -1: Awalan saat ini secara leksikografis lebih lambat dari s. Tambahkan semua program dengan awalan dan panjang ini < s.
• d = 0: Awalan saat ini adalah awalan dari s, jadi kami mungkin berubah dke 1 atau -1 nanti.

Sebagai contoh, jika kita memiliki s = "[-]"dan awalan kita saat ini p = "+", karena plebih lambat dari pada sleksikografis kita hanya tahu untuk menambahkan program yang dimulai dengan pyang lebih singkat dari itu s.

Untuk memberikan contoh yang lebih rinci, anggaplah kita memiliki program input s = "-[]". Ekspansi rekursif pertama melakukan ini:

  (o == 0)               # Adds a program shorter than s if it's valid
                         # For the first expansion, this is 1 for the empty program
+ f(s[1:], o=-1, d=1)    # ']', o goes down by one due to closing bracket
+ f(s[1:], o=1, d=1)     # '[', o goes up by one due to opening bracket
+ f(s[1:], o=0, d=1)     # '>'
+ f(s[1:], o=0, d=1)     # '<'
+ f(s[1:], o=0, d=1)     # '.', d is set to 1 for this and the previous branches
                         # since they are lexicographically earlier than s's first char
+ f(s[1:], o=0, d=0)     # '-', d is still 0 since this is equal to s's first char
+ f(s[1:], o=0, d=-1)    # ',', d is set to -1 for this and the later branches
                         # since they are lexicographically later than s's first char
+ f(s[1:], o=0, d=-1)    # '+'

Perhatikan bagaimana kita sebenarnya tidak menggunakan awalan dalam rekursi - semua yang kita pedulikan adalah ditangkap melalui variabel d, odan program input menyusut s. Anda akan melihat banyak pengulangan di atas - di sinilah caching masuk, memungkinkan kami untuk memproses program 100-ar dengan baik dalam batas waktu.

Ketika skosong, kita melihat (d>=0 and o==0), yang memutuskan apakah akan mengembalikan 1 (hitung program ini karena secara leksikografis awal / sama dan program itu valid), atau 0 (jangan hitung program ini).

Setiap situasi dengan o < 0segera kembali 0, karena setiap program dengan awalan ini memiliki lebih ]dari [, dan karenanya tidak valid.

20 output pertama adalah:

 1
> 2
< 3
. 4
- 5
, 6
+ 7
[] 8
>> 9
>< 10
>. 11
>- 12
>, 13
>+ 14
<> 15
<< 16
<. 17
<- 18
<, 19
<+ 20

Menggunakan contoh Hello World yang sama dengan jawaban @ TheNumberOne:

>>> f("++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.")
3465145076881283052460228065290888888678172704871007535700516169748342312215139431629577335423L

Python 2, 505 (tidak golf)

Saya menikmati mengembangkan pendekatan ini, tetapi saya mungkin tidak repot-repot bermain golf karena tidak kompetitif dibandingkan dengan pendekatan lain. Saya mempostingnya demi keberagaman dan kemungkinan minat estetika. Ini melibatkan rekursi dan sedikit matematika.

F={0:1}

def f(n):
    if n not in F:
        F[n]=6*f(n-1) + sum(f(i)*f(n-2-i) for i in range(n-1))

    return F[n]

def h(x):
    if x=='': return 0

    if len(x)==1: return '+-<>,.'.find(x)

    if x[0]!='[':
        return h(x[0]) * f(len(x)-1) + h(x[1:])

    d=i=1
    while d:
        if x[i]==']': d-=1
        elif x[i]=='[': d+=1
        i+=1

    a=i-2
    b=len(x)-i

    return 6*f(a+b+1) + sum(f(i)*f(a+b-i) for i in range(a)) + h(x[1:i-1]) * f(b) + h(x[i:])

def g(x):
    return sum(f(i) for i in range(len(x))) + h(x) + 1

print g(raw_input())

Fungsi f(n)menghitung jumlah program brainfuck yang valid dengan panjang n. h(x)program peta panjang nuntuk [0..f(n)-1], dan g(x)adalah fungsi peringkat bijective yang bersangkutan.

Gagasan utamanya adalah bahwa program yang tidak kosong dapat memulai dengan [atau dengan salah satu dari 6 []karakter yang bukan . Dalam kasus sebelumnya, kita dapat beralih pada kemungkinan lokasi pencocokan ]dan pengulangan pada bagian tertutup dan pada ekor (di mana ekor berarti substring mengikuti ]). Dalam kasus yang terakhir, kita dapat berulang pada ekor (di mana ekor berarti menjatuhkan karakter pertama). Alasan ini dapat digunakan baik untuk menghitung dan untuk peringkat komputasi.

Program yang lebih pendek akan selalu memiliki peringkat lebih rendah daripada program yang lebih lama, dan pola braket adalah faktor penentu sekunder. Non- []karakter diurutkan berdasarkan "+ - <> ,." (yang sewenang-wenang).

Misalnya dengan n=4kami memiliki kasus ini:

zxxx
[]xx
[x]x
[xx]

di mana zsingkatan untuk non- []karakter dan xsingkatan untuk karakter apa pun, di bawah batasan yang ]harus sesuai dengan inisial [. Program diberi peringkat berdasarkan urutan itu, dan secara rekursif pada xsub - bagian, dengan bagian kiri diprioritaskan di atas bagian kanan dalam kasus-kasus terakhir. Perhitungan peringkat mirip dengan sistem angka radix campuran, dan fpenting untuk menghitung "radix" saat ini.

Jawaban ini adalah bukti formal untuk jawaban oleh TheNumberOne , Enumerate Brainf ** k program yang valid , di mana mungkin agak sulit untuk memahami poin-poin penting mengapa enumerasi itu benar. Tidaklah penting untuk memahami mengapa tidak ada beberapa program yang tidak valid yang memetakan ke nomor yang tidak tercakup oleh program yang valid.

Sepanjang jawaban ini, huruf kapital digunakan untuk menunjukkan program, dan variabel huruf kecil digunakan untuk fungsi dan bilangan bulat. ~ adalah operator gabungan.

Proposisi 1:

Biarkan fungsi f menjadi program yang dijelaskan dalam jawaban itu. Kemudian untuk setiap program U terdapat program V yang valid sehingga f (U) = f (V)

Definisi 1:

Misalkan g (X) adalah jumlah [yang muncul dalam program X, dan misalkan h (X) adalah jumlah ]yang muncul.

Definisi 2:

Tentukan P (x) sebagai fungsi ini:

P(x) = "" (the empty program) when x <= 0
P(x) = "]" when x = 1
P(x) = "]]" when x = 2
etcetera

Definisi 3:

Diberikan program X, menyatakan X1 sebagai awalan [karakter terbesar, X2 pusatnya, dan X3 sufiks ]karakter terbesar.

Bukti proposisi 1:

Jika g (U) = h (U) maka U adalah program yang valid, dan kita dapat mengambil V = U. (kasus sepele).

Jika g (U) <h (U) maka kita dapat membuat V dengan menambahkan [simbol n = h (U) - g (U) . Jelas f (V) = f (U) karena semua [simbol di awalan dihapus.

Sekarang pertimbangkan g (U)> h (U). Tentukan T = U2 ~ U3. jika g (T) <= h (T), maka kita dapat membuat V dengan menghapus [simbol n = g (U) - h (U) .

Jadi kita dapat mengasumsikan bahwa h (T) <g (T). Bangun V = T ~ P (g (T) - h (T)).

Kami membutuhkan tiga fakta kecil untuk melanjutkan:

Klaim 1: g (U2) = g (T)

U3 tidak mengandung [simbol apa pun menurut definisinya. Sebagai T = U2 ~ U3, [simbol - simbolnya semuanya ada di bagian pertama.

Klaim 2: h (U3) <g (T)

Ini mengikuti dari mencatat bahwa h (T) <g (T) dan h (U3) <h (U3 ~ U2) = h (T).

Klaim 3: h (V3) = g (U2) - h (U2)

h(V3) = h(U3) + g(T) - h(T)                           using the construction of V
h(V3) = h(U3) + g(U2) + g(U3) - h(U2) - h(U3)         apply the definition of T
h(V3) = g(U2) - h(U2) *one term cancels, g(U3)        is always zero, as U3 contains only `]` symbols*

Sekarang kita tunjukkan bahwa f (V) = f (U).

f(U) = U2 ~ P(h(U3) - g(U2)) = U2                     claim 2, definition of P

f(V) = U2 ~ P(h(V3) - g(V2))
     = U2 ~ P(h(V3) - g(U2))
     = U2 ~ P(g(U2) - h(U2) - g(U2))                  claim 3
     = U2 ~ P(-h(U2))
     = U2                                             definition P

Ini melengkapi buktinya. QED

Ayo lakukan keunikan juga.

Proposisi 2:

Biarkan U, V menjadi dua program yang berbeda dan valid. Kemudian f (U)! = F (V)

Ini cukup mudah dibandingkan dengan proposisi sebelumnya.

Mari kita asumsikan bahwa U2 = V2. Tetapi kemudian satu-satunya cara U dan V dapat berbeda adalah dengan menambahkan atau menghapus n [dan ]simbol masing-masing ke U1 dan U3. Namun ini mengubah output dari f, karena f akan menghitung jumlah ]simbol yang tidak cocok dalam sufiks.

Jadi U2! = V2.

Jelas, ini mengarah pada kontradiksi. Karena U2 dan V2 secara harfiah terkandung dalam output dari f (U) dan f (V) masing-masing, mereka tidak dapat berbeda, kecuali di 'tepi', tempat di mana U2 digabungkan dengan U3. Tetapi simbol pertama dan terakhir dari U2 dan V2 tidak dapat [atau ]menurut definisi, sementara itu adalah satu-satunya simbol yang diperbolehkan masing-masing dalam U1, U3, V1, V3 dan masing-masing lagi. Jadi kita mendapatkan U2 = V2. QED