Komprimieren von RLE-Daten zum Zeichnen von ASCII-Grafiken

11

Diese Frage basiert auf dem, was ich mir ausgedacht habe , um eine andere Frage zu beantworten .

Manchmal stellen die Fragen hier das Zeichnen von ASCII-Kunst. Eine einfache Möglichkeit, die Daten für die Technik zu speichern, ist RLE (Run-Length-Codierung) . Damit:

qqqwwwwweeerrrrrtttyyyy

wird:

3q5w3e5r3t4y

Um nun eine große ASCII-Grafik zu zeichnen, erhalten Sie möglicherweise Daten wie diese (ohne Berücksichtigung der neuen Zeilenzeichen):

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)

Die für die ASCII-Grafik verwendeten Zeichen sind niemals Klein- oder Großbuchstaben oder Zahlen, sondern nur Zeichen, Markierungen und Symbole, sondern immer im druckbaren ASCII-Zeichensatz.

Sie möchten etwas Platz in dieser Zeichenfolge sparen, also ersetzen Sie die Zahlen durch den Großbuchstaben ('A' entspricht 1, 'B' entspricht 2, bis 'Z' 26 entspricht), da Sie dies niemals tun werden Erhalte mehr als 26 Wiederholungen eines Charakters. So bekommen Sie:

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

(Character count: 34)

Und schließlich bemerken Sie, dass sich einige Gruppen von (Buchstabe + Symbol) wiederholen. Ersetzen Sie daher die Gruppen, die dreimal oder öfter in der Zeichenfolge erscheinen, durch den Kleinbuchstaben-Zeichensatz, in der Reihenfolge oder im Erscheinungsbild der Zeichenfolge, speichern Sie jedoch die in einem Puffer Ersetzungen vorgenommen (im Format "Gruppe + Ersetzungszeichen" für jede Ersetzung) und den Rest der Zeichenfolge unverändert lassen. Also die folgenden Gruppen:

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

wird durch 'a', 'b' bzw. 'c' ersetzt, da sich nie mehr als 26 Gruppen wiederholen werden. So endlich bekommen Sie:

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

(Character count: 9+24=33)

[Der letzte Schritt spart nur 1 Byte, da die Gruppen, die nach dem Ersetzen tatsächlich Zeichen speichern, viermal oder öfter angezeigt werden.]

Die Herausforderung

Schreiben Sie bei einer Zeichenfolge mit den RLE-Daten zum Zeichnen einer ASCII-Grafik (mit den vorgeschlagenen Einschränkungen) das kürzeste Programm / die kürzeste Funktion / Methode, die Sie können, um sie wie beschrieben zu komprimieren. Der Algorithmus muss zwei Zeichenfolgen drucken / zurückgeben: die erste enthält das für die Komprimierung verwendete Wörterbuch und die zweite ist die resultierende komprimierte Zeichenfolge. Sie können die Zeichenfolgen als Tupel, Array, Liste oder was auch immer in der angegebenen Reihenfolge zurückgeben.

Beachten Sie, dass der Algorithmus, wenn die Zeichenfolge in Schritt 2 nicht komprimiert werden kann, eine leere Zeichenfolge als ersten Rückgabewert und das Ergebnis von Schritt 1 als zweiten Rückgabewert zurückgeben muss.

Sie müssen das Ergebnis von Schritt 1 nicht in die Ausgabewerte aufnehmen, sondern nur zur Verdeutlichung in die Beispiele aufnehmen.

Dies ist , also kann die kürzeste Antwort für jede Sprache gewinnen!

