Ee9108fb0f4a69c57042c47afa0d18ac

How to make this shorter ?

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 !

A0c394e31c9740376635c8878cf5889e

dave parker

September 27, 2007, September 27, 2007 23:52, permalink

No rating. Login to rate!

It's not C. It's not a loop. In fact, it's not even code. It is ASCII, I believe.

Avatar

bob

September 27, 2007, September 27, 2007 23:59, permalink

No rating. Login to rate!

har dee har har

Avatar

tj

September 28, 2007, September 28, 2007 00:32, permalink

No rating. Login to rate!

on your way to IOCCC eh?

E116f82ebbf866168f363b66a54cd486

Kuroki Kaze

September 28, 2007, September 28, 2007 02:48, permalink

No rating. Login to rate!

this is what you call a "Simple loop" ? ;):):)

7dad18e6e49e447a8a0eb7fb5ae66cbb

chris

September 28, 2007, September 28, 2007 02:55, permalink

No rating. Login to rate!
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);}
22ca8e11d07e6333c5ce7a414d905dfc

Bisqwit

September 28, 2007, September 28, 2007 04:20, permalink

1 rating. Login to rate!

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;
}
Ee9108fb0f4a69c57042c47afa0d18ac

Andy Sloane

September 28, 2007, September 28, 2007 23:06, permalink

No rating. Login to rate!

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);}
48c7113cf6a39b7cd9c590fa1835e3fa

tmiz

September 29, 2007, September 29, 2007 07:11, permalink

1 rating. Login to rate!

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);
    }
}
22ca8e11d07e6333c5ce7a414d905dfc

Bisqwit

September 29, 2007, September 29, 2007 09:16, permalink

1 rating. Login to rate!

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;}}  
22ca8e11d07e6333c5ce7a414d905dfc

Bisqwit

September 29, 2007, September 29, 2007 12:37, permalink

1 rating. Login to rate!

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

Andy Sloane

September 29, 2007, September 29, 2007 14:30, permalink

No rating. Login to rate!

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.

22ca8e11d07e6333c5ce7a414d905dfc

Bisqwit

September 29, 2007, September 29, 2007 17:29, permalink

No rating. Login to rate!

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.

D9a391fd7af75d6d43a2694865f7326f

msdos464

October 1, 2007, October 01, 2007 06:51, permalink

No rating. Login to rate!

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:
 __  __  _______ ___    ___   _______ _     _____   __     
|  \/  |/      /    \  /   \ /      / /    /  __/  / /     
|      /    __/ |    \/     /    __/ /__/|_| |____/ /__/|_ 
| |\/| \____  \ | |     |   \____  \___   _   _   ___   _/ 
| |  | |      / |    /\     /      /   | | | |_| |   | |   
|_|  |_______/  |___/  \___/______/    |_| \_____/   |_|   

***/
Ee9108fb0f4a69c57042c47afa0d18ac

Andy Sloane

October 2, 2007, October 02, 2007 07:00, permalink

No rating. Login to rate!

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))
22ca8e11d07e6333c5ce7a414d905dfc

Bisqwit

November 5, 2007, November 05, 2007 13:41, permalink

No rating. Login to rate!

Oh, the IOCCC 2006 winner Andy Sloane? No wonder then :P

Your refactoring





Format Copy from initial code

or Cancel