Tafsirkan TwoMega

9

Dalam tantangan ini, Anda akan menulis penerjemah untuk 2 Ω (ditranskripsikan sebagai TwoMega ), bahasa yang didasarkan pada brainfuck dengan ruang penyimpanan dimensi tak terbatas.

Bahasa

2 Ω berisi tiga bagian negara:

  • The Tape , yang merupakan daftar tak terbatas bit, semua diinisialisasi ke 0. Ini memiliki unsur paling kiri, tapi ada unsur paling kanan.

  • The Memory Pointer , yang merupakan bilangan bulat tak negatif yang merupakan indeks dari elemen dalam rekaman itu. Pointer memori yang lebih tinggi mengacu pada sel kaset lebih jauh ke kanan; pointer memori 0 mengacu pada elemen paling kiri. Penunjuk memori diinisialisasi ke 0.

  • The Hypercube , yang merupakan konseptual berdimensi "kotak" sel, masing-masing berisi sedikit diinisialisasi ke 0. Lebar Hypercube terikat dalam setiap dimensi hanya 2 sel, tetapi tak terhingga dari dimensi berarti jumlah sel-sel tidak terhitung .

Sebuah indeks ke hypercube merupakan daftar tak terbatas bit yang mengacu ke sel di hypercube (dalam cara yang sama bahwa daftar yang terbatas bit dapat digunakan untuk merujuk kepada hypercube berdimensi berhingga). Karena rekaman itu adalah daftar bit yang tak terbatas, seluruh pita selalu mengacu pada elemen Hypercube; elemen ini disebut referensi .

2 Ω memberi arti pada 7 karakter yang berbeda:

  • < mengurangi pointer memori dengan 1. Mengurangkannya di bawah 0 adalah perilaku yang tidak terdefinisi, sehingga Anda tidak perlu menanganinya.
  • > menambah penunjuk memori dengan 1.
  • ! membalik bit pada referensi.
  • . menampilkan bit pada referensi.
  • ^mengganti bit pada sel yang ditunjuk oleh penunjuk memori pada pita dengan kebalikan dari bit pada referensi.
  • [x]menjalankan kode xselama bit pada referensi adalah 1.

Tantangan

Tugas Anda adalah untuk menulis sebuah program yang mengambil string sebagai input dan mengeksekusi bahwa masukan sebagai 2 Ω Program.

Ini adalah , sehingga jawaban terpendek yang valid (diukur dalam byte) menang.

Catatan

  • Anda dapat mengasumsikan bahwa program hanya akan terdiri dari karakter <>!.^[]dan itu []akan disarangkan dengan benar.
  • Penerjemah Anda seharusnya hanya dibatasi oleh memori yang tersedia pada sistem. Seharusnya dapat menjalankan program sampel dalam jumlah waktu yang wajar.

Program Sampel

Cetak 1:

!.

Cetak 010:

.!.!.

Cetak 0 selamanya:

![!.!]

Cetak 0 selamanya, atau 1 selamanya jika !dituliskan:

[.]![!.!]
Buah Esolanging
sumber
2
Catatan kecil: jumlah sel penyimpanan sebenarnya tidak terhitung, karena jumlah 1s pada pita selalu terbatas. Pada kenyataannya, ada suatu bijection yang cukup sederhana antara bilangan asli dan status rekaman (menafsirkan konten rekaman sebagai angka biner mundur), yang menunjukkan bahwa Hypercube pada dasarnya adalah array 1D yang tak terbatas, diakses dengan membalik bit dalam nilai pointer integer , bukannya di / decrementing seperti di brainfuck.
Lynn
Juga, ulang: undangan Anda untuk menulis sebuah catprogram: sepertinya tidak ada instruksi untuk mengambil input.
Lynn
2
Saya pikir harus ada program sampel menggunakan lebih dari set instruksi. Dua yang sederhana: .- mencetak nol tunggal dan kemudian ada; !^!.- mencetak satu kemudian keluar. Akan lebih banyak yang baik. Saat ini seseorang harus memahami kiriman untuk memverifikasinya (dan karenanya meningkatkannya!)
Jonathan Allan
@ Lynn Input akan diberikan dengan memiliki 1 atau 0 pada sel [0,0,0,0,0,0,0...](yaitu keberadaan a !pada awal program).
Buah Esolanging
Maka Anda bisa lakukan [.]![!.!]untuk mencetak nilai sel itu selamanya
Leo

Jawaban:

2

Python 2 , 167 byte

t=h=I=0
m=1
E=''
for c in input():i='[<>!.^]'.find(c);E+=' '*I+'while+2**t&h: m/=2 m*=2 h^=2**t print+(2**t&h>0) t=t&~m|m*(2**t&h<1) #'.split()[i]+'\n';I-=~-i/5
exec E

Cobalah online!

t adalah rekamannya. t = 6 berarti rekaman itu [0 1 1 0 0 0 ...]

m adalah 2 pangkat dari penunjuk memori. Jadi m = 8 berarti kita menunjuk pada bit 3.

h adalah hypercube. h = 80 (bit 4 dan 6 set) berarti bit pada [0 0 1 0 ...] dan [0 1 1 0 ...] ditetapkan.

