Ini adalah Tantangan Mingguan # 2. Tema: Terjemahan
Tulis program atau fungsi yang mengambil kode sumber untuk program di Pendahuluan dan kode keluaran untuk program yang setara di Befunge-93 . Agar program menjadi setara, itu harus, untuk setiap input yang diberikan, menghasilkan output yang sama dengan program Prelude, dan berhenti jika dan hanya jika program Prelude berhenti.
Bahasa input: Pendahuluan
Penerjemah Python:
Program Prelude terdiri dari sejumlah "suara" yang menjalankan instruksi secara bersamaan. Instruksi untuk setiap suara berada pada jalur yang berbeda. Setiap suara memiliki tumpukan terpisah, yang diinisialisasi dengan jumlah nol yang tak terbatas. Eksekusi dimulai di kolom paling kiri, dan naik satu kolom ke kanan setiap centang, kecuali jika dipengaruhi oleh )
atau (
instruksi. Program berakhir ketika kolom terakhir tercapai.
Prelude spec untuk tantangan ini:
Digits 0-9 Push onto the stack a number from 0 to 9. Only single-digit
numeric literals can be used.
^ Push onto the stack the top value of the stack of the above
voice.
v Push onto the stack the top value of the stack of the below
voice.
# Remove the top value from the stack.
+ Pop the top two integers from the stack and push their sum.
- Pop the top two integers from the stack, subtract the topmost
from the second, and push the result.
( If the top of the stack is 0, jump to the column after the
matching `)` after the current column executes.
) If the top of the stack is not 0, jump to the column after
the matching `(` after the current column executes.
? Read an integer from STDIN.
! Pop one value from the stack and print it to STDOUT as an
integer.
<space> No-op
Catatan
v
dan^
bertindak secara siklis, sehinggav
pada suara bagian bawah akan menyalin elemen tumpukan suara atas, dan^
pada suara atas akan menyalin dari suara bawah. Konsekuensi: Keduanyav
dan^
menduplikasi bagian atas tumpukan dalam program suara tunggal.- A
(
dan pencocokannya)
mungkin terletak di jalur yang berbeda. Namun , a)
akan selalu melihat tumpukan suara di mana yang sesuai(
ditempatkan, bukan tumpukan di mana suara)
itu sendiri ditempatkan. - Nilai yang dihasilkan oleh
^
danv
instruksi beroperasi pada nilai yang ada sebelum selesainya operasi lain di kolom yang sama. ?
dan!
beroperasi secara berbeda dari spesifikasi yang ditemukan di esolangs.org, jadi pastikan untuk menguji dengan penerjemah yang sedikit dimodifikasi yang disediakan dalam posting ini.
Input dijamin memiliki:
- Tanda kurung yang cocok
- Tidak lebih dari satu kurung dalam satu kolom
- Jumlah karakter yang sama di setiap baris
- Setidaknya satu baris
- Tidak ada kolom dengan lebih dari satu instruksi I / O (
!
atau?
) - Satu karakter linefeed setelah instruksi untuk setiap suara
- Tidak ada karakter selain yang disebutkan di atas
Bahasa keluaran: Befunge-93
Befunge adalah bahasa berbasis tumpukan yang penghitung programnya (PC; pointer ke instruksi saat ini) bergerak bebas di kisi dua dimensi. Itu dimulai di sudut kiri atas, bergerak ke kanan. Playfield adalah toroidal, yaitu gerakan PC membungkus kedua sisi. Befunge juga memiliki tumpukan yang diinisialisasi ke angka nol tanpa batas. Befunge memiliki operasi berikut:
Anda dapat mengasumsikan karakteristik kompiler / juru bahasa Befunge-93 berikut:
- Integer tidak terbatas presisi.
- Ini memungkinkan kisi-kisi dalam berbagai ukuran.
- Koordinat kisi (untuk
g
danp
) berbasis 0.
Mencetak gol
Untuk mencegah pengiriman yang hanya menghasilkan juru bahasa Prelude di Befunge dan meng-hardcode sumber Prelude ke dalamnya, tujuannya adalah untuk meminimalkan ukuran kode sumber Befunge yang dihasilkan.
Di bawah ini disediakan sejumlah program Pendahuluan. Penerjemah Anda akan menjalankan semua ini. Skor Anda adalah jumlah dari ukuran program Befunge, asalkan semuanya valid.
Penerjemah Anda sebaiknya tidak dioptimalkan secara khusus terhadap kasus uji ini (mis. Dengan program Befunge tulisan tangan hardcoding untuk mereka). Jika saya mencurigai ada jawaban yang melakukannya, saya berhak untuk mengubah input atau membuat input tambahan.
Input Sampel
Cetak n-1
ke 0
:
?(1-^!)
Logis dan:
? (0)
?(0 )
1 !
Logis atau:
? (0)
? (0)
1 1 !
Periksa paritas input (yaitu modulo 2) dari nomor non-negatif:
?(1-)
^ v
v1-^^-!
Kuadratkan input:
^
^+ !
?(1-)
Cetak angka Fibonacci ke- n , di mana n = 0
sesuai dengan 0 dan n = 1
sesuai dengan 1:
0 v+v!
1 ^
?(1-)
Signum:
1) v # - !
vv (##^v^+)
?(# ^ ##
Pembagian untuk input non-negatif:
1 (# 1) v # - 1+)
vv (##^v^+)
? v-(0 # ^ #
?
1+ 1-!
Tentu saja, program Anda harus menunjukkan perilaku yang sama untuk semua kasus, bahkan jika perilaku program sampel untuk angka negatif tidak ditentukan.
Akhirnya, penerjemah Anda seharusnya tidak terlalu panjang:
- Itu harus terkandung di dalam pos Stack Exchange
- Ini harus memproses input sampel dalam waktu kurang dari 10 menit pada komputer desktop biasa.
Perhatikan bahwa input numerik untuk Prelude atau Befunge diberikan sebagai tanda minus opsional diikuti oleh satu atau lebih angka desimal, diikuti oleh baris baru. Input lain adalah perilaku yang tidak terdefinisi.
Anda dapat menulis penerjemah Anda dalam bahasa apa pun. Kode Befunge yang diterjemahkan terpendek, akan menang.
Papan peringkat
- Sp3000 : 16430 byte
1
ada di dalam satu loop, jadi mungkin tidak didorong. Angka 0 dapat berasal dari jumlah tak terbatas 0s yang dimulai pada tumpukan.Jawaban:
Python 3, akan mencetak gol nanti
Jalankan seperti
py -3 prefunge.py <input filename> <output filename>
.Ini minggu yang lambat bagi saya, jadi saya akhirnya cukup bosan untuk menangani pertanyaan enam bulan ini. Saya akan bertanya mengapa tidak ada orang lain yang mencoba, tetapi saya masih merasakan sakit karena debugging (dan mungkin masih ada bug yang tersisa untuk semua yang saya tahu).
Pertanyaannya tidak menyediakan penerjemah Befunge-93, jadi saya menggunakan yang ini , yang sedikit berbeda dari spek. Dua perbedaan utama adalah:
Jika char tidak ada di baris tertentu dari program, maka Anda tidak dapat menulis ke baris itu. Ini berarti Anda harus menekan Enter beberapa kali untuk memperkenalkan cukup baris baru di akhir . Jika Anda melihat
NaN
di output, ini kemungkinan penyebabnya.Sel-sel kisi tidak diinisialisasi ke nol - untuk kenyamanan saya telah memasukkan beberapa preinitialisation dalam output Befunge, tetapi karena itu tidak perlu saya mungkin mengambilnya ketika saya mulai mencetak.
Tata letak inti dari program keluaran adalah ini:
Ruang stack berada di luar program, oleh karena itu komentar Enter-spam baru dari sebelumnya.
Ide intinya adalah untuk menetapkan setiap suara baris yang berfungsi sebagai tumpukannya. Untuk mempertahankan tumpukan ini, kami juga memiliki baris panjang tumpukan khusus di mana panjang setiap tumpukan dicatat dalam sel di sepanjang baris. Program ini kemudian banyak
g
ets danp
uts, misal untuk mencetak prosesnya adalah:y = stack_row[stack], x = stack_length[stack]
.91+,
, yaitu cetak sebagai bilangan bulat lalu cetak baris barustack_length[stack]
Untuk melakukan evaluasi kolom secara simultan, semua sel yang diperlukan dibaca dan nilainya disimpan di tumpukan sebelum ada sel yang ditulis (misalnya untuk contoh pencetakan, mungkin ada lebih banyak instruksi di antara langkah pertama dan kedua).
`
, yang lebih besar dari, digunakan untuk memastikan panjang stack tidak menjadi negatif, dan untuk mendorong 0 ketika stack kosong. Di sinilah percabangan yang terlihat jelas berasal, tapi saya punya ide yang akan menghapus percabangan, yang seharusnya menghapus banyak spasi putih dari baris pertama dan ketiga.Untuk loop, karena Prelude loop dapat melompat dua arah, kami menggunakan dua baris per loop dalam konfigurasi seperti ini:
Loop-loop ini saat ini merupakan mayoritas dari byte, tetapi dapat dengan mudah diturunkan dengan menempatkannya ke dalam kotak kode dengan
p
, yang saya rencanakan untuk dilakukan setelah saya senang bahwa penerjemah bekerja dengan benar.Berikut adalah beberapa contoh keluaran
?(1-^!)
, yaitu cetakn-1
ke0
:Input persegi:
Divisi (disarankan input kecil):
Ada juga sekelompok optimisations kecil lainnya yang datang ke pikiran, seperti mengganti
07p07g
dengan:07p
, tapi saya mengambil langkah ini satu per satu :)sumber
Will score later
2 tahun dan terus bertambah! :)