title: Smallest Javascript CSS Selector Engine

text:
# Question
Title: Smallest Javascript CSS Selector Engine
Create a small acceptably efficient JS CSS selector engine.

Please post size of script, and function to call preferable $(selector,context) style.

EDIT: All major browsers support `document.querySelectorAll` which makes this question irrelevant.

# Answer
Funny, I just made one of these. It is quite efficient because it compiles selectors. I don't know if it's IE6-compatible but it should be, I think. It supports CSS3 too - bonus points? :)

```
if(![].indexOf)Array.prototype.indexOf=function(a,i){i=i||0;while(i<this.length)if(this[i++]===a)return i-1;return-1};
String.prototype.startsWith=function(s){return this.length>=s.length&&this.substring(0,s.length)===s};
String.prototype.endsWith=function(s){return this.length>=s.length&&this.substring(this.length-s.length)===s};

var Sprint = {
    Error: function(m) {
        this.message = m;
        this.toString = function() {
            return this.message;
        };
    },
    getAllElementsIn: function(element) {
        var r = [];
        var f = function recurse(l, arr) {
            from(l).each(function(k, v) {
                if(v.nodeType === 1) {
                    arr.push(v);
                    recurse(v, arr);
                }
            });
        };
        f(element, r);
        return r;
    },
    getAllElements: function() {
        return Sprint.getAllElementsIn(document.documentElement);
    },
    getSiblings: function(element) {
        return element.parentNode ? from(element.parentNode).where(function(k, v) { return v.nodeType === 1; }).toArray() : [element];
    },
    getInfo: function(selector) {
        var r = {ATTR: {}, CLASS: [], PSEUDO: []};

        var quotes = '\'"', nestable = '(){}', inAttribute = false, escaped = false, currentQuotes = null, currentNested = [], nonchar = /^[^a-zA-Z0-9_\-]$/, lastSplitter = null, i = -1, c, s = '';
        while(++i < selector.length) {
            c = selector.charAt(i);
            if(escaped) {
                escaped = false;
            } else if(c === '\\') {
                escaped = true;
                continue;
            } else if(currentQuotes) {
                if(currentQuotes === c) {
                    currentQuotes = null;
                }
            } else if(quotes.indexOf(c) > -1) {
                currentQuotes = c;
            } else if(currentNested.length) {
                if(nestable.indexOf(currentNested[currentNested.length - 1]) + 1 === nestable.indexOf(c)) {
                    currentNested.pop();
                }
            } else if(nestable.indexOf(c) > -1) {
                currentNested.push(c);
            } else if(nonchar.test(c)) {
                if(lastSplitter) {
                    switch(lastSplitter) {
                        case '#':
                            r.ID = s;
                            break;
                        case '.':
                            r.CLASS.push(s);
                            break;
                        case '[':
                        case ',':
                            if(inAttribute) {
                                var j;
                                if((j = s.indexOf('=')) > -1) {
                                    r.ATTR[s.substring(0, j)] = s.substring(j + 1);
                                } else {
                                    r.ATTR[s] = true;
                                }
                            }
                            break;
                        case ':':
                            r.PSEUDO.push(s);
                            break;
                    }
                } else {
                    r.TAG = s;
                }

                if(c === ']') {
                    inAttribute = false;
                } else if(c === '[') {
                    inAttribute = true;
                }

                lastSplitter = c;

                s = '';
                continue;
            }
            s += c;
        }

        if(lastSplitter) {
            switch(lastSplitter) {
                case '#':
                    r.ID = s;
                    break;
                case '.':
                    r.CLASS.push(s);
                    break;
                case '[':
                case ',':
                    if(inAttribute) {
                        var j;
                        if((j = s.indexOf('=')) > -1) {
                            r.ATTR[s.substring(0, j)] = s.substring(j + 1);
                        } else {
                            r.ATTR[s] = true;
                        }
                    }
                    break;
                case ':':
                    r.PSEUDO.push(s);
                    break;
            }
        } else {
            r.TAG = s;
        }

        return r;
    },
    compileSingle: function(info) {
        var f = 'var t=l.nodeName?l.nodeName.toLowerCase():"",i=l.id?l.id.toLowerCase():"",c=l.className?" "+l.className.toLowerCase()+" ":"",s=Sprint.getSiblings(l),ss=from(s).where(function(k,v){return v.nodeName?v.nodeName.toLowerCase()===t:false;}).toArray(),si=s.indexOf(l),ssi=ss.indexOf(l);return ';
        if(info.TAG && info.TAG !== '*') {
            f += 't===\'' + info.TAG.toLowerCase().replace(/[\\']/g, function(x) { return '\\' + x; }) + '\'&&';
        }
        if(info.ID) {
            f += 'i===\'' + info.ID.toLowerCase().replace(/[\\']/g, function(x) { return '\\' + x; }) + '\'&&';
        }
        if(info.CLASS) {
            for(var i = 0; i < info.CLASS.length; i++) {
                f += 'c.indexOf(\' ' + info.CLASS[i].toLowerCase() + ' \')>-1&&';
            }
        }
        if(info.PSEUDO) {
            for(var i = 0; i < info.PSEUDO.length; i++) {
                var p = info.PSEUDO[i], j, v = '';
                if((j = p.indexOf('(')) > -1) {
                    v = p.substring(j + 1, p.length - 1);
                    p = p.substring(0, j);
                }
                switch(p) {
                    case 'first-child':
                        f += '!si';
                        break;
                    case 'first-of-type':
                        f += '!ssi';
                        break;
                    case 'nth-child':
                        // TODO: Implement all nth-*** selectors.
                        break;
                    case 'nth-of-type':

                        break;
                    case 'last-child':
                        f += 'si===s.length-1';
                        break;
                    case 'last-of-type':
                        f += 'ssi===ss.length-1';
                        break;
                    case 'nth-last-child':

                        break;
                    case 'nth-last-of-type':

                        break;
                    case 'only-child':
                        f += 's.length===1';
                        break;
                    case 'only-of-type':
                        f += 'ss.length===1';
                        break;
                    case 'disabled':
                        f += 'l.disabled';
                        break;
                    case 'enabled':
                        f += '!l.disabled';
                        break;
                    case 'checked':
                        f += 'l.checked';
                        break;
                    case 'empty':
                        f += '!l.childNodes.length'; // TODO: Maybe restrict to elements (t 1) only?
                        break;
                    case 'not':
                        f += '!Sprint.isMatch(\'' + v.replace(/\\'/g, function(x) { return '\\' + x; }) + '\')(0,l)';
                        break;
                    default:
                        throw new Sprint.Error("Unrecognized pseudo-class \"" + p + "\".");
                }
                f += '&&';
            }
        }
        if(info.ATTR) {
            from(info.ATTR).each(function(k, v) {
                var c = k.charAt(k.length - 1);
                f += 'l.getAttribute(\'' + ('$^*~|'.indexOf(c) > -1 ? k.substring(0, k.length - 1) : k).replace(/\\'/g, function(x) { return '\\' + x; }) + '\')';
                if(typeof v === 'string') {
                    v = v.replace(/\\'/g, function(x) { return '\\' + x; });
                    switch(c) {
                        case '$':
                            f += '.endsWith(\'' + v + '\')';
                            break;
                        case '^':
                            f += '.startsWith(\'' + v + '\')';
                            break;
                        case '*':
                            f += '.indexOf(\'' + v + '\')+1';
                            break;
                        case '~':
                            f += '.split(\' \').indexOf(\'' + v + '\')+1';
                            break;
                        case '|':
                            f += '.split(\'-\').indexOf(\'' + v + '\')+1';
                            break;
                        default:
                            f += '===\'' + v + '\'';
                    }
                }
                f += '&&';
            });
        }

        if(f.substring(f.length - 2) !== '&&') {
            // It matches anything.
            f = 'return true  ';
        }

        return new Function(['l'], f.substring(0, f.length - 2) + ';');
    },
    compileTree: function(selector) {
        var t = Sprint.tokenizeSelector(selector), i = -1, j, splitters = ', >~+';
        while(++i < t.length) {
            if(splitters.indexOf(t[i]) > -1) {
                j = i;
                while(--j >= 0 && t[j] === ' ') t[j] = null;
                j = i;
                while(++j < t.length && t[j] === ' ') t[j] = null;
            }
        }
        return from(t).where().select(function(k, v) {
            return k % 2 ? v : Sprint.compileSingle(Sprint.getInfo(v));
        }).toArray();
    },
    matchSingleTree: function(element, tree) {
        if(!tree.length) {
            return true;
        }

        if(!tree[tree.length - 1](element)) {
            return false;
        }

        for(var i = tree.length - 3; i >= 0; i -= 2) {
            switch(tree[i + 1] || ' ') {
                case ' ':
                    while(true) {
                        if(!(element = element.parentNode)) {
                            return false;
                        }
                        if(tree[i](element)) {
                            break;
                        }
                    }
                    break;
                case '>':
                    if(!(element = element.parentNode) || !tree[i](element)) {
                        return false;
                    }
                    break;
                case '+':
                    while(true) {
                        if(!(element = element.previousSibling)) {
                            return false;
                        }
                        if(element.nodeType === 1) {
                            if(!tree[i](element)) {
                                return false;
                            } else {
                                break;
                            }
                        }
                    }
                    break;
                case '~':
                    while(true) {
                        if(!(element = element.previousSibling)) {
                            return false;
                        }
                        if(tree[i](element)) {
                            break;
                        }
                    }
                    break;
            }
        }

        return true;
    },
    matchTree: function(element, tree) {
        var c = [];
        for(var i = 0; i < tree.length; i++) {
            if(tree[i] === ',') {
                if(Sprint.matchSingleTree(element, c)) {
                    return true;
                }
                c = [];
            } else {
                c.push(tree[i]);
            }
        }
        return Sprint.matchSingleTree(element, c);
    },
    tokenizeSelector: function(selector) {
        var quotes = '\'"', nestable = '(){}[]', escaped = false, currentQuotes = null, currentNested = [], tokens = [], splitters = ', >~+', i = -1, c, s = '';
        while(++i < selector.length) {
            c = selector.charAt(i);
            if(escaped) {
                escaped = false;
            } else if(c === '\\') {
                escaped = true;
                continue;
            } else if(currentQuotes) {
                if(currentQuotes === c) {
                    currentQuotes = null;
                }
            } else if(quotes.indexOf(c) > -1) {
                currentQuotes = c;
            } else if(currentNested.length) {
                if(nestable.indexOf(currentNested[currentNested.length - 1]) + 1 === nestable.indexOf(c)) {
                    currentNested.pop();
                }
            } else if(nestable.indexOf(c) > -1) {
                currentNested.push(c);
            } else if(splitters.indexOf(c) > -1) {
                tokens.push(s);
                tokens.push(c);
                s = '';
                continue;
            }
            s += c;
        }
        tokens.push(s);

        return tokens;
    },
    isMatch: function(selector) {
        var f = Sprint.compileTree(selector);
        return function(key, element) {
            return Sprint.matchTree(element, f);
        };
    },
    select: function(selector) {
        return from(Sprint.getAllElements()).where(Sprint.isMatch(selector)).toArray();
    },
    selectIn: function(selector, element) {
        return from(Sprint.getAllElementsIn(element)).where(Sprint.isMatch(selector)).toArray();
    }
};

function from(x) {
    if(!x) {
        throw new Sprint.Error("null or undefined passed to Sprint:from().");
    }

    var r = {
        keys: [],
        values: []
    };

    if(x.length) {
        for(var i = 0; i < x.length; i++) {
            r.keys.push(i);
            r.values.push(x[i]);
        }
    } else if(x.childNodes) {
        return from(x.childNodes);
    } else {
        for(var y in x) {
            if(x.hasOwnProperty(y)) {
                r.keys.push(y);
                r.values.push(x[y]);
            }
        }
    }

    r.length = r.keys.length;

    r.where = function(f) {
        if(f) {
            if(typeof f === 'string') return this.where(new Function(['k', 'v'], 'return ' + f + ';'));

            var r = {};
            for(var i = 0; i < this.length; i++) {
                if(f(this.keys[i], this.values[i])) {
                    r[this.keys[i]] = this.values[i];
                }
            }
            return from(r);
        } else {
            return this.where(function(k, v) { return v; });
        }
    };

    r.select = function(f) {
        var r = {};
        for(var i = 0; i < this.length; i++) {
            r[this.keys[i]] = f(this.keys[i], this.values[i]);
        }
        return from(r);
    };

    r.each = function(f) {
        for(var i = 0; i < this.length; i++) {
            f(this.keys[i], this.values[i]);
        }
    };

    r.first = function() {
        return this.values[0];
    };

    r.last = function() {
        return this.values[this.length - 1];
    };

    r.splitBy = function(f) {
        if(typeof f === 'function') {
            var r = [], c = {};
            for(var i = 0; i < this.length; i++) {
                if(f(this.keys[i], this.values[i])) {
                    r.push(c);
                    c = {};
                } else {
                    c[this.keys[i]] = this.values[i];
                }
            }
            r.push(c);
            return from(r);
        } else {
            return this.splitBy(function(x) { return x === f; });
        }
    };

    r.limit = function(f) {
        var r = {}, i = -1;

        if(typeof f === 'function') {
            while(++i < this.length && f(this.keys[i], this.values[i])) {
                r[this.keys[i]] = this.values[i];
            }
        } else {
            while(++i < Math.min(this.length, f)) {
                r[this.keys[i]] = this.values[i];
            }
        }

        return from(r);
    };

    r.after = function(f) {
        var r = {}, i = -1;

        if(typeof f === 'function') {
            while(++i < this.length && !f(this.keys[i], this.values[i])) {
            }
            while(++i < this.length) {
                r[this.keys[i]] = this.values[i];
            }
        } else {
            if(f < this.length) {
                i = f - 1;
                while(++i < this.length) {
                    r[this.keys[i]] = this.values[i];
                }
            }
        }

        return from(r);
    };

    r.toArray = function() {
        return this.values;
    };

    return r;
}

```

