16
\$\begingroup\$

Introduction

Some ASCII characters are just so expensive these days...

To save money you've decided to write a program that encodes expensive characters using inexpensive ones.

However, character prices change frequently and you don't want to modify your program every time you need to encode or decode a different character! You'll need a more dynamic solution.

Challenge

Your task is to write two programs: an encoder and a decoder.

The encoder should accept a list of five inexpensive characters, and a single expensive character.

It should output a single string made up of the inexpensive characters, that encodes the expensive character.

This string may not be longer than 4 characters, to remain inexpensive. However, it does not have to use all of the inexpensive characters in the encoding and encodings may be of different lengths.


The decoder should accept the string outputted by the encoder, and output the expensive character.

The decoder shall accept no input other than the encoded string. It must work, unmodified, from the encoder's output for any (valid) combination of inputs. In other words, your decoder program doesn't know which characters are expensive or inexpensive.

Scoring

Shortest combined code wins!

Notes

  • All characters will be either uppercase letters [A-Z], lowercase letters [a-z], or numbers [0-9].

  • The list of inexpensive characters won't contain duplicates. No character will be both inexpensive and expensive.

  • The encoder and decoder don't have to be written in the same language, but they can be. You may write a program or a function.

  • Input and output may be in any reasonable format for your language.

  • The two programs may not share any variables or data.

Summary

  • Input of some inexpensive characters and an expensive character is given to encoder.

  • Encoder outputs a string of inexpensive characters, encoding the expensive character.

  • Decoder is given the encoder's output, and outputs the expensive character.

Examples

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

Encoder Possibilities:     a     eeee     caec

Decoder:     f


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

Encoder Possibilities:     bc     cea     eeaa

Decoder:     h


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

Encoder Possibilities:     777     P7     PPCG

Decoder:     f

\$\endgroup\$
  • \$\begingroup\$ This really just could be me, and I apologize for this question if it is, but how exactly are you supposed to encode your message with the inexpensive characters? Addition of the ASCII codes for the 5 inexpensive characters? Actually, this question only has a basis if your decoder must decode for all encoding possibilities generated. \$\endgroup\$ – cole Sep 8 '15 at 2:38
  • \$\begingroup\$ To be clear: The Encoder Possibilities are just examples and we can encode each character as we want, yes? \$\endgroup\$ – Dennis Sep 8 '15 at 2:45
  • \$\begingroup\$ @Dennis Yes, those are just examples. \$\endgroup\$ – jrich Sep 8 '15 at 2:46
  • \$\begingroup\$ @Cole Without giving away an actual algorithm, as that is the main challenge here, I believe that it is possible. There are only 62 possible expensive letters to encode, and with these 4 ascii characters up to 92 can be encoded, according to A239914. (huge thanks to PhiNotPi's sandbox comment for this one - I didn't calculate exactly how many could be encoded) \$\endgroup\$ – jrich Sep 8 '15 at 2:52
  • \$\begingroup\$ @UndefinedFunction I realize now what you've intended: Dennis's question answered what I was confused about. \$\endgroup\$ – cole Sep 8 '15 at 3:08
5
\$\begingroup\$

Pyth, 46 bytes

Encoder, 22 bytes

@smfql{Td^<Szd4S4-Cw48

Decoder, 24 bytes

C+48xsmfql{Td^<sS{zd4S4z
\$\endgroup\$
  • \$\begingroup\$ Wow, that fits perfectly. 75 different char-combinations and a char-range of 75. \$\endgroup\$ – Jakube Sep 9 '15 at 13:21
  • \$\begingroup\$ I think you can replace S4 with T and save each one byte in both programs. \$\endgroup\$ – Jakube Sep 9 '15 at 13:55
7
\$\begingroup\$

CJam, 55 50 48 47 bytes

Encoder, 24 22 21 bytes

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

Try it online.

Decoder, 31 28 27 26 bytes

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

Try it online.

\$\endgroup\$
  • \$\begingroup\$ Is there a CJam syntax sheet out there you use? The one on sourceforge and that other pdf cheat sheet don't contain all the characters you use like ' \$\endgroup\$ – Luminous Sep 9 '15 at 13:37
  • \$\begingroup\$ ' is not an operator. You can find it on the syntax page. \$\endgroup\$ – Dennis Sep 9 '15 at 14:05
4
\$\begingroup\$

gawk, 163 + 165 = 328

Tested with gawk 4.1.1, but should work in older gawk versions as well. Needs to be slightly modified (lengthened) to work with 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]]}

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

Well, it works, but I'm aware that this might not be the best approach for this. I have no idea what the fifth inexpensive letter is for, because I use only four.

These are for single use only. If you want to enter a second code you have to restart them. The spaces after the commas are required in the input to encode.

What I thought about

My first question was "What could a decoder get from these 4 characters?" (I'll call them a, b, c and d), and my initial idea was to get 6 bits of Information from following relations:

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

Wow, 6 bit, that's perfect! I thought it was genius, but testing showed this would not work. There are only 24 possible combinations. Damn.

The next step was trying to count, based on what I already knew. So the first letter appearing in the string would become 0, then the second letter introduced in the string would become 1 and so on. But it wouldn't bring me all the way to the 62 combinations needed.

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

But I like the idea anyhow.

Well, then it struck me, that I could combine these two, because the characters in the input already have relations, and I wouldn't have to wait until they were introduced to give them a value.

How it works

Note: This is no longer exactly how the golfed versions work, but the principle stayed the same.

For the decoder:

An array is constructed, whose index contains all the four digit numbers whose largest digit isn't greater than the number of distinct digits in that number. There are 75 different four digit numbers meeting that condition. I brute force them, because so far I couldn't figure out a way to construct them, and I'm not sure this would be shorter to do in awk anyway. While I find these I assign them the expensive characters in asciibetical order.

Then I replace every character from the input string with a digit. The smallest (for instance is 'B' smaller than 'a') becomes 1, the second smallest becomes 2, and so on up to 4. Of course it depends on how many different characters are in the input, what the highest digit in the resulting string will be.

Then I simply print the array element, which has that string as an index.

The encoder works accordingly.

How to use

Either copy the code directly in an awk bash line command or make two files "encode.awk" and "decode.awk" and paste the code accordingly. Or even better use the following code, which exits automatically after en/decoding, or can be used multiple times by removing the exit command at the end.

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
}

Here is a usage example:

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

Remember that the space after each comma is required, if you use the golfed versions.

If you want, you can use this short and dirty script to generate some sample data

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

and do something funny like

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

I've seen this more as a programming puzzle. I think it's a little sad, that almost everything on here is golfed, because you can learn a lot more from well documented, readable code, but that's just my opinion. And I golfed it like requested ;)

\$\endgroup\$
  • \$\begingroup\$ how to test it? please share some examples. \$\endgroup\$ – Shravan Yadav Sep 9 '15 at 13:54
  • \$\begingroup\$ +1 for the great explanation! Seems there are many different ways to approach this problem :) \$\endgroup\$ – jrich Sep 10 '15 at 10:38
  • 1
    \$\begingroup\$ This was very similar to my thought process except I didn't realize brute-forcing the unique weak combinations (where you described the largest digit not being greater than the amount of digits) was a viable approach. Kudos for following through. \$\endgroup\$ – Patrick Roberts Sep 12 '15 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.