Hintergrund

Nach dem Anwenden der BWT (wie in Burrows, Wheeler und Back ) und der MTF (wie in Move to the printable ASCII front ) wird die wendet bzip2- Kompressor eine ziemlich einzigartige Form der Lauflängencodierung an.

Definition

Für diese Herausforderung definieren wir die Transformation BRLE wie folgt:

Gehen Sie bei einer Eingabezeichenfolge s , die ausschließlich aus ASCII-Zeichen mit Codepunkten zwischen 0x20 und 0x7A besteht, wie folgt vor:

1. Ersetzen Sie jeden Lauf gleicher Zeichen durch ein einzelnes Vorkommen des Zeichens und speichern Sie die Anzahl der Wiederholungen nach dem ersten.

2. Codieren Sie die Anzahl der Wiederholungen nach dem ersten Auftreten des Zeichens mit der bijektiven Basis-2-Nummerierung und den Symbolen {und }.

   Eine nicht negative ganze Zahl n wird als die Zeichenkette b _k … b ₀ codiert, so dass n = 2 ^k i (b _k ) +… + 2 ⁰ i (b ₀ ) ist , wobei i ( {) = 1 und i ( }) = 2 .

   Beachten Sie, dass diese Darstellung immer eindeutig ist. Zum Beispiel kann die Nummer 0 wird als eine leere Zeichenfolge codiert.

3. Fügen Sie die geschweifte Klammer ein, die die Anzahl der Wiederholungen nach dem einzelnen Auftreten des entsprechenden Zeichens codiert.

Beispiel Schritt für Schritt

Input:  "abbcccddddeeeeeffffffggggggghhhhhhhh"
Step 1: "abcdefgh" with repetitions 0, 1, 2, 3, 4, 5, 6, 7
Step 2: "" "{" "}" "{{" "{}" "}{" "}}" "{{{"
Step 3: "ab{c}d{{e{}f}{g}}h{{{"

Aufgabe

Implementieren Sie ein involutives Programm oder eine involutive Funktion, die eine einzelne Zeichenfolge aus STDIN oder als Befehlszeilen- oder Funktionsargument liest und entweder die BRLE oder deren Inverse der Eingabezeichenfolge ausgibt oder zurückgibt.

Wenn die Eingabe keine geschweiften Klammern enthält, wenden Sie BRLE an. Wenn die Eingabe geschweifte Klammern enthält, wenden Sie die Umkehrung an.

Beispiele

INPUT:  CODEGOLF
OUTPUT: CODEGOLF