You use it like so:

```
Sprint.selectIn("mySelector", element);

```

Or

```
Sprint.select("mySelector")

```

. The code is 6.89KB minified and 2.26KB gzipped.
> 6 votes

---
Tags: code-golf, javascript, css
---


title: Polyomino generator

text:
# Question
Title: Polyomino generator
**Write a program that prints the shapes of** one-sided polyominoes.

Given input 4 (tetrominos), a sample output would be:

```
 *   *         *     *
 *   *    **   **   **  *
**   **   **    *   *  ***  ****

```

You are not restricted with respect to orientation, ordering or layout as long as polyominoes are not connected and not duplicated. (E.g. you can print the shapes in a column rather than a row)

Provide code that inputs a number from 3 to 6 and outputs the one-sided polyominoes of that size. The expected number of polyominoes output are 2, 7, 18, and 60 for 3, 4, 5, and 6 as inputs respectively.

Shortest code wins, present your solution for number 4.

# Answer
> 6 votes
## Python, 398 392 chars

```
n=input()
r=range
T=lambda P:set(p-min(p.real for p in P)-min(p.imag for p in P)*1j for p in P)
A=[]
for i in r(1<<18):
 P=[k%3+k/3*1j for k in r(18)if i>>k&1]
 C=set(P[:1])
 for x in P:[any(p+1j**k in C for k in r(4))and C.add(p)for p in P]
 P=T(P)
 if not(C^P or P in A or len(P)-n):
  for y in r(4):print''.join(' *'[y+x*1j in P] for x in r(6))
  A+=[T([p*1j**k for p in P])for k in r(4)]

```

Polyominos are represented as sets of complex numbers representing the cells of the polyomino. For example, T takes a polyomino and translates it so the minimum real and imaginary coordinates are 0.

The outer loop iterates through all 2^18 3x6 grids, generating a potential polyomino P, making sure P is connected (by computing C, the part of the polyomino connected to P\[0\]), checking that P isn't in the list A of previously found polyominos, and verifying that P has exactly n cells. Any new polyomino is added to A in all 4 rotations.

It takes two minutes or so to run to completion. Here's the result for n=4:

```
**
*
*

*
**
*

**
**

 *
**
*

*
*
**

*
**
 *

****

```

# Answer
> 3 votes
## Ruby, 266 241 320 (227 without reflections)

Given the input restrictions, it's easier to just use a bitmap of all the polyominos.

```
puts [%w[13 3],%w[1vqxip 1s9b3b],%w[1j85qxc81ax0oxld 1db08aq5w1vdul13 172qaw25hgn8jn5t],%w[5l91ancci09g0iuurrdbkbrsl58jjiodia8irxlivoufjjse42o4l8hlcz 3qbvfj70ksz14cngk9exust0w1qjshykauo6yvyyn3j6oefyy1xc58hsoj 26c0102a8vw34q88pktwlkepxzcslicg6ydtrz4zhyyutd4bukh73187qb]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}

```

Old version (outputs just the free polyominoes):

```
puts [%w[13 3],%w[9iz3 a5z],%w[cfu9zai70z b3tsb0pge1 12t8eks810j],%w[5wgmz704fjqc593xfwrmkwb7k0j9ztr31v fr8weq5t88qdxp93hit2fh8899qcbr2a9f 10r578ajcw2n15dwywsm0ep601kiv41cco3]][gets.hex-3].map{|n|n.to_i(36).to_s(2).tr'10','* '}

```

Output for n=4:

```
** **  *    *  ****  **   *
**  ** *** ***      **  ***

```

# Answer
> 1 votes
### Golfscript, 221 chars

Also 221 bytes. Inspired by Lowjacker's approach, but moderately different in actual implementation (and produces one-sided rather than two-sided polyominos).

Because some of the characters used, while valid Unicode codepoints (and one byte each in UTF-8), are non-printable, I present the base-64 encoding of the script:

```
fidAQEAVRRVALVs9TUZFUwhgA0BrdjVXGm4VOl8aDgMZfBdoVQQzNk0YLQ9eXCciBhwQH0ADDW9E
KlomSXgoLBxxI1oEeB9XPm51GF43bHBKQzl3WQ5vXTJCTABfEz4bJBlaWX0XL2QVDF5ZXFw5BxpF
IzNUKmUtYwEEfQEKckMSbjAlQmhYHShQaAtjK1QFbnt5WQokFkNkHgNlL35cXCU6Hj8nIkAiLz0x
MjdiYXNlIDRiYXNlWzNdL3tbKVxbMl0vLi0xJUAqXXt7eyIgKiI9fSVuK30vbn0vfS8=

```

And the script itself with the magic strings substituted:

```
~"@@@Magic@strings@go@here""@"/=127base 4base[3]/{[)\[2]/.-1%@*]{{{" *"=}%n+}/n}/}/

```

Example execution:

```
$ golfscript.rb poly.gs <<<"4"
****

***
*

*
***

**
**

***
 *

**
 **

 **
**

```

---
Tags: code-golf, ascii-art, connected-figure
---


# Question
Title: Sum of Fibonacci numbers -- speed contest
Write a program that print sum of as many Fibonacci numbers as possible. There is a limit in that your program should not run more than 10s on 2GHz single core PC. (equivalents are acceptable, for instance you have twice as many time on 1GHz PC). Memory consumption is not limited, but provide details, if you exceed normal values.

Your program has to work with different input values. Output can be calculated modulo 10^i, but i has to be at least 9 digits. Other types of results are also welcome as long as they are presented with 9 digits and are not trivially calculated.

Post source, language input value and result.

# Answer
## Python, 7 chars

It turns out that the period of *G(i)=F(i) mod 10^9* is *1.5e9* exactly. So when adding them up, we can group them into groups of size *1.5e9*, each of which will have the same sum (mod 10^9). Turns out, that sum is 0. So if we take N to be any multiple of *1.5e9*, the sum of the first N fibonacci numbers is 0. So:

```
print 0

```

will, given an argument `i`, print the sum of the first `i * 1.5e9` Fibonacci numbers. Super fast and works for an arbitrarily large `i`.
> 8 votes

# Answer
Compensating for my cores being 2.5GHz by allowing just under 8 seconds,

```
public class FiboSum
{
    public static void main(String[] args)
    {
        long now = System.currentTimeMillis();
        System.out.println("Taking F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2):");
        long n = 0, x = 1, y = 1, N = 1000000000;
        // x = F_n, y = F_{n+1}
        while (System.currentTimeMillis() - now < 7800)
        {
            n++;
            long t = (x*x + y*y) % N;
            x = x * (2*y - x) % N;
            y = t;
        }
        System.out.println("\\sum_{r=1}^{2^"+n+"} F(r) = " + (N+x+y-1)%N + " mod " + N);
    }
}

```

Output:

```
Taking F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2):
\sum_{r=1}^{2^94900480} F(r) = 755986263 mod 1000000000

```

And no sign of Binet's formula or any closed form evaluation of the sum, even though there is a trivial one.

---

As a closely related point of interest, note that we can use the identity `F(m+n) = F(m+1) F(n) + F(m) F(n+1) - F(m) F(n)` to compute the `n`th Fibonacci number in `O(lg n)` arithmetic operations. Replace `int` and `long` with a suitable BigInteger implementation to taste. I've made this tail-recursive.

```
static long Fibo(int n)
{
    if (n > 92) throw new ArithmeticException("Overflow");

    long Fm = 1, Fmp = 1;
    long Fn = 0, Fnp = 1;

    while (n > 0)
    {
        if ((n & 1) == 1)
        {
            long t = Fmp * Fn + Fm * (Fnp - Fn);
            Fnp = Fmp * Fnp + Fm * Fn;
            Fn = t;
        }

        long t = Fm * (2*Fmp - Fm);
        Fmp = Fmp*Fmp + Fm*Fm;
        Fm = t;

        n >>= 1;
    }

    return Fn;
}

```

Or if SML is your cup of tea then

```
fun fibo x =
    let fun f 0 _ _ Fn _ = Fn
          | f n Fm Fmp Fn Fnp =
            let val Fm2 = Fm * (2 * Fmp - Fm)
                val Fmp2 = Fmp * Fmp + Fm * Fm
            in if (n mod 2 = 0)
               then f (n div 2) Fm2 Fmp2 Fn Fnp
               else f (n div 2) Fm2 Fmp2 (Fmp * Fn + Fm * (Fnp - Fn)) (Fmp * Fnp + Fm * Fn)
            end
    in f x 1 1 0 1
    end;

```

