Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The golf challenge is to encode and compress the following image inside a source file.

Image

To do this you need to write 3 functions: red, green, and blue which accept x/y coordinates of the image and return the corresponding R/G/B pixel value between 0-255.

Here is the C/C++ test code:

#include <stdio.h>
#include "your_file"
int main() {
  int x, y;
  for(y = 0; y < 32; ++y)
  for(x = 0; x < 32; ++x)
    printf("%i %i %i\n", red(x, y), blue(x, y), green(x, y));
}

And the output: http://pastebin.com/A770ckxL (you can use this to generate your image data)

Rules & details:

  • This is a golf
  • Only your code/file is golfed - the test code is separate
  • The character set used is ASCII, however control characters in strings may only be used if escaped (like '\n' and '\r', etc)
  • Everything must be contained inside the source - no file loading
  • Your output must match the example output. This means loseless compression.

Languages:

The problem was written with C/C++ in mind, but I'm removing those restrictions. With that said, I'll still recommend using them.

share|improve this question
4  
If there is no specific reason to do so, fixing a question to a specific language is highly discouraged. What is the reason why one must not use other languages? –  FUZxxl Mar 18 '12 at 11:44
    
@FUZxxl I was afraid other languages would be less interesting and use something like Unicode hacks or base 64. If anyone has a great solution that requires another language then I'll gladly update the rules. –  Pubby Mar 18 '12 at 12:04
3  
If a solution is less interesting, don't vote it up. Forbidding "lame" solutions by exclusing languages is overkill. –  FUZxxl Mar 18 '12 at 12:43
2  
If you've already limited the character set to ASCII (which I consider absolutely ok), how could we use Unicode hacks? As for base 64, you can do that inside standard C as well as any other language, it only different amounts of wrapper code. — But I like the task. –  leftaroundabout Mar 18 '12 at 13:08
    
Alright, I removed the restriction but left the suggestion. –  Pubby Mar 18 '12 at 13:36
show 3 more comments

8 Answers

C, 796 754 712 703 692 685 682 670 666 662 656 648 chars

Changelog:

  • 754->712: Added return to the #define, replacing if with ? statements (thanks @FUZxxl), removing int from the functions parameter list.
  • 712->703: Shameless copy from bunnit again :) Moved the whole image creation into the #define
  • 703->692: Merged p[] and h[], some more ?: improvements
  • 692->685: Incrementing b so i isn't needed anymore. m=b instead of m=11 and n<2e3 instead of i<356 - these are close to undefined behaviour/memory corruption, but it seems I'm lucky :)
  • 685->682: k is now (32,16,8,4,2,1,0) instead of (5,4,3,2,1,0). Gotcha, D C ;)
  • 682->670: Split p[] and h[], converted h[] to a char* - awwww, there's a sleepy kitty in it ^<+_=>-
  • 670->666: while => for, l=l*2+... => l+=l+...
  • 666->662: m=m>9?... => c[n++]=m>9?...
  • 662->656: Reversed bit order in b[], so we can map to 64-127 instead of 0-63 and don't need bit index k anymore. Thanks @Piotr Tarsa. Replaced ?: (GCC extension) with ||. Thanks @JamesB
  • 656->648: Shameless copy from Shelwien :) (multi-character constants for p[])

Image is converted to a Base64-like string (ASCII 37-100), using huffman coding to encode colors 0-9 using 3-6 bits and a special color 10 (pixel is same as previous one) using only 1 bit.

