Dimungkinkan untuk mengompres beberapa jenis data, seperti teks manusia atau kode sumber, dengan tata bahasa garis lurus. Anda pada dasarnya membuat tata bahasa yang bahasanya memiliki satu kata - data yang tidak terkompresi. Dalam tugas ini, Anda harus menulis sebuah program yang mengimplementasikan metode pemadatan data ini.
Memasukkan
Input adalah string dengan panjang tidak lebih dari 65535 byte. Dijamin, bahwa input cocok dengan ekspresi reguler [!-~]+
(yaitu setidaknya satu karakter ASCII yang dapat dicetak tidak termasuk spasi).
Contoh input adalah
abcabcbcbcabcacacabababab
Keluaran
Outputnya adalah seperangkat aturan yang membentuk tata bahasa yang menggambarkan tepat satu kata (input). Setiap nonterminal dilambangkan dengan angka desimal lebih besar dari 9. Simbol awal adalah simbol nomor sepuluh. Contoh output yang sesuai dengan contoh input diberikan di bawah ini; sintaksnya dijelaskan lebih lanjut di bawah ini:
10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b
Setiap aturan memiliki bentuk <nonterminal>=<symbol> <symbol> ...
dengan jumlah simbol yang dipisahkan spasi-putih sewenang-wenang di sisi kanan. Setiap output yang mematuhi batasan berikut dan mendapatkan string input dengan benar.
Batasan
Untuk menghentikan orang melakukan hal-hal aneh, sejumlah pembatasan dilakukan:
Setiap nonterminal harus muncul setidaknya dua kali di sisi kanan aturan. Misalnya, tata bahasa untuk input
abcabc
ini ilegal karena aturan 12 hanya muncul sekali:10=12 11=a b c 12=11 11
Tidak ada urutan dari dua simbol yang berdekatan dapat muncul lebih dari sekali di semua sisi kanan semua aturan, kecuali jika mereka tumpang tindih. Misalnya, tata bahasa untuk input
abcabcbc
ini ilegal karena urutannyabc
muncul dua kali:10=11 11 b c 11=a b c
Tata bahasa yang valid adalah:
10=11 11 12 11=a 12 12=b c
Program Anda harus berhenti dalam waktu kurang dari satu menit untuk setiap input yang valid yang tidak lebih dari 65535 byte.
Seperti biasa, Anda tidak boleh menggunakan fasilitas apa pun dari bahasa Anda atau fungsi perpustakaan apa pun yang membuat solusi sepele atau mengimplementasikan sebagian besar dari itu.
Input sampel
Hasilkan input sampel dengan program C berikut.
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
unsigned int i,j = 0,k;
if (argc != 3
|| 2 != sscanf(argv[1],"%u",&i)
+ sscanf(argv[2],"%u",&k)) {
fprintf(stderr,"Usage: %s seed length\n",argv[0]);
return EXIT_FAILURE;
}
srand(i);
while(j < k) {
i = rand() & 0x7f;
if (i > 34 && i != 127) j++, putchar(i);
}
return EXIT_SUCCESS;
}
Input sampel yang dihasilkan oleh program di atas biasanya tidak akan menghasilkan hasil kompresi yang baik. Pertimbangkan untuk menggunakan teks manusia atau kode sumber sebagai input contoh.
Kriteria menang
Ini adalah kode golf; program dengan kode sumber terpendek akan menang. Untuk kredit tambahan, tulis sebuah program yang merekonstruksi input dari output.
sumber
Jawaban:
GolfScript,
111108 karakterIni adalah pendekatan yang cukup canggung menggunakan GolfScript. Versi kedua berkinerja lebih baik daripada versi awal. Ini jauh lebih lama daripada kode yang dimaksud tetapi implementasi saya telah membuat do-loop dan ini menyebabkan masalah dengan penerjemah.
Contoh:
sumber
Retraksi - algoritma tidak dapat menangani semua kasus.
C, 422 (diperbaiki untuk menghapus dups dalam output, dan menjatuhkan karakter)Implementasi awal, akan mulai bermain golf itu.
Karena aturan tidak mengharuskannya untuk benar-benar menekan pendekatan naif brute force ini akan dilakukan ...
Dapat memproses panjang 65535 dalam 10 detik
Contoh dijalankan:
sumber