Detailed reasoning at http://www.cheddarmonk.org/Fibonacci.html
> 2 votes

# Answer
Knowing that the sum of the fibbonacci series diverges, I can print the result rather trivially with 16 characters in Javascript.

```
alert(Infinity);

```

Ok, ok, enough glibness. This probably doesn't meet your criterion about trivial calculation. Here is my full version in Javascript:

```
var old = new Date().getTime();
var fib1 = 1, fib2 = 1, sum = 0;
while(new Date().getTime() - old < 2){
    sum = fib1 + fib2;
    fib1 = fib2;
    fib2 = sum;
}
alert(sum);

```

What it alerts is unpredictable, it ranges from 1e+100 to Infinity for me.

And here it is golfed (91 chars):

```
o=new Date().getTime();f=1,g=1,s=0;while(new Date().getTime()-o< 2){s=f+g;f=g;g=s}alert(s);

```
> 2 votes

# Answer
Okay. I took this question as find every fib from fib(0) to fib(n) and take the sum: what's the biggest n you can deal with in 8 sec?

```
#!/usr/bin/env clisp

(defun sum (list)
    (setf s 0)
    (loop for foo in list do
        (setf s (+ s foo))
    )
    s
)

(defun fib-list (n)
    (loop for x from 1 to n do
        (setf *fibs* (append *fibs* (list (sum (last *fibs* 2)))))
    )
)

(defun test ()
    (progn
            ;; variable initializations
        (setf n 12000)
        (setf ti (get-universal-time))
        (setf tf (get-universal-time))

        (loop while (<= (- tf ti) 8) do ; while the end time minus the start time
                                        ; is less than 8 sec...
            (progn
                (print n)
                (setf *fibs* '(1 1))
                (setf ti (get-universal-time))  ; record the start time

                (fib-list n)
                (print (sum *fibs*))

                (setf tf (get-universal-time))  ; record the end time
                (setf n (+ n 25))
            )
        )
        (print "MAXIMUM NUMBER......")
        (print n)
    )
)

(test)

```

Now. this only uses one optimization: my fib calculating method, which uses a list to minimize the repetition of calculations.

The test routine reports that this code can deal with an n of 13000 in 8 seconds under win7 on a 2.35Ghz chip. I discount my dual-cores because clisp is a single-threaded process which derives no benefit therefrom.

no fancy math here, just ANSI CLISP and brute force "trivial calculation".
> 1 votes

---
Tags: code-challenge, fibonacci
---


title: Compress programs

text:
# Question
Title: Compress programs
Write a program/script that decompresses and passes any compressed data appended at the end of the binary/file as standard input to a program specified as arguments.

```
$ gzip --to-stdout input >> your_solution
$ your_solution program args...

```

should have the same effects as:

```
$ program args... < input

```

# Answer
**zsh: (20 chars)**

*Edit:* because zsh doesn't re-parse arguments like bash, I can lose the `"`s and it will still work with spaces in args

```
#!/usr/bin/zsh
tail -n+3 $0|zcat|$@

```

**Bash (25 24 chars not including shebang line)**

```
#!/bin/bash
tail -n+3 "$0"|zcat|"$@"

```
> 7 votes

# Answer
**C (251 chars)**

Way too long to win, but I wanted to do one in a compiled language to make things interesting. (It turned out to be quite straightforward actually).

It's probably very compiler-dependent (I used GCC 4.4.3 with the default settings on 32-bit Linux)

```
#include<stdio.h>
#define q(x)FILE*x=x##open(
#define w strcpy(o+b
o,s=7462;char b[99];main(int i,char**a){q(f)*a,"r");while(--s)fgetc(f);
for(o=0;++s<i;o++[b]=32)w,a[s]),o+=strlen(a[s]);w,"|zcat");q(p)b,"w");
for(;~(i=fgetc(f));fputc(i,p));fclose(p);}

```
> 2 votes

# Answer
## Bash (OP solution)

This is an example I came up with:

```
cat $0 | awk 'NR > 1' | zcat | $* ; exit

```
> 1 votes

---
Tags: code-golf, compression
---


title: Amicable number calculator

text:
# Question
Title: Amicable number calculator
Write a program that calculates amicable numbers, starting from \[0,0\], intil the maximum value for an integer is reached in the language you chose to write it in.

Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. (A proper divisor of a number is a positive integer divisor other than the number itself. For example, the proper divisors of 6 are 1, 2, and 3.) A pair of amicable numbers constitutes an aliquot sequence of period 2. A related concept is that of a perfect number, which is a number which equals the sum of its own proper divisors, in other words a number which forms an aliquot sequence of period 1. Numbers that are members of an aliquot sequence with period greater than 2 are known as sociable numbers.

For example, the smallest pair of amicable numbers is (220, 284); for the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71, and 142, of which the sum is 220.

If you want more information on amicable numbers, here's a link to Wikipedia's entry on the subject.

NOTE: It cannot use pre-determined tables of which are and which are not amicable numbers

EDIT: I suppose I should have said how I will determine the winner:
Your score will be calculated by this formula: `Total_characters_of_code / Up_votes = Score`
I will select an answer on Sunday, May 1.
The lowest score wins!

# Answer
## Golfscript (51 50 chars)

```
2{.{:a,(\{.a\%!*+}/}:^~1$>{..^^={[..^](\p}*}*).}do

```

The core is the override of `^` as `:a,(\{.a\%!*+}/` which finds the aliquot of the number on the top of the stack (call it `n`) by the grossly inefficient approach of considering every number from `1` to `n-1` to see whether it's a factor.
> 5 votes

# Answer
# C (gcc), 162, 158, 146, 138 chars

```
s(n){int x=1,i=2;for(;i<=sqrt(n);++i)if(n%i==0)x+=i+n/i;return x;}main(i,a){for(;;)a=s(i),((a>i)?s(a):0)==i++?printf("%d,%d\n",i-1,a):0;}

```

compile with gcc using `gcc amic.c -o amic -lm -include math.h`

To shorten it any further I suspect the algorithm would have to change.

*Edits:*

162-\>158: Consolidated the variable `b` into the printf conditional.

158-\>146: Utilized main to declare `a` instead of using a global var, also using implicit `int` of the parameter *and* return type for the function `s(n)`

146-\>138: Add Lowjacker's suggestion of removing the cast to double. Thanks!
> 4 votes

# Answer
### Scala (120 chars):

```
def d(n:Int)=(1 to n-1).filter(n%_==0)
def i(x:Int,y:Int)=x!=y&&d(y).sum==x
(1 to Int.MaxValue).filter(x=>i(x,d(x).sum))

```
> 3 votes

# Answer
## Ruby 1.9, 126 124

Not quite a serious answer, but it's *theoretically* correct. If you're *really* patient, and have *lots* of RAM, it should eventually print every pair of amicable numbers.

```
s=->n{eval (1...n).select{|i|n%i==0}*?+}
i=0
loop{Thread.new(i+=1){|j,k=j|loop{s[k+=1]==j&&s[j]==k&&printf("%d,%d\n",j,k)}}}

```
> 2 votes

---
Tags: code-challenge, math, number
---


title: April Fools Jokes

text:
# Question
Title: April Fools Jokes
Figure out how to mess up another programmer's project by making a subtle, hard to find (but "harmless") "bug". (Double quotes FTW!)

Try to keep them short; `shorter ~= subtle`.

---

For example:

```
#define true false

```

---

Don't actually *destroy* the code *directly*. For example, from this:

```
for(size_t i = 0; i < 10; ++i)

```

To:

```
for(size_t *i = new size_t; ++i; delete i)

```

Or even:

```
for(size_t i = 0; i <= 10; ++i)

```

Is *not* OK. If a language actually allows you to change `<` to `<=` without changing that code "directly", then it's alright. (You know what I mean. Deleting all the code is just

---

## Voting

Up vote the most original/creative/subtle solutions.

On Mother's Day (May 8, 2011), the most up voted answer will be chosen as the winner.

# Answer
> 12 votes
```
#define if(x) if(random(100) > 0 && (x))

```

# Answer
> 7 votes
## Haskell

```
module UnsafePrelude where

import Prelude hiding ((.), (+), (-), sum, map, foldl)
import qualified Prelude as P

import Unsafe.Coerce

-- disallow (f . g . h)
infix 9 .
(.) = (P..)

-- Make arithmetic a bit more exciting.
-- These actually work correctly for trivial Int and Integer cases,
-- at least in GHC 6.12.1 on x86.
(+), (-) :: (Num a) => a -> a -> a
(+) = unsafeCoerce ((P.+) :: Float -> Float -> Float)
(-) = unsafeCoerce ((P.-) :: Float -> Float -> Float)

sum :: (Num a, Num b) => [a] -> b
sum = unsafeCoerce (P.sum :: [Float] -> Float)

-- Make map a little less type-safe.
map :: (a -> b) -> [c] -> [b]
map   = unsafeCoerce P.map

-- Make foldl associate the wrong way, but still have the same type.
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f = foldr (flip f)

```

# Answer
> 6 votes
## GolfScript

```
1:

```

Note there is a space after the colon. This assigns the value `1` to the space character. All further code that uses the space for readability will find unexpected extra ones on its stack!

Alternatively,

```
0:1

```

assigns the value `0` to the character `1`.

# Answer
> 3 votes
## Ruby

```
class Fixnum
    alias add +
    def + (n)
        add n.add 1
    end
end

```

And now, like in *1984*...

```
(33):0>  2 + 2 == 5
>>> true
(36):0>

```

---
Tags: code-challenge, popularity-contest
---


title: Lorem Ipsum Compressor

text:
# Question
Title: Lorem Ipsum Compressor
Write a program which can compress/decompress randomly generated Lorem Ipsum text.

Devise **your own** lossless algorithm. You may compress your data further using an existing algorithm afterwards, but you must cite the algorithm used.

You may use dictionaries.

---

**The text does not necessarily start with `Lorem ipsum dolor sit amet`.**

The length of the test cases should be between 6400 and 6600 characters. (A picture from this generator.)

Find some test cases here, here, and here.

---

The program with the best compression ratio wins.

# Answer
## C# — compression ratio: ≈ 0.27

Uses arithmetic encoding and a custom-designed frequency table derived from several tens of examples generated by Lorem Ipsum Generator3.

Compression is very slow, decompression is instantaneous.

The three test-cases provided give an average compression ratio of 0.27. Best I’ve seen was 0.22.