Ein weiterer Testfall

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
quelle
1
weil du nie mehr als 26 Wiederholungen eines Charakters bekommen wirst Nö. aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Okx
@Okx Das kann niemals der Fall sein.
Erik der Outgolfer
@ Okx ja, in der realen Welt. Die Regeln gelten jedoch für einen eingeschränkten Satz von ASCII-Grafiken.
Charlie
2
In einer realen Implementierung S,aT bK@cwürde wahrscheinlich nur gespeichert, S,T K@ohne explizit die Substitutionszeichen zu benennen, die sich daraus trivial ableiten lassen.
Arnauld
@Arnauld du hast vollkommen recht, das habe ich verpasst, aber ich werde die Frage so lassen, wie sie ist, nur für den Fall, dass jemand anfängt, seine / ihre Antwort zu schreiben.
Charlie

Antworten:

3

JavaScript (ES6), 168 167 Byte

Gibt ein Array mit zwei Zeichenfolgen zurück : [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``]

Testfälle

Arnauld
quelle
3

Python 2 , 269 280 268 266 Bytes

Hier ist nichts Besonderes los. Gute Gelegenheit, einige einfache reguläre Ausdrücke zu verwenden.

Die erste Version schlug für Zeichenfolgen mit Sonderzeichen fehl, die innerhalb des regulären Ausdrucks interpretiert wurden. Die zweite Version (mit re.escape) funktioniert mit allen Testfällen. Diese Korrektur kostete 11 Bytes.

In der zweiten Version wurden die Ersetzungszeichen nicht in der Reihenfolge zugewiesen, wie in der Problemspezifikation gefordert und von @CarlosAlejo hervorgehoben. Also zurück zum Zeichenbrett.

Korrigierte Version, weiter golfen

  • -6 Bytes werden gespeichert, wenn die Ausgabe nicht in zwei Zeilen gedruckt wird
  • +3 Bytes: Wechseln zu Code-Ersetzungen über eine Zeichenfolge, um die angegebene Herausforderung zu erfüllen.
  • -4 Bytes: Da ich re.findall nicht mehr zweimal aufrufe, muss ich es nicht umbenennen
  • -5 Bytes: Umschalten von for-Schleifen auf while-Schleifen.
  • -2 Bytes dank @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

Probieren Sie es online aus!

CCB60
quelle
Sie sind fast da. Beachten Sie, dass die Gruppen im zweiten Schritt nicht in der richtigen Reihenfolge erstellt werden (siehe Beispiel). Gruppen müssen in der Reihenfolge ihres Auftretens erstellt werden, daher sollte die erste sein O,a.
Charlie
@CarlosAlejo Ich hatte das nicht als Voraussetzung bemerkt, da die Substitutionen aus funktionaler Sicht willkürlich sind. Die Standardwörterbücher von Python, eine natürliche Möglichkeit, dies zu implementieren, sind ungeordnet.
Muss
Könnten Sie nicht einige Bytes mit b=a=input()und speichern n,s,p=96,'',0?
Genosse SparklePony
\d+wäre eine kürzere Regex zu verwenden. Du wirst sowieso nie über 26 gehen, also gibt es keinen Grund sicherzustellen, dass es spezifisch 1-2 Stellen sind. Verwenden re.escapebedeutet auch, dass eine Basiszeichenfolge replaceetwas kürzer wird: 253 Bytes
Value Ink
0

Lua, 215 Bytes

Nur ein gutes Stück Mustervergleich.

Ich denke, Lua wird beim Golfen unterschätzt ... sieh dir all diese Aussagen an, die zusammengedrückt wurden!

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
quelle
0

Python 2 , 186 Bytes

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

Ich hatte gehofft, endlich Verwendung zu finden für 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

In Schritt 2 komprimiert

In Schritt 2 nicht komprimiert


Python 2 , 246 Bytes

Ganzer zweiter Schritt in Repl Lambda von re. Nur zum Spaß.

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

Probieren Sie es online aus!

Totes Opossum
quelle
0

Perl 5 -pl , 81 Bytes

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

Probieren Sie es online aus!

Druckt die codierte Zeichenfolge in der ersten Zeile, die Tripel in der zweiten Zeile

Xcali
quelle
0

Ruby -p , 133 Bytes

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

Probieren Sie es online aus!

Wert Tinte
quelle