INPUT:  PROGRAMMING
OUTPUT: PROGRAM{ING

INPUT:  PUZ{LES
OUTPUT: PUZZLES

INPUT:  444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
OUTPUT: 4{{8{{{G{{{{W{{{{{

INPUT:  y}}}{{
OUTPUT: yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

Zusätzliche Regeln

• Sie können keine integrierten Funktionen verwenden, die die BRLE oder die Umkehrung einer Zeichenfolge berechnen.

• Sie können integrierte Funktionen verwenden, die:

  • Berechnen Sie die RLE oder RLD eines Strings, solange die Anzahl der Wiederholungen nicht in der bijektiven Basis 2 gespeichert ist.

  • Grundkonvertierung aller Art durchführen.

• Ihr Code druckt möglicherweise eine abschließende neue Zeile, wenn Sie für die Ausgabe STDOUT auswählen.

• Ihr Code muss für jede Eingabe von 1000 oder weniger ASCII-Zeichen im Bereich von 0x20 bis 0x7A sowie geschweiften Klammern (0x7B und 0x7D) funktionieren.

• Wenn die Eingabe geschweifte Klammern enthält, können Sie davon ausgehen, dass es sich um ein gültiges Ergebnis der Anwendung der BRLE auf eine Zeichenfolge handelt.

• Es gelten die Standard-Code-Golfregeln. Die kürzeste Übermittlung in Bytes gewinnt.

CJam, 50 48 Bytes

l_{}`:T&1${_T#)_(@a?)+}%{(\2b)*}%@e`{(2b1>Tf=}%?

Vielen Dank für Dennis für das Speichern von 2 Bytes.

Probieren Sie es online aus.

Erläuterung

l_              e# Read and duplicate input.
{}`:T           e# T = "{}"
&               e# If the input has '{ or '}:
    1$          e# Input.
    {           e# For each character:
        _T#)    e# If it is '{ or '}:
            _(  e# Return 0 for '{ or 1 for '}.
            @a  e# Otherwise, convert the character itself to an array (string).
        ?
        )+      e# If it is a number, increment and append to the previous array.
                e# If it is a string with at least 1 character, do nothing.
    }%
    {(\         e# For each character and bijective base 2 number:
        2b)*    e# Repeat the character 1 + that many times.
    }%
                e# Else:
    @           e# Input.
    e`          e# Run-length encoding.
    {(          e# For each character and length:
        2b1>    e# Convert the length to base 2 and remove the first bit.
        Tf=     e# Map 0 to '{ and 1 to '}.
    }%
?               e# End if.

Pyth, 48 50 Bytes

J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8

2 Bytes dank @Maltysen.

Demonstration. Kabelbaum testen.

Erläuterung:

J`Hs?m*hdi+1xLJtd2tczf-@zTJUz@Jzsm+ed@LJtjhd2rz8
                                                    Implicit: z = input()
                                                    H is empty dict.
J`H                                                 J = repr(H) = "{}"
   s                                                Print the concatenation of
    ?                        @Jz                    If z and J share any chars:
                     f     Uz                       Filter range(len(z))
                      -@zTJ                         On the absence of z[T] in J.
                   cz                               Chop z at these indices.
                                                    just before each non '{}'.
                  t                                 Remove empty initial piece.
     m*hd                                           Map to d[0] *
         i       2                                  the base 2 number                             
            xLJtd                                   index in J mapped over d[:-1]
          +1                                        with a 1 prepended.
                                             rz8    Otherwise, run len. encode z
                                 m                  map over (len, char)
                                         jhd2       Convert len to binary.
                                        t           Remove leading 1  
                                     @LJ            Map to element of J.
                                  +ed               Prepend char.
                                s                   Concatenate. 

OCaml, 252

t ist die Funktion, die die Transformation ausführt.

#load"str.cma"open Str
let rec(!)=group_beginning and
g=function|1->""|x->(g(x/2)^[|"{";"}"|].(x mod 2))and($)i s=if g i=s then i else(i+1)$s and
t s=global_substitute(regexp"\(.\)\1*\([{}]*\)")(fun s->String.make(1$matched_group 2 s)s.[!1]^g(!2- !1))s

Zuerst dachte ich, ich müsste nach geschweiften Klammern suchen, aber es stellte sich als unnötig heraus. Die Dekodierung hat eindeutig keine Auswirkung auf bereits dekodierte Zeichenfolgen, und der Kodierungsteil erwies sich als ebenso harmlos wie die bereits kodierten.

JavaScript ( ES6 ), 162

f=s=>
(t=s[R='replace'](/[^{}][{}]+/g,n=>n[0].repeat('0b'+n[R](/./g,c=>c!='{'|0))))==s
?s[R](/(.)\1*/g,(r,c)=>c+r.length.toString(2).slice(1)[R](/./g,c=>'{}'[c])):t

// TEST
out=x=>O.innerHTML += x + '\n';

test=s=>O.innerHTML = s+' -> '+f(s) +'\n\n' + O.innerHTML;

[['CODEGOLF','CODEGOLF']
,['PROGRAMMING','PROGRAM{ING']
,['PUZ{LES','PUZZLES']
,['444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW','4{{8{{{G{{{{W{{{{{']
,['y}}}{{','yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy']]
.forEach(v=>{
  w=f(v[0])  
  out('Test ' + (w==v[1]?'OK':'Fail')+'\nInput:    '+v[0]+'\nExpected: '+v[1]+'\nResult:   '+w)
})  

Your test: <input id=I style='width:300px'><button onclick='test(I.value)'>-></button>
<pre id=O></pre>

Eine Erklärung

Nummer n bis BB2 mit 0 und 1:(n+1).toString(2).slice(1)

Zeichenfolge in BB2 zu Nummer: to_number ("0b1" + Zeichenfolge) - Fügen Sie also eine Binärziffer ganz links hinzu und konvertieren Sie sie von binär (und verringern Sie sie um 1, was in diesem speziellen Fall nicht erforderlich ist).

Regulärer Ausdruck, um ein beliebiges Zeichen zu finden, gefolgt von {oder }:/[^{}][{}]+/g

Regulärer Ausdruck, um wiederholte Zeichen zu finden: /(.)\1*/g

Unter Verwendung dieses regulären Ausdrucks beim Ersetzen ist der erste Parameter das "wiederholte" Zeichen (eventuell nur ein Mal wiederholen), der zweite Parameter ist die gesamte wiederholte Zeichenfolge, deren Länge die Zahl ist, die ich in BB2 codieren muss, die bereits um 1 erhöht wurde

... dann füge alles zusammen ...