Tantangan
Tantangan Anda adalah merancang juru bahasa untuk bahasa mirip lisp , yang sejak saat itu akan diciptakan: GLisp . Kode program untuk GLisp akan terdiri dari jumlah ekspresi bersarang yang ditunjukkan oleh tanda kurung, dalam bentuk berikut:
(func arg1 arg2 ...)
Perhatikan bahwa interpreter harus mengizinkan karakter spasi kosong sebelum dan sesudah tanda kurung, fungsi, dan argumen.
Jenis
Anda akan menerapkan empat jenis, Integer, Daftar, Boolean, dan Fungsi. Nilai integer dan Boolean dapat secara eksplisit dimasukkan ke dalam kode sumber dengan sintaks mereka sendiri. Penerjemah Anda harus mengasumsikan bahwa sejumlah karakter numerik menunjukkan Integer (Anda tidak harus menerapkan sintaks untuk secara eksplisit memasukkan bilangan bulat negatif). Penerjemah Anda juga harus mengasumsikan bahwa true
dan false
diberi nilai Boolean. Fungsi tidak dapat didefinisikan secara eksplisit oleh pengguna, dan akan selalu mengembalikan nilai tunggal (Daftar panjang apa pun dianggap sebagai nilai tunggal).
Fungsi
Fungsi-fungsi berikut harus diimplementasikan, dan berada dalam format Function , Arity . Jika Arity n
diproses oleh tanda plus, maka itu menunjukkan n
atau lebih banyak argumen. Anda dapat mengasumsikan bahwa semua argumen yang diberikan untuk suatu fungsi adalah dari jenis yang sama, kecuali dinyatakan sebaliknya. Anda juga dapat mengasumsikan bahwa jika tidak ada perilaku yang ditentukan untuk tipe certian, maka Anda dapat mengasumsikan bahwa tidak ada argumen fungsi yang akan menjadi tipe itu. Argumen akan disebut sebagai dalam diagram berikut:
(func argument1 argument2 ... argumentn)
+ , 2+
- Jika semua argumen bertipe Integer , Anda harus mengembalikan jumlah argumen
- Jika semua argumen bertipe List , Anda harus mengembalikan rangkaian argumen dalam urutan menaik (
arg1+arg2+ ...
) - Jika semua argumen bertipe Boolean , Anda harus mengembalikan logis Semua urutan argumen
(+ 1 2 3 4 5) -> 15
(+ (list 1 2) (list 3 4)) -> (list 1 2 3 4)
(+ true true true) -> true
- , 2+
- Jika semua argumen bertipe Integer , Anda harus mengembalikan perbedaan argumen (
arg1-arg2- ...
) - Jika semua argumen bertipe Boolean , Anda harus mengembalikan logika Apa pun dari urutan argumen
(- 8 4 3) -> 1
(- 0 123) -> -123
(- true false false true false) -> true
- Jika semua argumen bertipe Integer , Anda harus mengembalikan perbedaan argumen (
* , 2+
- Jika semua argumen bertipe Integer , Anda harus mengembalikan produk dari argumen tersebut
- Jika satu argumen bertipe Daftar dan yang lainnya bertipe Integer (Anda dapat mengasumsikan bahwa ini hanya akan menjadi satu-satunya argumen yang diberikan), Anda harus mengembalikan Daftar baru dengan item dalam waktu yang
arg1
berulangarg2
. (* 1 2 3 4 5) -> 120
(* (list 1 2 3) 2) -> (list 1 2 3 1 2 3)
/ , 2+
- Jika semua argumen bertipe Integer , Anda harus mengembalikan hasil bagi argumen (
arg/arg2/ ...
) (Anda dapat mengasumsikan bahwa pembagian dilakukan secara berurutan, dan bahwa bagian desimal pada setiap langkah terpotong) - Jika satu argumen bertipe Daftar dan yang lainnya bertipe Function , maka Anda harus mengembalikan Daftar yang dihasilkan setelah
arg2
dipetakan pada setiap nilai (/ 100 10 3) -> 3
(/ (list 1 2 3) inc) -> (list 2 3 4)
- Jika semua argumen bertipe Integer , Anda harus mengembalikan hasil bagi argumen (
% , 2
- Jika semua argumen bertipe Integer , Anda harus mengembalikan modulus argumen
(% 4 2) -> 0
= , 2+
- Jika kedua jenis dan nilai semua argumen adalah sama, Anda harus kembali benar. Jika tidak, kembalikan salah.
(= 0 0 0) -> true
(= 0 false (list)) -> false
daftar , 0+
- Anda harus mengembalikan daftar semua argumen, apa pun jenisnya. Jika tidak ada argumen yang diberikan, maka Anda harus mengembalikan daftar kosong
(list 3 4 (list 5)) -> (list 3 4 (list 5))
inc , 1
- Jika argumen bertipe Integer , Anda harus mengembalikan Integer yang bertambah satu
- Jika argumen adalah tipe List , Anda harus mengembalikan List yang diputar searah jarum jam satu putaran
(inc 1) -> 2
(inc (list 1 2 3)) -> (list 3 1 2)
Desember , 1
- Jika argumen bertipe Integer , Anda harus mengembalikan Integer yang dikurangi satu
- Jika argumen adalah tipe List , Anda harus mengembalikan List yang diputar berlawanan arah jarum jam satu putaran
(dec 1) -> 0
(dec (list 1 2 3)) -> (list 2 3 1)
jika , 3
- Jika diberi tiga argumen jenis apa pun: Jika nilai kebenarannya
arg1
benar, kembalikanarg2
, kembalikan lagiarg3
(if (not (list 1)) 8 false) -> false
- Jika diberi tiga argumen jenis apa pun: Jika nilai kebenarannya
tidak , 1
- Jika diberi argumen jenis apa pun, jika nilai kebenarannya
arg1
False, kembalikantrue
, kembalikan lagifalse
. (not (list)) -> true
- Jika diberi argumen jenis apa pun, jika nilai kebenarannya
len , 1
- Jika diberi argumen tipe daftar , kembalikan panjang
arg1
(len (list 4 2 true (list 3) (list))) -> 5
- Jika diberi argumen tipe daftar , kembalikan panjang
Tabel kebenaran
:, di 0, (list), false -> false
mana (list)
menunjukkan daftar kosong. Yang lainnya adalah true
.
Penerjemah Anda dapat berupa program lengkap yang membaca input sumber dari stdin atau file, atau fungsi yang mengambil sumber sebagai string dan mengembalikan nilai output.
Jika memilih yang pertama, output untuk Integer hanyalah angka, untuk Boolean adalah true
atau false
, dan untuk daftar adalah urutan nilai-nilai yang dipisahkan spasi dalam tanda kurung (mis. (1 2 3 4 (5 6 7))
Menunjukkan (list 1 2 3 4 (list 5 6 7))
).
Jika memilih yang terakhir, nilainya harus dikembalikan dalam tipe yang sesuai bahasa implementasi, atau, jika tidak ada tipe yang serupa, tipe kustom. Daftar dapat dikembalikan sebagai Array atau Vektor jika bahasa tidak memiliki jenis Daftar , Boolean harus dikembalikan sebagai jenis Boolean dalam bahasa, atau jenis khusus jika bahasa tidak mendukung mereka.
Uji kasus
(list 1 2 3 (list 4 5 true)) -> (1 2 3 (4 5 true))
(/ 4000 (+ 1 2 3 4 (* 5 8))) -> 80
(+ (not (- (len (list 5 6 7)) (/ 10 3))) true) -> true
(if ( len (list ) ) 4 (if (+ (= 8 8 8) (not (list 4))) 8 5)) -> 5
Klarifikasi
- Penerjemah Anda mungkin berurusan dengan input yang tidak valid dengan cara apa pun yang Anda pilih, tetapi itu tidak boleh membuang pengecualian (meskipun, ia dapat mencetak pesan kesalahan dan keluar dengan lancar)
- Fungsi akan selalu mengevaluasi argumen dari kiri ke kanan
- Input yang tidak valid adalah setiap input yang secara sintaksis salah. Ini termasuk, tetapi tidak terbatas pada, tanda kurung yang tidak cocok, pembagian dengan nol, dan fungsi yang diterapkan sebagian (kecuali berlaku untuk bonus)
- Karena
=
, jika ada nilai yang berbeda atau tipe yang berbeda, kembalikanfalse
Bonus
- Nilai * 0,8 jika Anda mendukung fungsi yang diterapkan sebagian. Misalnya,
((+ 2) 3)
akan sama dengan(+ 2 3)
, tetapi memungkinkan untuk hal-hal seperti(/ (list 1 2 3) (+ 2))
. Anda dapat mengasumsikan bahwa suatu fungsi diterapkan sebagian jika menerima kurang dari jumlah minimum argumen - Nilai * 0,85 jika Anda tidak mengevaluasi argumen yang diterapkan
if
kecuali mereka akan dikembalikan
Ini adalah kode-golf, jadi penerjemah dengan jumlah byte terendah menang!
sumber
(if (not (array 1)) 8 false) -> false
?(+ 3 (if false 5))
? Secara umum, apa yang sebenarnya "tidak mengembalikan apa-apa"? Anda tidak menentukan tipe unit apa pun yang akan(+ bool bool...)
logis DAN dan(- bool bool...)
logis ATAU? Notasi dering standar akan digunakan+
untuk OR dan*
untuk AND. 2. Apakah "input tidak valid" dimaksudkan untuk mencakup kasus-kasus seperti(/ 2 0)
mana yang secara sintaksis benar? 3. Karena=
, jika nilainya tidak semuanya sama, haruskah itu dikembalikanfalse
? 4. Definisinot
tampaknya mundur. 5. Apa tokennya? Anda mengatakan bahwa penerjemah harus menangani spasi tambahan, tetapi Anda tidak mengatakan spasi apa yang bisa diandalkan. Untuk pertanyaan kompleks seperti ini, Anda harus menggunakan kotak pasir agar spek dapat diperiksa.((+ 2 3) 4)
sama dengan9
atau kesalahan? Khususnya, untuk fungsi var-arg, tidak jelas kapan seseorang harus mempertimbangkan aplikasi parsial. Itu menjadi lebih kacau dengan hal-hal seperti((if true (+ 2 3) (- 5)) 4)
Jawaban:
Haskell,
1370126311791128116311071084 bytes * 0.8 * 0.85 = 737.12Program lengkap, membaca
stdin
dan menulis untukstdout
.g
adalah versi fungsi, juga.Menerapkan fungsi parsial, dan evaluasi malas
if
.Contoh dijalankan (dari versi fungsi):
Sekarang miliki semua unit test dari deskripsi:
sumber
e[K,L _]
yang dapat Anda gunakandrop 1
sebagai versi amantail
dan gunakantake
untuk versi amanhead
bergabung dengan dua definisie[K,L _]
notElem
.another tip: Anda dapat melakukannyas=string
dan menggunakannya sebagai ganti keduanyastring
danchar
(s"C"
vs.char 'C'
). tip lain: gunakan penjaga bukannyaif
sMaybe
nilai berdasarkan daftar.Nothing
adalah[]
danJust x
sekarang[x]
. Ini menghilangkan konstruktor yang panjang dan menambahkan beberapa fungsi lagi:if p then Just x else Nothing
adalah[x|p]
,(==Nothing)
adalahnull
, daftar monad menjadi sama dengan mungkin monad, dan sebagainya.Python 2, 1417 * 0.8 * 0.85 = 963.56
Perombakan total. Jika Anda ingin melihat versi sebelumnya, lihat riwayat edit .
Ada banyak lagi yang bisa dimainkan. Perlahan aku mengerjakannya.
Dengan zlib / base64 kita mendapatkan 1093 * 0.8 * 0.85 = 743.24 :
Catatan: Jika Anda melihat skor saya naik, itu mungkin karena saya menemukan beberapa bug
sumber
Common Lisp, 868 bytes * 0.85 = 737.8
Apakah curang menerapkan Lisp dengan Lisp? Masih banyak yang harus dioptimalkan di sini.
Mencetak E jika terjadi kesalahan input. Sampel berjalan:
sumber
Haskell, 972
solusi yang cukup meretas. ini menyimpan segala sesuatu sebagai string dalam bentuk siap-keluaran - tipe mereka dapat dibedakan dengan huruf pertama mereka -
0..9
untuk angka,(
untuk daftar,t
atauf
untuk boolean, dan segala sesuatu lainnya untuk fungsi.untuk menjalankan gunakan
r
fungsi.sumber