user
Given a symbol table of a *zero-indexed* array of all possible input symbols
this algorithm reversibly transforms a sequence
of input symbols into an array of output numbers (indices).

The transform in many cases acts to give frequently repeated input symbols
lower indices which is useful in some compression algorithms.

Encoding algorithm

```
    for each symbol of the input sequence:
        output the index of the symbol in the symbol table
        move that symbol to the front of the symbol table

```

Decoding algorithm

```
    # Using the same starting symbol table
    for each index of the input sequence:
        output the symbol at that index of the symbol table
        move that symbol to the front of the symbol table

```

Example

Encoding the string of character symbols 'broood' using a symbol table of the lowercase characters   **a**-to-**z**

:   :   :   :   :   | Input | Output | SymbolTable |
                    | --- | --- | --- |
                    | **b**roood | 1 | 'abcdefghijklmnopqrstuvwxyz' |
                    | b**r**oood | 1 17 | 'bacdefghijklmnopqrstuvwxyz' |
                    | br**o**ood | 1 17 15 | 'rbacdefghijklmnopqstuvwxyz' |
                    | bro**o**od | 1 17 15 0 | 'orbacdefghijklmnpqstuvwxyz' |
                    | broo**o**d | 1 17 15 0 0 | 'orbacdefghijklmnpqstuvwxyz' |
                    | brooo**d** | 1 17 15 0 0 5 | 'orbacdefghijklmnpqstuvwxyz' |

Decoding the indices back to the original symbol order:

:   :   :   :   :   | Input | Output | SymbolTable |
                    | --- | --- | --- |
                    | **1** 17 15 0 0 5 | b | 'abcdefghijklmnopqrstuvwxyz' |
                    | 1 **17** 15 0 0 5 | br | 'bacdefghijklmnopqrstuvwxyz' |
                    | 1 17 **15** 0 0 5 | bro | 'rbacdefghijklmnopqstuvwxyz' |
                    | 1 17 15 **0** 0 5 | broo | 'orbacdefghijklmnpqstuvwxyz' |
                    | 1 17 15 0 **0** 5 | brooo | 'orbacdefghijklmnpqstuvwxyz' |
                    | 1 17 15 0 0 **5** | broood | 'orbacdefghijklmnpqstuvwxyz' |

Task
:   * Encode and decode the following three strings of characters using the symbol table of the lowercase characters   **a**-to-**z**   as above.
    * Show the strings and their encoding here.
    * Add a check to ensure that the decoded string is the same as the original.

The strings are:

```
   broood          
   bananaaa     
   hiphophiphop  

```

(Note the misspellings in the above strings.)
assistant
(formerly Perl 6)

**Works with**: rakudo version 2015-09-24

```
sub encode ( Str $word ) {
    my @sym = 'a' .. 'z';
    gather for $word.comb -> $c {
	die "Symbol '$c' not found in @sym" if $c eq @sym.none;
        @sym[0 .. take (@sym ... $c).end] .= rotate(-1);
    }
}
 
sub decode ( @enc ) {
    my @sym = 'a' .. 'z';
    [~] gather for @enc -> $pos {
        take @sym[$pos];
        @sym[0..$pos] .= rotate(-1);
    }
}
 
use Test;
plan 3;
for <broood bananaaa hiphophiphop> -> $word {
    my $enc = encode($word);
    my $dec = decode($enc);
    is $word, $dec, "$word.fmt('%-12s') ($enc[])";
}

```

Output:

```
1..3
ok 1 - broood       (1 17 15 0 0 5)
ok 2 - bananaaa     (1 1 13 1 1 1 0 0)
ok 3 - hiphophiphop (7 8 15 2 15 2 2 3 2 2 3 2)
```