Mengkompresi data RLE untuk menggambar seni ASCII

11

Pertanyaan ini didasarkan pada apa yang saya temukan untuk menjawab pertanyaan lain .

Terkadang pertanyaan di sini meminta menggambar seni ASCII. Salah satu cara sederhana untuk menyimpan data untuk seni adalah RLE (run-length encoding) . Begitu:

qqqwwwwweeerrrrrtttyyyy

menjadi:

3q5w3e5r3t4y

Sekarang untuk menggambar seni ASCII besar Anda mungkin mendapatkan data seperti ini (mengabaikan karakter baris baru):

19,20 3(4)11@1$20 11@19,15"4:20 4)19,4:20 11@
   ^^^
   Note that this is "20 whitespaces"

(Character count: 45)

Karakter yang digunakan untuk seni ASCII tidak akan menjadi huruf kecil atau huruf besar atau angka, hanya tanda, tanda dan simbol tetapi selalu dalam set karakter ASCII yang dapat dicetak.

Anda ingin menghemat ruang dalam string itu, jadi Anda mengganti angka dengan set karakter huruf besar (menjadi 'A' sama dengan 1, 'B' sama dengan 2 sampai 'Z' sama dengan 26), karena Anda tidak akan pernah mau dapatkan lebih dari 26 repetisi karakter. Jadi, Anda mendapatkan:

S,T C(D)K@A$T K@S,O"D:T D)S,D:T K@

(Character count: 34)

Dan akhirnya Anda memperhatikan bahwa beberapa grup (huruf + simbol) berulang, jadi Anda mengganti grup yang muncul 3 kali atau lebih dalam string dengan karakter huruf kecil, dalam urutan atau penampilan dalam string, tetapi menyimpan dalam buffer substitusi dibuat (dalam format "grup + karakter pengganti" untuk setiap substitusi), dan membiarkan sisa string apa adanya. Jadi kelompok-kelompok berikut:

S, (3 times) 
T  (4 times)
K@ (3 times)

digantikan oleh 'a', 'b' dan 'c', masing-masing, karena tidak akan pernah ada lebih dari 26 kelompok yang berulang. Jadi akhirnya Anda mendapatkan:

S,aT bK@c
abC(D)cA$bcaO"D:bD)aD:bc

(Character count: 9+24=33)

[Langkah terakhir hanya menghemat 1 byte karena grup yang benar-benar menyimpan karakter setelah diganti adalah yang muncul 4 kali atau lebih.]

Tantangan

Diberikan string yang berisi data RLE untuk menggambar seni ASCII (dengan batasan yang diusulkan), tulis program / fungsi / metode terpendek yang Anda bisa untuk mengompresnya seperti yang dijelaskan. Algoritme harus mencetak / mengembalikan dua string: yang pertama berisi kamus yang digunakan untuk kompresi, dan yang kedua adalah string terkompresi yang dihasilkan. Anda dapat mengembalikan string sebagai Tuple, array, Daftar atau apa pun, dalam urutan yang diberikan.

Perhatikan bahwa jika string tidak dapat dikompresi di langkah 2, algoritma harus mengembalikan string kosong sebagai nilai pengembalian pertama dan hasil langkah 1 sebagai nilai balik kedua.

Anda tidak perlu menyertakan hasil langkah 1 dalam nilai output, saya hanya memasukkannya dalam contoh untuk tujuan klarifikasi.

Ini adalah , jadi semoga jawaban terpendek untuk setiap bahasa menang!

Kasus uji lain

Input:                   15,15/10$15,15/10"10$10"10$10"10$10"15,15/

Output of step 1:        O,O/J$O,O/J"J$J"J$J"J$J"O,O/

Final algorithm output:  O,aO/bJ$cJ"d
                         abcabdcdcdcdab

---

Input:                   15,15/10$15,15/10"

Output of step 1:        O,O/J$O,O/J"

Final algorithm output:  <empty string>
                         O,O/J$O,O/J"
Charlie
sumber
1
karena Anda tidak akan pernah mendapatkan lebih dari 26 pengulangan karakter . aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Okx
@Okx Itu tidak pernah terjadi.
Erik the Outgolfer
@Okx ya, di dunia nyata. Aturannya dibuat untuk set seni ASCII yang terbatas.
Charlie
2
Dalam implementasi nyata, S,aT bK@cmungkin akan disimpan hanya S,T K@tanpa secara eksplisit menyebutkan karakter substitusi yang dapat disimpulkan secara sepele dari itu.
Arnauld
@Arnauld Anda benar-benar benar, saya melewatkan itu, tetapi saya akan meninggalkan pertanyaan apa adanya, kalau-kalau ada orang yang mulai menulis jawabannya.
Charlie

Jawaban:

3

JavaScript (ES6), 168 167 byte

Mengembalikan array dua string: [dictionary, compressed_string].

s=>[(a=(s=s.replace(/\d+/g,n=>C(n|64),C=String.fromCharCode)).match(/../g)).map(v=>s.split(v)[a[v]||3]>=''?D+=v+(a[v]=C(i++)):0,i=97,D='')&&D,a.map(v=>a[v]||v).join``]

Uji kasus

Arnauld
sumber
3

Python 2 , 269 280 268 266 byte

Tidak ada yang mewah terjadi di sini. Peluang yang baik untuk menggunakan beberapa ekspresi reguler sederhana.