```
using System;
using System.IO;
using System.Linq;

namespace Timwi.Temp
{
    public sealed class ArithmeticCodingReader : IDisposable
    {
        private ulong _high, _low, _code;
        private ulong[] _probs;
        private ulong _totalprob;
        private Stream _basestream;
        private byte _curbyte;
        private int _curbit;

        public ArithmeticCodingReader(Stream basestr, ulong[] probabilities)
        {
            _basestream = basestr;
            _high = 0xffffffff;
            _low = 0;
            _probs = probabilities;
            _totalprob = 0;
            for (int i = 0; i < _probs.Length; i++)
                _totalprob += _probs[i];
            _curbyte = 0;
            _curbit = 8;
            _code = 0;
            for (int i = 0; i < 32; i++)
            {
                _code <<= 1;
                _code |= ReadBit() ? 1UL : 0UL;
            }
        }

        public void Dispose()
        {
            _basestream.Close();
        }

        private bool ReadBit()
        {
            if (_curbit > 7)
            {
                _curbit = 0;
                _curbyte = (byte) _basestream.ReadByte();
            }
            bool ret = (_curbyte & (1 << _curbit)) != 0;
            _curbit++;
            return ret;
        }

        public int ReadSymbol()
        {
            ulong pos = ((_code - _low + 1) * _totalprob - 1) / (_high - _low + 1);
            int symbol = 0;
            ulong postmp = pos;
            while (postmp >= _probs[symbol])
            {
                postmp -= _probs[symbol];
                symbol++;
            }
            pos -= postmp;

            ulong newlow = (_high - _low + 1) * pos / _totalprob + _low;
            _high = (_high - _low + 1) * (pos + _probs[symbol]) / _totalprob + _low - 1;
            _low = newlow;

            while ((_high & 0x80000000) == (_low & 0x80000000))
            {
                _high = ((_high << 1) & 0xffffffff) | 1;
                _low = (_low << 1) & 0xffffffff;
                _code = (_code << 1) & 0xffffffff;
                if (ReadBit()) _code++;
            }

            while (((_low & 0x40000000) != 0) && ((_high & 0x40000000) == 0))
            {
                _high = ((_high & 0x7fffffff) << 1) | 0x80000001;
                _low = (_low << 1) & 0x7fffffff;
                _code = ((_code & 0x7fffffff) ^ 0x40000000) << 1;
                if (ReadBit()) _code++;
            }

            return symbol;
        }
    }

    public sealed class ArithmeticCodingWriter : IDisposable
    {
        private ulong _high, _low;
        private int _underflow;
        private ulong[] _probs;
        private ulong _totalprob;
        private Stream _basestream;
        private byte _curbyte;
        private int _curbit;

        public ArithmeticCodingWriter(Stream basestr, ulong[] probabilities)
        {
            _basestream = basestr;
            _high = 0xffffffff;
            _low = 0;
            _probs = probabilities;
            _totalprob = 0;
            for (int i = 0; i < _probs.Length; i++)
                _totalprob += _probs[i];
            _curbyte = 0;
            _curbit = 0;
            _underflow = 0;
        }

        public void WriteSymbol(int p)
        {
            if (p >= _probs.Length)
                throw new Exception("Attempt to encode non-existent symbol");
            if (_probs[p] == 0)
                throw new Exception("Attempt to encode a symbol with zero probability");

            ulong pos = 0;
            for (int i = 0; i < p; i++)
                pos += _probs[i];

            ulong newlow = (_high - _low + 1) * pos / _totalprob + _low;
            _high = (_high - _low + 1) * (pos + _probs[p]) / _totalprob + _low - 1;
            _low = newlow;

            while ((_high & 0x80000000) == (_low & 0x80000000))
            {
                OutputBit((_high & 0x80000000) != 0);
                while (_underflow > 0)
                {
                    OutputBit((_high & 0x80000000) == 0);
                    _underflow--;
                }
                _high = ((_high << 1) & 0xffffffff) | 1;
                _low = (_low << 1) & 0xffffffff;
            }

            while (((_low & 0x40000000) != 0) && ((_high & 0x40000000) == 0))
            {
                _underflow++;
                _high = ((_high & 0x7fffffff) << 1) | 0x80000001;
                _low = (_low << 1) & 0x7fffffff;
            }
        }

        private void OutputBit(bool p)
        {
            if (p) _curbyte |= (byte) (1 << _curbit);
            if (_curbit >= 7)
            {
                _basestream.WriteByte(_curbyte);
                _curbit = 0;
                _curbyte = 0;
            }
            else
                _curbit++;
        }

        public void Dispose()
        {
            OutputBit((_low & 0x40000000) != 0);
            _underflow++;
            while (_underflow > 0)
            {
                OutputBit((_low & 0x40000000) == 0);
                _underflow--;
            }
            _basestream.WriteByte(_curbyte);
            _basestream.Close();
        }
    }

    public class Program
    {
        static string[] elements = { "conclusionemque", "vituperatoribus", "necessitatibus", "concludaturque", "delicatissimi", "signiferumque", "mediocritatem", "interpretaris", "complectitur", "consequuntur", "intellegebat", "deterruisset", "reprehendunt", "definitionem", "disputationi", "definitiones", "contentiones", "voluptatibus", "comprehensam", "theophrastus", "consectetuer", "suscipiantur", "Theophrastus", "dissentiunt", "ullamcorper", "instructior", "liberavisse", "efficiantur", "referrentur", "accommodare", "eloquentiam", "repudiandae", "appellantur", "reformidans", "adversarium", "persequeris", "philosophia", "Efficiantur", "neglegentur", "scriptorem", "Adolescens", "voluptaria", "maiestatis", "sententiae", "moderatius", "quaerendum", "interesset", "efficiendi", "omittantur", "sadipscing", "forensibus", "scripserit", "argumentum", "rationibus", "dissentiet", "reprimique", "elaboraret", "inciderint", "adipiscing", "Consetetur", "assueverit", "democritum", "intellegat", "expetendis", "mnesarchum", "voluptatum", "adolescens", "constituto", "vituperata", "scribentur", "posidonium", "percipitur", "abhorreant", "dissentias", "consetetur", "intellegam", "constituam", "temporibus", "incorrupte", "honestatis", "disputando", "definiebas", "deseruisse", "Voluptatum", "pertinacia", "suavitate", "laboramus", "aliquando", "patrioque", "consulatu", "torquatos", "similique", "evertitur", "assentior", "tractatos", "ocurreret", "accusamus", "consequat", "gubergren", "Urbanitas", "iudicabit", "urbanitas", "splendide", "principes", "convenire", "hendrerit", "partiendo", "Prodesset", "persecuti", "petentium", "expetenda", "prodesset", "maluisset", "tincidunt", "vulputate", "gloriatur", "iracundia", "salutatus", "salutandi", "molestiae", "postulant", "periculis", "mediocrem", "Petentium", "facilisis", "imperdiet", "Periculis", "Accusamus", "Ocurreret", "dignissim", "euripidis", "sapientem", "repudiare", "corrumpit", "erroribus", "qualisque", "explicari", "conceptam", "platonem", "detracto", "oporteat", "insolens", "aliquyam", "verterem", "percipit", "albucius", "propriae", "noluisse", "nominati", "fabellas", "deleniti", "recusabo", "Legendos", "apeirian", "probatus", "recteque", "antiopam", "volutpat", "vivendum", "mentitum", "lucilius", "offendit", "pericula", "fastidii", "detraxit", "accusata", "suscipit", "Appetere", "phaedrum", "delicata", "atomorum", "praesent", "nominavi", "appareat", "senserit", "indoctum", "sensibus", "legendos", "placerat", "takimata", "invidunt", "omnesque", "facilisi", "menandri", "accumsan", "voluptua", "perfecto", "invenire", "eleifend", "perpetua", "quaestio", "lobortis", "scaevola", "Recusabo", "Menandri", "electram", "copiosae", "epicurei", "mandamus", "Placerat", "appetere", "deserunt", "inimicus", "luptatum", "oportere", "ancillae", "molestie", "delectus", "Lucilius", "officiis", "eligendi", "Vivendum", "Atomorum", "adipisci", "pertinax", "Offendit", "ponderum", "Singulis", "Invidunt", "aeterno", "iuvaret", "feugait", "Nostrum", "fierent", "viderer", "meliore", "admodum", "fabulas", "facilis", "nostrud", "aliquip", "dolorum", "docendi", "dolores", "ornatus", "Diceret", "denique", "eruditi", "ceteros", "alterum", "volumus", "Nonummy", "delenit", "laoreet", "impedit", "virtute", "habemus", "alienum", "numquam", "blandit", "equidem", "vivendo", "epicuri", "bonorum", "integre", "oblique", "prompta", "debitis", "impetus", "maiorum", "labitur", "nostrum", "corpora", "Omittam", "Ceteros", "omittam", "labores", "aperiam", "discere", "regione", "graecis", "Epicuri", "nonummy", "commodo", "malorum", "civibus", "aliquid", "commune", "veritus", "Tritani", "Sanctus", "vidisse", "eripuit", "euismod", "tibique", "dolorem", "Denique", "Prompta", "nusquam", "aliquam", "fuisset", "saperet", "utroque", "Minimum", "legimus", "Fuisset", "quaeque", "Scripta", "persius", "aperiri", "sanctus", "Volumus", "inermis", "Corpora", "minimum", "tamquam", "tritani", "Virtute", "vocibus", "feugiat", "Docendi", "Viderer", "accusam", "Iuvaret", "scripta", "Malorum", "Laoreet", "nonumy", "iudico", "cetero", "putant", "verear", "ignota", "Causae", "audiam", "oratio", "facete", "primis", "populo", "possim", "animal", "utinam", "utamur", "doming", "semper", "mollis", "graeco", "timeam", "graece", "partem", "Soluta", "mucius", "omnium", "quando", "munere", "essent", "causae", "Melius", "Decore", "tation", "consul", "tempor", "tantas", "Veniam", "eirmod", "veniam", "quodsi", "audire", "Munere", "graeci", "Essent", "melius", "nemore", "Soleat", "noster", "everti", "putent", "congue", "nostro", "postea", "Tempor", "iriure", "homero", "quidam", "dicunt", "decore", "Noster", "dictas", "laudem", "exerci", "Exerci", "iisque", "legere", "Iriure", "soluta", "dolore", "vocent", "Nostro", "ubique", "ridens", "Ubique", "option", "Mollis", "Audiam", "Postea", "labore", "Semper", "Partem", "Dolore", "possit", "dicant", "Iudico", "affert", "Labore", "latine", "soleat", "doctus", "Putent", "Congue", "Iisque", "libris", "tollit", "Verear", "Vocent", "Dictas", "Consul", "Affert", "Tantas", "Putant", "altera", "Homero", "Lorem", "ipsum", "liber", "Rebum", "aeque", "magna", "dicat", "Harum", "dicam", ".\r\n\r\n", "omnes", "Dicat", "choro", "Simul", "summo", "ullum", "mutat", "Aeque", "reque", "errem", "porro", "viris", "Erant", "nobis", "justo", "Modus", "velit", "solet", "zzril", "facer", "posse", "dicta", "mazim", "paulo", "inani", "movet", "falli", "Illum", "assum", "dicit", "Fugit", "ferri", "Clita", "solum", "adhuc", "sonet", "Solet", "rebum", "Ullum", "elitr", "Natum", "lorem", "Facer", "idque", "brute", "natum", "modus", "iusto", "Omnis", "illud", "minim", "Elitr", "dolor", "saepe", "Ferri", "autem", "atqui", "malis", "error", "erant", "fugit", "vitae", "nihil", "nulla", "simul", "habeo", "Augue", "harum", "Sonet", "Nobis", "Illud", "Summo", "mundi", "Brute", "Minim", "Autem", "Dicit", "Zzril", "Novum", "novum", "illum", "Nulla", "Error", "Movet", "etiam", "augue", "debet", "omnis", "clita", "probo", "Mundi", "Malis", "prima", "Falli", "vidit", "Debet", "Prima", "Errem", "diam", "alia", "kasd", "Amet", "modo", "wisi", "sint", "meis", "Elit", "enim", "vero", "quot", "tale", "puto", "Cibo", "quod", "quis", "erat", "Hinc", "Quod", "hinc", "Nisl", "dico", "quem", "Vero", "Sumo", "odio", "unum", "duis", "Odio", "eros", "Dico", "stet", "vide", "tota", "Alii", "Puto", "Eius", "sumo", "nisl", "Quas", "sale", "agam", "alii", "quas", "Stet", "Nibh", "cibo", "Agam", "veri", "nibh", "elit", "esse", "eius", "suas", "Quis", "Quot", "Erat", "amet", "vix", "nec", "vis", "est", "Cum", "vim", "pri", "mel", "cum", "qui", "ius", "duo", "Eos", "vel", "sed", "His", "Nec", "usu", "eos", "Pri", "mea", "sit", "sea", "Ius", "eam", "nam", "Duo", "Eum", "Nam", "Eam", "mei", "has", "eum", "pro", "per", "quo", "his", "Vix", "Sed", "Quo", "Est", "Vim", "Per", "Vel", "Mel", "Mei", "Vis", "Mea", "Sea", "Has", "Usu", "Pro", "Sit", "Qui", "no", ", ", "eu", ". ", "ea", "et", "cu", "te", "ut", "Ut", "Et", "ei", "ad", "at", "in", "Ne", "ex", "ne", "id", "Ei", "An", "an", "Ea", "Eu", "At", "Te", "No", "Ex", "In", "Cu", "Id", "Ad", " ", "." };
        static ulong[] frequencies = { 4, 5, 9, 7, 3, 7, 3, 2, 6, 8, 6, 8, 6, 5, 3, 7, 6, 5, 4, 5, 3, 4, 1, 4, 7, 5, 10, 8, 4, 8, 5, 2, 3, 3, 5, 3, 5, 1, 3, 7, 1, 11, 4, 4, 9, 6, 8, 6, 8, 3, 9, 8, 7, 5, 4, 9, 9, 2, 5, 1, 3, 5, 6, 4, 3, 6, 8, 11, 4, 3, 4, 6, 3, 2, 7, 3, 4, 5, 2, 8, 6, 6, 2, 1, 1, 5, 6, 3, 8, 6, 9, 3, 1, 7, 5, 5, 5, 4, 6, 1, 7, 6, 5, 8, 8, 4, 3, 1, 6, 7, 8, 6, 4, 2, 10, 7, 9, 5, 5, 4, 5, 6, 6, 1, 5, 3, 1, 1, 1, 5, 5, 6, 1, 3, 6, 1, 1, 2, 5, 8, 10, 6, 9, 8, 3, 6, 6, 4, 3, 5, 4, 3, 2, 3, 2, 6, 4, 6, 4, 3, 2, 5, 5, 4, 7, 3, 4, 1, 7, 5, 6, 9, 2, 2, 1, 3, 4, 4, 7, 7, 7, 6, 7, 1, 5, 2, 4, 9, 3, 3, 4, 2, 3, 1, 1, 3, 4, 2, 4, 1, 5, 3, 2, 4, 4, 6, 4, 3, 1, 4, 2, 1, 1, 2, 1, 1, 4, 1, 1, 5, 4, 3, 1, 7, 9, 6, 7, 7, 1, 8, 6, 4, 7, 4, 4, 2, 6, 8, 10, 6, 8, 1, 8, 11, 6, 2, 9, 6, 8, 5, 5, 4, 9, 4, 5, 7, 8, 8, 3, 4, 3, 6, 10, 1, 1, 7, 7, 4, 5, 3, 3, 1, 3, 3, 3, 6, 2, 7, 11, 2, 1, 6, 2, 7, 3, 6, 2, 1, 6, 5, 4, 4, 6, 1, 6, 1, 6, 1, 1, 5, 5, 1, 4, 1, 8, 1, 3, 1, 4, 1, 1, 1, 6, 1, 2, 1, 1, 4, 5, 6, 9, 8, 4, 1, 3, 4, 6, 5, 3, 5, 6, 8, 3, 4, 5, 9, 8, 7, 7, 6, 2, 4, 6, 6, 4, 4, 6, 2, 1, 6, 9, 6, 5, 1, 2, 5, 4, 3, 1, 5, 2, 6, 4, 2, 8, 9, 4, 5, 2, 2, 2, 6, 4, 10, 11, 4, 1, 5, 5, 5, 1, 3, 8, 1, 5, 3, 5, 1, 5, 8, 2, 4, 1, 2, 1, 1, 1, 1, 2, 7, 3, 1, 3, 1, 3, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 6, 5, 5, 2, 4, 99, 8, 1, 4, 1, 5, 5, 7, 1, 8, 4, 5, 2, 4, 6, 6, 2, 4, 3, 4, 7, 8, 4, 6, 6, 2, 5, 3, 2, 4, 6, 2, 7, 2, 8, 6, 8, 3, 7, 2, 4, 2, 7, 1, 5, 6, 5, 4, 4, 1, 4, 4, 1, 7, 3, 2, 8, 4, 7, 4, 7, 5, 5, 3, 4, 3, 3, 1, 5, 2, 1, 3, 2, 3, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 5, 7, 4, 2, 6, 3, 8, 4, 2, 7, 6, 2, 4, 6, 1, 4, 6, 8, 1, 2, 5, 2, 4, 5, 2, 1, 4, 2, 3, 1, 8, 2, 4, 2, 3, 1, 2, 1, 2, 4, 1, 5, 5, 2, 2, 2, 3, 4, 1, 3, 2, 3, 2, 3, 1, 1, 1, 1, 2, 21, 26, 35, 26, 9, 23, 34, 30, 33, 28, 30, 38, 4, 36, 20, 10, 3, 31, 21, 8, 34, 29, 26, 9, 25, 29, 11, 6, 7, 11, 32, 38, 23, 34, 22, 22, 33, 4, 6, 7, 4, 7, 7, 5, 8, 8, 7, 6, 4, 9, 7, 4, 5, 4, 70, 458, 57, 401, 52, 47, 63, 65, 59, 10, 12, 56, 42, 46, 45, 15, 53, 57, 55, 9, 9, 45, 9, 5, 8, 12, 14, 13, 5, 11, 8, 7, 3358, 1 };

        static void Main(string[] args)
        {
            if (args.Length != 2 || !new[] { "-c", "-d" }.Contains(args[0]) || !File.Exists(args[1]))
            {
                Console.WriteLine("Command-line parameters:");
                Console.WriteLine(" -c [file]   Compress file. (Output is file + “.compressed”.)");
                Console.WriteLine(" -d [file]   Decompress file. (Output is file + “.decompressed.txt”.)");
                return;
            }

            var freqs = Enumerable.Range(0, 129).Select(i => 1UL).Concat(frequencies).ToArray();

            if (args[0] == "-c")
            {
                var input = File.ReadAllText(args[1]);
                if (input.Any(ch => ch > 127))
                    throw new InvalidOperationException("Only ASCII characters are supported.");

                using (var file = File.Open(args[1] + ".compressed", FileMode.Create, FileAccess.Write))
                using (var acw = new ArithmeticCodingWriter(file, freqs))
                {
                    while (input.Length > 0)
                    {
                        int i = 0;
                        while (i < elements.Length && !input.StartsWith(elements[i]))
                            i++;
                        if (i < elements.Length)
                        {
                            acw.WriteSymbol(i + 129);
                            input = input.Substring(elements[i].Length);
                        }
                        else
                        {
                            acw.WriteSymbol(input[0]);
                            input = input.Substring(1);
                        }
                    }
                    acw.WriteSymbol(128);
                }
            }
            else
            {
                using (var file = File.Open(args[1], FileMode.Open, FileAccess.Read))
                using (var acr = new ArithmeticCodingReader(file, freqs))
                using (var outputFile = File.Open(args[1] + ".decompressed.txt", FileMode.Create, FileAccess.Write))
                using (var outputWriter = new StreamWriter(outputFile))
                {
                    while (true)
                    {
                        int i = acr.ReadSymbol();
                        if (i == 128)
                            break;
                        outputWriter.Write(i < 128 ? ((char) i).ToString() : elements[i - 129]);
                    }
                }
            }

            Console.WriteLine("Done.");
        }
    }
}

```
> 7 votes