#define P (x,y){for(;n<2e3;j/=2){j>1||(j=*b+++27);l+=l+(j&1);for(m=0;m<11;m++)l-h[m]+32||(c[n++]=m>9?c[n-1]:m,l=0,m=b);}return 255&p[c[x+y*32]]
char*h="$^<+_=>-,* ",*b="F0(%A=A=%SE&?AEVF1E01IN8X&WA=%S+E+A-(,+IZZM&=%]U5;SK;cM84%WE*cAZ7dJT3R.H1I2@;a^/2DIK&=&>^X/2U*0%'0E+;VC<-0c>&YU'%],;]70R=.[1U4EZ:Y=6[0WU4%SQARE0=-XDcXd_WW*UAF&cFZJJ0EV*(a(P05S3IXA>51cH:S5SAE6+W%/[]7SF(153UM]4U()(53DA+J:]&5+5KX,L6>*4I,/UMBcML9WKLa9%UYIHKWW(9-*):(-ZW(9%T'N&9;C,C/Ea/Y7(JJ\\6CD9E,2%J*,ac]NIW8(M=VFac)/^)?IS-;W&45^%*N7>V,,C-4N35FMQaF,EaWX&*EJ4'";p[]={0,'R@+','aXL',7783255,'4k`',16354410,'NNv',5295994,4671418,9975021},c[1024],j,l,m,n;red P;}blue P>>16;}green P>>8;}

Copied two things from bunnit's answer, the #define and the whole image being decoded completely every time red/green/blue are called. There's some room for additional improvement, so expect some updates :) I'm not sure about code compliance, used GCC 4.6.1 to compile and test.

Compression-wise, I think arithmetic coding would help as the distribution is pretty skewed, but maybe code overhead would be too heavy in this case. LZW also should do a very good job. Colors are quite local, so adaptive coding might be an idea.

More readable 754 character version with some comments:

#define P 255&p[c[x+y*32]]
// Base64 coded image bitstream, ASCII 37-100
// Huffman codes: 100, 111110, 11100, 1011, 111111, 11101, 11110, 1101, 1100, 1010, 0
char b[]="FYU%3+3+%B&E;3&HF1&Y1.JWXE83+%B=&=3)U]=.PP*E+%,('?B>?D*Wa%8&MD3P7dNbARIV1.Q[?4L9Qc.>E+EKLX9Q(MY%5Y&=?HC_)YDKE0(5%,]?,7YR+I@1(a&PO0+G@Y8(a%B23R&Y+)XcDXd<88M(3FEDFPNNY&HMU4UZY'BA.X3K'1DVOB'B3&G=8%9@,7BFU1'A(*,a(U-U'Ac3=NO,E'='>X]^GKMa.]9(*SD*^/8>^4/%(0.V>88U/)M-OU)P8U/%b5JE/?C]C9&4907UNN`GCc/&]Q%NM]4D,J.8WU*+HF4D-9L-;.B)?8Ea'L%MJ7KH]]C)aJA'F*24F]&48XEM&Na5";
// Colors, order GBR (one char shorter than all the others)
p[]={0,5390379,6379596,7783255,3435360,16354410,5131894,5295994,4671418,9975021};
// Huffman codes for colors 0-10
h[]={4,62,28,11,63,29,30,13,12,10,0};
// Array for image data
c[1024];
i,j,k,l,m,n;
red(int x,int y){
  while(i<356){
    k--;
    if (k<0) {
      j=b[i++]-37;
      k=5;
    }
    l*=2;
    if (j&(1<<k)) l++;
    for(m=0;m<11;m++){
      if(l==h[m]){
        if (m>9) m=c[n-1];
        c[n++]=m;
        l=0;
        m=12;
      }
    }
  }
  return P;
}
blue(int x,int y){return P>>16;}
green(int x,int y){return P>>8;}
share|improve this answer
    
Very nice, can't believe I didn't think about using base 64. I think you can still save quite a few characters though, especially in that loop. Works fine in VS2008 btw. –  Bunnit Mar 22 '12 at 1:51
    
I think you can remove that int's from the parameter lists to remove some more bytes. –  FUZxxl Mar 22 '12 at 10:10
    
How about m=m>9?c[n-1]:m; for if(m>9)m=c[n-1];? –  FUZxxl Mar 22 '12 at 10:12
    
