introduction

Certains caractères ASCII sont tellement chers de nos jours ...

Pour économiser de l'argent, vous avez décidé d'écrire un programme qui code des caractères coûteux en utilisant des caractères peu coûteux.

Cependant, les prix des caractères changent fréquemment et vous ne voulez pas modifier votre programme chaque fois que vous devez encoder ou décoder un caractère différent! Vous aurez besoin d'une solution plus dynamique.

Défi

Votre tâche consiste à écrire deux programmes: un encodeur et un décodeur .

L' encodeur doit accepter une liste de cinq caractères bon marché et un seul caractère coûteux.

Il devrait produire une seule chaîne composée de caractères bon marché, qui encode le caractère coûteux.

Cette chaîne ne doit pas dépasser 4 caractères , pour rester peu coûteuse. Cependant, il n'est pas nécessaire d'utiliser tous les caractères bon marché dans le codage et les codages peuvent être de longueurs différentes.

Le décodeur doit accepter la chaîne émise par l'encodeur et produire le caractère coûteux.

Le décodeur ne doit accepter aucune entrée autre que la chaîne codée. Il doit fonctionner, non modifié, à partir de la sortie du codeur pour toute combinaison (valide) d'entrées. En d'autres termes, votre programme de décodage ne sait pas quels caractères sont chers ou peu coûteux.

Notation

Le code combiné le plus court gagne!

Remarques

• Tous les caractères seront des majuscules [A-Z], des minuscules [a-z]ou des chiffres [0-9].

• La liste des personnages bon marché ne contiendra pas de doublons. Aucun personnage ne sera à la fois peu coûteux et coûteux.

• L'encodeur et le décodeur ne doivent pas être écrits dans la même langue, mais ils peuvent l'être. Vous pouvez écrire un programme ou une fonction.

• L'entrée et la sortie peuvent être dans n'importe quel format raisonnable pour votre langue.

• Les deux programmes ne peuvent partager aucune variable ou donnée.

Sommaire

• L'entrée de certains caractères peu coûteux et d'un caractère coûteux est donnée à l'encodeur.

• L'encodeur produit une chaîne de caractères bon marché, encodant le caractère coûteux.

• Le décodeur reçoit la sortie de l'encodeur et sort le caractère coûteux.

Exemples

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

Possibilités d'encodeur:     a     eeee     caec

Décodeur:     f

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

Possibilités d'encodeur:     bc     cea     eeaa

Décodeur:     h

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

Possibilités d'encodeur:     777     P7     PPCG

Décodeur:     f

Pyth, 46 octets

Encodeur, 22 octets

@smfql{Td^<Szd4S4-Cw48

Décodeur, 24 octets

C+48xsmfql{Td^<sS{zd4S4z

CJam, 55 50 48 47 octets

Encodeur, 24 22 21 octets

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

Essayez-le en ligne.

Décodeur, 31 28 27 26 octets

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

Essayez-le en ligne.

gawk, 163 + 165 = 328

Testé avec gawk 4.1.1, mais devrait également fonctionner dans les anciennes versions de gawk. Doit être légèrement modifié (allongé) pour fonctionner avec mawk.

encodeur (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]]}

décodeur (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)}

Eh bien, cela fonctionne, mais je suis conscient que ce n'est peut-être pas la meilleure approche pour cela. Je ne sais pas à quoi sert la cinquième lettre bon marché, car je n'en utilise que quatre.

Ils sont à usage unique. Si vous souhaitez entrer un deuxième code, vous devez les redémarrer. Les espaces après les virgules sont requis dans l'entrée pour encoder.

Ce que j'ai pensé

Ma première question était "Qu'est-ce qu'un décodeur pourrait obtenir de ces 4 caractères?" (Je vais les appeler a, b, c et d), et mon idée initiale était d'obtenir 6 bits d'informations à partir des relations suivantes:

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

Wow, 6 bits, c'est parfait! Je pensais que c'était du génie, mais les tests ont montré que cela ne fonctionnerait pas. Il n'y a que 24 combinaisons possibles. Zut.

La prochaine étape consistait à compter, d'après ce que je savais déjà. Ainsi, la première lettre apparaissant dans la chaîne deviendrait 0, puis la deuxième lettre introduite dans la chaîne deviendrait 1 et ainsi de suite. Mais cela ne m'amènerait pas jusqu'aux 62 combinaisons nécessaires.

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

Mais j'aime l'idée quand même.

Eh bien, il m'a alors semblé que je pouvais combiner ces deux, car les caractères dans l'entrée ont déjà des relations, et je n'aurais pas à attendre qu'ils aient été introduits pour leur donner une valeur.

Comment ça fonctionne

Remarque: Ce n'est plus exactement le fonctionnement des versions golf, mais le principe est resté le même.

Pour le décodeur:

Un tableau est construit, dont l'index contient tous les nombres à quatre chiffres dont le plus grand chiffre n'est pas supérieur au nombre de chiffres distincts de ce nombre. Il y a 75 numéros à quatre chiffres différents remplissant cette condition. Je les force brutalement, car jusqu'à présent, je ne pouvais pas trouver un moyen de les construire, et je ne suis pas sûr que ce serait plus court à faire dans awk de toute façon. Pendant que je les trouve, je leur attribue les caractères coûteux par ordre asciibétique.

Ensuite, je remplace chaque caractère de la chaîne d'entrée par un chiffre. Le plus petit (par exemple, «B» est plus petit que «a») devient 1, le deuxième plus petit devient 2, et ainsi de suite jusqu'à 4. Bien sûr, cela dépend du nombre de caractères différents dans l'entrée, du chiffre le plus élevé dans la chaîne résultante sera.

Ensuite, j'imprime simplement l'élément de tableau, qui a cette chaîne comme index.

L'encodeur fonctionne en conséquence.

Comment utiliser

Soit copiez le code directement dans une commande de ligne bash awk ou créez deux fichiers "encode.awk" et "decode.awk" et collez le code en conséquence. Ou encore mieux utilisez le code suivant, qui se ferme automatiquement après le décodage / en, ou peut être utilisé plusieurs fois en supprimant la commande exit à la fin.

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
}

Voici un exemple d'utilisation:

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

N'oubliez pas que l'espace après chaque virgule est requis, si vous utilisez les versions golfées.

Si vous le souhaitez, vous pouvez utiliser ce script court et sale pour générer des exemples de données

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)
    }
}

et faire quelque chose de drôle comme

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

J'ai vu cela plus comme un puzzle de programmation. Je pense que c'est un peu triste, que presque tout ici soit joué au golf, car vous pouvez en apprendre beaucoup plus à partir d'un code bien documenté et lisible, mais c'est juste mon opinion. Et je l'ai joué au golf comme demandé;)