Untuk membaca bit pada referensi, kami memeriksa 2 t & h . Untuk membaliknya, kami melakukan h ^ = 2 t .

Kami menerjemahkan instruksi ke kode Python dan menjalankan hasilnya. Saya menyimpan level lekukan loop sementara.

Lynn
sumber
Program Anda atau test case kedua salah
wastl
@Wastl Test case kedua salah. ;)
DLosc
2

JavaScript (Node.js) , 148 byte

x=>eval(x.replace(e=/./g,c=>({'<':'u/=2','>':'u*=2','!':'e[v]^=1','.':'alert(+!!e[v])','^':'v=(v|u)^u*e[v]','[':'while(e[v]){'}[c]||'}')+';',v=u=1))

Cobalah online!

Ini turing lengkap

BoolFuck TwoMega
< >^>^>[!]^<<<<[!]^>>[!]!^>[!]!^>[!]!^<<<<(>^>^>1<<<<1>>0>0>0<<<<)
> ^<^<[!]^>>>>[!]^<<[!]!^<[!]!^<[!]!^>>>(^<^<1>>>>1<<0<0<0>>>)

Perlu init sebagai memindahkan beberapa tempat dan init bit saat ini dan kanan sebagai 1 ( >>>>>>>>^>^<)

Cobalah online!