And also: for if(k<0){j=b[i++]-37;k=5;} why not k>=0?:(j=b[i++]-37,k=5);? (This code uses a C extension of gcc, x=a?:b is the same as x=a?a:b, with the difference that a is evaluated only once. –  FUZxxl Mar 22 '12 at 10:23
    
red(x,y){while(i<356){--k>=0?:(j=b[i++]-37,k=5);l*=2;if(j&(1<<k))l++;for(m=0;m<‌​11;m++)l!=h[m]?:(m=m<=9?:c[n-1],c[n++]=m,l=0,m=12);}return P;} –  FUZxxl Mar 22 '12 at 10:25
show 4 more comments

Python (684 592 characters)

red,blue,green=[lambda x,y,i=i:[15570996,2839104,7010700,5732035,6304875,0,12207943,8016079,7753294,5005656][int('eJxtkgGSxSAIQ6+kaLTe/2JLImj7Z9MZ6/gMIgjAzMbVWisGySRNm2ut5Hhx/2M0JMfHH5PWwo9x4mNO8pb6JkFM3hpqrR4+qY6eVK1mjlsFeSOBjPyCMy3348aXVRtq9X8czovMIwA5FeXKtGOcvfcf/lbvyW0n2BTOh122HiIH0g/uNrx47zupzMxuuTv808pZd3K7deJ/+PiH61AztmaNwPAsOnNGYovWIxswRill6vnAL4HgxDF17jFcjwRk/5b3Q1x1flLI9n64CIci8bmQe7NL8XoKliu+Jk/AR9rnjkwAYaDka8OXu/a+5NvvNzkcmqifL47H04kAz9M+9slKkDMGuOHi5PR7GZwv7MeApkz5JOSPHFVW3QTbzDJtzDIczkuWjeupLbckLyU5/gByftMg'.decode('base64').decode('zip')[32*y+x])]>>i&255 for i in 16,8,0]

Since this challenge is now open to all, why not! It's the familiar zlib -> base64 encoding route, so I apologize for that. Hopefully an entry with some semblance of ingenuity will be shorter!

Here's a test snippet analogous to the original:

for y in range(32):
    for x in range(32):
        print red(x,y), blue(x,y), green(x,y)
share|improve this answer
    
You should try adding a special color to repeat the previous pixel value, too. 588 chars base64 is much larger than the string in my answer (365 chars) and although zLib is overkill here, it should give a similar result, so around 500 chars total should be possible this way. –  schnaader Mar 22 '12 at 13:32
add comment

C++, 631 chars; C - 613

A base-92 unary mtf coder, C++, 631 chars:

#define A(Z)int Z(int X,int Y){char*s="xdGe*V+KHSBBGM`'WcN^NAw[,;ZQ@bbZVjCyMww=71xK1)zn>]8b#3&PX>cyqy@6iL?68nF]k?bv/,Q`{i)n[2Df1zR}w0yIez+%^M)Diye{TC]dEY\\0,dU]s'0Z?+bo;7;$c~W;tvFl%2ruqWk$Rj0N[uP)fSjk?Tnpn_:7?`VbJ%r@7*MQDFCDo3)l#ln<kuRzzHTwCg&gYgSXtv\\m_Eb}zRK7JK<AZzOe}UX{Crk)SyBn;;gdDv=.j*O{^/q6)`lHm*YYrdM/O8dg{sKW#B3BLMiI8@-Zo-EsgE.R#viYL$-<EU*~u5pe$r:`b)^dgXOJtf4";int*v,B=92,R=1,C=0,w[]={0,16354410,4671418,'aXL',7783255,5295994,'R@+','4k`',9975021,'NNv'};for(X+=Y*32+1;X--;)for(v=w;;){for(Y=*v++;R<B*B*B;C=C%R*B+*s++-35)R*=B;if(R/=2,C>=R){for(C-=R;--v>w;*v=v[-1]);*v=Y;break;}}return 255&Y
A(red);}A(blue)>>16;}A(green)>>8;}

