Tantangan ini diposting sebagai bagian dari tantangan LotM April 2018 , serta untuk ulang tahun 2nd Brain-flak
Saya sedang berpikir tentang apa cara paling efisien untuk menyandikan program brain-flak. Hal yang jelas harus dilakukan, karena hanya ada 8 karakter yang valid, adalah memetakan setiap karakter ke urutan 3-bit. Ini tentu sangat efektif, tetapi masih sangat berlebihan. Ada beberapa fitur kode brain-flak yang dapat kita manfaatkan untuk mempersingkat pengodean.
Nilad, yang semuanya diwakili oleh 2 tanda kurung yang cocok, benar-benar bertindak sebagai satu unit informasi daripada 2. Jika kita mengganti setiap braket dengan karakter byte tunggal, ini akan membuat pengkodean jauh lebih kecil tanpa kehilangan data.
Yang ini kurang jelas, tetapi byte penutup dari monad juga berlebihan. Pikirkan Anda dapat menebak apa yang
'?'
dilambangkan karakter dalam cuplikan berikut?{(({}?<>?<>?
Jika kita asumsikan inputnya adalah kode anti-otak yang valid, maka hanya ada satu opsi untuk masing-masing tanda tanya itu. Ini berarti bahwa kita dapat menggunakan karakter close monad untuk mewakili setiap braket penutup. Ini memiliki manfaat tambahan menjaga karakter tetap kecil, yang akan sangat membantu jika kita ingin menggunakan pengodean huffman. Karena karakter monad dekat kemungkinan besar akan menjadi karakter paling umum dengan margin lebar, itu bisa diwakili oleh bit tunggal, yang sangat efisien.
Dua trik ini akan memungkinkan kita memampatkan kode brain-flak melalui algoritma berikut:
Ganti setiap braket penutup dari monad dengan
|
. Atau dengan kata lain, ganti setiap braket penutup yang tidak didahului dengan pertandingan pembuka dengan bilah. Begitu...(({})<(()()())>{})
akan menjadi
(({}|<(()()()||{}|
Ganti setiap nilad dengan braket penutupnya. Karenanya, kurung yang cocok dengan tidak ada di dalamnya menggunakan pemetaan berikut:
() --> ) {} --> } [] --> ] <> --> >
Sekarang contoh terakhir kita menjadi:
((}|<()))||}|
Hapus
|
karakter tambahan. Karena kita tahu bahwa jumlah total bar harus sama dengan jumlah({[<
karakter, jika ada bar pada akhirnya hilang, kita dapat menyimpulkannya. Jadi contohnya seperti:({({})({}[()])})
akan menjadi
({(}|(}[)
Tantangan Anda untuk hari ini adalah membalikkan proses ini.
Diberikan string brain-flak terkompresi yang hanya berisi karakter (){}[]<>|
, memperluasnya ke kode brain-flak asli. Anda dapat mengasumsikan bahwa input akan selalu berkembang menjadi brain-flak yang valid. Ini berarti bahwa tidak ada awalan input yang akan mengandung lebih |
dari ({[<
karakter.
Input tidak akan mengandung |
karakter tambahan. Ini harus disimpulkan dari konteks.
Seperti biasa, Anda dapat mengirimkan program atau fungsi lengkap, dan format input / output permisif. Dan karena ini adalah kode-golf , kode Anda akan dinilai oleh panjang kode sumber dalam byte, semakin kecil skor semakin baik.
Uji kasus
Berikut ini beberapa test case. Jika Anda menginginkan lebih, Anda dapat membuat kotak uji Anda sendiri dengan skrip python ini dan Brain-Flak Wiki , yang merupakan asal sebagian besar kotak uji ini.
#Compressed code
#Original code
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
sumber
Jawaban:
Brain-Flak ,
952 916818 byteDisimpan 360 byte dengan menghitung kurung berlawanan secara relatif daripada dari awal (mis
')'
='(' + 1
bukan(((5 * 2) * 2) * 2) + 1
)Disimpan 34 byte dengan beberapa penggantian langsung dari DJMcMayhem
Disimpan 10 byte dengan tumpang tindih
>]}
kode penangananDisimpan 118 byte dengan gulungan deduplicating
Disimpan 40 byte dengan memanfaatkan tumpukan kosong untuk menyederhanakan gulungan pertama
Disimpan 48 byte dengan menandai EOF dengan -1, memungkinkan kode roll lebih ringkas
Disimpan 36 byte dengan menggunakan logika sama dengan saham bukan milikku
Disimpan 98 byte berkat Jo King menemukan cara yang lebih efisien untuk membangun output
Cobalah online!
Pertama kali bermain golf di Brain-Flak, jadi mungkin ada beberapa peningkatan yang sangat besar, tetapi berhasil. Banyak salinan / tempel untuk menangani setiap jenis braket, dan terima kasih banyak untuk generator integer otomatis dan cuplikan Roll dari sini .
Penjelasan di sini , format TIO lebih mudah
Jawaban bonus:
Brain-Flak Terkompresi 583 byte
Cobalah online!
(Perhatikan bahwa tautan di atas tidak berjalan karena TIO tidak memiliki penerjemah Brain-Flak Terkompresi. Anda dapat menemukan transpiler ke Brain-Flak di sini )
Saya telah memeriksa bahwa ini valid dengan mentransformasikan ke Brain-Flak menggunakan alat ini , sekarang cukup efisien sehingga pengaturan waktu tidak memungkinkan.
sumber
<>(<()>)
dengan(<>)
. Anda juga dapat mengubah(<>{}<>)(<()>)
ke(<(<>{}<>)>)
Retina 0.8.2 ,
10398 byteCobalah online! Tautan termasuk kasus uji. Sunting: Disimpan 5 byte dengan inspirasi dari @MartinEnder. Penjelasan:
Letakkan
;
setelah setiap braket dekat dan mengubah mereka semua untuk kurung terbuka, dan mengubah|
s untuk;
s juga.Hitung jumlah tanda kurung terbuka yang tidak cocok dan tambahkan banyak
;
.Salin setiap braket pembuka ke pencocokannya
;
.Balikkan kurung yang disalin dan hapus
;
s.sumber
|
ke sesuatu seperti!
. Itu tidak akan bahkan byte biaya jika Anda menerjemahkan>-}
ke<-{
(yang saya pikir memberikanz
untuk|
).z
tetapi saya datang dengan cara mencukur beberapa byte lagi.TIS ,
670666 byte-4 byte untuk melompat maju untuk melompat kembali
Kode:
Tata ruang:
Cobalah online!
Saya ragu ini terkecil, tapi saya tidak melihat cara untuk membuatnya lebih kecil. Sayangnya, semua
NOP
tampaknya perlu untuk menentukan waktu, dan saya tidak bisa meletakkan tumpukan di mana@14
saat ini karena membaca dariANY
dalam@11
.Struktur solusi ini adalah sebagai berikut:
Setelah melihat penjepit terbuka, buka dikirim sepanjang kolom kiri untuk menjadi output, dan tutup dikirim sepanjang kolom kanan ke tumpukan.
Setelah melihat penjepit dekat, buka dan tutup keduanya dikirim di sepanjang kolom kiri untuk menjadi output.
Setelah melihat pipa, tumpukan muncul dan dikirim ke keluaran.
Setelah EOF,
@1
akan mulai membaca dari@2
, bukannya input stream dari@0
.@2
menghasilkan aliran pipa tanpa akhir, sehingga tumpukan akan dikeringkan.Setelah input dan tumpukan habis, program berhenti.
Peringatan: karena keterbatasan TIS, ukuran tumpukan dibatasi hingga 15. Jika ada yang bersarang lebih dalam dari itu, implementasi ini akan menghasilkan hasil yang salah.
sumber
JavaScript (ES6), 107 byte
Mengambil input sebagai array karakter. Mengembalikan string.
Cobalah online!
sumber
Haskell,
127121 byteCobalah online!
Edit: -6 byte dengan menggunakan fungsi @ Laikoni untuk menemukan braket yang cocok .
sumber
Ruby , 104 byte
Ini adalah program lengkap yang di-output ke konsol.
(i<5?a:$>)<<r[-i]
harus menjadi salah satu golf paling keren yang pernah saya lakukan.Cobalah online!
Ruby , 106 byte
Ini solusi pertama saya. Fungsi lambda anonim yang mengambil dan mengembalikan string.
Cobalah online!
sumber
Brain-Flak ,
606 548 496 418 394390 byteCobalah online!
Saya memulai ini dengan memasukkan jawaban Kamil Drakari , tetapi itu menjauh dari saya sampai saya memutuskan untuk mempostingnya sebagai jawaban terpisah.
Penjelasan:
Dan tentu saja...
Brain-Flak Terkompresi, 285 byte:
sumber
Java 10, 424 byte
Agak panjang, tapi saya tidak tahu bagaimana mempersingkatnya. Ini adalah tantangan yang bagus.
Cobalah online di sini .
Versi tidak disatukan:
sumber
Python 2,
188184180177174173 byteDisimpan 4 byte berkat DJMcMayhem.
Cobalah online!
sumber
s
berakhir kosong. Jika tidak, Anda berakhir dengan karakter tambahan di ujung yang salah.Python 3 , 122 byte
Cobalah online!
sumber
Haskell , 152 byte
Cobalah online! atau verifikasi semua kasus uji .
p
mengimplementasikan pengurai rekursif, yang mungkin lebih dari membunuh untuk tata bahasa sederhana.sumber
m
untuk menemukan braket yang cocok.Python 2 , 244 byte
Cobalah online!
Butuh lebih dari satu atau dua jam untuk menyelesaikannya ...
sumber