Tempat ndi BoolFuck ditulis sebagai (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Karena >, itu n=>n+1

     0 0 0 0 0[1]1 0 0 0 0
^    0 0 0 0 0[x]1 0 0 0 0
<    0 0 0 0[0]x 1 0 0 0 0
^    0 0 0 0[y]x 1 0 0 0 0, yx != 01
<    0 0 0[0]y x 1 0 0 0 0
[!]^ 0 0 0[1]y x 1 0 0 0 0, (0yx10) = 0
>>>> 0 0 0 1 y x 1[0]0 0 0
[!]^ 0 0 0 1 y x 1[1]0 0 0, (1yx10) = 0
<<   0 0 0 1 y[x]1 1 0 0 0
[!]! 0 0 0 1 y[x]1 1 0 0 0, (1yx11) = 1
^    0 0 0 1 y[0]1 1 0 0 0
<    0 0 0 1[y]0 1 1 0 0 0
[!]! 0 0 0 1[y]0 1 1 0 0 0, (1y011) = 1
^    0 0 0 1[0]0 1 1 0 0 0
<    0 0 0[1]0 0 1 1 0 0 0
[!]! 0 0 0[1]0 0 1 1 0 0 0, (10011) = 1
^    0 0 0[0]0 0 1 1 0 0 0
>>>  0 0 0 0 0 0[1]1 0 0 0

Sama seperti cara <kerjanya

l4m2
sumber
Apakah Anda yakin terjemahan ini valid? !>.mencetak 1dalam boolfuck tetapi menerjemahkan !>^.yang mencetak 1 dalam TwoMega ( >tidak mempengaruhi rekaman; ^tidak mempengaruhi rekaman karena referensi adalah 1)
Esolanging Fruit
@EsolangingFruit +>;do [1]00... 1[0]0...(output 0), !>^.do (0,0,...)=1, ptr=([0],0,...) (0,0,...)=1, ptr=(0,[0],...) (0,0,...)=1, ptr=(0,[1],...)(output 0), ada apa?
14m2
@EsolangingFruit untuk !>., hanya >perintah yang valid di boolfuck ...
ASCII-only
1
@ 14m2 Dalam TwoMega, !membalikkan referensi, bukan sel rekaman.
Buah Esolanging
@EsolangingFruit jadi apa yang salah di sini?
14m2
1

Brain-Flak Classic , 816 bytes

<>(((<(())>)))<>{(([][][])(((({}){}[])({}))({})[]([][](({})(({}())(({}){}{}({}(<()>))<{<>({}<>)}{}>))))))(([]{()(<{}>)}{}){<((<{}>))<>(()(){[](<{}>)}{}<{({}[]<({}<>)<>>)}{}{}>)<>({()<({}<>)<>>}<<>{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(({})<<>{({}[]<({}<>)<>>)}({}<>)<>{({}<>)<>}>)<>>)<>({}<>)<>>}{}([]{()(<{}>)}{}){{}<>({})(<>)}{}([]{()(<{}>)}{}){(<{}<>({}<{((<({}[])>))}{}{((<(())>))}{}>)<>>)}{}([]{()(<{}>)}{}){(<{}<>({}<({}())>)<>>)}{}([]{()(<{}>)}{}){(<{}<>[({})]<>>)}{}([]{()(<{}>)}{})<{((<{}>))<>{}({}<{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(((){[](<{}>)}{})<<>{({}[]<({}<>)<>>)}{}(<>)<>{({}<>)<>}>)<>>)<>({}<>)<>}{}(<>)<>{({}<>)<>}{}>()){((({}[]<>){(<{}({}<>)>)}{}())<{({}<({}<>)<>((((((([][][]){}){}){}()){}){}({})())[][])>{[](<{}>)}{}{()(<{}>)}{})}{}({}<>)>[]){{}(<>)}}{}}

Cobalah online!

Kode ini ditulis supaya saya dapat menulis bukti kelengkapan Turing.

Bukti Turing-kelengkapan

Kami menunjukkan pengurangan dari Boolfuck ke TwoMega:

Boolfuck   TwoMega
>          >>
<          <<
.          !^!.!^!
[          !^![!^!
]          !^!]!^!
+          !^[!]^[>!^<[!]!^>[!]!^<]

Terjemahan ini menyimpan status Boolfuck dalam sel rekaman bernomor genap di TwoMega. Semua perintah yang diterjemahkan akan mempertahankan invarian berikut:

  • Pointer memori berada pada sel genap.
  • Semua sel kaset bernomor ganjil adalah nol.
  • Untuk setiap kemungkinan pita dengan semua sel ganjil nol, nilai yang sesuai pada hypercube adalah nol.

Cuplikan !^!akan tetap [0]0konstan dan bertukar di antara 0[0]dan [1]1(di mana perhatian terbatas pada garis pada hypercube yang dapat dijangkau tanpa memindahkan penunjuk memori). Dengan demikian, digunakan untuk sementara menempatkan nilai rekaman saat ini ke dalam referensi untuk perintah Boolfuck yang peduli.

Jika TwoMega diberi perintah input ,dengan semantik yang diharapkan, perintah Boolfuck ,akan diterjemahkan >^<,!^>[!]!^<. Karena ,tidak perlu untuk membuktikan bahwa Boolfuck adalah Turing-complete, kurangnya perintah input tidak mempengaruhi bukti ini.

Nitrodon
sumber
Ini terutama menyimpan info dalam posisi di hypercube daripada kubus itu sendiri?
l4m2
@ l4m2 Pengurangan saya dari BoolFuck tidak menyimpan data apa pun di dalam kubus itu sendiri. Setiap 1s yang saya buat di hypercube hanya ada di sana untuk mengatur sel kaset ke 0.
Nitrodon
0

Python 3 , 297 284 274 byte

-10 byte berkat ovs dan Jonathan Allan

C=input()
h={}
t=set()
def f(C,p):
 c=C[0];r=hash(frozenset(t));v=h.get(r,0)
 p={"<":p-1,">":p+1}.get(c,p)
 if'"'>c:h[r]=not v
 if"."==c:print(int(v))
 if"]"<c:t.discard(p)if v else t.add(p)
 if"["==c:
  while f(C[1:],p):1
 else:return c=="]"and v or C and f(C[1:],p)
f(C,0)

Cobalah online!

fergusq
sumber
t.discard(p)->t-={p}
shooqie
@shooqie Itu tidak berfungsi kecuali titu global.
fergusq
@fergusq Meskipun saya cukup yakin itu bekerja jika Anda menyatakan fsebagaif(C,p,t=set())
shooqie
0

Pip , 75 71 byte

lPB0aR:^"!><[].^_""!:_
--viPU0
++v
W_{
}
O_
i@v:!_LFBilPB0
l@FBi"^n;Vau

Cobalah online!

Menerjemahkan 2 Ω kode ke kode Pip setara dan mengevaluasi itu.

Kami gunakan iuntuk mewakili rekaman, vuntuk penunjuk tape *, dan luntuk hypercube. Dua yang pertama diinisialisasi ke nilai yang berguna; ldimulai dengan [], yang kami tekan a 0( lPU0) untuk menghindari masalah pengindeksan daftar kosong.

* Sebenarnya, ini adalah negasi bitwise dari penunjuk kaset, karena kami menyimpan rekaman itu ke belakang untuk konversi yang lebih mudah ke desimal.

Sisa kode adalah:

aR:...;     Do a bunch of replacements in a, translating it into Pip code
       Va   Evaluate a
         u  Suppress output of the final expression that was evaluated

Tabel terjemahan:

!  !:_
>  --viPU0
<  ++v
[  W_{
]  }
.  O_
^  i@v:!_LFBilPB0
_  l@FBi

l@FBiadalah referent: elemen hypercube lpada indeks (convert ifrom binary). Itu sering muncul, jadi kami menyebutnya _dan ganti _dengan kode asli di akhir.

  • !:_ secara logis meniadakan referensi di tempat.

  • --viPU0decrements v(memindahkan penunjuk kaset ke kanan); kemudian mendorong yang lain 0ke sisi kiri i, untuk memastikan bahwa penunjuk pita tetap dalam batas.

  • ++vtambahan v(tidak perlu untuk memeriksa batas, per OP).

  • W_{menjalankan perulangan sementara referensi adalah benar (yaitu bukan nol, yaitu 1).

  • } menutup loop.

  • O_ menampilkan referensi tanpa baris baru.

Akhirnya, untuk ^:

i@v:            Set the current tape cell to
    !_          The logical negation of the referent
                Now, make sure the list representing the hypercube is long enough:
      LFBi      Loop frombinary(i) times:
          lPB0  Push another 0 to the end of l
                This ensures that FBi will always be a valid index into l
DLosc
sumber