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.


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.


Shortest combined code wins!


  • 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.


  • 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.


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

  • \$\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, 2015 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, 2015 at 2:45
  • \$\begingroup\$ @Dennis Yes, those are just examples. \$\endgroup\$
    – jrich
    Sep 8, 2015 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, 2015 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, 2015 at 3:08

3 Answers 3


CJam, 55 50 48 47 bytes

Encoder, 24 22 21 bytes


Try it online.

Decoder, 31 28 27 26 bytes


Try it online.

  • \$\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, 2015 at 13:37
  • \$\begingroup\$ ' is not an operator. You can find it on the syntax page. \$\endgroup\$
    – Dennis
    Sep 9, 2015 at 14:05

Pyth, 46 bytes

Encoder, 22 bytes


Decoder, 24 bytes

  • \$\begingroup\$ Wow, that fits perfectly. 75 different char-combinations and a char-range of 75. \$\endgroup\$
    – Jakube
    Sep 9, 2015 at 13:21
  • \$\begingroup\$ I think you can replace S4 with T and save each one byte in both programs. \$\endgroup\$
    – Jakube
    Sep 9, 2015 at 13:55

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:


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.


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.


    if(!x) # only do first time
        for(i=1e3;i++<5e3;delete a)
    r=u=_; # clear reused variables 
    for(gsub(",",FS);sprintf("%c",++r)!=$NF;); # more flexible concerning
    --NF;                                      # spaces in input
    for(j in a)u=u b[a[j]]; # prettier printing than golfed version
    print u
    exit # <=== remove to encode input file


    if(!x) # only do first time 
        for(i=1e3;i++<5e3;delete a)
    delete t; delete d; o=_; # clear reused variables 
    for(i in a)t[a[i]]=1;
    for(i in t)d[++y]=i;
    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
me@home:~/$ awk -f decode.awk

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

            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

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

  • \$\begingroup\$ how to test it? please share some examples. \$\endgroup\$ Sep 9, 2015 at 13:54
  • \$\begingroup\$ +1 for the great explanation! Seems there are many different ways to approach this problem :) \$\endgroup\$
    – jrich
    Sep 10, 2015 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\$ Sep 12, 2015 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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