# Answer
# Python - Star Transform Turned Huffman \[ratio=55% (decimal), and 45.4% (base36)\]

This started out as a star transformation algorithm, but morphed into a Huffman-style frequency based encoding.

I generated a frequency dictionary of lorem ipsum words (using the NLTK) from the samples, and then assigned them decimal values. Words are then substituted for their decimal values. There are some special cases for new lines and capital letters.

There are 3 different compression options: normal, strict, and stricter. Normal uses decimal encoding, strict uses hex encoding, and stricter uses base 36 encoding. Both strict and stricter will have problems if there are new words.

## compress.py

```
#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()
dict = lorem.dictionary

splitter = re.compile(r'([a-zA-Z]+|\s+|[,\.]*)')
words = splitter.findall(text)
for w in words:
    if w.lower() in dict:
        code = int(dict[w.lower()])
        if strict:
            code = lorem.strict_code(code)
        elif stricter:
            code = lorem.base36encode(code)
        if w.istitle():
                code = '^%s' %(code)
        sys.stdout.write(str(code))
    elif w == '\n\n ':
        sys.stdout.write('~')
    else:
        sys.stdout.write(w)

```

## decompress.py

```
#!/usr/bin/env python
import sys,re,lorem

strict = len(sys.argv) == 2 and sys.argv[1] == '-s'
stricter = len(sys.argv) == 2 and sys.argv[1] == '-ss'

text = sys.stdin.read()

# create the inverse of the dictionary
dict = dict((v,k) for k, v in lorem.dictionary.iteritems())

splitter = re.compile(r'(\s+|\^?[0-9a-zA-Z]+|[a-zA-Z]+|\^?\d+|[,\.~]?)')
words = splitter.findall(text)
for w in words:
    code = w
    upper = False
    if len(code) > 1 and code[0] == '^':
        code = code[1:]
        upper = True
    if strict:
        #print code, lorem.strict_str(code)
        code = lorem.strict_str(code)
    elif stricter:
        try:
            #print "\n'"+code+"'", lorem.base36decode(code)
            code = str(lorem.base36decode(code))
        except ValueError:
            pass
    if code in dict:
        sys.stdout.write(dict[code].title() if upper else dict[code])
    elif w == '~':
        sys.stdout.write('\n\n ')
    else:
        sys.stdout.write(w)

```

## lorem.py - library file

