Pendahuluan: Logika Kombinasi
Combinatory logic (CL) didasarkan pada hal-hal yang disebut combinators , yang pada dasarnya berfungsi. Ada dua kombinasi "built-in" dasar, Sdan K, yang akan dijelaskan nanti.
Asosiatif kiri
CL adalah asosiatif kiri , yang berarti kurung (berisi barang-barang) yang berada di paling kiri dari sepasang kurung berisi anther yang dapat dihapus, dengan barang-barangnya dilepaskan. Misalnya, sesuatu seperti ini:
((a b) c)
Dapat dikurangi menjadi
(a b c)
Di mana (a b)ada di paling kiri dari braket yang lebih besar ((a b) c), sehingga bisa dilepas.
Contoh asosiasi kiri yang jauh lebih besar (tanda kurung adalah penjelasan):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Kurung juga dapat dikurangi ketika lebih dari satu pasangan membungkus benda yang sama. Contoh:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Dibangun
CL memiliki dua combinator "built-in", Sdan K, yang dapat mengubah objek (combinator tunggal, atau sekelompok combinator / grup yang dibungkus tanda kurung) seperti:
K x y = x
S x y z = x z (y z)
Di mana x, ydan zbisa menjadi stand-in untuk apa pun.
Contoh dari Sdan Kadalah sebagai berikut:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Contoh lain:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Di atas adalah contoh pernyataan CL normal, di mana pernyataan itu tidak dapat dievaluasi lebih lanjut dan mencapai hasil akhir dalam jumlah waktu yang terbatas. Ada pernyataan tidak normal (yang merupakan pernyataan CL yang tidak berakhir dan akan terus dievaluasi selamanya), tetapi mereka tidak berada dalam lingkup tantangan dan tidak perlu dibahas.
Jika Anda ingin mempelajari lebih lanjut tentang CL, baca halaman Wikipedia ini .
Tugas:
Tugas Anda adalah membuat kombinator tambahan, mengingat jumlah argumen, dan apa yang dievaluasi sebagai input, yang diberikan seperti:
{amount_of_args} = {evaluated}
Di mana {amount_of_args}bilangan bulat positif sama dengan jumlah arg, dan {evaluated}terdiri dari:
- argumen hingga jumlah argumen, dengan
1menjadi argumen pertama,2menjadi argumen kedua, dan sebagainya.- Anda dijamin nomor argumen di atas jumlah argumen (jadi
4saat{amount_of_args}itu saja3) tidak akan muncul di{evaluated}.
- Anda dijamin nomor argumen di atas jumlah argumen (jadi
- kurung
()
Jadi contoh input adalah:
3 = 2 3 1
4 = 1 (2 (3 4))
Input pertama meminta combinator (katakanlah R) dengan tiga argumen ( R 1 2 3), yang kemudian dievaluasi menjadi:
R 1 2 3 -> 2 3 1
Input kedua menanyakan ini (dengan nama kombinator A):
A 1 2 3 4 -> 1 (2 (3 4))
Diberikan input dalam format ini, Anda harus mengembalikan string S, Kdan (), yang ketika diganti dengan nama kombinator dan dijalankan dengan argumen, mengembalikan pernyataan yang dievaluasi sama dengan {evaluated}blok ketika blok perintah diganti kembali untuk nama kombinator tersebut.
Pernyataan kombinator keluaran mungkin memiliki spasi putih dihapus dan tanda kurung luar dihapus, sehingga sesuatu seperti (S K K (S S))bisa diubah menjadi SKK(SS).
Jika Anda ingin menguji output program anda, @aditsu telah membuat logika parser combinatory (yang meliputi S, K, Idan bahkan yang lainnya seperti Bdan C) di sini .
Skor:
Karena ini adalah metagolf , tujuan dari tantangan ini adalah untuk mencapai jumlah byte terkecil dalam output yang mungkin, mengingat 50 kasus uji ini . Harap masukkan hasil Anda untuk 50 kasus uji dalam jawabannya, atau buat pastebin (atau yang serupa) dan poskan tautan ke pastebin itu.
Dalam hal seri, solusi paling awal menang.
Aturan:
- Jawaban Anda harus mengembalikan hasil CORRECT - jadi diberi input, harus mengembalikan hasil yang benar sesuai definisi dalam tugas.
- Jawaban Anda harus dikeluarkan dalam waktu satu jam pada laptop modern untuk setiap test case.
- Setiap hard-coding solusi tidak diizinkan. Namun, Anda diizinkan untuk melakukan hard-code hingga 10 combinator.
- Program Anda harus mengembalikan solusi yang sama setiap kali untuk input yang sama.
- Program Anda harus mengembalikan hasil yang valid untuk input apa pun yang diberikan, bukan hanya kasus uji.
sumber
1, Anda dapat mengurangi1dari semuanya, dan kemudian membungkus solusi untuk jawaban ituK(). Contoh: Solusi untuk2 -> 1isK, maka solusi untuk3 -> 2isKK, solution for4 -> 3isK(KK)etc.Jawaban:
Haskell , skor 5017
Ini menggabungkan algoritma yang paling mungkin untuk menghilangkan abstraksi ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M ) (λ x . N ) ) dengan pengoptimal lubang digunakan setelah setiap aplikasi. Aturan optimasi yang paling penting adalah S (K x ) (K y ) ↦ K ( xy ), yang menghentikan algoritma agar selalu meledak secara eksponensial.
Seperangkat aturan dikonfigurasi sebagai daftar pasangan string sehingga mudah untuk bermain-main dengan aturan baru. Sebagai bonus khusus menggunakan kembali parser input untuk tujuan ini, S, K, dan saya juga diterima dalam kombinator input.
Aturan tidak diterapkan tanpa syarat; alih-alih, baik versi lama dan baru disimpan, dan versi suboptimal dipangkas hanya ketika panjangnya melebihi versi terbaik lebih dari beberapa konstanta (saat ini 3 byte).
Skornya sedikit ditingkatkan dengan memperlakukan I sebagai kombinator fundamental sampai tahap output menulis ulang untuk SKK. Dengan cara itu KI = K (SKK) dapat dipersingkat 4 byte menjadi SK pada output tanpa membingungkan sisa optimasi.
Cobalah online!
Keluaran
sumber
S (K x) (K y) = K (x y))?ruleStrings. Jika tidak, output akan lebih lama secara eksponensial: untuk contoh kecil ini, kita akan mendapatkan S (S (KS) (S (S (KS) (S (KK) (KS) (KS))) (S (S) (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS) (KS))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK)))) bukan S (KS) K.Jumlah panjang solusi:
12945 85085872Kode Haskell yang mengambil jalur input dari stdin dan tidak peduli jika pemisahnya adalah
=atau->:Ini mengimplementasikan abstraksi braket yang ditingkatkan dari bagian 3.2 dari John Tromp: Binary Lambda Calculus dan Combinatory Logic yang dihubungkan dengan dari artikel Wikipedia tentang logika kombinasi. Kasing khusus yang paling berguna hanya menggunakan
Skombinator untuk mencukupi subterma untuk menghindari variabel yang bersarang secara mendalam. Kasing yang memeriksa kesetaraan beberapa subterms tidak diperlukan untuk semua kasing. Meskipun tidak ada kasus khusus untuk menanganiWcombinator (lihat jawaban Peter), aturannya bekerja bersama untuk menemukanSS(SK)ekspresi yang lebih pendek . (Saya pertama kali membuat kesalahan dengan mencoba mengoptimalkan panggilan internalabstract, kemudianWoptimasi ini tidak terjadi dan hasil keseluruhan 16 byte lebih lama.)Dan ini adalah hasil dari test case:
sumber
8486 menggunakan S, K, I, W
Penjelasan
Algoritma standar (seperti yang dijelaskan misalnya dalam bab 18 dari Untuk Mock a Mockingbird ) menggunakan empat kasus, sesuai dengan combinators
S,K,I = SKK, dan sederhana kiri-asosiasi. Saya pikir inilah yang diterapkan oleh jawaban Kristen. Ini cukup, tetapi belum tentu optimal, dan karena kami diizinkan untuk mengkode-keras hingga 10 kombinator, ia meninggalkan 7 opsi.Combinator kombinatorial terkenal lainnya adalah
yang, bersama dengan
K, menjadi dasar yang lengkap . Di SK inidan
SKIaturan - aturan itu menghasilkan ungkapan-ungkapan yang sama untukBdanC, tetapi karenaWitu diturunkanS S (K (S K K)). Karena itu saya memilih untuk menerapkanWsebagai kasus khusus.Program (CJam)
Test suite online
Output yang dihasilkan:
sumber