And the C version of above (613 chars):

#define A (X,Y){char*s="xdGe*V+KHSBBGM`'WcN^NAw[,;ZQ@bbZVjCyMww=71xK1)zn>]8b#3&PX>cyqy@6iL?68nF]k?bv/,Q`{i)n[2Df1zR}w0yIez+%^M)Diye{TC]dEY\\0,dU]s'0Z?+bo;7;$c~W;tvFl%2ruqWk$Rj0N[uP)fSjk?Tnpn_:7?`VbJ%r@7*MQDFCDo3)l#ln<kuRzzHTwCg&gYgSXtv\\m_Eb}zRK7JK<AZzOe}UX{Crk)SyBn;;gdDv=.j*O{^/q6)`lHm*YYrdM/O8dg{sKW#B3BLMiI8@-Zo-EsgE.R#viYL$-<EU*~u5pe$r:`b)^dgXOJtf4";int*v,B=92,R=1,C=0,w[]={0,16354410,4671418,'aXL',7783255,5295994,'R@+','4k`',9975021,'NNv'};for(X+=Y*32+1;X--;)for(v=w;;){for(Y=*v++;R<B*B*B;C=C%R*B+*s++-35)R*=B;if(R/=2,C>=R){for(C-=R;--v>w;*v=v[-1]);*v=Y;break;}}return 255&Y
red A;}blue A>>16;}green A>>8;}

Just to include an entry with base-95 data and arithmetic coding + adaptive statistical model.
schnaader's code uses ~438 chars for data, and mine only 318 (311 w/o masking).
But as expected, arithmetic coding is too complicated for a small sample like this.

(This is 844 chars)

char* q="q^<A\">7T~pUN1 adz824K$5a>C@kC8<;3DlnF!z8@nD|9D(OpBdE#C7{yDaz9s;{gF[Dxad'[oyg\\,j69MGuFcka?LClkYFh=:q\\\\W(*zhf:x)`O7ZWKLPJsP&wd?cEu9hj 6(lg0wt\\g[Wn:5l]}_NUmgs]-&Hs'IT[ Z2+oS^=lwO(FEYWgtx),)>kjJSIP#Y?&.tx-3xxuqgrI2/m~fw \\?~SV={EL2FVrDD=1/^<r*2{{mIukR:]Fy=Bl.'pLz?*2a? #=b>n]F~99Rt?6&*;%d7Uh3SpLjI)_abGG$t~m{N=ino@N:";
#define I int
#define F(N) for(i=0;i<N;i++)
#define Z C=(C%T)*B+(*q++)-32
enum{B=95,H=1024,T=B*B*B};I p[B],v[B+H],n=3,*m=&v[B],R=T*B,C,i,j,y,c,x,w;void D(I P){w=(R>>11)*P;(y=C>=w)?R-=w,C-=w:R=w;while(R<T)R*=B,Z;}struct u{u(){F(4)Z;F(B)p[i]=H,v[i]=0;F(H){v[0]=m[i-1];v[1]=m[i-32];j=i;F(n){I&P=p[i];D(P);if(y){P-=P>>4;c=v[i];goto t;}else P+=H+H-P>>4;}c<<=7;for(x=-255;x<0;x+=x+y)D(H);v[n++]=c=x;t:m[i=j]=c;}}}d;I red(I x,I y,I z=0){return m[y*32+x]>>z&255;}
#define blue(x,y) red(x,y,8)
#define green(x,y) red(x,y,16)

Tests (from earlier base-96 version):
http://codepad.org/qrwuV3Oy
http://ideone.com/ATngC

Somehow SO eats 7F codes, so I had to update it to base=95

share|improve this answer
add comment

C++ - 1525 1004 964 chars

