Pindah ke depan ASCII yang dapat dicetak

19

Latar Belakang

The Langkah-to-front transform (MTF) adalah data yang pengkodean algoritma yang dirancang untuk meningkatkan kinerja teknik encoding entropi.

Dalam algoritma kompresi bzip2 , ini diterapkan setelah transformasi Burrows-Wheeler (seperti yang terlihat di Burrows, Wheeler dan Kembali ), dengan tujuan mengubah kelompok karakter yang diulang menjadi bilangan bulat non-negatif yang kecil dan mudah dikompres.

Definisi

Untuk tujuan tantangan ini, kami akan menentukan versi MTC ASCII yang dapat dicetak sebagai berikut:

Diberikan string input s , ambil array kosong r , string d dari semua karakter ASCII yang dapat dicetak (0x20 hingga 0x7E) dan ulangi yang berikut untuk setiap karakter c dari s :

  1. Tambahkan indeks c dalam d ke r .

  2. Pindahkan c ke bagian depan d , yaitu, hapus c dari d dan tambahkan ke sisanya.

Akhirnya, kita mengambil elemen r sebagai indeks dalam d asli dan mengambil karakter yang sesuai.

Contoh langkah demi langkah

INPUT: "CODEGOLF"

0. s = "CODEGOLF"
   d = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = []
1. s = "ODEGOLF"
   d = "C !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35]
2. s = "DEGOLF"
   d = "OC !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47]
3. s = "EGOLF"
   d = "DOC !\"#$%&'()*+,-./0123456789:;<=>?@ABEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37]
4. s = "GOLF"
   d = "EDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37 38]
5. s = "OLF"
   d = "GEDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37 38 40]
6. s = "LF"
   d = "OGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37 38 40 3]
7. s = "F"
   d = "LOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37 38 40 3 45]
8. s = ""
   d = "FLOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
   r = [35 47 37 38 40 3 45 41]

OUTPUT: "COEFH#MI"

Tugas

Tulis program atau fungsi yang mengimplementasikan MTF ASCII yang dapat dicetak (sebagaimana didefinisikan di atas).

Uji kasus

Input:  Programming Puzzles & Code Golf
Output: Prpi"do lp%((uz rnu&3!P/o&$U$(p

Input:  NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN BATMAN!
Output: Na! !! !! !! !! !! !! !! !! !! !! !! !! !! !! !!"DDUP"%'

Input:  Two more questions and I have bzip2 in less than 100 bytes!
Output: Twp#o"si$sv#uvq(u$(l#o#W!r%w+$pz,xF%#,"x(. #0--'$GG ".z(**:

Aturan tambahan

  • Anda tidak dapat menggunakan operator bawaan yang menghitung MTF string.

  • Kode Anda dapat mencetak baris tambahan jika Anda memilih STDOUT untuk hasil.

  • Kode Anda harus berfungsi untuk input 1000 atau kurang karakter ASCII yang dapat dicetak (0x20 hingga 0x7E).

  • Aturan golf kode standar berlaku. Pengajuan terpendek dalam byte menang.

Dennis
sumber
1
"Nanananana DDUP!" hanya tidak semenarik "Batman!" ...
Gagang pintu
8
@ Doorknob: Tapi Batman tidak mudah kompres.
Dennis
Bisakah kita menampilkan hasilnya dalam fungsi pengembalian alih-alih mencetaknya ke STDOUT?
Fatalkan
@Fatalize: Itu bentuk keluaran yang paling alami untuk fungsi, jadi ya. Ngomong-ngomong, kami memiliki standar untuk I / O , jadi kecuali jika pertanyaannya secara eksplisit mengatakan sebaliknya, itu selalu diizinkan.
Dennis

Jawaban:

6

CJam, 20

'¡,q{_C#c' ,C+@|}fC;

Cobalah online

Penjelasan:

'¡,      make a string of characters with codes from 0 to 160 (a modified "d")
         could have been to 126 but stackexchange doesn't like the DEL character
q        read the input (s)
{…}fC    for each character C in s
  _      duplicate the d string
  C#     find the index of C in d
  c      convert to character (this is the result)
  ' ,    make a string of characters from 0 to 31
  C+     append C to the string
  @      bring d to the top
  |      set union, preserving order; effectively, C is moved to position 32
         this is the updated d string
;        pop the last d
aditsu
sumber
6

Burung unta , 46 45 karakter

Tidak memiliki nomor versi di header karena ini sebenarnya hanya komit terbaru . Saya menambahkan Ooperator (kode ascii ke string) setelah merilis versi terbaru (tetapi masih sebelum tantangan ini diposting).

{a95,{32+O}%:d3@{:x\.3@?3@\+\x-x\+}/;{d=}%s*}

Penjelasan:

