Introdução

Alguns caracteres ASCII são tão caros hoje em dia ...

Para economizar dinheiro, você decidiu escrever um programa que codifica caracteres caros usando caracteres baratos.

No entanto, os preços dos caracteres mudam com freqüência e você não deseja modificar seu programa toda vez que precisar codificar ou decodificar um caractere diferente! Você precisará de uma solução mais dinâmica.

Desafio

Sua tarefa é escrever dois programas: um codificador e um decodificador .

O codificador deve aceitar uma lista de cinco caracteres baratos e um único caractere caro.

Ele deve gerar uma única sequência composta de caracteres baratos, que codifica o caractere caro.

Essa sequência não pode ter mais de 4 caracteres , para permanecer barata. No entanto, ele não precisa usar todos os caracteres baratos na codificação e as codificações podem ter comprimentos diferentes.

O decodificador deve aceitar a cadeia de caracteres emitida pelo codificador e gerar o caractere caro.

O decodificador não aceitará nenhuma entrada além da sequência codificada. Ele deve funcionar, sem modificação, a partir da saída do codificador para qualquer combinação (válida) de entradas. Em outras palavras, seu programa de decodificador não sabe quais caracteres são caros ou baratos.

Pontuação

O código combinado mais curto vence!

Notas

• Todos os caracteres serão letras maiúsculas [A-Z], minúsculas [a-z]ou números [0-9].

• A lista de caracteres baratos não conterá duplicatas. Nenhum personagem será barato e caro.

• O codificador e o decodificador não precisam ser escritos no mesmo idioma, mas podem ser. Você pode escrever um programa ou uma função.

• A entrada e a saída podem estar em qualquer formato razoável para o seu idioma.

• Os dois programas não podem compartilhar nenhuma variável ou dado.

Sumário

• A entrada de alguns caracteres baratos e um caractere caro é fornecida ao codificador.

• O codificador gera uma sequência de caracteres baratos, codificando o caractere caro.

• O decodificador recebe a saída do codificador e gera o caractere caro.

Exemplos

Entrada:     a, b, c, d, e     f

Possibilidades de codificador:     a     eeee     caec

Decodificador:     f

Entrada:     a, b, c, d, e     h

Possibilidades de codificador:     bc     cea     eeaa

Decodificador:     h

Entrada:     q, P, G, 7, C     f

Possibilidades de codificador:     777     P7     PPCG

Decodificador:     f

Pitão, 46 ​​bytes

Codificador, 22 bytes