Versi pertama gagal untuk string yang berisi karakter khusus yang ditafsirkan dalam regex. Versi kedua (menggunakan re.escape) berfungsi dengan semua test case. Koreksi itu menghabiskan 11 byte.

Versi kedua tidak menetapkan karakter substitusi secara berurutan, seperti yang diperlukan dalam spesifikasi masalah, dan seperti yang ditunjukkan oleh @CarlosAlejo. Jadi kembali ke papan gambar.

Versi terkoreksi, lebih lanjut golf

  • -6 byte disimpan dengan tidak mencetak output pada dua baris
  • +3 byte: Beralih ke penggantian kode melalui string untuk memungkinkan memenuhi tantangan sebagaimana ditentukan.
  • -4 byte: Karena saya tidak lagi memanggil re.findall dua kali, saya tidak perlu mengganti nama
  • -5 byte: beralih dari untuk loop ke while loop.
  • -2 byte berkat @Comrade Sparkle Pony
import re
S=re.sub
b=a=input()
for i in re.findall('\d{1,2}',a):
 b=S(i, chr(64+int(i)),b)
n,s,p=96,'',0
while p<len(b):
 c=b[p:p+2];f=b.count(c)
 if f>2and not c in s:n+=1;s+=c+chr(n)
 p+=2
p=0
while p<len(s):k=s[p:p+2];v=s[p+2];b=S(re.escape(k),v,b);p+=3
print s,b

Cobalah online!

CCB60
sumber
Anda hampir sampai, perhatikan bahwa grup di langkah kedua tidak dibuat dalam urutan yang benar (lihat contoh). Grup harus dibuat dalam urutan penampilan, jadi yang pertama harus O,a.
Charlie
@CarlosAlejo Saya tidak mencatat bahwa sebagai persyaratan, karena pergantiannya sewenang-wenang, dari sudut pandang fungsional. Kamus standar Python, cara alami untuk mengimplementasikannya, tidak diurusi.
Harus
Tidak bisakah Anda menyimpan beberapa byte dengan menggunakan b=a=input()dan n,s,p=96,'',0?
Kamerad SparklePony
\d+akan menjadi regex yang lebih pendek untuk digunakan. Anda tidak akan pernah membahas lebih dari 26, jadi tidak ada alasan untuk memastikan bahwa itu khusus 1-2 digit. Juga, menggunakan re.escapeberarti bahwa string dasar replaceberakhir sedikit lebih pendek: 253 byte
Nilai Tinta
0

Lua, 215 byte

Sedikit pencocokan pola yang bagus.

Saya pikir Lua diremehkan ketika datang ke golf ... lihat semua pernyataan itu terjepit bersama!

g,c=string.gsub,string.char
u=g(arg[1],"%d%d?",function(n)return c(n+64)end)l,d=97,""g(u,"..",function(m)n,e=0,g(m,".", "%%%0")g(u,e,function()n=n+1 end)if n>2 then
l,s=l+1,c(l)d,u=d..m..s,g(u,e,s)end
end)print(u,d)
Trebuchette
sumber
0

Python 2 , 186 byte

from re import*
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
Q=[]
for p in findall('[A-Z].',S):
 if S.count(p)>2:a=chr(len(Q)+97);Q+=[p+a];S=sub(escape(p),a,S)
print''.join(Q),S

Saya berharap akhirnya berguna untuk re.subn: C

# first step - convert all numbers to uppercase letters
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
# empty list to hold encoding of second step
Q=[]
# find every encoded pair (uppercase letter and some char)
for p in findall('[A-Z].',S):
 # if it occures 3 or move times
 if S.count(p)>2:
  # get lowercase letter to substitute with
  a=chr(len(Q)+97)
  # store encoding into list
  Q+=[p+a]
  # update string - substitute pair with lowercase letter
  S=sub(escape(p),a,S)
# output
# encodings of second step, space, result
# if nothing was compressed at step 2, space would prepend result (of step 1)
print''.join(Q),S

Terkompresi pada langkah 2

Tidak dikompresi pada langkah 2


Python 2 , 246 byte

Seluruh langkah kedua dilakukan dalam mengganti lambda dari re.sub. Hanya untuk bersenang-senang.

from re import*
Q=[]
S=sub('\d+',lambda m:chr(int(m.group(0))+64),input())
S=sub('[A-Z].',lambda m:(lambda m:S.count(m)>2and(m in Q or not Q.append(m))and chr(Q.index(m)+97)or m)(m.group(0)),S)
print''.join(Q[i]+chr(i+97)for i in range(len(Q))),S

Cobalah online!

Possum Mati
sumber
0

Perl 5 -pl , 81 byte

s/\d+/chr$&+64/ge;$b=a;for$a(/([A-Z].)(?=.*\1.*\1)/g){s/\Q$a/$b/g&&($\.=$a.$b++)}

Cobalah online!

Mencetak string yang disandikan pada baris pertama, tiga kali lipat pada baris kedua

Xcali
sumber
0

Ruby -p , 133 byte

gsub(/(\d+)(.)/){(64+$1.to_i).chr+$2}
c=?`;s=''
$_.scan(/(..)(?=.*\1.*\1)/){s+=$&+c.succ!if !s[$&]}
puts s.scan(/(..)(.)/){gsub$1,$2}

Cobalah online!

Nilai Tinta
sumber