```
dictionary ={'consul': '64', 'discere': '378', 'virtute': '78', 'salutatus': '430', 'appareat': '362', 'doctus': '452', 'definiebas': '285', 'labitur': '399', 'vel': '34', 'te': '7', 'audire': '447', 'libris': '232', 'delicatissimi': '290', 'consequat': '194', 'veri': '351', 'fierent': '307', 'solet': '166', 'aliquip': '359', 'vero': '173', 'torquatos': '346', 'urbanitas': '483', 'habeo': '309', 'clita': '369', 'ferri': '390', 'integre': '313', 'nemore': '46', 'aeterno': '183', 'partem': '103', 'nusquam': '467', 'cetero': '191', 'natum': '465', 'fabulas': '215', 'eleifend': '454', 'voluptatibus': '79', 'apeirian': '187', 'diam': '291', 'interpretaris': '314', 'essent': '304', 'nec': '35', 'mollis': '319', 'erroribus': '52', 'mea': '30', 'ludus': '235', 'mel': '31', 'sint': '112', 'error': '51', 'mei': '39', 'decore': '126', 'repudiandae': '161', 'imperdiet': '393', 'soluta': '113', 'saperet': '337', 'aliquam': '184', 'invidunt': '460', 'dicta': '85', 'viderer': '441', 'nulla': '99', 'takimata': '263', 'insolens': '312', 'dicunt': '294', 'tractatos': '266', 'vim': '36', 'vis': '18', 'causae': '368', 'modus': '408', 'iusto': '143', 'vix': '16', 'oporteat': '74', 'zzril': '80', 'assentior': '189', 'meliore': '241', 'liber': '402', 'molestiae': '318', 'efficiendi': '87', 'usu': '29', 'lucilius': '403', 'ocurreret': '100', 'indoctum': '396', 'solum': '478', 'luptatum': '236', 'legendos': '230', 'voluptatum': '271', 'democritum': '128', 'detracto': '376', 'officiis': '153', 'sententiae': '477', 'salutandi': '429', 'prompta': '332', 'dictas': '202', 'accusamus': '355', 'alia': '81', 'conclusionemque': '449', 'phaedrum': '328', 'reque': '60', 'exerci': '305', 'minimum': '463', 'antiopam': '186', 'nullam': '246', 'similique': '261', 'regione': '258', 'quot': '335', 'mnesarchum': '147', 'inimicus': '92', 'aeque': '274', 'animal': '121', 'quod': '424', 'vitae': '43', 'dissentias': '296', 'affert': '119', 'numquam': '414', 'abhorreant': '273', 'gloriatur': '308', 'mutat': '410', 'disputando': '379', 'conceptam': '193', 'sit': '40', 'honestatis': '311', 'iracundia': '461', 'maluisset': '240', 'dicant': '377', 'electram': '134', 'petentium': '156', 'propriae': '333', 'recusabo': '336', 'adversarium': '118', 'oblique': '72', 'possim': '254', 'elit': '209', 'euripidis': '385', 'nonumy': '151', 'possit': '472', 'iudico': '462', 'omnes': '249', 'ius': '28', 'nostro': '152', 'eum': '25', 'repudiare': '427', 'etiam': '384', 'omittam': '247', 'ornatus': '154', 'suavitate': '262', 'civibus': '192', 'comprehensam': '84', 'dicit': '50', 'nibh': '321', 'facilis': '306', 'patrioque': '155', 'laboramus': '316', 'nihil': '243', 'odio': '468', 'ipsum': '315', 'tollit': '61', 'scribentur': '432', 'docendi': '204', 'quaerendum': '106', 'diceret': '200', 'fastidii': '136', 'liberavisse': '317', 'ei': '11', 'ea': '3', 'recteque': '425', 'ex': '4', 'eu': '10', 'et': '8', 'molestie': '98', 'aliquid': '446', 'aliquyam': '276', 'mediocritatem': '405', 'efficiantur': '133', 'menandri': '406', 'dissentiet': '67', 'pericula': '251', 'tamquam': '481', 'hendrerit': '310', 'tritani': '436', 'cibo': '83', 'scriptorem': '260', 'disputationi': '295', 'euismod': '455', 'qui': '17', 'equidem': '135', 'quo': '15', 'saepe': '163', 'accusata': '180', 'tibique': '265', 'homero': '140', 'referrentur': '257', 'neglegentur': '148', 'bonorum': '448', 'principes': '158', 'enim': '211', 'appellantur': '122', 'volumus': '443', 'graeco': '90', 'graeci': '138', 'persecuti': '56', 'posidonium': '253', 'percipitur': '470', 'dolorum': '297', 'option': '250', 'quando': '256', 'veritus': '172', 'quas': '421', 'epicuri': '300', 'gubergren': '139', 'accumsan': '354', 'graece': '457', 'nominati': '150', 'splendide': '343', 'ponderum': '75', 'sonet': '77', 'instructior': '141', 'omnis': '415', 'intellegam': '93', 'habemus': '392', 'verear': '439', 'corrumpit': '284', 'pri': '14', 'vocent': '484', 'expetendis': '387', 'duis': '132', 'soleat': '342', 'ridens': '162', 'tale': '480', 'latine': '228', 'aperiam': '277', 'mazim': '69', 'ignota': '222', 'elitr': '210', 'scripta': '259', 'argumentum': '188', 'veniam': '350', 'perpetua': '104', 'expetenda': '386', 'esse': '213', 'erant': '383', 'philosophia': '416', 'constituam': '282', 'ceteros': '124', 'sale': '428', 'inani': '394', 'oratio': '47', 'adipiscing': '116', 'alienum': '445', 'errem': '68', 'dolor': '205', 'probo': '418', 'elaboraret': '208', 'laoreet': '401', 'blandit': '123', 'quaestio': '476', 'delenit': '287', 'nobis': '244', 'sadipscing': '110', 'platonem': '329', 'contentiones': '374', 'quem': '422', 'dico': '201', 'oportere': '102', 'dolore': '453', 'laudem': '229', 'reprehendunt': '426', 'invenire': '95', 'consequuntur': '450', 'vocibus': '177', 'his': '38', 'signiferumque': '111', 'utroque': '348', 'congue': '372', 'intellegat': '142', 'qualisque': '58', 'complectitur': '371', 'meis': '70', 'unum': '438', 'prima': '474', 'nisl': '149', 'accommodare': '178', 'tation': '435', 'ancillae': '185', 'suscipit': '345', 'sed': '33', 'sea': '32', 'incorrupte': '395', 'labore': '400', 'postulant': '473', 'temporibus': '482', 'nostrum': '245', 'nostrud': '413', 'posse': '471', 'partiendo': '469', 'debitis': '197', 'aliquando': '358', 'eirmod': '207', 'detraxit': '130', 'malorum': '96', 'verterem': '267', 'melius': '54', 'viris': '442', 'altera': '120', 'mandamus': '145', 'magna': '237', 'amet': '361', 'omnium': '101', 'summo': '167', 'tempor': '169', 'facer': '216', 'facilisis': '217', 'placerat': '57', 'maiestatis': '404', 'doming': '206', 'evertitur': '456', 'quodsi': '76', 'assum': '278', 'cu': '13', 'mentitum': '71', 'quis': '59', 'duo': '23', 'eros': '302', 'puto': '475', 'feugiat': '137', 'pro': '21', 'inciderint': '45', 'lobortis': '233', 'dolores': '86', 'consulatu': '283', 'vituperatoribus': '269', 'senserit': '433', 'atqui': '190', 'suas': '479', 'pertinax': '327', 'eligendi': '381', 'impedit': '224', 'corpora': '196', 'agam': '275', 'vulputate': '115', 'fuisset': '220', 'volutpat': '272', 'noster': '322', 'rationibus': '160', 'offendit': '323', 'semper': '340', 'erat': '212', 'prodesset': '419', 'accusam': '179', 'in': '0', 'debet': '375', 'id': '20', 'cotidieque': '65', 'minim': '55', 'movet': '464', 'sensibus': '341', 'paulo': '324', 'omittantur': '248', 'audiam': '365', 'commune': '370', 'vivendo': '270', 'commodo': '280', 'fabellas': '88', 'brute': '367', 'persius': '252', 'delicata': '289', 'iuvaret': '144', 'graecis': '391', 'appetere': '363', 'deleniti': '288', 'legere': '231', 'aperiri': '82', 'choro': '63', 'deseruisse': '129', 'utamur': '347', 'iisque': '53', 'inermis': '91', 'concludaturque': '281', 'scripserit': '339', 'theophrastus': '264', 'eruditi': '303', 'noluisse': '412', 'impetus': '459', 'vide': '440', 'hinc': '221', 'dissentiunt': '131', 'cum': '37', 'has': '19', 'percipit': '325', 'tantas': '168', 'eripuit': '301', 'sumo': '434', 'perfecto': '42', 'interesset': '397', 'primis': '255', 'copiosae': '451', 'kasd': '227', 'munere': '409', 'facilisi': '44', 'scaevola': '431', 'explicari': '214', 'omnesque': '73', 'vidisse': '174', 'velit': '349', 'facete': '388', 'iudicabit': '225', 'timeam': '170', 'augue': '279', 'eloquentiam': '382', 'tota': '62', 'est': '41', 'persequeris': '105', 'iriure': '398', 'per': '22', 'epicurei': '299', 'reprimique': '109', 'necessitatibus': '411', 'adipisci': '182', 'atomorum': '48', 'sapientem': '338', 'definitionem': '127', 'definitiones': '286', 'stet': '114', 'probatus': '417', 'moderatius': '97', 'rebum': '107', 'intellegebat': '94', 'justo': '226', 'simul': '164', 'modo': '407', 'autem': '366', 'falli': '389', 'putant': '159', 'vituperata': '268', 'delectus': '198', 'adolescens': '356', 'praesent': '331', 'putent': '334', 'feugait': '218', 'maiorum': '238', 'dolorem': '380', 'singulis': '165', 'vivendum': '176', 'ubique': '171', 'forensibus': '219', 'illum': '223', 'eam': '27', 'illud': '458', 'mediocrem': '146', 'voluptaria': '444', 'admodum': '117', 'postea': '157', 'deserunt': '66', 'adhuc': '181', 'wisi': '353', 'ut': '9', 'malis': '239', 'reformidans': '108', 'eius': '298', 'vidit': '175', 'ad': '1', 'mundi': '320', 'fugit': '89', 'an': '2', 'consetetur': '373', 'at': '5', 'pertinacia': '326', 'albucius': '357', 'constituto': '125', 'no': '6', 'quaeque': '420', 'ne': '12', 'nam': '26', 'mucius': '242', 'dignissim': '203', 'alterum': '360', 'convenire': '195', 'denique': '199', 'dicam': '292', 'quidam': '423', 'assueverit': '364', 'lorem': '234', 'suscipiantur': '344', 'dicat': '293', 'voluptua': '352', 'ullamcorper': '437', 'nominavi': '466', 'eos': '24', 'porro': '330', 'consectetuer': '49'}

# base 36 impl from wikipedia
# http://en.wikipedia.org/wiki/Base_36#Python_implementation
def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    """Convert positive integer to a base36 string."""
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return alphabet[0]

    base36 = ''

    sign = ''
    if number < 0:
        sign = '-'
        number = - number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def base36decode(number):
    return int(number, 36)

def strict_code(code):
    return hex(int(code))[2:]

def strict_str(code):
    try:
        return str(int(code,16))
    except ValueError:
        return code

```

## process.py - creates the encoding dictionary

```
#!/usr/bin/env python

from nltk.probability import *
from nltk.tokenize import *
from sets import Set

txt = open('lorem', 'r').read()
tokens = list(WordTokenizer().tokenize(txt))
freq = FreqDist()
for w in tokens:
    freq.inc(w.lower())
tokens_sorted = sorted(freq, key=freq.get, reverse=True)

d = {}
star_count = 0
for i in tokens_sorted:
    d[i] = str(star_count)
    star_count += 1

print d

```

## First test case compressed