#define e (int x,int y){for(i=g=0;i<702;i=i+2)for(j=48;j<d[i];++j)c[g++]=d[i+1]-48;return 255&z[c[x+y*32]]
int i,g,j,z[]={0,7010700,12207943,5005656,5732035,8016079,2839104,6304875,15570996,7753294},c[1024];
char*d="3031;23322337261524453223310625132101214103453101233722172643310323342102521229492333210352112241036141014821042552621241014161016141024121022103210151015104526211034361034726510352625107441:530855425201511551045378554>55755312410242035201510528725212044451015411032:73135216561321012171017101725313581125152572531358122415257257110213310131231422022172025105110315322103210623815203110113053521053223817506920721013361322282530991062101213361322282520491049682224133614121028101510291029;812341023342835694810582018841018356978194810842835193329781019482410542835192310193668399428454319362928102829843845331019263028101330441014382035104369285338101810284536334910291018534820283546891019102943883536";
int red e>>16;}
int blue e>>8;}
int green e;}

Created an array z which stores all of the possible colours as a single integer.(r<<16 | g<<8 | b). Created an array d which stores {amount, value}, the value is the position in the array z, the amount is the number of consecutive pixels with that value.(i.e 3,0, means colout t[0] appears the next 3 pixels. The actual array of pixels(c) is then calculated every time red is called. The value in the array is then right shifted and ANDed as necessary to get the correct component.

I could probably save a few more characters(~50) by taking more patterns out of the array as defines.

Edit 1 - changed the d array for a char array with each value offset by 48, which means I can represent it as a string saving a load of commas.

Edit 2 - Took a larger portion of the functions out in the define statement.

share|improve this answer
    
Why don't you use C? In C, it is possible to remove the type-name from a declaratrion if it is int (so int f(int x,int y) becomes f(x,y). –  FUZxxl Mar 22 '12 at 10:08
    
@FUzxxl, yes C will almost always be shorter than C++ but I don't really use C on a day to day basis and don't really know all of it's nuances that can be used to reduce the length. I'm not bothered by trying to win anyway, I just try to beat any other C++ answers. –  Bunnit Mar 22 '12 at 18:08
add comment

C++, 1357 chars

int i,j,C[]={0,0,0,106,249,140,186,71,71,76,97,88,87,118,195,122,80,207,43,82,64,96,52,107,237,152,52,118,78,78},E[]={30,31,112,33,22,33,72,61,52,44,53,22,33,10,62,51,32,10,12,14,10,34,53,10,12,33,72,21,72,64,33,10,32,33,42,10,25,21,22,94,92,33,32,10,35,21,12,24,10,36,14,10,14,82,10,42,55,26,21,24,10,14,16,10,16,14,10,24,12,10,22,10,32,10,15,10,15,10,45,26,21,10,34,36,10,34,72,65,10,35,26,25,10,74,41,105,30,85,54,25,20,15,11,55,10,45,37,85,54,145,57,55,31,24,10,24,20,35,20,15,10,52,87,25,21,20,44,45,10,15,41,10,32,107,31,35,21,65,61,32,10,12,17,10,17,10,17,25,31,35,81,12,51,52,57,25,31,35,81,22,41,52,57,25,71,10,21,33,10,13,12,31,42,20,22,17,20,25,10,51,10,31,53,22,10,32,10,62,38,15,20,31,10,11,30,53,52,10,53,22,38,17,50,69,20,72,10,13,36,13,22,28,25,30,99,10,62,10,12,13,36,13,22,28,25,20,49,10,49,68,22,24,13,36,14,12,10,28,10,15,10,29,10,29,118,12,34,10,23,34,28,35,69,48,10,58,20,18,84,10,18,35,69,78,19,48,10,84,28,35,19,33,29,78,10,19,48,24,10,54,28,35,19,23,10,19,36,68,39,94,28,45,43,19,36,29,28,10,28,29,84,38,45,33,10,19,26,30,28,10,13,30,44,10,14,38,20,35,10,43,69,28,53,38,10,18,10,28,45,36,33,49,10,29,10,18,53,48,20,28,35,46,89,10,19,10,29,43,88,35,36,10};int*Q(int n){for(i=0;1;i++){for(j=0;j<E[i]/10;j++){if(!n)return&C[E[i]%10*3];n--;}}}
#define red(x,y) Q(x+32*y)[0]
#define blue(x,y) Q(x+32*y)[1]
#define green(x,y) Q(x+32*y)[2]

Deobfuscated a bit:

int C[]={0,0,0,106,249,140,186,71,71,76,97,88,87,118,195,122,80,207,43,82,64,96,52,107,237,152,52,118,78,78},
int E[]={30,31,112,33,22,33,72,61,52,44,53,22,33,10,62,51,32,10,12,14,10,34,53,10,12,33,72,21,72,64,33,10,32,33,42,10,25,21,22,94,92,33,32,10,35,21,12,24,10,36,14,10,14,82,10,42,55,26,21,24,10,14,16,10,16,14,10,24,12,10,22,10,32,10,15,10,15,10,45,26,21,10,34,36,10,34,72,65,10,35,26,25,10,74,41,105,30,85,54,25,20,15,11,55,10,45,37,85,54,145,57,55,31,24,10,24,20,35,20,15,10,52,87,25,21,20,44,45,10,15,41,10,32,107,31,35,21,65,61,32,10,12,17,10,17,10,17,25,31,35,81,12,51,52,57,25,31,35,81,22,41,52,57,25,71,10,21,33,10,13,12,31,42,20,22,17,20,25,10,51,10,31,53,22,10,32,10,62,38,15,20,31,10,11,30,53,52,10,53,22,38,17,50,69,20,72,10,13,36,13,22,28,25,30,99,10,62,10,12,13,36,13,22,28,25,20,49,10,49,68,22,24,13,36,14,12,10,28,10,15,10,29,10,29,118,12,34,10,23,34,28,35,69,48,10,58,20,18,84,10,18,35,69,78,19,48,10,84,28,35,19,33,29,78,10,19,48,24,10,54,28,35,19,23,10,19,36,68,39,94,28,45,43,19,36,29,28,10,28,29,84,38,45,33,10,19,26,30,28,10,13,30,44,10,14,38,20,35,10,43,69,28,53,38,10,18,10,28,45,36,33,49,10,29,10,18,53,48,20,28,35,46,89,10,19,10,29,43,88,35,36,10};
int*Q(int n){
  for(int i=0;1;i++){
    for(int j=0;j<E[i]/10;j++){
      if(!n)return&C[E[i]%10*3];
      n--;
    }
  }
}
#define red(x,y) Q(x+32*y)[0]
#define blue(x,y) Q(x+32*y)[1]
#define green(x,y) Q(x+32*y)[2]

C contains the RGB values for the ten distinct colors of the image. E contains the data for the picture, where each element E[i] encodes both a repeat count E[i]/10 and a color index E[i]%10.

share|improve this answer
    
+1 You could shave a few characters off in the loop: pastebin.com/2UY8H2qt –  Pubby Mar 19 '12 at 6:17
    
If you rebrand your solution as C (no code changes required) and turn the define's into functions whithout type names like int red(x,y){R Q(x+32*y)[0]}(only #define` return), then you might be able to shave of more characters. –  FUZxxl Mar 19 '12 at 19:59
    
Somehow, this is cheating, since red, blue and green are not functions but macros. –  FUZxxl Mar 19 '12 at 20:03
    
This implements a function and is shorter (1339 bytes). Please notice, that this program is probably only valid in plain old C: hpaste.org/65584 –  FUZxxl Mar 19 '12 at 20:10
    
I removed all type information from the source. It is still valid C. –  FUZxxl Mar 19 '12 at 20:16
add comment

Javascript, 696 694 chars

Thanks to schnaader for 696 -> 694.

I figured a different encoding format, which essentially is Run-length encoding with a color lookup table. It works quite nice, because there are less than 16 colors and they apear less that 16 times in a row; so every pixel definition including length fits into one byte. I put the color in the high part of the byte and the count in the low part.

In the end, the base64 string turned out to be longer than I had expected (472 chars), but the decoding program is really short.

for(b=i=a=[];a&15||(a=atob("AxMrMyIzJxYlRDUiMwEmFSMBIUEBQzUBITMnEidGMwEjMyQBUhIi
SSkzIwFTEiFCAWNBAUEoASRVYhJCAUFhAWFBAUIhASIBIwFRAVEBVGISAUNjAUMnVgFTYlIBRxRaA1hF
UgJREVUBVHNYRV51VRNCAUICUwJRASV4UhICRFQBURQBI3oTUxJWFiMBIXEBcQFxUhNTGCEVJXVSE1MY
IhQldVIXARIzATEhEyQCInECUgEVARM1IgEjASaDUQITAREDNSUBNSKDcQWWAicBMWMxIoJSA5kBJgEh
MWMxIoJSApQBlIYiQjFjQSEBggFRAZIBkoshQwEyQ4JTloQBhQKBSAGBU5aHkYQBSIJTkTOShwGRhEIB
RYJTkTIBkWOGk0mCVDSRY5KCAYKSSINUMwGRYgOCATEDRAFBgwJTATSWgjWDAYEBglRjM5QBkgGBNYQC
glNkmAGRAZI0iFNjAQ==").charCodeAt(i++));b.push([0,16354410,4671418,6379596,77832
55,5295994,5390379,3435360,9975021,5131894][a-- >>4]));green=(red=function(c,d){
return b[32*d+c]>>this&255}).bind(16);blue=red.bind(8)

Note: I split up the code to have a little readability. It needs to be on one line to run.

Test code:

for(var y = 0; y < 32; ++y) {
    for(var x = 0; x < 32; ++x) {
        console.log(red(x, y), green(x, y), blue(x, y));
    }
}

I think the example result is actually the output of red, green, blue (not red, blue, green like in the original test code); it works for me like that anyway.

share|improve this answer
    
Try to change the palette array to [0,16354410,4671418,6379596,7783255,5295994,5390379,3435360,9975021,5131894] - this saves 1 character and is GBR order instead of RGB. –  schnaader Mar 22 '12 at 19:06
    
@schnaader Thanks. I love those micro-optimizations :-) Edit: It even saved 2 chars because I used blue two times in my orignial source –  copy Mar 22 '12 at 19:41
add comment

