tło

Po zastosowaniu BWT (jak widać w Burrows, Wheeler and Back ) i MTF (jak widać w Move to the printable ASCII front ), bzip2 kompresor stosuje raczej unikalną formę kodowania długości przebiegu.

Definicja

Na potrzeby tego wyzwania definiujemy transformację BRLE w następujący sposób:

Biorąc pod uwagę ciąg wejściowy S , który składa się wyłącznie ze znaków ASCII z punktów kodowych między 0x20 i 0x7A, wykonaj następujące czynności:

1. Zastąp każdy ciąg równych znaków pojedynczym wystąpieniem znaku i zapisz liczbę powtórzeń po pierwszym.

2. Zakoduj liczbę powtórzeń po pierwszym wystąpieniu znaku , używając numeracji bijective base-2 i symboli{ i }.

   Nieujemna liczba całkowita n jest kodowana jako ciąg b _k … b _{0 w} taki sposób, że n = 2 ^k i (b _k ) +… + 2 ⁰ i (b ₀ ) , gdzie i ( {) = 1 i i ( }) = 2 .

   Pamiętaj, że ta reprezentacja jest zawsze unikalna. Na przykład liczba 0 jest kodowana jako pusty ciąg.

3. Wstaw ciąg nawiasów klamrowych, który koduje liczbę powtórzeń po pojedynczym wystąpieniu odpowiedniego znaku.

Przykład krok po kroku

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

Zadanie

Zaimplementuj program lub funkcję, która odczytuje pojedynczy ciąg znaków ze STDIN lub jako argument wiersza polecenia lub funkcji i wypisuje lub zwraca BRLE lub jego odwrotność ciągu wejściowego.

Jeśli dane wejściowe nie zawierają nawiasów klamrowych, zastosuj BRLE. Jeśli dane wejściowe zawierają nawiasy klamrowe, zastosuj odwrotność.

Przykłady

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

Dodatkowe zasady

• Nie można używać żadnych wbudowanych funkcji, które obliczają BRLE lub jego odwrotność.

• Państwo może używać Zabudowy że:

  • Oblicz RLE lub RLD ciągu, o ile liczba powtórzeń nie jest przechowywana w bijective base-2.

  • Wykonaj dowolną konwersję podstawową.

• Twój kod może wydrukować końcowy znak nowej linii, jeśli wybierzesz STDOUT jako wynik.

• Twój kod musi działać na każdym wprowadzeniu 1000 lub mniej znaków ASCII w zakresie od 0x20 do 0x7A, a także nawiasach klamrowych (0x7B i 0x7D).

• Jeśli dane wejściowe zawierają nawiasy klamrowe, możesz założyć, że jest to poprawny wynik zastosowania BRLE do łańcucha.

• Obowiązują standardowe zasady gry w golfa. Najkrótsze przesłanie w bajtach wygrywa.

CJam, 50 48 bajtów

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

Dzięki za Dennisa za oszczędność 2 bajtów.

Wypróbuj online.

Wyjaśnienie

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 bajtów

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

2 bajty dzięki @Maltysen.

Demonstracja. Uprząż testowa.

Wyjaśnienie:

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 jest funkcją, która dokonuje transformacji.

#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

Na początku myślałem, że muszę sprawdzić obecność nawiasów klamrowych, ale okazało się to niepotrzebne. Dekodowanie wyraźnie nie ma wpływu na ciągi, które są już dekodowane, a część kodująca okazała się równie nieszkodliwa jak te, które zostały już zakodowane.

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>

Jakieś wyjaśnienie

Liczba n do BB2 przy użyciu 0 i 1:(n+1).toString(2).slice(1)

Łańcuch w BB2 na numer: to_number („0b1” + ciąg) - to znaczy dodaj 1 lewą cyfrę binarną i przekonwertuj z binarnej (i zmniejsz o 1, niepotrzebne w tym konkretnym przypadku).

Wyrażenie regularne, aby znaleźć dowolny znak, po którym następuje {lub }:/[^{}][{}]+/g

Wyrażenie regularne, aby znaleźć powtarzające się znaki: /(.)\1*/g

Używając tego wyrażenia regularnego w zamian, pierwszy parametr jest „powtarzanym” char (w końcu powtórzy tylko 1 raz), drugi parametr jest całkowitym powtórzonym ciągiem, którego długość jest liczbą, którą muszę zakodować w BB2 już zwiększoną o 1

... a następnie złóż wszystko razem ...