pengantar

Beberapa karakter ASCII sangat mahal belakangan ini ...

Untuk menghemat uang Anda telah memutuskan untuk menulis sebuah program yang menyandikan karakter mahal menggunakan yang murah.

Namun, harga karakter sering berubah dan Anda tidak ingin memodifikasi program Anda setiap kali Anda perlu menyandikan atau mendekodekan karakter yang berbeda! Anda akan membutuhkan solusi yang lebih dinamis.

Tantangan

Tugas Anda adalah menulis dua program: encoder dan decoder .

The encoder harus menerima daftar lima karakter murah, dan karakter mahal tunggal.

Seharusnya menampilkan string tunggal yang terdiri dari karakter murah, yang mengkodekan karakter mahal.

String ini mungkin tidak lebih dari 4 karakter , tetap murah Namun, tidak harus menggunakan semua karakter murah dalam penyandian dan penyandian mungkin memiliki panjang yang berbeda.

The decoder harus menerima string yang dikeluarkan oleh encoder, dan output karakter mahal.

Decoder tidak akan menerima input selain dari string yang disandikan. Ini harus bekerja, tidak dimodifikasi, dari output encoder untuk setiap kombinasi input yang valid. Dengan kata lain, program dekoder Anda tidak tahu karakter mana yang mahal atau tidak mahal.

Mencetak gol

Kode gabungan terpendek menang!

Catatan

• Semua karakter akan berupa huruf besar [A-Z], huruf kecil [a-z], atau angka [0-9].

• Daftar karakter murah tidak akan mengandung duplikat. Karakter tidak akan murah dan mahal.

• Encoder dan decoder tidak harus ditulis dalam bahasa yang sama, tetapi mereka bisa. Anda dapat menulis program atau fungsi.

• Input dan output mungkin dalam format yang masuk akal untuk bahasa Anda.

• Kedua program tidak boleh membagikan variabel atau data apa pun.

Ringkasan

• Input dari beberapa karakter murah dan karakter mahal diberikan ke enkoder.

• Encoder menampilkan serangkaian karakter yang tidak mahal, menyandikan karakter yang mahal.

• Decoder diberikan output encoder, dan output karakter mahal.

Contohnya

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

Kemungkinan Encoder:     a     eeee     caec

Dekoder:     f

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

Kemungkinan Encoder:     bc     cea     eeaa

Dekoder:     h

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

Kemungkinan Encoder:     777     P7     PPCG

Dekoder:     f

Pyth, 46 byte

Encoder, 22 byte

@smfql{Td^<Szd4S4-Cw48

Dekoder, 24 byte

C+48xsmfql{Td^<sS{zd4S4z

CJam, 55 50 48 47 byte

Encoder, 24 22 21 byte

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

Cobalah online.

Decoder, 31 28 27 26 byte

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

Cobalah online.

gawk, 163 + 165 = 328

Diuji dengan gawk 4.1.1, tetapi juga bisa digunakan pada versi gawk yang lebih lama. Perlu sedikit dimodifikasi (diperpanjang) untuk bekerja dengan mawk.

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

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

Ya, itu berhasil, tapi saya sadar ini mungkin bukan pendekatan terbaik untuk ini. Saya tidak tahu untuk apa surat kelima itu, karena saya hanya menggunakan empat.

Ini hanya untuk penggunaan tunggal. Jika Anda ingin memasukkan kode kedua Anda harus me-restart mereka. Spasi setelah koma diperlukan dalam input untuk menyandikan.

Apa yang saya pikirkan

Pertanyaan pertama saya adalah "Apa yang bisa didapatkan oleh decoder dari 4 karakter ini?" (Saya akan memanggil mereka a, b, c dan d), dan ide awal saya adalah untuk mendapatkan 6 bit Informasi dari relasi berikut:

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

Wow, 6 bit, itu sempurna! Saya pikir itu jenius, tetapi pengujian menunjukkan ini tidak akan berhasil. Hanya ada 24 kemungkinan kombinasi. Sial.

Langkah selanjutnya adalah mencoba menghitung, berdasarkan apa yang sudah saya ketahui. Jadi huruf pertama yang muncul dalam string akan menjadi 0, maka huruf kedua yang diperkenalkan dalam string akan menjadi 1 dan seterusnya. Tapi itu tidak akan membawa saya ke 62 kombinasi yang dibutuhkan.

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

Tapi saya suka ide itu.

Nah, kemudian saya tersadar, bahwa saya bisa menggabungkan keduanya, karena karakter dalam input sudah memiliki hubungan, dan saya tidak perlu menunggu sampai mereka diperkenalkan untuk memberi mereka nilai.

Bagaimana itu bekerja

Catatan: Ini bukan lagi cara kerja versi golf, tetapi prinsipnya tetap sama.

Untuk dekoder:

Array dikonstruksi, yang indeksnya berisi semua empat digit angka yang digit terbesarnya tidak lebih besar dari jumlah digit berbeda dalam angka itu. Ada 75 angka empat digit berbeda memenuhi kondisi itu. Saya dengan kasar memaksa mereka, karena sejauh ini saya tidak bisa menemukan cara untuk membangunnya, dan saya tidak yakin ini akan lebih pendek untuk dilakukan dalam awk. Sementara saya menemukan ini, saya menetapkan mereka karakter mahal dalam urutan asciibetical.

Lalu saya mengganti setiap karakter dari string input dengan digit. Yang terkecil (misalnya 'B' lebih kecil dari 'a') menjadi 1, terkecil kedua menjadi 2, dan seterusnya hingga 4. Tentu saja itu tergantung pada berapa banyak karakter yang berbeda dalam input, berapa digit tertinggi dalam string yang dihasilkan akan.

Lalu saya cukup mencetak elemen array, yang memiliki string sebagai indeks.

Encoder bekerja dengan baik.

Cara Penggunaan

Salin kode secara langsung dalam perintah awk bash line atau buat dua file "encode.awk" dan "decode.awk" dan tempel kode sesuai. Atau bahkan lebih baik menggunakan kode berikut, yang keluar secara otomatis setelah en / decoding, atau dapat digunakan beberapa kali dengan menghapus perintah keluar di akhir.

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
}

Ini adalah contoh penggunaan:

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

Ingatlah bahwa ruang setelah setiap koma diperlukan, jika Anda menggunakan versi golf.

Jika mau, Anda dapat menggunakan skrip pendek dan kotor ini untuk menghasilkan beberapa data sampel

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

dan melakukan sesuatu yang lucu seperti

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

Saya telah melihat ini lebih sebagai teka-teki pemrograman. Saya pikir ini agak menyedihkan, bahwa hampir semua yang ada di sini adalah golf, karena Anda dapat belajar lebih banyak dari kode yang terdokumentasi dengan baik dan mudah dibaca, tetapi itu hanya pendapat saya. Dan saya bermain golf seperti yang diminta;)