Python 3 (589 characters)

import base64,zlib
red,blue,green=(lambda x,y,i=i:b'\xed\x984+R@j\xf9\x8cWv\xc3`4k\0\0\0\xbaGGzP\xcfvNNLaX'[zlib.decompress(base64.decodebytes(b'eJxtkgGSxSAIQxWN1vtfeEkEbf9sOmMdn0EEAZjZuFprxSCZpGlzrZUcL+5/jIbk+Phj0lr4MU58zEneUt8kiMlbQ63VwyfV0ZOq1cxxqyBvJJCRX3Cm5X7c+LJqQ63+j8N5kXkEIKeiXJl2jLP3/sPf6j257QSbwvmwy9ZD5ED6wd2GF+99J5WZ2S13h39aOetObrdO/A8f/3AdasbWrBEYnkVnzkhs0XpkA8YopUw9H/glEJw4ps49huuRgOzf8n6Iq85PCtneDxfhUCQ+F3JvdileT8FyxdfkCfhI+9yRCSAMlHxt+HLX3pd8+/0mh0MT9fPF8Xg6EeB52sc+WQlyxgA3XJycfi+D84X9GNCUKZ+E/JGjyqqbYJtZpo1ZhsN5ybJxPbXlluSlJMcf++8TIA=='))[32*y+x]*3+i]for i in(0,1,2))

