Wprowadzenie

Niektóre znaki ASCII są obecnie tak drogie ...

Aby zaoszczędzić pieniądze, postanowiłeś napisać program, który koduje drogie znaki przy użyciu niedrogich.

Jednak ceny postaci zmieniają się często i nie chcesz modyfikować programu za każdym razem, gdy musisz zakodować lub odkodować inny znak! Potrzebujesz bardziej dynamicznego rozwiązania.

Wyzwanie

Twoim zadaniem jest napisanie dwóch programów: kodera i dekodera .

Koder powinien przyjąć listę pięciu znaków niedrogie i jeden kosztowny charakter.

Powinien generować pojedynczy ciąg znaków złożony z niedrogich znaków, który koduje drogi znak.

Ciąg ten nie może być dłuższy niż 4 znaki , aby pozostać niedrogi. Jednak nie musi używać wszystkich niedrogich znaków w kodowaniu, a kodowanie może mieć różną długość.

Dekoder powinien przyjąć ciąg wyprowadzony przez koder, i wysyła drogie znaków.

Dekoder nie akceptuje żadnych danych wejściowych poza zakodowanym łańcuchem. Musi działać niezmodyfikowany z danych wyjściowych kodera dla dowolnej (prawidłowej) kombinacji danych wejściowych. Innymi słowy, twój program dekodujący nie wie, które znaki są drogie lub tanie.

Punktacja

Najkrótszy łączony kod wygrywa!

Notatki

• Wszystkie znaki będą albo dużymi [A-Z], małymi literami [a-z], albo cyframi [0-9].

• Lista niedrogich postaci nie będzie zawierać duplikatów. Żadna postać nie będzie zarówno tania, jak i droga.

• Koder i dekoder nie muszą być napisane w tym samym języku, ale mogą być. Możesz napisać program lub funkcję.

• Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie dla twojego języka.

• Oba programy mogą nie udostępniać żadnych zmiennych ani danych.

streszczenie

• Wprowadzanie niedrogich i drogich znaków do kodera.

• Koder wyprowadza ciąg niedrogich znaków, kodując drogi znak.

• Dekoder otrzymuje dane wyjściowe kodera i wyświetla kosztowny charakter.

Przykłady

Wejście:     a, b, c, d, e     f

Możliwości enkodera:     a     eeee     caec

Dekoder:     f

Wejście:     a, b, c, d, e     h

Możliwości enkodera:     bc     cea     eeaa

Dekoder:     h

Wejście:     q, P, G, 7, C     f

Możliwości enkodera:     777     P7     PPCG

Dekoder:     f

Pyth, 46 bajtów

Koder, 22 bajty

@smfql{Td^<Szd4S4-Cw48

Dekoder, 24 bajty

C+48xsmfql{Td^<sS{zd4S4z

CJam, 55 50 48 47 bajtów

Koder, 24 22 21 bajtów

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

Wypróbuj online.

Dekoder, 31 28 27 26 bajtów

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

Wypróbuj online.

gawk, 163 + 165 = 328

Testowany z gawk 4.1.1, ale powinien również działać w starszych wersjach gawk. Musi zostać nieco zmodyfikowany (wydłużony), aby współpracował z mawk.

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

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

Cóż, działa, ale jestem świadomy, że może to nie być najlepsze podejście do tego. Nie mam pojęcia, do czego służy piąty niedrogi list, ponieważ używam tylko czterech.

Są tylko do jednorazowego użytku. Jeśli chcesz wprowadzić drugi kod, musisz go ponownie uruchomić. Spacje po przecinkach są wymagane na wejściu do kodowania.

O czym myślałem

Moje pierwsze pytanie brzmiało: „Co dekoder może uzyskać z tych 4 znaków?” (Nazywam je a, b, cid), a moim początkowym pomysłem było uzyskanie 6 bitów informacji z następujących relacji:

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

Wow, 6 bitów, to jest idealne! Myślałem, że to genialne, ale testy wykazały, że to nie zadziała. Istnieją tylko 24 możliwe kombinacje. Cholera.

Kolejnym krokiem była próba policzenia na podstawie tego, co już wiedziałam. Tak więc pierwsza litera pojawiająca się w ciągu będzie miała wartość 0, a następnie druga litera wprowadzona w ciągu będzie miała wartość 1 i tak dalej. Ale nie doprowadziłoby mnie to aż do potrzebnych 62 kombinacji.

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

Ale i tak podoba mi się ten pomysł.

Cóż, wtedy uderzyło mnie, że mogłem połączyć te dwa, ponieważ znaki na wejściu już mają relacje i nie musiałbym czekać, aż zostaną przedstawione, aby nadać im wartość.

Jak to działa

Uwaga: Nie tak już działają wersje w golfa, ale zasada pozostała taka sama.

Dla dekodera:

Konstruowana jest tablica, której indeks zawiera wszystkie czterocyfrowe liczby, których największa cyfra nie jest większa niż liczba odrębnych cyfr w tej liczbie. Istnieje 75 różnych czterocyfrowych liczb spełniających ten warunek. Brutalnie je zmuszam, bo jak dotąd nie mogłem znaleźć sposobu na ich zbudowanie i nie jestem pewien, czy i tak byłoby to krótsze w awk. Gdy je znajduję, przypisuję im drogie postacie w porządku asciibetycznym.

Następnie zastępuję każdy znak z ciągu wejściowego cyfrą. Najmniejszy (na przykład „B” mniejszy niż „a”) staje się 1, drugi najmniejszy staje się 2, i tak dalej do 4. Oczywiście zależy to od tego, ile różnych znaków jest na wejściu, jaka jest najwyższa cyfra w wynikowy ciąg będzie.

Następnie po prostu wypisuję element tablicy, który ma ten ciąg znaków jako indeks.

Enkoder działa odpowiednio.

Jak używać

Skopiuj kod bezpośrednio w linii poleceń awk bash lub utwórz dwa pliki „encode.awk” i „decode.awk” i odpowiednio wklej kod. Lub jeszcze lepiej użyj następującego kodu, który kończy się automatycznie po en / dekodowaniu, lub można go użyć wiele razy, usuwając polecenie exit na końcu.

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
}

Oto przykład użycia:

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

Pamiętaj, że wymagane jest miejsce po każdym przecinku, jeśli używasz wersji golfowych.

Jeśli chcesz, możesz użyć tego krótkiego i brudnego skryptu do wygenerowania przykładowych danych

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

i zrobić coś śmiesznego jak

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

Widziałem to bardziej jako zagadkę programistyczną. Myślę, że to trochę smutne, że prawie wszystko tutaj gra w golfa, ponieważ można dowiedzieć się o wiele więcej z dobrze udokumentowanego, czytelnego kodu, ale to tylko moja opinia. I grałem w golfa zgodnie z życzeniem;)