```
^M 8 6B 4F 2O, 1F 7A M C. ^BB 2H 18 2 10, 25 1P AG 13 D. ^I 1G 92 1, 7 8R 3Q S. ^0 11 5M 9D 9J. ^M 2 2O B1.~^5 Z 4N 5H 1D, M 9F 19 1. ^5 2V 1G 3E E, AU 1Z E 3. ^5 7Q 22 2K H, T 4V AO 0, W 7 5K 3Y. ^9Z 2M G 8, T 7 3C 1A.~^1P 4P 3M 6 O, I 4O 4P 4G 4, 1H CJ 57 S 1. ^1R 1A P 3, B J 5R 4W 4Y. ^V 1 B6 AW 42, BQ 17 7B C X, 1J 2Q 18 0 G. ^7 4T 2U V. ^V 4 2D A3 3H.~^0 Z 17 6D 9G, 2 Q 51 3A, 0 77 6K BL R. ^6 16 31 M, Y 0 96 89. ^R 5 1Q 6D 58, C 49 2N Y. ^7 2B 3Y P. ^2R 17 2Y U 1, 2A 2E 7A W 3.~^4J 7O L C. ^6 T 8V 6W 7Y, 1 3W D4 P, 1B 1L 43 N 9. ^4 CK 7P 4E S, N 4 4T 7O. ^D 12 6X 4J CM, X 1F 9G 9. ^G C9 4X C, V 67 5U 2N 1. ^7 W AN 5H 37, 66 4W 3P P 4.~^V 6D 2L 78 6, 2R 6F 4 H. ^A 3W 2A 8D X. ^0 O 76 1D. ^CX 3S R 3, 2 16 3P L, 5 Y B7 5D. ^U 1 3U AI BY, 4 49 43 8Q X. ^1B 1S 24 X K, 1Q 6A 2L L 8.~^E 1 5V 2Z 9J. ^K S 6A AQ 7U, 2H 7K 7X 1 J. ^2H 75 1D Q 1. ^4T 78 3E B L, 51 2L B 11, 4K 5B 41 D S. ^0 5C 7H G, 1H 9J X 7.~^11 6L 46 A. ^5 U 9P BI 23, O 2U 6W 2. ^X 3 2D 4Q 3F, M 5L 3R 0, B5 B9 2 Z. ^60 3K 4 X, V K 9Q 8O 2Y. ^P 5 7S 2N 7X. ^G B 35 98, 8W 3V B 15.~^2 V 4S 95 5E, J 0 5R A3. ^P 0 1B 27. ^E BW AH 5, 1A 3Q Q 2. ^25 8P 1L T A, I 7Q 6X 5.~^Q 8 39 3G 55. ^42 4H T 1. ^1 11 24 AL 2C. ^9 P 8A DA 9N, E K 6C 8I, 3 G 1Y 2U 7J.~^4N 2P L A, 54 8T 3 E. ^93 9W 88 K E, C 83 1R 44 E, D7 17 4G Y D. ^13 D 7D AQ 63. ^V 2 C2 5J 3Y, 51 5G B G. ^3 16 5D 1D L. ^8G BO I 7.~^M 4 6A 16 7W, 3 E 2A 3M, J 2 5M 2S. ^8J B9 V 1. ^74 7K O D, 2 2G 5N 3H Y. ^1B 62 1M T 9, 1N 73 CB B G, X C 1E 7H. ^R 1 2J 9U, 49 AE A S, B 9R 5F 3A 13. ^Q 26 61 2, M A 50 3V BF.~^5 16 41 27 10. ^5X 1R 7K 5 G, A 15 1J CN 9S. ^11 6J 2K 7K D, 12 7M 4S 19 K. ^0 6P 6T 27 R, 1U 9C 8N 3 Z. ^N 0 5V CB A2, S 5H 2X 4.~^2Z 5U F 1. ^2 I CS 1T, 7L 1T J 8. ^7I 3F 7T W 1. ^R 8 9E 19. ^F 3T 3N 2, 2Q 2Y F 4. ^H 5 7Z 3Y, A 1O 57 A4 W, I 25 2L A.~^0 9B 9A G, X 5 72 2K 3N, 4 F 6U 22. ^9 4W AX T, W 1 2T 71 AB. ^E 85 60 6F 6. ^51 7F BX A H, M 4 7Z BN.~^A L 47 6E. ^8X 6S 5Y 2 12, 93 4C B Q. ^1 I 7N 1V 33, 1 13 36 2P 27. ^4 9U 97 10. ^L 0 5A 3W, M 9X 56 6. ^7 5I 75 Q.~^7M 2T 0 Q, AK 2W 4B U 8. ^7N 1I 92 12 8, 9S 2W F 4. ^V 7 5T 1I 64, 14 66 9L 6. ^O 2 4V 4S, 74 5C P 4.~^5 O 25 2Q, 15 62 1V 0, 3G 2X 10 9. ^9G 38 58 M 7, 11 B 84 BL 52. ^2D 41 F 1. ^K 7S 7P F.~^3 7Q 30 T. ^4 G 4F 89, Q 1E 1I D2 K. ^B Z 3S 7V. ^5 AY 23 Q, 4Q 23 6E T 2, E 8 A7 5J 82.~^9L 94 8 E. ^B 62 8K U. ^S 3 67 6I 1R, BS 26 L 7, B3 3E K H. ^72 3D 30 10 2, A 45 83 22 F.~^4N 6R 5 L, 12 D 65 3Z AA. ^K M 60 6C, 9 4V 88 3A N. ^D V 5W 4G. ^H 1 5I 52 79, S 4 34 C0. ^36 7X 30 L 9. ^P 3D 1V 5. ^Q 1E 70 1.~^6 12 1Q 3L, 5P 77 49 2 13. ^7R 2A 3E 5 W, 8 BH 5O 55 T, 8W 1B 0 N. ^DC 5V 9T 6 H, V 26 3V A. ^2 7O 2P 32 E. ^D 38 6W M.~^16 50 31 A 10, X 3 5Q DG 9F, A8 99 0 11. ^3I 7J B H, 5B D1 5S 6 P. ^E A 6U 2O, E 1J 62 5S 6. ^I 2 6N 35, 1W 28 9 U, J 34 8C A. ^Z 4D 37 7C 1, L 6 5K BZ 9M.~^7W 2Y Z 0. ^4M 4H U 5, 0 15 2V 9V 63, 2D 4G P 4. ^AH 2E F 3, 0 15 91 6O 1T, 3 N 2G 6Z. ^U K 1J 4K 46, 3 H BD DF AJ, 11 D D6 1H.

```

Sources in my github repo.
> 7 votes

# Answer
## A simple but good JavaScript compressor (ratio=0.312)

Averaging the three test cases together, this program can reduce Lorem Ipsum text to 31.2% of its original size by converting each word to a base-36 number (**demo page**). I optimized my dictionary for the test cases, but the output from lipsum.com is not much less compressible if I also include its words in the dictionary.

### Example output for test case 3

> `@U6r8f36A!@9a1va6XH)K456m2w10)SD2fc28v!@6125VC)8u1g19D)Q7s9n9c16!@F17886g64!@3o2g6fYD!##@117o8q%)BXal2c2v)(Z3nbw4l!@c6377eMA!@IE1c2523)IC1s4y8k)C156q8k4p!@HJ1y75)%265y14)324fVQ!##@C4g6f2tU)&133i1n!@1s3o1gT&!@279lNF)b6ar56CJ!@F2s4qY!@G4m4q18)Ac5biY!##@DO4b5b!@137y5iB!@L^3f4k!@Y1pcb2tD)IA1m6k!@9r7aawH1a)GYaz2o)^Z1q5g4t!##@3m7kaaFN!@(61bm3tN)4vbmDU!@5k6bcpR*!@7v2tSF)173a7t76H)18H1w42!@A3c7q49R)D1c2q2iN)C3h8oV!@PDbe2j)15K1zcb!##@881db3Y()7u51OC!@6q2458PA!@153a385xB!@4h2aB15!##@at1g1n(Y)4a4j%M)cf291u^12!@E5p2411!@5v2j18^)L6t6o7nD!@155v1q3wC)H1h93W!@akc7DN)12&2q98!@1637574d^!##@UB1j1i!@1t2q6x&O)^S335s2n)428h2lGI!@J^26717v!@5j8bGL)I&ca3z)*161i5x1f!@UK4s7k39)18998y8k%)O3y2eD!@27a8aiX(!##@E3h4kO!@1e3g7xM*!@a926EL)173d6163D!@C4m5nI!@C6e46T)3x2bWA!##@*271s7kT)3o1d7jHS!@%1a6z1m!@633e8z^U!@O4j918eC!@KZ1w1q)G16675z2i!##@Dc58174U)B8d9411)W2s61F!@H48bpc01a!@16*1pb1)N4o2jG!@601rJF)O(afam42!@3s2xIK!##@A4b2a3uR!@U*4m9y!@M&1ib890)3r6v5b13C!@898w2bW&!@1c4yd5A11)5h3ybyPK!##@M(2y1v2r!@%2aag7zZ)S8x5m2kE!@MD6020)L7t1nQ!@*452g7aX!##@171w8l77E)16&2c3z4r)Eap897rJ!@5y3766UQ)5dcdX^!@956j1m^17)9197bc%16)O43a7K!@956f14E)*265u36Y!@19D923gbb)BI5w4o)&81d38wZ!@6q1nA12!##@ZK1w1b)F18bo3v!@7u2814%!@14&23ab39)a53aE12)111s587hG!@(3x7j6e18)9e8l6jA19)P5p7pH!@O7c23C)U6ibgbcE)H1a3g9u6o!@az3s7717C)IGcy2p!##@I2h294d(!@T1oa1()Yajbt6oE!@HT3b70)289iGL!@4y6x2o18A!##@XH1t29)D146u2ab3!@bnc319^)J*a71l8p!@G153q23!@G151gae52)1t73NK!##@BYa33y!@17B2dcd)Pca3s&!@K4ibv85W)P726bbk%)OCb75z1n!@(133c9d41!##@UF1h23!@ad5010^)9p1f15A)K11988e!@8y3x8iI%)CY2u3d4i!@C8s2s7gJ)Z^23319c!@^4j6z6kM)&X267b6e)1k3a43IH!##@1g1lF10)(1d4d14!@&1o4aW!@IF3m2c3l)2mbz9bQ13!@9x6pCM)&d24w15)K181c4a2a!@O6xan46G)RH6s8c!##@1b9z(13)1q487zGI!@5e2j4dDM!@C1j4051T)b978MQ!@6h5h5mC16)B272x19!##@1a7d4aB!@8m2zR^)%622eL!@4v3917G)&X1n522l!@5c2t12%!@17723kE)%6n8j13)%Tav8r!@1t9f2c11(!@1aQ2scz9h)E1y9oZ!##@9j87Q18)1h999zAY)8n514rUD!@LDas8b48)1z4a7b10D!@1126ax1lB)A3k864r1a)67b9BJ!@FM23dg!@U403pG)7730HV!@&123c32!@FN2f6y!##@Q4570R)7d7fA13!@Acv4z561a)FL3wba39!@RB6cdd7i)G218g12!@2hbrBW)Y5w55avG)1v4614QA!`

---

### Code listing