Test code

for y in range(32):
    for x in range(32):
        print(red(x,y), blue(x,y), green(x,y))

Based on solution from Dillon Cower

share|improve this answer
add comment

PHP (5.4) - 822

I've done this deliberately not using any of the built-in compression functions. This solution is not finished, I'm not sure if I've given up, I can see areas for improvement but I can't find the time/willpower to refactor the whole thing at the moment, so I'm posting what I have so far.

Newlines + comments to be removed for 822 bytes.

// Colour map
$c=[0,16354410,4671418,6379596,7783255,5295994,5390379,3435360,9975021,5131894];

// Optimised RLE map
$r=array_merge(array_diff(range(10,89),[27,40,47,56,59,60,63,66,67,70,73,75,76,77,79,80,83,86]),[92,94,99,105,107,112,118,145]);

// Image data (base 70)
$e="CDsF<Fd]WPX<F0^VE0240GX02Fd;d_F0EFN0?;<onFE0H;2>0I404h0NZ@;>0460640>20<0E05050Q@;0GI0Gd`0H@?0eMqCjY?:51Z0QJjYu[ZD>0>:H:50Wk?;:PQ05M0ErDH;`]E0270707?DHg2VW[?DHg<MW[?c0;F032DN:<7:?0V0DX<0E0^K5:D01CXW0X<K7Ub:d03I3<A?Cp0^023I3<A?:T0Ta<>3I420A050B0Bt2G0=GAHbS0\:8i08Hbf9S0iAH9FBf09S>0YAH9=09IaLoAQO9IBA0ABiKQF09@CA03CP04K:H0ObAXK080AQIFT0B08XS:AHRm090BOlHI0";