a             this is the "r" array (a is short for [], empty array)
95,{32+O}%:d  this is the "d" array
3@{...}/      for each character in the input (as an "argument")...
  :x            store in variable x (stack is now [r d c])
  \.3@?         find index in d     (stack is now [r d idx])
  3@\+          append index to r   (stack is now [d modified_r])
  \x-           remove char from d, and then...
  x\+           prepend char to d   (stack is now [modified_r modified_d])
;             throw away modified_d
{d=}%         map r to indices of (original) d
s*            join (s is short for ``, empty string)
Gagang pintu
sumber
Saya bertanya-tanya apakah PPCG beralih dari "kode tugas ini dengan cara yang paling mungkin dalam bahasa favorit Anda" ke "rancang bahasa pemrograman Anda sendiri untuk menyelesaikan tugas kode golf yang lebih pendek daripada skrip golf"
John Dvorak
1
@AlexA. ... tunggu, ya, dieja seperti itu? seluruh hidupku bohong
Doorknob
@JanDvorak Ostrich hampir identik dengan GolfScript. Hanya alasan sebenarnya yang saya buat adalah karena a.) GolfScript mengganggu tidak memiliki REPL dan b.) Ada beberapa operator / fitur yang hilang (floating point, I / O, dll). Dan desain bahasa memang menyenangkan!
Gagang pintu
3

Python 3, 88

*d,=range(127)
for c in input():y=d.index(ord(c));d[:32]+=d.pop(y),;print(chr(y),end='')

Menggunakan beberapa ide dari solusi CJam saya.
-4 byte milik Sp3000 :)

aditsu
sumber
2

SWI-Prolog, 239 197 189 byte

a(S):-l([126],X),a(S,X,[],R),b(R,X).
a([A|T],X,S,R):-nth0(I,X,A,Z),(a(T,[A|Z],[I|S],R);R=[I|S]).
b([A|T],X):-(b(T,X);!),nth0(A,X,E),put(E).
l([B|R],Z):-A is B-1,X=[A,B|R],(A=32,Z=X;l(X,Z)).

Contoh: a(`Two more questions and I have bzip2 in less than 100 bytes!`).keluaran:

Twp#o"si$sv#uvq(u$(l#o#W!r%w+$pz,xF%#,"x(. #0--'$GG ".z(**:

(dan true .setelah itu, jelas)

Catatan: versi SWI-Prolog Anda harus salah satu yang lebih baru di mana backquote `mewakili string kode. String kode yang digunakan untuk diwakili dengan tanda kutip ganda "dalam versi yang lebih lama.

Fatalisasi
sumber
2

Python 2, 137 110 104

Tidak sulit untuk diterapkan, tetapi mungkin masih bisa golf?

Coba di sini

e=d=map(chr,range(32,127))
r=""
for c in raw_input():n=e.index(c);r+=d[n];e=[e[n]]+e[:n]+e[n+1:]
print r
mbomb007
sumber
1
Saya pikir Anda lebih baik melakukan daftar peta e=d=map(chr,range(32,127))dengan Python 2, meskipun Anda harus men-tweak euntuk menangani daftar.
xnor
@ Terima kasih. Saya juga mencoba menggunakan e=[e.pop(n)]+e, tetapi tidak berhasil. Mengapa demikian?
mbomb007
Anda punya e=d=, jadi ketika Anda pop dari eAnda juga muncul dari d. Coba d=e[:].
Sp3000
1
Tetapi pada titik ini mungkin lebih baik untuk melakukan n=e.index(ord(c));r+=chr(n+32);dan menjatuhkand
Sp3000
1

Pyth, 24 byte

JK>95CM127s@LKxL~J+d-Jdz

Demonstrasi. Uji Harness.

Bit pertama. JK>95CM127mengatur daftar yang diperlukan dan menyimpannya ke Jdan K. ~J+d-Jdmelakukan pembaruan daftar, sementara xL ... zmemetakan karakter input ke posisi mereka dalam daftar. Akhirnya, s@LKubah indeks tersebut menjadi karakter dalam daftar asli.

isaacg
sumber
1

Haskell, 120 byte

e#s=[b|(b,a)<-zip[0..]s,a==e]!!0
a=[' '..'~']
f=snd.foldl(\(d,r)e->(e:take(e#d)d++tail(drop(e#d)d),r++[a!!(e#d)]))(a,[])

Contoh penggunaan: f "CODEGOLF"->"COEFH#MI"

Cara kerjanya: #adalah fungsi indeks yang mengembalikan posisi edalam s(tidak dapat menggunakan asli Haskell elemIndexkarena mahal import). Fungsi utama fmengikuti pola lipatan di mana ia memperbarui string posisi ddan string hasil rsaat berjalan melalui string input.

nimi
sumber