Salah satu paradigma pemrograman yang kurang dikenal yang tampaknya cukup pas untuk kode golf adalah Overlapping Oriented Programming (OOP) *. Saat menulis kode yang sebagian identik, banyak byte yang dapat disimpan dengan hanya menumpangtindih bagian-bagian yang identik dan mengingat dengan cara di mana dua baris kode asli dimulai. Tugas Anda adalah menulis dua program atau fungsi yang tumpang tindihcompress
dan decompress
dengan spesifikasi berikut:
* Jangan gunakan dalam kode produksi, mungkin.
compress
compress
mengambil dua string dalam format apa pun yang nyaman dan tumpang tindih sebanyak mungkin. Itu adalah string s
dengan panjang minimal dikembalikan sehingga kedua string input adalah substring dari s
. Selain itu, beberapa output yang mengidentifikasi indeks awal dan akhir dari kedua string dikembalikan.
Contoh: (Format IO yang tepat terserah Anda)
compress("abcd", "deab") -> "deabcd" ((2,5),(0,3))
compress("abcd", "bc") -> "abcd" ((0,3),(1,2))
compress("abc", "def") -> "abcdef" ((0,2),(3,5)) or "defabc" ((3,5),(0,2))
decompress
decompress
menghitung fungsi kebalikan dari compress
, yang diberi string dan dua indeks awal dan akhir (dalam format di mana mereka dikembalikan oleh Anda compress
), mengembalikan dua string asli. Anda hanya perlu menangani input yang valid. Kesetaraan berikut harus berlaku untuk semua string s1
, s2
:
(s1, s2) == decompress (compress (s1, s2))
Contoh: (terbalik compress
contoh)
decompress "deabcd" ((2,5),(0,3)) -> "abcd" "deab"
decompress "abcd" ((0,3),(1,2)) -> "abcd" "bc"
decompress "abcdef" ((0,2),(3,5)) -> "abc" "def"
or (whichever version your "compress" generates)
decompress "defabc" ((3,5),(0,2)) -> "abc" "def"
Mencetak gol
Skor Anda adalah ukuran string yang dikembalikan dengan menelepon compress("<code of compress>", "<code of decompress>")
. Karena ini adalah kode-golf, skor yang lebih rendah lebih baik.
Contoh:
Asumsikan kode untuk fungsi Anda compress
adalah c=abcd
dan kode untuk decompress
adalah d=efghi
. Kemudian compress("c=abcd", "d=efghi")
menghasilkan "c=abcd=efghi"
(dan indeks, tetapi itu tidak mempengaruhi penilaian) sehingga nilainya length "c=abcd=efghi" = 12
.
Aturan tambahan
- Dalam semangat tantangan ini, Anda
compress
dandecompress
harus tumpang tindih dalam setidaknya satu karakter. Anda mungkin mencapai ini sepele dengan menambahkan komentar, tetapi perhatikan bahwa hal itu akan meningkatkan skor Anda dan mungkin ada solusi yang lebih pendek menggunakan kode yang tumpang tindih secara inheren. compress
dandecompress
harus dapat menangani string yang berisi karakter ASCII yang dapat dicetak serta semua karakter yang Anda gunakan untuk mendefinisikancompress
dandecompress
.- Indeks bisa nol atau satu diindeks.
- Program atau fungsi Anda tidak harus benar-benar diberi nama
compress
dandecompress
.
Jawaban:
GNU Prolog, 105 poin
(Ini memerlukan GNU Prolog karena
prefix
dansuffix
tidak portabel.)Prolog memiliki satu keuntungan utama yang menarik untuk tantangan ini; Anda dapat menulis fungsi untuk menangani beberapa pola panggilan (yaitu Anda tidak hanya dapat memberikan fungsi input untuk mendapatkan output yang sesuai, Anda dapat memberikan fungsi output untuk mendapatkan input yang sesuai). Dengan demikian, kita dapat mendefinisikan fungsi yang dapat menangani kompresi dan dekompresi, yang mengarah ke pengiriman 105 byte yang mendefinisikan fungsi
o
yang bekerja dengan dua arah. (Kebetulan, saya sebagian besar menulisnya sebagai dekompresor - karena lebih sederhana - dan mendapat kompresor "gratis".) Secara umum, kita dapat mengharapkan program yang sangat singkat di Prolog untuk tugas ini, jika bukan karena fakta bahwa itu sangat buruk pada penanganan string (baik dalam hal primitif yang hilang, dan dalam hal primitif yang bersangkutan memiliki nama yang sangat panjang).Argumen pertama
o
adalah tupel string, misalnya"abcd"-"deab"
. Argumen kedua memiliki bentuk seperti"deabcd"-4/6-4/4
; ini adalah tusuk bersarang yang cukup standar, dan berarti bahwa string tersebut "deabcd", string pertama memiliki panjang 4 dan berakhir pada karakter keenam, string kedua memiliki panjang 4 dan berakhir pada karakter keempat. (Perhatikan bahwa string dalam GNU Prolog hanyalah daftar kode karakter, yang membuat debugging mengganggu karena implementasi lebih memilih interpretasi yang terakhir secara default.) Jika Anda memberikano
satu argumen, itu akan menampilkan yang lain untuk Anda (dengan demikian berfungsi sebagai kompresor jika Anda memberikan argumen pertama, dan dekompresor jika Anda memberikan argumen kedua). Jika Anda memberikan kedua argumen, itu akan memverifikasi bahwa representasi terkompresi cocok dengan string yang diberikan. Jika Anda memberikan argumen nol, itu akan menghasilkan output seperti ini:Deskripsi format I / O di atas hampir seluruhnya hanya deskripsi program, juga; tidak ada banyak dalam program sama sekali. Satu-satunya kehalusan adalah berkaitan dengan petunjuk urutan evaluasi; kita perlu memastikan bahwa program tidak hanya menggunakan strategi pencarian yang dijamin akan berakhir, tetapi juga menghasilkan string keluaran sesingkat mungkin.
Saat mengompresi, kita mulai dengan
length(C,_)
("C
memiliki panjang"), yang merupakan trik yang saya gunakan dalam banyak jawaban Prolog dan Brachylog; jika ini adalah hal pertama yang dilihat Prolog, itu akan membuatnya memprioritaskan pengurangan panjangC
daripada yang lainnya. Ini memastikan bahwa kami memiliki panjang minimumC
. Urutan kendala dalams
dipilih dengan cermat sehingga pencarian akan memakan waktu terbatas untuk setiap kemungkinan panjang kandidatC
;A
dibatasi olehC
(kita tidak tahuC
, tetapi kita tahu nilai target yang kita miliki untuk panjangnya),M
olehA
,U
olehA
, danL
olehU
, sehingga tidak ada pencarian yang dapat memakan waktu tanpa batas.Saat dekompresi, kami diberikan
C
langsung oleh pengguna. Ini lagi memastikan program akan berjalan dalam waktu yang terbatas, karena urutan kendala yang sama. (Orang-orang yang mengetahui urutan evaluasi Prolog akan mencatat bahwa definisis
sangat tidak efisien ketika dekompresi; penempatanlength(A,M)
danlength(U,L)
pertama akan lebih cepat, tetapi pindahlength(A,M)
ke awal dapat menyebabkan loop tak terbatas ketika dikompresi karena tidakA
jugaM
tidak terikat oleh apa pun pada saat itu) .)sumber
Brachylog ,
5046 byteCobalah online!
Dekompresi:
Cobalah online!
Disimpan 5 byte berkat @ ais523
Penjelasan
Sisi baik dari bahasa deklaratif adalah kita dapat menggunakan kembali kode yang sama untuk mengompresi dan mendekompresi. Dengan demikian, kode untuk kompres sama persis dengan untuk dekompresi , dengan tambahan
~
di awal.Ini
~
memberitahu Brachylog untuk membalik urutan argumen (yaitu, gunakan Input sebagai output dan Output sebagai input). Karena kompres tidak ada~
, itu benar-benar menjalankan predikat dalam urutan standar. Karena dekompresi hanya memiliki satu, ia menjalankannya dengan Input sebagai output dan Output sebagai input.Dengan begitu, kita bisa menggunakan kode yang sama (modulo ekstra
~
) untuk kompres dan dekompresi: kompres menyediakan dua string sebagai input dan variabel sebagai output, dan dekompresi menyediakan indeks dan string terkompresi sebagai output dan variabel sebagai input .Jelas ini juga berarti bahwa kita harus sedikit eksplisit tentang kode kompresi kita, sehingga penerjemah mampu menjalankannya "mundur". Inilah sebabnya mengapa kompresor itu sendiri agak panjang.
Berikut ini adalah rincian kode untuk Kompres (dan karenanya juga dari dekompresi):
sumber
Jelly ,
5850 byte-1 byte terima kasih kepada ais523 (gunakan
⁾
untuk string dua byte)Ini mungkin cukup golf ...
Kompresi mengambil dua argumen string dan mengembalikan daftar:
[[[startA, lengthA], [startB, lengthB]], compressedString]
Dekompresi mengambil satu argumen (daftar seperti itu) dan mengembalikan dua * string:
Kode yang tumpang tindih:
Diindeks satu.
* ini mungkin tidak jelas karena pemformatan cetak implisit Jelly, jadi kode di TryItOnline yang ditautkan ke atas memiliki byte tambahan (a
Y
di bagian akhir) untuk menyisipkan feed garis antara keduanya dalam output yang dicetak.Saya mulai dengan satu program, yang menggunakan kedalaman argumen pertama (atau satu-satunya) untuk memutuskan antara kompresi dan dekompresi, tetapi memiliki tautan yang tidak digunakan dalam kode dekompresi (baris pertama) dan satu byte tumpang tindih tunggal lebih pendek sebesar tujuh byte .
Bagaimana?
sumber
“ṫḣ”
dapat di-golf dengan 1 byte menggunakan sintaks Jelly untuk string 2-karakter.