14

1

### Background

After applying the BWT (as seen in Burrows, Wheeler and Back) and the MTF (as seen in Move to the printable ASCII front), the bzip2 compressor applies a rather unique form of run-length encoding.

### Definition

For the purpose of this challenge, we define the transformation BRLE as follows:

Given an input string **s** that consists solely of ASCII characters with code points between 0x20 and 0x7A, do the following:

Replace each run of equal characters by a single occurrence of the character and store number of repetitions after the first.

Encode the number of repetitions

*after the first occurrence of the character*, using bijective base-2 numeration and the symbols`{`

and`}`

.A non-negative integer

**n**is encoded as the string**b**such that_{k}…b_{0}**n = 2**, where^{k}i(b_{k})+…+2^{0}i(b_{0})**i(**and`{`

) = 1**i(**.`}`

) = 2Note that this representation is always unique. For example, the number

**0**is encoded as an empty string.Insert the string of curly brackets that encodes the number of repetitions after the single occurrence of the corresponding character.

# Step-by-step example

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

### Task

Implement an involutive program or function that reads a single string from STDIN or as command-line or function argument and prints or returns either the BRLE or its inverse of the input string.

If the input contains no curly brackets, apply the BRLE. If the input contains curly brackets, apply its inverse.

### Examples

```
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
```

### Additional rules

You

*cannot*use any built-ins that compute the BRLE or its inverse of a string.You

*can*use built-ins that:Compute the RLE or RLD of a string, as long as the number of repetitions is not stored in bijective base-2.

Perform base conversion of any kind.

Your code may print a trailing newline if you choose STDOUT for output.

Your code has to work for any input of 1000 or less ASCII characters in the range from 0x20 to 0x7A, plus curly brackets (0x7B and 0x7D).

If the input contains curly brackets, you may assume that it is a valid result of applying the BRLE to a string.

Standard code golf rules apply. The shortest submission in bytes wins.

Why are builtins not allowed? – MilkyWay90 – 2019-06-02T17:25:10.633