// Expand image data
for($i=0;$i<352;$i++){$b=$r[ord($e[$i])-48];$l=(int)($b/10);while($l--)$d[]=$c[$b%10];}

// Colour retrieval functions
function red($x,$y){global$d;return$d[$x+$y*32]&0xff;}
function green($x,$y){global$d;return$d[$x+$y*32]>>8;}
function blue($x,$y){global$d;return($d[$x+$y*32]>>8)&0xff;}

Test stub:

for ($y=0;$y<32;$y++) {
    for ($x=0;$x<32;$x++) {
        printf("%d %d %d\n", red($x, $y), blue($x, $y), green($x, $y));
    }
}

The compression of the image data itself is pretty good, but the functions to retrieve RGB values take up 1/4 of the code.

I'm using a custom base70 + run length encoding mechanism.

  1. There are 10 unique colours
  2. Colours have run lengths between 1 and 14 (12 used).
  3. There are 120 possible combinations.
  4. There are only 70 unique run/colour combinations actually used.

The encoded image data references the array index of an RLE, which in turn indexes the array of colours. I'm not sure how much overhead this adds or subtracts over directly referencing the colours.

Sine there are 10 colours (0 to 9), RLEs are stored as run_length * 10 + colour_index. Giving a range of encodings between 10 and 145 without experimenting with optimisations based on colour ordering. (i.e. I could make the range 19 to 140 by moving colours 0 to 5, 5 to 9, and 9 to 0 - but this may have other knock-on effects)

A previous answer states their encoded data is 472 bytes. My encoded image data is 352 bytes, but the intermediate RLE / colour map (which is not binary encoded) is a further 129 bytes, putting the total at 481. (as well as additional overhead for joining up the two). However I suspect my method might scale better for larger images.

TODO:

  1. Investigate binary encoding of RLE map
  2. Find a way of reducing the size of the functions. global is a bitch, but can't access character indexes on constants.
  3. Experiment with colour index ordering to see if RLE map size can be reduced with longer sequential runs of numbers
  4. Potential 64bit specific optimisations of colour map? (r0 << 56 | r1 << 48 | ...)?
  5. Experiment with vertical RLE to see if it results in a more compact set of encodings.
  6. Area encoding?
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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