Tulis program terpendek yang mencetak seluruh lirik "Never Gonna Give You Up" oleh Rick Astley.
Aturan:
- Harus menampilkan lirik persis seperti yang ditampilkan dalam pastebin di atas *. Inilah dump mentah: http://pastebin.com/raw/wwvdjvEj
- Tidak dapat mengandalkan sumber daya eksternal - semua lirik harus dihasilkan oleh / tertanam dalam kode.
- Tidak ada penggunaan algoritma kompresi yang ada (mis. Gzip / bzip2) kecuali Anda menyertakan algoritma lengkap dalam kode Anda.
- Gunakan bahasa apa saja, kode terpendek menang.
Pembaruan, 1 Juni 2012:
Untuk solusi yang mengandung teks non-ASCII, ukuran solusi Anda akan dihitung dalam byte, berdasarkan pada pengkodean UTF-8. Jika Anda menggunakan codepoint yang tidak dapat dikodekan dalam UTF-8, solusi Anda tidak akan dinilai sebagai valid.
Pembaruan, 7 Juni 2012:
Terima kasih atas solusi Anda yang luar biasa! Saya akan menerima jawaban tersingkat besok sore. Saat ini, jawaban GolfScript Peter Taylor menang, jadi dapatkan perbaikan jika Anda ingin mengalahkannya! :)
* Ada kesalahan ketik di Pastebin (baris 46, "tahu" harus "diketahui"). Anda bisa meniru atau tidak atas kebijakan Anda.
code-golf
kolmogorov-complexity
Polinomial
sumber
sumber
Jawaban:
Ruby
576 557556 (552) karakter && PHP 543 karakterSolusi pencarian dan ganti yang lain. Perhatikan bahwa bentuk solusi ini pada dasarnya adalah Kode Kompresi Berbasis Tata Bahasa http://en.wikipedia.org/wiki/Grammar-based_code Lihatlah http://www.cs.washington.edu/education/courses/csep590a/07au /lectures/lecture05small.pdf untuk contoh kompresi yang mudah dipahami.
Saya telah menulis aturan substitusi sehingga karakter awal untuk setiap substitusi dihitung (mereka berada dalam urutan ASCII berurutan); tidak perlu ada dalam data transisi.
catatan implementasi
implementasi yang lebih lama
Implementasi yang lebih lama ini memiliki 576 karakter dan dimulai dengan aturan substitusi dari implementasi bash / sed ugoren. Mengabaikan penggantian nama variabel substitusi, 28 penggantian pertama saya persis sama dengan yang dilakukan dalam program ugoren. Saya menambahkan beberapa lagi untuk menurunkan jumlah byte keseluruhan. Ini dimungkinkan karena aturan saya lebih terwakili secara efisien daripada yang ada dalam implementasi ugoren.
Saya tidak mencoba mengoptimalkan aturan substitusi yang satu ini.
catatan kontes
Skema dekompresi pencarian-dan-ganti berfungsi dengan baik untuk kontes ini karena sebagian besar bahasa memiliki rutinitas pra-bangun yang dapat melakukan ini. Dengan sejumlah kecil teks yang akan dihasilkan, skema dekompresi yang rumit tampaknya tidak layak menjadi pemenang.
Saya hanya menggunakan teks ASCII dan juga menghindari penggunaan karakter ASCII yang tidak patut. Dengan pembatasan ini, setiap karakter dalam kode Anda hanya dapat mewakili hingga maksimum 6,6 bit informasi; ini sangat berbeda dari teknik kompresi nyata di mana Anda menggunakan semua 8 bit. Dalam beberapa hal, itu tidak "adil" untuk membandingkan dengan ukuran kode gzip / bzip2 karena algoritma tersebut akan menggunakan semua 8 bit. Algoritma dekompresi yang lebih menarik mungkin dimungkinkan jika Anda dapat memasukkan ASCII yang secara tradisional tidak dapat dituliskan dalam string Anda DAN setiap karakter yang tidak dicetak masih ditulis dalam kode Anda sebagai satu byte.
Solusi PHP
Solusi di atas mengambil PHP dari "a sad dude" dan menggabungkannya dengan aturan substitusi saya. Jawaban PHP ternyata memiliki kode dekompresi terpendek. Lihat http://ideone.com/XoW5t
sumber
sed
Solusi saya pasti tidak bisa mengalahkannya. Saya sedang mengerjakan sesuatu yang semoga memiliki peluang - Anda memiliki 75 byte overhead, mungkin saya akan menguranginya (bukan di Ruby).Bash / Sed,
705650588582 karakterLogika :
Ide dasarnya adalah penggantian sederhana. Alih-alih menulis, misalnya
Never gonna give you up\nNever gonna let you down
, saya menulisXgive you up\nXlet you down
dan mengganti semuaX
denganNever gonna
.Ini dicapai dengan menjalankan
sed
dengan seperangkat aturan, dalam bentuks/X/Never gonna /g
.Penggantian bisa disarangkan. Sebagai contoh,
Never gonna
adalah umum, tetapi begitu jugagonna
dalam konteks lain. Jadi saya bisa menggunakan dua aturan:s/Y/ gonna/g
dans/X/NeverY/g
.Saat menambahkan aturan, bagian dari teks lagu diganti dengan karakter tunggal, sehingga menjadi lebih pendek. Aturan menjadi lebih panjang, tetapi jika string yang diganti panjang dan sering, itu sangat berharga.
Langkah selanjutnya adalah menghapus pengulangan dari
sed
perintah itu sendiri. Urutannyas/X/something/g
cukup berulang.Untuk membuatnya lebih pendek, saya mengubah perintah sed agar terlihat seperti
Xsomething
. Lalu saya gunakansed
untuk mengonversikan ini menjadised
perintah normal . Kodesed 's#.#s/&/#;s#$#/g;#
melakukannya.Hasil akhir adalah
sed
perintah, yang argumennya dihasilkan olehsed
perintah lain , dalam tanda kutip kembali.Anda dapat menemukan penjelasan yang lebih rinci di tautan ini .
Kode:
Catatan:
Mesin dekompresi hanya 40 karakter. 543 lainnya adalah tabel terjemahan dan teks terkompresi.
bzip2
kompres lagu ke 500 byte (tanpa mesin, tentu saja), jadi harus ada ruang untuk perbaikan (meskipun saya tidak melihat bagaimana saya akan menambahkan pengkodean Huffman atau sesuatu seperti ini cukup murah).<<Q
(atau<<_
) digunakan untuk membaca hingga karakter yang diberikan. Tetapi akhir dari skrip (atau ungkapan backquote) sudah cukup baik. Ini terkadang menyebabkan peringatan.Solusi yang lebih tua dan sederhana, 666 karakter:
sumber
\0
dengan&
.&
itu Anda membuat 5.Ruang putih - 33115 karakter
StackExchange menjawab jawaban saya, berikut adalah sumbernya: https://gist.github.com/lucaspiller/2852385
Tidak hebat ... Saya pikir saya mungkin bisa menyusut sedikit.
(Jika Anda tidak tahu apa itu Whitespace: http://en.wikipedia.org/wiki/Whitespace_(programming_language) )
sumber
JavaScript,
590588 byteTergantung sedikit pada cara string "dicetak".
https://gist.github.com/2864108
sumber
if(g.indexOf(g[i])!=-1)
sebelume=
untuk memperbaikinya.with(f.split(g[i]))f=join(pop())
dalamfor..in
loop menghemat satu byteC #
879816789 karakterUpaya pertama di CodeGolf jadi jelas bukan pemenang, cukup yakin itu valid meskipun itu nastiness.
sumber
var s1="a";var s2="b";
coba gunakanstring s1="a",s2="b"
; jika Anda memiliki deklarasi 2+, ini lebih pendek.!
dan membawanya keluar dari tempat lain.Python,
597589 byteDimungkinkan untuk memeras beberapa byte lagi:
sumber
BrainFuck - 9905
Cukup yakin saya bisa sedikit lebih baik dengan menyetelnya, tapi ini cukup bagus untuk saat ini. Dengan asumsi Anda tidak memiliki masalah dengan ini menjadi jauh lebih besar dari teks aslinya.
sumber
Scala, 613 byte
Ini adalah algoritma dekompresi teks, secara rekursif menerapkan aturan yang
~stuff~ blah ~ ~
harus dikonversistuff blah stuff stuff
(yaitu saat pertama kali Anda melihat pasangan simbol yang tidak dikenal, ia membatasi apa yang akan disalin; setelah itu, Anda mengisi nilainya saat melihatnya).Catatan: mungkin ada carriage return di akhir, tergantung pada bagaimana Anda menghitung. Jika ini tidak diizinkan, Anda dapat menjatuhkan yang terakhir pada penawaran (menyimpan satu karakter) dan mengubah pembagian menjadi
split(" ",-1)
(menghabiskan 3 karakter), untuk 615 byte.sumber
N
pengulangan panjangL
, Anda menggunakanL+N+1
karakter, sementara saya gunakanL+N+2
. Tetapi kode dekompresi Anda adalah 102 karakter, sedangkan kode saya adalah 40.589, C (hanya fungsi perpustakaan adalah putchar)
Tabel aturan substitusi di mana karakter dalam rentang -.._ (45..90) menentukan aturan mana yang akan diterapkan, sehingga beberapa aturan 48 (45, c-45> kode U48), karakter lain harus dicetak
aturan dibatasi oleh karakter '&' (38 dalam kode, n dikurangi hingga nol dan dengan demikian menunjuk ke aturan yang benar)
aturan 0 menunjukkan bahwa karakter selanjutnya harus ditulis dengan huruf besar (dengan menetapkan k = 32 dalam kode), ini membebaskan lebih banyak ruang untuk menambahkan rentang karakter yang lebih besar untuk aturan
main (..) dipanggil dengan 1 (sesuai nol argumen konvensi program C), dan dengan demikian aturan 1 adalah aturan root
Evolusi kode
mencukur 9 byte lebih lanjut berkat saran ugoren
mencukur 36 byte lainnya dengan membuat tabel secara algoritmik alih-alih dengan tangan, dan melalui tip "" "
mencukur 15 byte lagi dengan mengubah tabel dari char * [] menjadi string tunggal di mana '&' membatasi porsi
mencukur 19 byte lagi berkat lebih banyak tips dari ugoren
mencukur 31 byte dengan menambahkan lebih banyak aturan, membuat aturan khusus untuk huruf besar, sehingga memungkinkan lebih banyak ruang untuk indeks aturan.
mencukur 10 byte berkat lebih banyak tips dari urgoren, dan sedikit mengubah aturan
sumber
*p>>4^3?putchar(*p):e(r[*p-48])
"\'"
terjemahan tidak diperlukan."We're"
adalah string yang valid.ing
adalah kandidat yang lebih baik.d(int n)
->d(n)
. Ubah*s=='~'
ke*s-'~' and reverse the
?:, also saving parenthesis around
! N? ..: 0. Using 126 instead of
'~' `tidak berguna, tapi mengapa~
?main
rekursif. Panggilan awal adalahmain(1)
bukand(0)
, tetapi dapat ditangani dengan (mungkin terkemuka~
dis
). Juga, alternatif terbaik~
adalah tab (ascii 9 - digit tunggal).Perl,
724714883 byteJadi perubahan pada aturan menghukum penggunaan jenis Latin-1 membunuh solusi saya. Itu pendekatan yang cukup berbeda yang saya benci untuk hanya menghapusnya, jadi di sini adalah versi terbatas yang hanya menggunakan ASCII 7-bit, sesuai aturan baru, dengan peningkatan besar dalam ukuran.
Tentu saja karakter kontrol masih hancur di sini, jadi Anda tetap ingin menggunakan pengkodean base64:
Karena saya pikir itu harus tetap terlihat meskipun DQ, inilah solusi asli:
Pengkodean naskah base64:
sumber
Python
781731605579 CharsAda lebih banyak dan lebih banyak jawaban yang lebih baik dari ketika saya pertama kali melihat ini, tetapi saya membuang banyak waktu pada skrip python saya jadi saya akan mempostingnya dengan cara apa pun, akan luar biasa untuk melihat saran untuk memperpendeknya,
Sunting: berkat saran Ed H, 2 karakter dicincang, untuk melangkah lebih jauh saya mungkin harus merestrukturisasi banyak hal di sini yang akan memakan waktu
Setelah pertama kali saya menghasilkan string secara manual (sangat membosankan), saya menulis sebuah fungsi untuk secara rekursif menemukan penggantian pola yang paling menguntungkan (pada langkah itu), yang memberi saya solusi tetapi ternyata meningkatkan ukurannya sebesar 10 karakter.
Jadi, saya membuat algoritma saya sedikit kurang serakah dengan alih-alih melakukan peringkat akhir hanya pada 'karakter dikurangi', peringkat pada fungsi 'karakter berkurang', 'panjang pola' dan 'jumlah pola'
panjang pola = jumlah panjang = jumlah
Kemudian saya meminta laptop saya yang buruk untuk berjalan tanpa batas, memberikan nilai acak ke
lengthWeight
dancountWeight
dan mendapatkan ukuran kompresi akhir yang berbeda, dan menyimpan data untuk ukuran kompresi minimum dalam fileDalam setengah jam atau lebih itu muncul dengan string di atas (saya mencoba untuk mengotak-atik lebih jauh untuk melihat apakah saya dapat mempersingkat kode), dan itu tidak akan lebih rendah, saya kira saya kehilangan sesuatu di sini.
inilah kode saya untuk itu, juga
max_pattern
sangat lambat (Catatan: kode mengeluarkan string yang mirip dengan bentuk di versi saya sebelumnya dari solusi, saya secara manual bekerja melewatinya untuk mendapatkan bentuk saat ini, secara manual maksud saya, secara manual di shell python)sumber
\n
biaya 5 karakter dan menghemat 9. 2. Ruang ekstra diin (g,l..)
. 3.join(..)
bekerja dengan baikjoin([..])
(setidaknya dalam 2,7).Malbolge, 12735 byte
Cobalah online.
Dihasilkan menggunakan alat di sini.
sumber
JavaScript 666 Bytes
Terinspirasi oleh solusi tkazec .
Lihat posting blog yang saya tulis tentang itu, itu berisi semua sumber dan menjelaskan bagaimana saya membangun kode itu.
Anda dapat menyalin dan menempelkan kode ke konsol browser Anda. Atau coba di http://jsfiddle.net/eikes/Sws4g/1/
sumber
Perl,
584578577576575571564554553540Solusi ini mengikuti pendekatan dasar yang sama seperti kebanyakan yang lain: diberi string awal, melakukan penggantian berulang dari bagian teks yang diulang.
Aturan substitusi ditentukan oleh satu karakter, lebih disukai yang tidak muncul dalam teks output, sehingga aturan panjang L dan terjadi N kali akan menghemat sekitar N * LNL-1 (N * L adalah panjang asli dari semua kejadian, tetapi karakter substitusi terjadi N kali, dan teks literal itu sendiri memiliki panjang L, dan aturan dibagi dengan karakter pemisah.) Jika karakter substitusi ditentukan secara eksplisit, maka penghematan dikurangi menjadi N * LNL-2. Mengingat bahwa sebagian besar bahasa dapat menghitung karakter dengan chr () atau kode pendek yang serupa, pendekatan pertama cenderung lebih unggul.
Ada beberapa kelemahan untuk menghitung karakter substitusi, yang paling penting adalah kebutuhan akan rangkaian karakter ASCII yang berkelanjutan. Keluaran menggunakan sebagian besar huruf kecil, tetapi ada cukup huruf besar dan tanda baca untuk mengharuskan mengganti karakter dengan dirinya sendiri, memetakan kembali beberapa karakter dalam tahap perbaikan setelahnya, atau memesan aturan sedemikian rupa sehingga penggantian dengan karakter bermasalah terjadi sebelumnya. Menggunakan bahasa yang menggantikan menggunakan regex juga berarti ada gotcha untuk karakter yang memiliki arti khusus dalam suatu regex:
.
+
*
\
?
Pendekatan asli saya memiliki 63 byte dalam decoder dan 521 dalam aturan. Saya menghabiskan banyak waktu untuk mengoptimalkan aturan, yang bisa rumit terutama dengan aturan pendek karena bisa tumpang tindih. Saya mendapatkan decoding hingga 55 byte dan aturan turun ke 485 dengan menipu formula sedikit. Biasanya, aturan 2 karakter yang muncul 3 kali atau aturan 3 karakter yang muncul dua kali tidak akan benar-benar menghemat panjang, tetapi ada celah - yang juga memungkinkan untuk membuat kata-kata yang bukan bagian dari output; - ).
Saya menggunakan karakter kontrol dalam solusi ini, jadi solusinya disediakan di sini base64-encoded.
Dan ini dia versi yang sedikit lebih mudah dibaca (tapi kurang bisa dieksekusi).
Namun, saya menduga ini masih belum minimum, karena Ed H. menunjukkan bahwa pendekodean php adalah yang terpendek pada 44 byte dan saya telah melihat ruang untuk perbaikan dalam aturan yang dia gunakan. Saya memang memiliki decoder 52-byte di Perl tetapi saya tidak dapat menggunakannya untuk solusi ini karena saya perlu menjalankan rentang secara terbalik.
sumber
PHP
730707 karaktersumber
$s="Never gonna give...
dapat disingkat dengan$n
.Perl -
589 588 583 579576 BytesSetiap aturan terdiri dari 1 char head, body, dan garis bawah. Selama aturan dapat dipotong dari beginnig, kepala aturan diganti dengan badannya di sisa Teks. Kepala aturan pertama diberikan, kepala semua aturan berikut dihasilkan dari variabel $ i.
Karena kepala untuk aturan selanjutnya ditempatkan di awal teks dengan aturan sebelumnya, aturan terakhir akan membuat karakter yang tidak akan dihapus lagi. Saya harus memilih serangkaian nama di mana yang terakhir adalah "W", sehingga saya dapat menghapus "W" yang asli dari awal lirik, dan menggantinya dengan penggantian aturan.
Pengkodean dilakukan dengan skrip Python menggunakan algoritma hillclimbing sederhana.
Berikut adalah kode Perl:
(Saya merasa luar biasa bahwa Teks yang dikompresi berisi "hearBach": D)
Dan di sini kode Python yang menghasilkannya:
sumber
while
untuk loop; ini memungkinkan Anda melepaskan kawat gigi serta tanda kurung. Gagasan lain: cari tahu cara menggunakansay
alih-alihprint
melakukan output.Python 2.7,
975803 byteBukan yang terbesar - Saya (sekarang) berharap python melakukan format ekspansi seperti itu. Sayangnya tidak.
Sunting: Simulasi ekspansi dengan sintaks pemformatan alternatif (semacam ..)
sumber
Clojure
720 byte / karakter:
(Direproduksi di sini dengan spasi kosong sehingga Anda dapat melihat formatnya)
sumber
C # - 605 karakter | T-SQL - 795 karakter | C # - 732 karakter | C # - 659 karakter
Inspirasi untuk ini berasal dari contoh sed. Satu-satunya perubahan besar yang saya lakukan adalah membuat pencarian karakter ASCII berturut-turut sehingga tidak harus dinyatakan. Sayangnya, ini adalah C #, jadi saya tidak tahu bagaimana membuatnya lebih kecil. Saya mengambil teks pengganti yang sama dan melakukan kode dalam T-SQL menggunakan tabel temp.
T-SQL
C # - Coba Kedua Ini dicoba pada pendekatan yang berbeda. Kompresi dilakukan sepenuhnya oleh komputer mencari pengganti terbaik. Pencarian dilakukan secara berurutan dan dipesan berdasarkan ukuran sehingga tidak perlu untuk pencarian yang dibatasi, namun, kode untuk melakukan pencarian itu kurang efisien daripada yang saya kira sehingga akhirnya menghabiskan 127 karakter lebih banyak secara keseluruhan! Hidup dan belajar.
Coba ke-3 di C #. Kali ini saya kedaluwarsa dengan karakter \ b, \ r, \ t. Anda dapat menggunakan \ rN \ n untuk mengganti karakter pertama pada baris dengan huruf kapital N, tetapi sebenarnya tidak menyimpan karakter. Saya membuat alias untuk memindahkan kursor kembali dan kemudian menulis di atas teks yang ada. Tapi tidak ada yang menyelamatkan ruang ini dan pada akhirnya saya masih lebih buruk daripada strategi pencarian-dan-ganti yang sederhana.
sumber
REPLACE
pendekatan pintar , terutama dengan SQL dinamis, tetapi ada banyak cara untuk bermain golf yang lebih: Gunakan@
sebagai variabel, bukan@s
, buat tabel permanen,t
bukan#t
(Anda tidak harus membersihkan sendiri), singkirkan pernyataan COLLATE 29-karakter dan hanya perlu dijalankan di server / database dengan pemeriksaan yang tepat, gunakanvarchar(999)
atauvarchar(max)
, ton ruang putih yang tidak perlu di sekitar sama dengan tanda dan koma, dll.PHP,
591585568564 bytesumber
Ruby, 1014 byte
Saya hanya belajar pemrograman, jadi saya tidak akan memecahkan rekor apa pun di sini. Tapi, ini tugas yang menyenangkan.
sumber
GolfScript (511 bytes)
Ini menggunakan perubahan basis untuk mengemas bit, sehingga termasuk karakter yang tidak ada dalam ASCII. Namun, tidak tepat untuk menilai karakter-karakter tersebut dengan pengkodean UTF-8 mereka karena penerjemah menganggap program sebagai ISO-8859-1. Untuk alasan ini saya telah menentukan panjang dalam byte daripada karakter.
Base-64 dikodekan:
Hex dump (keluaran dari
xxd
):Karena sebagian besar solusi terbaik, ini menggunakan pendekatan berbasis tata bahasa dengan perpecahan string dan bergabung untuk memperluas tata bahasa. Tata bahasa memiliki 30 aturan dan ditemukan oleh pencarian serakah.
sumber
JavaScript, 854 karakter (menambahkan baris baru untuk "keterbacaan")
sumber
Naif sh / echo - 810 byte
sumber
JavaScript 789 karakter
Javascript saya (dicetak dengan "document.write ()"):
Saya mengubah beberapa kata dan frasa umum dengan huruf cyril dan kemudian mengubahnya kembali dengan fungsi replace ().
Setelah saya mempersingkat lirik, saya mempersingkat program saya dengan metode yang sama, dan mengeksekusi kode dengan eval ().
sumber
Ruby,
741678657627619 byteIni adalah perluasan simbol berulang. Untuk masing-masing 28 karakter string dalam argumen pertama
gsub!
, semua kemunculan karakter_
tersebut digantikan oleh bagian yang sesuai dari string kedua (dipisahkan oleh+
karakter).sumber
Python, 573 karakter
sed
Solusi saya tidak akan melangkah lebih jauh, dan itu dikalahkan oleh beberapa orang, jadi saya mencari pendekatan baru.Sayangnya, itu hanya cukup untuk
posisike-2ke-3 (seperti yang sekarang) - Ed H. masih jauh di depan saya .Catatan :
Gagasan utama dipinjam dari Ed H. - menggunakan karakter berturut-turut untuk penggantian, alih-alih menentukannya dalam setiap aturan penggantian.
Cara saya berurusan dengan karakter yang ada dalam lagu
berbeda dari Ed- saya hanya memastikan untuk menerjemahkan masing-masing ke dirinya sendiri (dan jika itu selalu diikuti oleh sesuatu, tambahkan juga, yang hanya berfungsi untukW
).Kode dihasilkan oleh skrip yang mencari terjemahan yang baik. Pada awalnya, saya menggunakan algoritma serakah, yang hanya mengambil satu yang memberikan pengurangan terbaik. Kemudian saya telah menemukan bahwa mengutak-atiknya untuk memilih string yang lebih lama meningkatkannya sedikit. Saya kira itu masih belum optimal.
sumber
Golfscript,
708702699691 bytesumber
" I'm feeling":i;
?j
, saya menetapkan tiga string yang digabungkan (dihapus{
dan}
, tetapi ditambahkan++
untuk digabungkan). Ini memungkinkan saya untuk menyatakani
sebaris, saat menulis kontenj
.g
dan untuk paduan suara menggunakan string tunggal dengan baris baru dan kemudiann/g*
g
karena ini juga digunakan menjelang akhir (sebenarnya mungkin, tetapi akan menghabiskan 1 char pada akhirnya). Namun, pendekatan split / fold untuk memasukkan g pada awal setiap baris adalah penghemat karakter yang hebat.Java, 858 byte
Wow. Saya tidak benar-benar berpikir saya dapat menekan ini dengan keras.
Tidak Digubahdalam bentuk yang dapat dibaca manusia:sumber
String foo; String bar;
ungolfing.JavaScript,
14281451883 * karakterJelas bukan solusi terpendek, tapi ini dia.
Logika solusi cukup sederhana:
* Tentu saja solusinya menjadi jauh lebih pendek saat mengambil garis yang unik daripada kata-kata yang unik.
sumber