Contexte

Après avoir appliqué le BWT (comme on le voit dans Burrows, Wheeler et Back ) et le MTF (comme on le voit dans Move to the imprimable ASCII front ), le compresseur bzip2 applique une forme plutôt unique d'encodage de longueur.

Définition

Aux fins de ce défi, nous définissons la transformation BRLE comme suit:

Étant donné une chaîne d'entrée s composée uniquement de caractères ASCII avec des points de code compris entre 0x20 et 0x7A, procédez comme suit:

1. Remplacez chaque série de caractères égaux par une seule occurrence du caractère et stockez le nombre de répétitions après la première.

2. Encode le nombre de répétitions après la première occurrence du caractère , en utilisant la numération bijective base-2 et les symboles {et }.

   Un entier non négatif n est codé comme la chaîne b _k … b ₀ telle que n = 2 ^k i (b _k ) +… + 2 ⁰ i (b ₀ ) , où i ( {) = 1 et i ( }) = 2 .

   Notez que cette représentation est toujours unique. Par exemple, le nombre 0 est codé comme une chaîne vide.

3. Insérez la chaîne entre accolades qui code le nombre de répétitions après l'occurrence unique du caractère correspondant.

Exemple pas à pas

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{{{"

Tâche

Implémentez un programme ou une fonction involutive qui lit une chaîne unique à partir de STDIN ou comme argument de ligne de commande ou de fonction et imprime ou renvoie soit le BRLE soit son inverse de la chaîne d'entrée.

Si l'entrée ne contient pas de crochets, appliquez le BRLE. Si l'entrée contient des accolades, appliquez son inverse.

Exemples

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

Règles supplémentaires

• Vous ne pouvez pas utiliser de fonctions intégrées qui calculent le BRLE ou son inverse d'une chaîne.

• Vous pouvez utiliser des fonctions intégrées qui:

  • Calculez le RLE ou le RLD d'une chaîne, tant que le nombre de répétitions n'est pas stocké dans la base bijective-2.

  • Effectuez une conversion de base de tout type.

• Votre code peut imprimer une nouvelle ligne de fin si vous choisissez STDOUT pour la sortie.

• Votre code doit fonctionner pour toute entrée de 1000 caractères ASCII ou moins dans la plage de 0x20 à 0x7A, plus les accolades (0x7B et 0x7D).

• Si l'entrée contient des accolades, vous pouvez supposer que c'est un résultat valide de l'application du BRLE à une chaîne.

• Les règles de golf à code standard s'appliquent. La soumission la plus courte en octets l'emporte.

CJam, 50 48 octets

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

Merci pour Dennis d'avoir économisé 2 octets.

Essayez-le en ligne.

Explication

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 octets

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

2 octets grâce à @Maltysen.

Manifestation. Harnais de test.

Explication:

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 est la fonction qui fait la transformation.

#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

Au début, je pensais que je devais vérifier la présence d'appareils orthopédiques, mais cela s'est avéré inutile. Le décodage n'a clairement aucun effet sur les chaînes qui sont déjà décodées, et la partie encodage s'est avérée tout aussi inoffensive pour celles qui étaient déjà encodées.

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>

Quelques explications

Numéro n à BB2 en utilisant 0 et 1:(n+1).toString(2).slice(1)

Chaîne dans BB2 en nombre: to_number ("0b1" + chaîne) - c'est-à-dire, ajoutez un chiffre binaire à l'extrême gauche et convertissez en binaire (et diminuez de 1, pas nécessaire dans cette instance spécifique).

Expression régulière pour rechercher n'importe quel caractère suivi de {ou }:/[^{}][{}]+/g

Expression régulière pour trouver des caractères répétés: /(.)\1*/g

En utilisant cette expression rationnelle dans replace, le premier paramètre est le caractère "répété" (éventuellement répéter une seule fois), le deuxième paramètre est la chaîne totale répétée, dont la longueur est le nombre que j'ai besoin d'encoder en BB2 déjà incrémenté de 1

... puis mettez tout ensemble ...