1 2 3 4 5
_=0;c(q){q<0?putchar("`',)( \n-\\_/"[q+11]):c(("#" "CB#_,ab:@BbBXb\\bG]N_2JNH4`X:.MRLA,aA(J`)BFRTBRL" "'####_SJ[0RJbb\\R]N=5,64XMMR976Hb\\QLARZ[O-TZ[RT" "<RTJZ\\5#`R,"[_/6]-35>>_++%6&1?"Y_Zdfghbak":"X\\" "c[e^`ij]")[q]-99);}main(){while(_<629)c(9);}
Refactorings
No refactoring yet !
dave parker
September 27, 2007, September 27, 2007 23:52, permalink
It's not C. It's not a loop. In fact, it's not even code. It is ASCII, I believe.
Kuroki Kaze
September 28, 2007, September 28, 2007 02:48, permalink
this is what you call a "Simple loop" ? ;):):)
chris
September 28, 2007, September 28, 2007 02:55, permalink
1 2 3 4 5
_=0;c(q){q<0?putchar("`',)( \n-\\_/"[q+11]):c(("#" "CB#_,ab:@BbBXb\\bG]N_2JNH4`X:.MRLA,aA(J`)BFRTBRL" "'####_SJ[0RJbb\\R]N=5,64XMMR976Hb\\QLARZ[O-TZ[RT" "<RTJZ\\5#`R,"[_/6]-35>>_++%6&1?"Y_Zdfghbak":"X\\" "c[e^`ij]")[q]-99);}main(){while(_<629)c(9);}
Bisqwit
September 28, 2007, September 28, 2007 04:20, permalink
Your code is not portable. Under Cygwin, it produces just a string of backslashes.
I suggest this version. It is a lot better documented, and also runs faster.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
#include <stdio.h> int main(void) { /* The string to output. * Note: backslashes have been replaced with pipe characters * to preseve formatting in the source code. They will be * transformed back upon program run. */ const char*s = " ___ __\n" " _______ / _/__ _____/ /____ ____\n" " / __/ -_) _/ _ `/ __/ __/ _ |/ __/\n" "/_/ |__/_/ |_,_/|__/|__/|___/_/\n" "\n" " __ __\n" " __ _ __ __ _______ ___/ /__ / /\n" " / ' |/ // / / __/ _ |/ _ / -_)_/\n" "/_/_/_/|_, / |__/|___/|_,_/|__(_)\n" " /___/\n"; /* For each character in the string */ for(; *s; ++s) { /* Output a backslash in place of pipe, * otherwise the character. */ putchar(*s == '|' ? '\\' : *s); } /* Successful exit */ return 0; }
Andy Sloane
September 28, 2007, September 28, 2007 23:06, permalink
dave parker: It is C, and it is a loop. A while loop that calls a function which recurses up to nine times.
tj: Be sure to check the results when the winners are revealed in November. :P
Bisquit: It's strange that you say it isn't portable to Cygwin, since I developed it under Cygwin. What version of cygwin/gcc? Mine says "gcc version 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)"
Seriously now, I am trying to make it shorter. I'm sure the Kolmogorov complexity for the language C of that string is less than what I've got. Doesn't anyone care about algorithmic information theory?
Adjusting the encoding to eliminate \\ obviously helps.
1 2 3 4
_=0;c(q){q<0?putchar("`',)( \n-\\_/"[q+11]):c(("!A@!]*_`8>@" "`@V`Z`E[L]0HLF2^V8,KPJ?*_?&H^'@DPR@PJ%!!!!]QHY.PH``ZP[L;3*" "42VKKP754F`ZOJ?PXYM+RXYPR:PRHXZ3!^P*"[_/6]-33>>_++%6&1?"FL" "GQSTUONX":"EIPHRKMVWJ")[q]-80);}main(){while(_<629)c(9);}
tmiz
September 29, 2007, September 29, 2007 07:11, permalink
I changed it for the almost same semantics.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
int k=0; const char *const LITERAL_1 = "#CB#_,ab:@BbBXb\\bG]N_2JNH4`X:.MRLA," "aA(J`)BFRTBRL'####_SJ[0RJbb\\R]N=5,6" "4XMMR976Hb\\QLARZ[O-TZ[RT<RTJZ\\5#`R,"; const char *const LITERAL_2 = "Y_Zdfghbak"; const char *const LITERAL_3 = "X\\c[e^`ij]"; const char *const LITERAL_4 = "`',)( \n-\\_/"; int func(int q) { int a; int y = k / 6; int x = k % 6; k++; if ((LITERAL_1[y] - 35 >> x) & 1) { a = LITERAL_2[q]; } else { a = LITERAL_3[q]; } return a - 99; } void func2(int q){ if (q < 0) { putchar(LITERAL_4[q+11]); } else { func2(func(q)); } } main() { while(k < 629){ func2(9); } }
Bisqwit
September 29, 2007, September 29, 2007 09:16, permalink
I must admit that I'm not very good at this.
1 2 3 4 5
char*a="%c\0 \0_/\\_\0__\0/ /\0/ _ \\/ ",*f,c,n,*q="e5 m1_e4 m1\ne1m3_ / " "_/m1 m2_p1m2e1m2\n / m1/ -_) _/ _ `/ m1/ m1t1m1/\n/_/e1\\m1/_/ \\_,h3m1/_" "/\n\ne>m1e2m1\ne1m1 _e1m1 m1e1m3_e1m1_p1m1 p1\n /e1' \\p2 / m1t1_e1/ -_)_" "/\n/_/_/h1, /e1\\_h1_h1,h1_(_)\ne3/m1_/\n";main(){while(*q){c=n=1;f=a;if(* q>'a'){f+=*q-'b';c=q[n++]-'0';}while(c--)printf(f,*q);q+=n;}}
Bisqwit
September 29, 2007, September 29, 2007 12:37, permalink
Fail, again!
Oh, Cygwin version?
gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
Yes, this later version of yours seemed to work. I don't know why, it seems identical to me. Maybe it was a copy&paste issue.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
#define tw(a,b) a(),b() #define twd(a,b,c) a(){tw(b,c);} #define ptd(a,b,s,d) a(){b;printf(s);d;} #define xd(a,b,c,d,e,f) twd(a,b,c)twd(d,e,f) ptd(a,," ",)twd(d,a,a)ptd(r,," /",a())ptd(h,,"\\_,",)ptd(w,," _",) ptd(b,,"__",)twd(i,a,b)ptd(k,b(),"\n",)ptd(m,tw(b,b),"_",) ptd(c,,"/ ",)twd(j,d,d)ptd(n,c(),"/",)ptd(g,(tw(c,b),c()),"_ \\",c()) ptd(e,,"\\",b())ptd(o,e(),"/",)ptd(p,c(),"-_)",)ptd(u,," ",c()) ptd(f,,"_/",)ptd(l,f(),"\n",)ptd(x,,"/",f())ptd(s,," ",b()) ptd(q,tw(o,e),"",f())twd(t,k,i)ptd(v,b()," ",)xd(y,h,f,z,j,a) twd(A,z,s)ptd(B,A(),"_",) twd(C,B,j)ptd(D,C()," ",) xd(E,D,t,F,E,m)xd(G,F,u,H,G,f)xd(I,H,v,J,I,m)xd(K,J,n,L,K,b) xd(M,L,b,N,M,i)xd(O,N,k,P,O,u)xd(Q,P,b,R,Q,p)xd(S,R,w,T,S,c) ptd(U,T(),"_",) ptd(V,U()," ",) ptd(W,V(),"`",) xd(X,W,c,Y,X,b)twd(Z,Y,g) main() { tw(Z,b);printf("/\n");tw(x,a); o(); printf("_"); tw(c,y); tw(o,q); l(); printf("\n"); tw(j,j); tw(j,d); tw(b,d); tw(t,w); tw(i,s); tw(i,m); i(); printf("_"); tw(n,v); n(); printf("\n"); r(); printf("' \\"); tw(n,c); tw(c,g); printf("_"); tw(a,p); tw(l,x); tw(f,f); tw(h,r); tw(q,y); e(); printf("(_)\n"); tw(d,a); printf("/"); tw(b,l); }
Andy Sloane
September 29, 2007, September 29, 2007 14:30, permalink
Heheh, very nice. The first one looks like a RLE encoding of substrings, and there is probably merit to this approach... The second one looks more like an IOCCC winner.
My version is just straight-up Huffman minimum redundancy coding and quasi-base64 bit encoding. tmiz's LITERAL_2 and 3 form the Huffman tree. I have a version that outputs pairs of strings to encode 13 bits across two characters, which is only shorter than the 6-bits-per-character version if the output string is long enough, and this one isn't.
Bisqwit
September 29, 2007, September 29, 2007 17:29, permalink
I noticed the base64'ish part and thought of trying it myself, but just base64 without other features wouldn't beat yours. The reduction would be too small. I also noticed the huffman encoding, though I didn't believe it until I read tmiz's version and noticed that it indeed may call func2() recursively (more than two recursions). Quite impressive.
My second version is a variant of the substring encoding. In this version, each substring is transformed into a function, and the resulting string is compiled into a sequence of function calls and prints. I pondered if I can make a short version from that using function pointer tables and stuff like that, but I think it'll still be much too large.
The substring table generation is a rather naïve algorithm that just searches for the biggest saving with brute force, repeating until no improvement can be found. The RLE part was a moment's idea, but I think the conditional RLE decoder produced more overhead than the coding saved.
msdos464
October 1, 2007, October 01, 2007 06:51, permalink
This doesn't have the same output, but I wanted to show this code to someone :D Quite simple RLE.. Not even any recursion.
ASCII graphics is still bit ugly :/ well atleast code is rather short. I'm not sure if those characters will encode correctly on other platforms etc.
3 bits of space count, 2 bits of character data, 3 bits of character count
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
#include <stdio.h> #define p(a) putchar(a); int main(void){unsigned char*s="Zz[»ŸYÚÑi!q!á©a‰AáA¡z!aAÑáº!Q©!ú!A:!19" "1Q<!A:!19QQ)!1I<iQQщ<i;™™›™!QQqQáQ¡)Ãá‘QQQ91Q‘Q‘91q?!q;!i;!>!±91I=!‘91", m=0,i,t,*c="/\\|_";while(*s){t=*s++-32;for(i=0;i<t>>5;i++,m++)p(' ')for(i= 0;i<(t&7);m++,i++){if(!(m%59))p('\n'^(m=0))p(c[(t>>3)&3])}}return 0;} /*** output: __ __ _______ ___ ___ _______ _ _____ __ | \/ |/ / \ / \ / / / / __/ / / | / __/ | \/ / __/ /__/|_| |____/ /__/|_ | |\/| \____ \ | | | \____ \___ _ _ ___ _/ | | | | / | /\ / / | | | |_| | | | |_| |_______/ |___/ \___/______/ |_| \_____/ |_| ***/
Andy Sloane
October 2, 2007, October 02, 2007 07:00, permalink
Yeah, those characters don't paste cleanly, so I get corrupted output. There are a bunch of tricks you still have available if you want to make that shorter; for instance, you can eliminate some braces by replacing your if statement with a conditional. I like your ^(m=0) idea though.
My Huffman compressor is a little bit shorter on that. That's the funny thing about Kolmogorov complexity... obviously, the encoded string would be shorter with RLE, but a) the code to perform the RLE takes up more space than the encoding saves if the string is short enough and b) RLE adds more infrequent codes, so using minimum redundancy coding (like Huffman or arithmetic coding) on the result may actually be bigger than not doing the RLE. That's why it's so hard to determine what's the smallest way to encode a given string.
The other thing is that I encode the newlines explicitly, which makes decompressor simpler at the expense of a very slightly larger compressed string.
More obfuscated while loop
1 2 3
while(*s){t=*s++-32;for(i=0;i<t>>5;i++,m++)p(' ')for(i= 0;i<(t&7);m++,i++)putchar(m%59?c[3&t>>3]:'\n'^(m=0));}return 0;}
My Huffman version
1 2 3 4
_=0;c(q){q<0?putchar(" /\n\\|_"[q+6]):c(("??_`X0]D``.Y`R8#VGU!.5J26$U;IZ<;>*" "!.]N!V'UQX[PT2_PV@H,2K>5`HK)AA[`5`R9]D\\3%C!U#U61$U)C)(\"2+Z1_`P*`.V`_`PB=5" "``'Z5!"[_/6]-33>>_++%6&1?"MKQOS":"LPNRJ")[q]-80);}main(){while(_<673)c(4);}
Huffman compressor source
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
-- Here's the source to the Huffman compressor that generates the above. It's written in Lua. verbose = true local max_asciibase = 80 ascii_base = 33 -- can range from 32..35; encodes actual image data, 91 chars wide function vprint(...) if verbose then print(unpack(arg)) end end function make_cstring(str) local s = string.format("%q", str) s = string.gsub(s, "["..string.char(127).."-"..string.char(255).."]", function(c) return string.format("\\x%02x",string.byte(c)) end) return string.gsub(s, "\n", "n") end function schar(x) assert(x>=32, "trying to encode ASCII "..x) assert(x<=255, "trying to encode ASCII "..x) return string.char(x) end function walk_tree(hufftbl,codelen,codes,node,depth,bits) if hufftbl[node].code then codes[hufftbl[node].code] = bits codelen[hufftbl[node].code] = depth else walk_tree(hufftbl,codelen,codes,hufftbl[node].l, depth+1, bits..'0') walk_tree(hufftbl,codelen,codes,hufftbl[node].r, depth+1, bits..'1') end return codes,codelen end function min_weight(hufftree) local min1,min2 for i,v in ipairs(hufftree) do if v.weight then if not min1 then min1=i elseif v.weight < hufftree[min1].weight then min2=min1 min1=i elseif not min2 then min2 = i elseif v.weight < hufftree[min2].weight then min2=i end end end return min1,min2 end function build_tree(freq) local hufftree = {} for k,v in pairs(freq) do if k ~= "total" then table.insert(hufftree, {code=k, weight=v}) end end local treebase=table.getn(hufftree) vprint(table.getn(hufftree)..' total unique codes') while true do local n1,n2 = min_weight(hufftree) if not n1 or not n2 then vprint(table.getn(hufftree)..' total tree nodes') return hufftree,treebase end table.insert(hufftree, {l=n1,r=n2,weight=hufftree[n1].weight+hufftree[n2].weight}) hufftree[n1].weight = nil hufftree[n2].weight = nil end -- not reached end function inc_freq(symbolbuf,freq,k) freq[k] = (freq[k] or 0)+1 table.insert(symbolbuf,k) freq.total = (freq.total or 0) + 1 end function add_bit(codebuf, bit) codebuf.n = codebuf.n or 1 codebuf.b = (codebuf.b or 0) codebuf.x = (bit*(2^codebuf.b))+(codebuf.x or 0) codebuf.b = codebuf.b + 1 if(codebuf.b >= 6) then --vprint('ok: '..codebuf[codebuf.n]) codebuf.lo = codebuf.lo or {} codebuf.lo[codebuf.n] = schar(ascii_base+codebuf.x,91) codebuf.n = codebuf.n+1 codebuf.b = 0 codebuf.x = 0 end end function flush_bits(codebuf) codebuf.totalbits = (codebuf.n-1)*6+codebuf.b while codebuf.b ~= 0 do add_bit(codebuf,0) end codebuf.n=nil end function add_code(codebuf, code) --vprint('code: '..code) for i=1,string.len(code) do add_bit(codebuf,tonumber(string.sub(code,i,i))) end end function read_stdin() local image = {} local freq = {},{} for line in io.lines() do line = string.gsub(line, "%s*$", "") -- strip trailing space for i=1,string.len(line) do inc_freq(image, freq, string.sub(line,i,i)) end inc_freq(image, freq, "\n") end return image,freq end image,cfreq = read_stdin() vprint(cfreq.total..' total char codes') function calculate_entropy(freqtbl) local entropy = 0 local total = freqtbl.total freqtbl.total = nil for k,v in pairs(freqtbl) do local bits = -v*math.log(v/total)/math.log(2) entropy = entropy + bits local kk=k if(type(k) == "string") then kk=make_cstring(k) end vprint(kk,v,bits) end freqtbl.total = total return entropy end centropy = calculate_entropy(cfreq) vprint('entropy(chars) = '..centropy) function build_hufftree(freq) local hufftbl,treebase = build_tree(freq) local asciibase -- to encode the tree nodes into a C string, we split it up into the actual -- tree nodes, which are all the 'states' above <treebase>, and the actual -- codes, which are states 0..<treebase>. if treebase < (max_asciibase-32) then asciibase = max_asciibase else asciibase = 32+treebase end local hufftree_upperlimit = table.getn(hufftbl) + asciibase vprint('huffman tree node coding space: 32 - '..hufftree_upperlimit) if hufftree_upperlimit > 255 then error('Image too complex to do this in single-byte format...') end treeroot = table.getn(hufftbl)-1 codes,codelen = walk_tree(hufftbl,{},{},table.getn(hufftbl),0,"") hufflen=0 for k,v in pairs(codelen) do hufflen = hufflen + v*freq[k] local kk=k if(type(k) == "string") then kk=make_cstring(k) end vprint("code "..kk..": len "..v.." code "..codes[k].."\t\t"..v*freq[k]) end return hufftbl,asciibase,treebase,hufflen,codes end chufftbl,casciibase,ctreebase,chufflen,ccodes = build_hufftree(cfreq) vprint("total hufflen(chars): "..hufflen..', '..chufflen-centropy..' bits from optimal.') function build_codetables(hufftbl, treebase, tree_asciibase, code_asciibase) l,r,c = {},{},{} for i,v in ipairs(hufftbl) do if v.l then --vprint('l='..v.l..' r='..v.r) table.insert(l, schar(v.l-1+tree_asciibase-treebase)) table.insert(r, schar(v.r-1+tree_asciibase-treebase)) else local code = v.code if type(code) == "string" then code=string.byte(code) end table.insert(c, string.char(code+code_asciibase)) end end return l,r,c end cl,cr,cc = build_codetables(chufftbl, ctreebase, casciibase, 0) croot = table.getn(chufftbl)-1-ctreebase vprint('char root: '..croot) vprint('char base: '..ctreebase) vprint("char l: "..make_cstring(table.concat(cl))..'[q]-'..casciibase) vprint("char r: "..make_cstring(table.concat(cr))..'[q]-'..casciibase) vprint("char c: "..make_cstring(table.concat(cc))..'[q]') vprint("total coding bytes: "..math.ceil(chufflen/6)+table.getn(cl)+table.getn(cr)+table.getn(cc)) imagebuf = {} for i,v in ipairs(image) do add_code(imagebuf, ccodes[v]) end flush_bits(imagebuf) vprint("imagelo: "..make_cstring( table.concat(imagebuf.lo))) vprint(imagebuf.totalbits..' total bits in image') vprint("here's the code:\n\n") print(string.format([[_=0;c(q){q<0?putchar(%s[q+%d]):c((%s [_/6]-%d>>_++%%6&1?%s:%s)[q]-%d);}main(){while(_<%d)c(%d);}]], make_cstring(table.concat(cc)), ctreebase, make_cstring(table.concat(imagebuf.lo)), ascii_base, make_cstring(table.concat(cr)), make_cstring(table.concat(cl)), casciibase, imagebuf.totalbits, croot))
Bisqwit
November 5, 2007, November 05, 2007 13:41, permalink
Oh, the IOCCC 2006 winner Andy Sloane? No wonder then :P
ganesh
January 20, 2009, January 20, 2009 07:32, permalink
#include <stdio.h>
int main(void)
{
/* The string to output.
* Note: backslashes have been replaced with pipe characters
* to preseve formatting in the source code. They will be
* transformed back upon program run.
*/
const char*s =
" ___ __\n"
" _______ / _/__ _____/ /____ ____\n"
" / __/ -_) _/ _ `/ __/ __/ _ |/ __/\n"
"/_/ |__/_/ |_,_/|__/|__/|___/_/\n"
"\n"
" __ __\n"
" __ _ __ __ _______ ___/ /__ / /\n"
" / ' |/ // / / __/ _ |/ _ / -_)_/\n"
"/_/_/_/|_, / |__/|___/|_,_/|__(_)\n"
" /___/\n";
/* For each character in the string */
for(; *s; ++s)
{
/* Output a backslash in place of pipe,
* otherwise the character. */
putchar(*s == '|' ? '\\' : *s);
}
/* Successful exit */
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
#include <stdio.h> int main(void) { /* The string to output. * Note: backslashes have been replaced with pipe characters * to preseve formatting in the source code. They will be * transformed back upon program run. */ const char*s = " ___ __\n" " _______ / _/__ _____/ /____ ____\n" " / __/ -_) _/ _ `/ __/ __/ _ |/ __/\n" "/_/ |__/_/ |_,_/|__/|__/|___/_/\n" "\n" " __ __\n" " __ _ __ __ _______ ___/ /__ / /\n" " / ' |/ // / / __/ _ |/ _ / -_)_/\n" "/_/_/_/|_, / |__/|___/|_,_/|__(_)\n" " /___/\n"; /* For each character in the string */ for(; *s; ++s) { /* Output a backslash in place of pipe, * otherwise the character. */ putchar(*s == '|' ? '\\' : *s); } /* Successful exit */ return 0; }
How to make this shorter ?