Einführung

Einige ASCII-Zeichen sind heutzutage so teuer ...

Um Geld zu sparen, haben Sie sich entschieden, ein Programm zu schreiben, das teure Zeichen mit billigen Zeichen codiert.

Die Zeichenpreise ändern sich jedoch häufig und Sie möchten Ihr Programm nicht jedes Mal ändern, wenn Sie ein anderes Zeichen codieren oder decodieren müssen! Sie benötigen eine dynamischere Lösung.

Herausforderung

Ihre Aufgabe ist es, zwei Programme zu schreiben: einen Encoder und einen Decoder .

Der Encoder sollte eine Liste von fünf billigen Zeichen und ein einziges teures Zeichen akzeptieren.

Es sollte eine einzelne Zeichenfolge aus den billigen Zeichen ausgegeben werden, die das teure Zeichen codiert.

Diese Zeichenfolge darf nicht länger als 4 Zeichen sein , um kostengünstig zu bleiben. Es müssen jedoch nicht alle kostengünstigen Zeichen in der Codierung verwendet werden und die Codierungen können unterschiedlich lang sein.

Der Decoder sollte die vom Encoder ausgegebene Zeichenfolge akzeptieren und das teure Zeichen ausgeben.

Der Decoder darf keine andere Eingabe als die codierte Zeichenfolge akzeptieren. Es muss für jede (gültige) Kombination von Eingängen unverändert vom Ausgang des Encoders funktionieren. Mit anderen Worten, Ihr Decoderprogramm weiß nicht, welche Zeichen teuer oder billig sind.

Wertung

Kürzester kombinierter Code gewinnt!

Anmerkungen

• Alle Zeichen sind entweder Großbuchstaben [A-Z], Kleinbuchstaben [a-z]oder Zahlen [0-9].

• Die Liste der billigen Zeichen enthält keine Duplikate. Kein Charakter wird sowohl billig als auch teuer sein.

• Der Codierer und der Decodierer müssen nicht in derselben Sprache geschrieben sein, können es aber sein. Sie können ein Programm oder eine Funktion schreiben.

• Die Eingabe und Ausgabe kann in einem für Ihre Sprache angemessenen Format erfolgen.

• Die beiden Programme dürfen keine Variablen oder Daten gemeinsam nutzen.

Zusammenfassung

• Die Eingabe einiger billiger Zeichen und eines teuren Zeichens erfolgt an den Codierer.

• Encoder gibt eine Zeichenfolge mit kostengünstigen Zeichen aus, die das teure Zeichen codiert.

• Der Decoder erhält die Ausgabe des Encoders und gibt das teure Zeichen aus.

Beispiele

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

Encoder-Möglichkeiten:     a     eeee     caec

Decoder:     f

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

Encoder-Möglichkeiten:     bc     cea     eeaa

Decoder:     h

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

Encoder-Möglichkeiten:     777     P7     PPCG

Decoder:     f

Pyth, 46 Bytes

Encoder, 22 Bytes

@smfql{Td^<Szd4S4-Cw48

Decoder, 24 Bytes

C+48xsmfql{Td^<sS{zd4S4z

CJam, 55 50 48 47 Bytes

Encoder, 24 22 21 Bytes

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

Probieren Sie es online aus.

Decoder, 31 28 27 26 Bytes

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

Probieren Sie es online aus.

Gawk, 163 + 165 = 328

Getestet mit Gawk 4.1.1, sollte aber auch in älteren Gawk-Versionen funktionieren. Muss leicht modifiziert (verlängert) werden, um mit Mawk zu arbeiten.

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

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

Nun, es funktioniert, aber ich bin mir bewusst, dass dies möglicherweise nicht der beste Ansatz dafür ist. Ich habe keine Ahnung, wofür der fünfte preiswerte Brief ist, weil ich nur vier benutze.

Diese sind nur zum einmaligen Gebrauch bestimmt. Wenn Sie einen zweiten Code eingeben möchten, müssen Sie diese neu starten. Die Leerzeichen nach den Kommas müssen in der Eingabe codiert werden.

Was ich darüber nachgedacht habe

Meine erste Frage war "Was kann ein Decoder aus diesen 4 Zeichen machen?" (Ich werde sie a, b, c und d nennen), und meine ursprüngliche Idee war, 6 Bits an Informationen aus folgenden Beziehungen zu erhalten:

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

Wow, 6 Bit, das ist perfekt! Ich hielt es für genial, aber Tests ergaben, dass dies nicht funktionieren würde. Es gibt nur 24 mögliche Kombinationen. Verdammt.

Der nächste Schritt war zu zählen, basierend auf dem, was ich bereits wusste. Der erste Buchstabe in der Zeichenfolge wird zu 0, der zweite Buchstabe in der Zeichenfolge wird zu 1 und so weiter. Aber es würde mich nicht bis zu den 62 benötigten Kombinationen bringen.

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

Aber die Idee gefällt mir trotzdem.

Nun, dann fiel mir auf, dass ich diese beiden kombinieren könnte, da die Zeichen in der Eingabe bereits Beziehungen haben und ich nicht warten müsste, bis sie eingeführt wurden, um ihnen einen Wert zu geben.

Wie es funktioniert

Hinweis: Genau so funktionieren die Golf-Versionen nicht mehr, aber das Prinzip ist gleich geblieben.

Für den Decoder:

Es wird ein Array erstellt, dessen Index alle vier Ziffern enthält, deren größte Ziffer nicht größer ist als die Anzahl der einzelnen Ziffern in dieser Ziffer. Es gibt 75 verschiedene vierstellige Zahlen, die diese Bedingung erfüllen. Ich zwinge sie brutal, weil ich bisher keinen Weg gefunden habe, sie zu konstruieren, und ich bin mir nicht sicher, ob dies in awk sowieso kürzer sein würde. Während ich diese finde, ordne ich ihnen die teuren Zeichen in ASCII-Reihenfolge zu.

Dann ersetze ich jedes Zeichen aus der Eingabezeichenfolge durch eine Ziffer. Das kleinste (zum Beispiel ist 'B' kleiner als 'a') wird zu 1, das zweitkleinste wird zu 2 und so weiter bis zu 4. Natürlich hängt es davon ab, wie viele verschiedene Zeichen in der Eingabe sind, was die höchste Ziffer ist Die resultierende Zeichenfolge ist.

Dann drucke ich einfach das Array-Element, das diesen String als Index hat.

Der Encoder arbeitet entsprechend.

Wie benutzt man

Kopieren Sie den Code entweder direkt in einen awk-bash-Zeilenbefehl oder erstellen Sie zwei Dateien "encode.awk" und "decode.awk" und fügen Sie den Code entsprechend ein. Oder verwenden Sie besser den folgenden Code, der nach dem En / Decodieren automatisch beendet wird, oder Sie können ihn mehrmals verwenden, indem Sie den Befehl exit am Ende entfernen.

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
}

Hier ist ein Anwendungsbeispiel:

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

Denken Sie daran, dass das Leerzeichen nach jedem Komma erforderlich ist, wenn Sie die Golf-Versionen verwenden.

Wenn Sie möchten, können Sie dieses kurze und unsaubere Skript verwenden, um einige Beispieldaten zu generieren

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

und mach sowas lustiges wie

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

Ich habe das eher als Programmierpuzzle gesehen. Ich finde es ein bisschen traurig, dass hier fast alles golfen ist, denn man kann viel mehr aus gut dokumentiertem, lesbarem Code lernen, aber das ist nur meine Meinung. Und ich habe es wie gewünscht golfen;)