HTML page
```
<textarea id=dict>
in
an
ad
ex
ea
at
no
te
ut
et
eu
ei
ne
quo
pri
cu
vix
qui
vis
has
pro
id
per
eum
eos
duo
nam
usu
ius
eam
vel
sed
sea
mel
mea
vim
nec
cum
sit
mei
his
est
perfecto
vitae
oratio
nemore
inciderint
facilisi
tota
tollit
reque
quis
qualisque
placerat
persecuti
minim
melius
iisque
erroribus
error
dicit
consectetuer
atomorum
zzril
voluptatibus
virtute
sonet
quodsi
ponderum
oporteat
omnesque
oblique
mentitum
meis
mazim
errem
dissentiet
deserunt
cotidieque
consul
choro
vulputate
stet
soluta
sint
signiferumque
sadipscing
reprimique
reformidans
rebum
quaerendum
persequeris
perpetua
partem
oportere
omnium
ocurreret
nulla
molestie
moderatius
malorum
invenire
intellegebat
intellegam
inimicus
inermis
graeco
fugit
fabellas
efficiendi
dolores
dicta
comprehensam
cibo
aperiri
alia
vocibus
vivendum
vidit
vidisse
vero
veritus
ubique
timeam
tempor
tantas
summo
solet
singulis
simul
saepe
ridens
repudiandae
rationibus
putant
principes
postea
petentium
patrioque
ornatus
officiis
nostro
nonumy
nominati
nisl
neglegentur
mnesarchum
mediocrem
mandamus
iuvaret
iusto
intellegat
instructior
homero
gubergren
graeci
feugiat
fastidii
equidem
electram
efficiantur
duis
dissentiunt
detraxit
deseruisse
democritum
definitionem
decore
constituto
ceteros
blandit
appellantur
animal
altera
affert
adversarium
admodum
adipiscing
volutpat
voluptatum
vivendo
vituperatoribus
vituperata
verterem
tractatos
tibique
theophrastus
takimata
suavitate
similique
scriptorem
scripta
regione
referrentur
quando
primis
possim
posidonium
persius
pericula
option
omnes
omittantur
omittam
nullam
nostrum
nobis
nihil
mucius
meliore
maluisset
malis
maiorum
magna
luptatum
ludus
lorem
lobortis
libris
legere
legendos
laudem
latine
kasd
justo
iudicabit
impedit
illum
ignota
hinc
fuisset
forensibus
feugait
facilisis
facer
fabulas
explicari
esse
erat
enim
elitr
elit
elaboraret
eirmod
doming
dolor
docendi
dignissim
dictas
dico
diceret
denique
delectus
debitis
corpora
convenire
consequat
conceptam
civibus
cetero
atqui
assentior
argumentum
apeirian
antiopam
ancillae
aliquam
aeterno
adipisci
adhuc
accusata
accusam
accommodare
wisi
voluptua
veri
veniam
velit
utroque
utamur
torquatos
suscipit
suscipiantur
splendide
soleat
sensibus
semper
scripserit
sapientem
saperet
recusabo
quot
putent
propriae
prompta
praesent
porro
platonem
phaedrum
pertinax
pertinacia
percipit
paulo
offendit
noster
nibh
mundi
mollis
molestiae
liberavisse
laboramus
ipsum
interpretaris
integre
insolens
honestatis
hendrerit
habeo
gloriatur
fierent
facilis
exerci
essent
eruditi
eros
eripuit
epicuri
epicurei
eius
dolorum
dissentias
disputationi
dicunt
dicat
dicam
diam
delicatissimi
delicata
deleniti
delenit
definitiones
definiebas
corrumpit
consulatu
constituam
concludaturque
commodo
augue
assum
aperiam
aliquyam
agam
aeque
abhorreant
voluptaria
volumus
viris
viderer
vide
verear
unum
ullamcorper
tritani
tation
sumo
senserit
scribentur
scaevola
salutatus
salutandi
sale
repudiare
reprehendunt
recteque
quod
quidam
quem
quas
quaeque
prodesset
probo
probatus
philosophia
omnis
numquam
nostrud
noluisse
necessitatibus
mutat
munere
modus
modo
menandri
mediocritatem
maiestatis
lucilius
liber
laoreet
labore
labitur
iriure
interesset
indoctum
incorrupte
inani
imperdiet
habemus
graecis
ferri
falli
facete
expetendis
expetenda
euripidis
etiam
erant
eloquentiam
eligendi
dolorem
disputando
discere
dicant
detracto
debet
contentiones
consetetur
congue
complectitur
commune
clita
causae
brute
autem
audiam
assueverit
appetere
appareat
amet
alterum
aliquip
aliquando
albucius
adolescens
accusamus
accumsan
vocent
urbanitas
temporibus
tamquam
tale
suas
solum
sententiae
quaestio
puto
prima
postulant
possit
posse
percipitur
partiendo
odio
nusquam
nominavi
natum
movet
minimum
iudico
iracundia
invidunt
impetus
illud
graece
evertitur
euismod
eleifend
dolore
doctus
copiosae
consequuntur
conclusionemque
bonorum
audire
aliquid
alienum
non
eget
ac
a
vestibulum
nunc
mauris
tincidunt
pellentesque
ante
donec
turpis
orci
massa
arcu
ultrices
luctus
neque
tortor
dui
metus
posuere
leo
ligula
libero
sem
nisi
quam
sapien
risus
mi
faucibus
purus
consectetur
malesuada
urna
tellus
lectus
felis
egestas
porta
varius
tristique
lacus
dictum
convallis
rutrum
morbi
rhoncus
aliquet
sodales
viverra
sollicitudin
tempus
suspendisse
lacinia
interdum
scelerisque
fusce
fringilla
sagittis
pretium
cursus
auctor
condimentum
ultricies
elementum
gravida
pulvinar
porttitor
pharetra
vivamus
integer
bibendum
vehicula
iaculis
fermentum
proin
ornare
mattis
cras
curabitur
aenean
quisque
phasellus
venenatis
maecenas
dapibus
curae
cubilia
torquent
taciti
sociosqu
nostra
litora
inceptos
himenaeos
conubia
class
aptent
platea
hac
habitasse
dictumst
senectus
netus
habitant
fames
everti
sociis
sanctus
ridiculus
penatibus
parturient
nonummy
natoque
nascetur
mus
montes
magnis
dis
utinam
ullum
harum
alii
potenti
populo
legimus
idque
periculis
novum
labores
deterruisset
enean
</textarea>

<textarea rows=25 cols=80 id=box></textarea>
<button id=comp>compress</button><button id=decomp>decompress</button>

```
Source code (uses jQuery 1.5.2)
```
var $box = $('#box'),
    dict = $('#dict').val().split(/\n/g).filter(function(v) {
        return v.length;
    }),
    CODE = {
        COMMA: 0,
        FULL_STOP: 1,
        SHIFT: 2,
        NEWLINE: 3,
        UNCOMP: 4,
        FIRST_WORD: 5
    },
    base36UpperAlphabet = ")!@#$%^&*(ABCDEFGHIJKLMNOPQRSTUVWXYZ";

function compress(orig) {
    function writeCode(n) {
        if(n < 36) {
            comped += base36UpperAlphabet[n];
        } else {
            comped += n.toString(36);
        }
    }

    function writeUncompressed(d) {
        comped += d;
        comped += '.';
    }

    function writeCurrentWord() {
        if(word) {
            // look up word in dictionary
            var wordIndex = dict.indexOf(word), shift = false;

            // try lowercasing first letter
            if(wordIndex < 0) {
                shift = true;
                wordIndex = dict.indexOf(word[0].toLowerCase() + word.slice(1));
            }

            if(wordIndex < 0) {
                writeCode(CODE.UNCOMP);
                writeUncompressed(word);
            } else {
                if(shift) writeCode(CODE.SHIFT);
                writeCode(wordIndex + CODE.FIRST_WORD);
            }
        }
        word = '';
    }

    var comped = '', word = '';
    for(var i = 0; i < orig.length; ++i) {
        var ch = orig[i];
        switch(ch) {
            case ' ': writeCurrentWord(); break;
            case ',': writeCurrentWord(); writeCode(CODE.COMMA); break;
            case '.': writeCurrentWord(); writeCode(CODE.FULL_STOP); break;
            case '\n': writeCurrentWord(); writeCode(CODE.NEWLINE); break;
            default: word += ch;
        }
    }

    writeCurrentWord();
    return comped;
}

function decompress(comped) {
    function readCode() {
        var c = comped[i++],
            n = base36UpperAlphabet.indexOf(c);
        if(n >= 0) return n;
        return parseInt(c + comped[i++], 36);
    }
    function readUncompressed() {
        var c, d = '';
        while((c = comped[i++]) != '.') d += c;
        return d;
    }

    var code, i = 0, shift = false, orig = '';
    while(i < comped.length) switch(code = readCode()) {
            case CODE.COMMA: orig += ','; break;
            case CODE.FULL_STOP: orig += '.'; break;
            case CODE.SHIFT: shift = true; break;
            case CODE.NEWLINE: orig += '\n'; break;
            case CODE.UNCOMP: orig += ' ' + readUncompressed(); break;
            default:
            var word = dict[code - CODE.FIRST_WORD];
            orig += ' ' + (shift ? word[0].toUpperCase() + word.slice(1) : word);
            shift = false;
    }

    return orig.slice(1);
}

$('#comp').click(function() {
    var orig = $box.val(), comped = compress(orig);
    $box.val(comped);
    alert('ratio=' + (comped.length / orig.length).toFixed(5));
});

$('#decomp').click(function() {
    $box.val(decompress($box.val()));
});

```
Command for generating a frequency-sorted dictionary
```
tr '[:upper:]' '[:lower:]' < lipsum.txt | tr -cs '[:lower:]' '\n' | sort | uniq -c | sort -rn | cut -c9- > lipsumwords.txt

```
> 4 votes

# Answer
## JavaScript, ≈ 11%

I can't figure out how to decompress it yet, but I think it is possible. I'll edit it when I figure out how, but if anybody here does before me, please tell me how!

This one can compress to ≈ 45%, but when run recursively settles down at ≈ 11% for the one I tried.

```
function liCompress(text, s) {
    // Some variables used throughout the function
    var c, i, result = [];

    // First, we get the unique characters in the text.
    var uniqueCharacters = '';
    for(i = 0; i < text.length; i++) {
        c = text.charAt(i);
        if(uniqueCharacters.indexOf(c) === -1) uniqueCharacters += c;
    }

    // Add them to the string:
    result.push(uniqueCharacters.length);
    for(i = 0; i < uniqueCharacters.length; i++) result.push(uniqueCharacters.charCodeAt(i));

    // Now we convert the base-x string to base-256.
    var total = 0, exponent = 0;
    for(i = 0; i < text.length; i++) {
        c = text.charAt(i);
        var n = uniqueCharacters.indexOf(c);
        total += n * Math.pow(uniqueCharacters.length, i - exponent);

        if(total > 255) {
            result.push(total % 256);
            total = total === 256 ? 0 : 1;
            exponent = i + 1;
        }
    }

    // Return the string representation of the result.
    var r = String.fromCharCode.apply(String, result);
    if(!s) {
        var x = liCompress(r, true);
        return x.length < r.length ? liCompress(r) : r;
    }
    return r;
}

```
> 3 votes

---
Tags: code-challenge, optimization, compression
---