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 kodex
selama 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 kode-golf , 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:
[.]![!.!]
sumber
1
s 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.cat
program: sepertinya tidak ada instruksi untuk mengambil input..
- 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!)[0,0,0,0,0,0,0...]
(yaitu keberadaan a!
pada awal program).[.]![!.!]
untuk mencetak nilai sel itu selamanyaJawaban:
Python 2 , 167 byte
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.
sumber
2**t
(-6 byte).JavaScript (Node.js) , 148 byte
Cobalah online!
Ini turing lengkap
Perlu init sebagai memindahkan beberapa tempat dan init bit saat ini dan kanan sebagai 1 (
>>>>>>>>^>^<
)Cobalah online!
Tempat
n
di BoolFuck ditulis sebagai(0, 0, ..., 0(n*0), [1], 1, 0, 0, ...)
.Karena
>
, itun
=>n+1
Sama seperti cara
<
kerjanyasumber
!>.
mencetak1
dalam boolfuck tetapi menerjemahkan!>^.
yang mencetak 1 dalam TwoMega (>
tidak mempengaruhi rekaman;^
tidak mempengaruhi rekaman karena referensi adalah 1)+>;
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?!>.
, hanya>
perintah yang valid di boolfuck ...!
membalikkan referensi, bukan sel rekaman.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:
Terjemahan ini menyimpan status Boolfuck dalam sel rekaman bernomor genap di TwoMega. Semua perintah yang diterjemahkan akan mempertahankan invarian berikut:
Cuplikan
!^!
akan tetap[0]0
konstan dan bertukar di antara0[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.sumber
Python 3 ,
297284274 byte-10 byte berkat ovs dan Jonathan Allan
Cobalah online!
sumber
t.discard(p)
->t-={p}
t
ituglobal
.f
sebagaif(C,p,t=set())
Pip ,
7571 byteCobalah online!
Menerjemahkan 2 Ω kode ke kode Pip setara dan mengevaluasi itu.
Kami gunakan
i
untuk mewakili rekaman,v
untuk penunjuk tape *, danl
untuk hypercube. Dua yang pertama diinisialisasi ke nilai yang berguna;l
dimulai dengan[]
, yang kami tekan a0
(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:
Tabel terjemahan:
l@FBi
adalah referent: elemen hypercubel
pada indeks (converti
from binary). Itu sering muncul, jadi kami menyebutnya_
dan ganti_
dengan kode asli di akhir.!:_
secara logis meniadakan referensi di tempat.--viPU0
decrementsv
(memindahkan penunjuk kaset ke kanan); kemudian mendorong yang lain0
ke sisi kirii
, untuk memastikan bahwa penunjuk pita tetap dalam batas.++v
tambahanv
(tidak perlu untuk memeriksa batas, per OP).W_{
menjalankan perulangan sementara referensi adalah benar (yaitu bukan nol, yaitu1
).}
menutup loop.O_
menampilkan referensi tanpa baris baru.Akhirnya, untuk
^
:sumber