@smfql{Td^<Szd4S4-Cw48

Decodificador, 24 bytes

C+48xsmfql{Td^<sS{zd4S4z

CJam, 55 50 48 47 bytes

Codificador, 24 22 21 bytes

l$:L4m*{$L|L=},rc'0-=

Experimente online.

Decodificador, 31 28 27 26 bytes

4_m*{$4,|4,=},l_$_|f#a#'0+

Experimente online.

gawk, 163 + 165 = 328

Testado com o gawk 4.1.1, mas também deve funcionar em versões mais antigas do gawk. Precisa ser ligeiramente modificado (alongado) para trabalhar com o mawk.

codificador (163):

{for(gsub(", ",_);sprintf("%c",++r)!=$NF;asort(a))split($1,a,_);r-=r>64?53:46;for(k=4^5;r-=_~i;j=_)for(i=++k;gsub(++j,_,i);)split(k,b,_);for(j in b)printf a[b[j]]}

decodificador (165):

{split($1,a,_);for(i in a)d[a[i]]=a[i];asort(d);for(k=4^5;c!~$1;x+=_~i){i=++k;for(c=j=_;gsub(++j,_,i);split(k,b,_));for(g in b)c=c d[b[g]]}printf"%c",x+(x>10?54:47)}

Bem, funciona, mas sei que essa pode não ser a melhor abordagem para isso. Não faço ideia para que serve a quinta carta barata, porque uso apenas quatro.

Estes são apenas para uso único. Se você quiser inserir um segundo código, precisará reiniciá-lo. Os espaços após as vírgulas são necessários na entrada para codificação.

O que eu pensei sobre

Minha primeira pergunta foi "O que um decodificador poderia obter desses 4 caracteres?" (Vou chamá-los de a, b, c e d), e minha ideia inicial era obter 6 bits de informações das seguintes relações:

a>b
a>c
a>d
b>c
b>d
c>d

Uau, 6 bits, isso é perfeito! Eu pensei que era genial, mas os testes mostraram que isso não funcionaria. Existem apenas 24 combinações possíveis. Droga.

O próximo passo foi tentar contar, com base no que eu já sabia. Portanto, a primeira letra que aparecer na string se tornará 0, a segunda letra introduzida na string se tornará 1 e assim por diante. Mas isso não me levaria até as 62 combinações necessárias.

0000
0001
0010
0011
0012
0100
0101
0102
0110
0111
0112
0120
0121
0122
0123

Mas eu gosto da ideia de qualquer maneira.

Bem, então me ocorreu que eu poderia combinar esses dois, porque os caracteres na entrada já têm relações e eu não precisaria esperar até que eles fossem apresentados para lhes dar um valor.

Como funciona

Nota: Não é mais exatamente assim que as versões golfadas funcionam, mas o princípio permanece o mesmo.

Para o decodificador:

Uma matriz é construída, cujo índice contém todos os quatro números de dígitos cujo maior dígito não é maior que o número de dígitos distintos nesse número. Existem 75 números diferentes de quatro dígitos que atendem a essa condição. Eu os forço brutalmente, porque até agora não consegui descobrir uma maneira de construí-los, e não tenho certeza se isso seria mais curto no awk de qualquer maneira. Enquanto os encontro, atribuo-lhes os caros caracteres em ordem asciibética.

Em seguida, substituo cada caractere da sequência de entrada por um dígito. O menor (por exemplo, 'B' menor que 'a') se torna 1, o segundo menor se torna 2 e assim por diante até 4. É claro que depende de quantos caracteres diferentes existem na entrada, qual o dígito mais alto em a sequência resultante será.

Simplesmente imprimo o elemento da matriz, que possui essa sequência como um índice.

O codificador funciona de acordo.

Como usar

Copie o código diretamente em um comando awk bash line ou crie dois arquivos "encode.awk" e "decode.awk" e cole o código adequadamente. Ou, melhor ainda, use o código a seguir, que sai automaticamente após en / decodificação, ou pode ser usado várias vezes removendo o comando exit no final.

encode.awk

{
    if(!x) # only do first time
        for(i=1e3;i++<5e3;delete a)
        {
            for(m=j=0;p=substr(i,++j,1);p>m?m=p:0)++a[p];
            length(a)>=m&&i!~0?c[(x>9?55:48)+x++]=i:_
        }
    r=u=_; # clear reused variables 
    for(gsub(",",FS);sprintf("%c",++r)!=$NF;); # more flexible concerning
    --NF;                                      # spaces in input
    split($0,b);
    asort(b);
    split(c[r],a,_);
    for(j in a)u=u b[a[j]]; # prettier printing than golfed version
    print u
    exit # <=== remove to encode input file
}

decode.awk

{
    if(!x) # only do first time 
        for(i=1e3;i++<5e3;delete a)
        {
            for(m=j=0;p=substr(i,++j,1);p>m?m=p:_)++a[p];
            length(a)>=m&&i!~0?c[i]=sprintf("%c",(x>9?55:48)+x++):_
        }
    delete t; delete d; o=_; # clear reused variables 
    split($1,a,_);
    for(i in a)t[a[i]]=1;
    for(i in t)d[++y]=i;
    asort(d);
    for(i in a)for(j in d)if(d[j]~a[i])o=o j;
    print c[o]
    exit # <=== remove to encode input file
}

Aqui está um exemplo de uso:

me@home:~/$ awk -f encode.awk
w, 0, R, 1, d X
10R1
me@home:~/$ awk -f decode.awk
10R1
X

Lembre-se de que o espaço após cada vírgula é necessário, se você usar as versões em golfe.

Se desejar, você pode usar este script curto e sujo para gerar alguns dados de amostra

BEGIN{
    for(srand();i++<1000;)
    {
        erg="";
        for(j=0;j++<5;)
        {
            while(erg~(a[j]=substr(c="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",rand()*62+1,1)));
            erg=erg a[j]
        }
        print a[1]", "a[2]", "a[3]", "a[4]", "a[5](rand()>.5?" ":rand()>.5?"  ":"   ")substr(c,rand()*62+1,1)
    }
}

e fazer algo engraçado como

me@home:~/$ awk -f gen.awk|awk -f encode.awk|awk -f decode.awk|sort -u|wc -l
62

Eu já vi isso mais como um quebra-cabeça de programação. Acho um pouco triste que quase tudo aqui seja jogado de golfe, porque você pode aprender muito mais com códigos bem documentados e legíveis, mas essa é apenas a minha opinião. E joguei como solicitado;)