title: Implement glob Matcher

text:
# Question
Title: Implement glob Matcher
Implement a function of pattern and string to be matched, return true if the pattern matches the WHOLE string, otherwise false.

Our glob pattern syntax is:

* `?` matches any one character
* `+` matches one or more characters
* `*` matches zero or more characters
* `\` escapes

Rules:

* No eval, no converting into regular expression, no calling a system glob function.
* I/O are not required: you can just write a function
* Shortest wins

Examples:

```
glob('abc', 'abc') => true
glob('abc', 'abcdef') => false IMPORTANT!
glob('a??', 'aww') => true
glob('a*b', 'ab') => true
glob('a*b', 'agwijgwbgioeb') => true
glob('a*?', 'a') => false
glob('?*', 'def') => true
glob('5+', '5ggggg') => true
glob('+', '') => false
glob('a\*b', 'a*b') => true

```

Here is a tip to get started: http://en.wikipedia.org/wiki/Backtracking

# Answer
## Golfscript - 82 chars

```
{1,\@n+:|;{:<;{:I)I|="\\+*?"[<]+?[{|=<={I))}*}I~{I\C}{}.{;}]=~}:C%}/{|>'*'-n=},}:g

```

Assumes that there are no newlines in the strings. Returns an empty array for false, and a non-empty array for true (consistent with golfscript definition of true/false).

This is a non-recursive solution (except for consecutive `*`s), which maintains a list of the positions in the pattern string `i` such that `pattern[0..i]` matches `string[0..cur]`.

This has the potential to run for a very long time. You can add `.&` after `:C%` to prevent this.
> 4 votes

# Answer
## Haskell, 141 characters

```
c('\\':a:z)s=a&s>>=c z
c(a:z)s=a%s>>=c z
c[]s=[null s]
p&(a:z)|a==p=[z]
_&_=[]
'?'%(a:z)=[z]
'*'%a=a:'+'%a
'+'%(a:z)='*'%z
l%a=l&a
g=(or.).c

```

Works for all input, both patterns and strings to match against. Handles trailing backslash in the pattern as a literal match (behavior was unspecified.)

This can be run with the following test driver:

```
main = do
    globtest "abc" "abc"    True
    globtest "abc" "abcdef" False
    globtest "a??" "aww"    True
    globtest "a*b" "ab"     True
    globtest "a*b" "agwijgwbgioeb" True
    globtest "a*?" "a"      False
    globtest "?*" "def"     True
    globtest "5+" "5ggggg"  True
    globtest "+" ""         False
    globtest "a\\*b" "a*b"  True
  where
    globtest p s e =
      if g p s == e
        then putStrLn "pass"
        else putStrLn$"fail: g " ++ show p ++ " " ++ show s ++ " /= " ++ show e

```

---

**Update:** I wrote a blog post about this particular answer, as I think it shows off well how Haskell so easily encodes the problem.

---

* Edit: (181 -\> 174) replaced `d` and `m` with operators
* Edit: (174 -\> 151) inlined `r` into `c`
* Edit: (151 -\> 149) removed an unnecessarily generated option in the `+` case
* Edit: (149 -\> 141) removed an unnecessary clause for `%`, which was handled by `&`
> 5 votes

# Answer
## JavaScript - 259 characters

My implementation is very recursive, so the stack will overflow if an extremely long pattern is used. Ignoring the plus sign (which I could have optimized but chose not to for simplicity), one level of recursion is used for each token.

```
glob=function f(e,c){var b=e[0],d=e.slice(1),g=c.length;if(b=="+")return f("?*"+d,c);if(b=="?")b=g;else if(b=="*"){for(b=0;b<=g;++b)if(f(d,c.slice(b)))return 1;return 0}else{if(b=="\\"){b=e[1];d=e.slice(2)}b=b==c[0]}return b&&(!d.length&&!g||f(d,c.slice(1)))}

```

The function sometimes returns a number instead of a boolean. If that is a problem, you can use it as `!!glob(pattern, str)`.

---

Ungolfed (unminified, rather) to serve as a useful resource:

```
function glob(pattern, str) {
    var head = pattern[0], tail = pattern.slice(1), strLen = str.length, matched;
    if(head == '+') {
        // The plus is really just syntactic sugar.
        return glob('?*' + tail, str);
    }
    if(head == '?') { // Match any single character
        matched = strLen;
    } else if(head == '*') { // Match zero or more characters.
        // N.B. I reuse the variable matched to save space.
        for(matched = 0; matched <= strLen; ++matched) {
            if(glob(tail, str.slice(matched))) {
                return 1;
            }
        }
        return 0;
    } else { // Match a literal character
        if(head == '\\') { // Handle escaping
            head = pattern[1];
            tail = pattern.slice(2);
        }
        matched = head == str[0];
    }
    return matched && ((!tail.length && !strLen) || glob(tail, str.slice(1)));
}

```

Note that indexing into characters of a string as for array elements is not part of the older (ECMAScript 3) language standard, so it may not work in older browsers.
> 2 votes

# Answer
# PHP - ~~275~~ 243 characters

```
<?function g($P,$I){$o='array_shift';if(@$I[0]==="")return 0;for(;$P;$o($P)){$p=$P[0];if($p=='?'|$p=='+'&&@$N===$o($I))return 0;if($p=='+'|$p=='*'&&$I&&g($P,array_slice($I,1)))return 1;if(!strpos(" ?+*\\",$p)&&$p!==$o($I))return 0;}return!$I;}

```

Ungolfed:

```
<?php

function g($P,$I) {
        if ($I && $I[0] === "") return false;
        for(;$P;array_shift($P)) {
                $p = $P[0];
                if( $p == '?' || $p == '+') {
                        if (NULL === array_shift($I)) {
                                return false;
                        }
                }
                if( $p=='+' || $p=='*' ) {
                        if ($I && g($P, array_slice($I,1))) {
                                return true;
                        }
                }
                if (!strpos(" ?+*\\",$p) && $p !== array_shift($I)) {
                        return false;
                }
        }
        return !$I;
}

function my_glob($pattern,$subject) {
    return !!g(str_split($pattern),str_split($subject));
}

```
> 2 votes

# Answer
## Overly Verbose Python (384 367 Characters)

```
t=lambda a:a[1:]
h=lambda a:a[0]
n=lambda p,s:s and(h(p)==h(s)and m(t(p),t(s)))
def m(p,s):
 if not p:
  return not s
 else:
  return {
   '?':lambda p,s:s and m(t(p),t(s)),
   '+':lambda p,s:s and(m(p,t(s))or m(t(p),t(s))),
   '*':lambda p,s:m(t(p),s)or(s and m(p,t(s))),
   '\\':lambda p,s:n(t(p),s),
  }.get(h(p),n)(p,s)
glob=lambda p,s:not not m(p,s)

```

It's not the shortest, but it's nice and functional. The dispatch dict thing in the middle could presumably be rewritten as a disjunction over `(h(p) == '?') and (? lambda body)` type things. Defining that h operator costs me some characters for no benefit, but its nice to have a keyword for head.

I'd like to have a crack at golfscripting it later if time permits.

edit: removed unnecessary third branch in '\*' case after reading user300's ruby answer
> 2 votes

# Answer
# Ruby - ~~199~~ 171

```
g=->p,s{x=(b=->a{a[1..-1]})[p];y=s[0];w=b[s];v=p[0];_=->p,s{p[0]==y&&g[x,w]}
v==??? g[x,y&&w||s]:v==?+? y&&g[?*+x,w]:v==?*?
y&&g[p,w]||g[x,s]:v==?\\? _[x,s]:v ? _[p,s]:!y}

```

Ungolfed:

```
def glob(pattern, subject)
        b=->a{a[1..-1]}
        _=->p,s{ p[0]==s[0] && glob(b[p],b[s]) }
        ({
                ??=>->p,s { glob(b[p], s[0] ? b[s] : s) },
                ?+=>->p,s { s[0] && glob(?*+b[p], b[s]) },
                ?*=>->p,s { s[0] && glob(p,b[s]) || glob(b[p],s) },
                ?\\=>->p,s{ _[b[p],s] },
                nil=>->p,s{ !subject[0] }
        }[pattern[0]] || _)[pattern, subject]
end

```

Tests:

```
p glob('abc', 'abc')
p glob('abc', 'abcdef')
p glob('a??', 'aww')
p glob('a*b', 'ab')
p glob('a*b', 'agwijgwbgioeb')
p glob('a*?', 'a')
p glob('?*', 'def')
p glob('5+', '5ggggg')
p glob('+', '')

```

Inspired by roobs' answer
> 2 votes

# Answer
## Shorter Snappier Python 2.6 (272 characters)

**golfed:**

```
n=lambda p,s:p[0]==s[0]and m(p[1:],s[1:])
def m(p,s):
 q,r,t,u=p[0],p[1:],s[0],s[1:]
 return any((q=='?'and(t and m(r,u)),q=='+'and(t and(m(p,u)or m(r,u))),q=='*'and(m(r,s)or(t and m(p,u))),q=='\\'and n(r,s),q==t==0))or n(p,s)
glob=lambda*a:m(*[list(x)+[0]for x in a])

```

**ungolfed:**

```
TERMINATOR = 0

def unpack(a):
    return a[0], a[1:]

def terminated_string(s):
    return list(s) + [TERMINATOR]

def match_literal(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return p_head == s_head and match(p_tail, s_tail)

def match(p, s):
    p_head, p_tail = unpack(p)
    s_head, s_tail = unpack(s)
    return any((
        p_head == '?' and (s_head and match(p_tail, s_tail)),
        p_head == '+' and (s_head and(match(p, s_tail) or match(p_tail, s_tail))),
        p_head == '*' and (match(p_tail, s) or (s_head and match(p, s_tail))),
        p_head == '\\' and match_literal(p_tail, s),
        p_head == s_head == TERMINATOR,
    )) or match_literal(p, s)

def glob(p, s):
    return match(terminated_string(p), terminated_string(s))

```

**featuring:**

* lazily-evaluated logical mess!
* C style strings!
* cute multiple comparison idiom!
* plenty of ugly!

credit to user300's answer for illustrating how things are simplified if you can get some kind of terminator value when popping the head from an empty string.

i wish the head/tail unpacking could be performed inline during the declaration of m's arguments. then m could be a lambda, just like its friends n and glob. python2 cannot do it, and after a bit of reading, it looks like python3 cannot either. woe.

**testing:**

```
test_cases = {
    ('abc', 'abc') : True,
    ('abc', 'abcdef') : False,
    ('a??', 'aww') : True,
    ('a*b', 'ab') : True,
    ('a*b', 'aqwghfkjdfgshkfsfddsobbob') : True,
    ('a*?', 'a') : False,
    ('?*', 'def') : True,
    ('5+', '5ggggg') : True,
    ('+', '') : False,
}
for (p, s) in test_cases:
    computed_result = glob(p, s)
    desired_result = test_cases[(p, s)]
    print '%s %s' % (p, s)
    print '\tPASS' if (computed_result == desired_result) else '\tFAIL'

```
> 2 votes

# Answer
## C function - 178 necessary characters

Compiled with GCC, this produces no warnings.

```
#define g glob
int g(p,s)const char*p,*s;{return*p==42?g(p+1,s)||(*s&&g(p,
s+1)):*p==43?*s&&(g(p+1,++s)||g(p,s)):*p==63?*s&&g(p+1,s+1)
:*p==92?*++p&&*s++==*p++&&g(p,s):*s==*p++&&(!*s++||g(p,s));}
#undef g

```

The first and last lines are not included in the character count. They are provided for convenience only.

Blown-up:

```
int glob(p,s)
const char *p, *s; /* K&R-style function declaration */
{
    return
        *p=='*'  ? glob(p+1,s) || (*s && glob(p,s+1)) :
        *p=='+'  ? *s && (glob(p+1,++s) || glob(p,s)) :
        *p=='?'  ? *s && glob(p+1,s+1)                :
        *p=='\\' ? *++p && *s++==*p++ && glob(p,s)    :
        *s==*p++ && (!*s++ || glob(p,s));
}

```
> 2 votes

# Answer
**Python** (454 characters)

```
def glob(p,s):
  ps,pns=[0],[]
  for ch in s:
    for i in ps:
      if i<0:
        pns+=[i]
        if i>-len(p) and p[-i]==ch:pns+=[-i]
      elif i<len(p):
        pc=p[i]
        d={'?':[i+1],'+':[i,-i-1],'*':[i+1,-i-1]}
        if pc in d:pns+=d[pc]
        else:
          if pc=='\\':pc=p[i+1]
          if pc==ch:pns+=[i+1]
    ps,pns=pns,[]
  if (s or p in '*') and (len(p) in ps or -len(p)+1 in ps or -len(p) in ps): return True
  return False

```
> 1 votes

# Answer
# D: 363 Characters

```
bool glob(S)(S s,S t){alias front f;alias popFront p;alias empty e;while(!e(s)&&!e(t)){switch(f(s)){case'+':if(e(t))return false;p(t);case'*':p(s);if(e(s))return true;if(f(s)!='+'&&f(s)!='*'){for(;!e(t);p(t)){if(f(s)==f(t)&&glob(s,t))return true;}}break;case'\\':p(s);if(e(s))return false;default:if(f(s)!=f(s))return false;case'?':p(s);p(t);}}return e(s)&&e(t);}

```

More Legibly:

```
bool glob(S)(S s, S t)
{
    alias front f;
    alias popFront p;
    alias empty e;

    while(!e(s) && !e(t))
    {
        switch(f(s))
        {
            case '+':
                if(e(t))
                    return false;

                p(t);
            case '*':
                p(s);

                if(e(s))
                    return true;

                if(f(s) != '+' && f(s) != '*')
                {
                    for(; !e(t); p(t))
                    {
                        if(f(s) == f(t) && glob(s, t))
                            return true;
                    }
                }

                break;
            case '\\':
                p(s);

                if(e(s))
                    return false;
            default:
                if(f(s) != f(s))
                    return false;
            case '?':
                p(s);
                p(t);
        }
    }

    return e(s) && e(t);
}

```
> 1 votes

# Answer
## golfscript

```
{{;;}2$+}:x;{x if}:a;{x\if}:o;{1$1$}:b;{(@(@={\m}a}:r;{b(63={\({\m}a}a{b(43={\({\b m{'+'\+m}o}a}a{b(42={b m{\({\'*'\+m}a}o}a{b(92={r}a{b 0=0=\0=0=*{r}o}o}o}o}o}:m;{[0]+\[0]+m}:glob;

```

it's built out of functions that consume two arguments from the stack, s and p, and produce a single boolean return value. there's a bit of mucking around to make that compatible with the lazy and and lazy or operators. i really doubt this approach is anywhere near optimal, or even in the right direction.

there's also a few entertainingly stupid moments, such as popping a `'*'` off the pattern, consuming the `'*'` in a comparison, only to realise that the subsequent branch doesn't match. in order to go down the other branch, we need the pattern with the `'*'` on the front, but we've consumed that original pattern when we popped the `'*'`, and we consumed the `'*'`, so to get ourselves the pattern again we load a shiny new string constant `'*'`, and prepend it in place. it gets even uglier because for some reason the character matching needs to be done with ascii values, but prepending back onto the string needs strings.

**less golfed golfscript**

```
{[0]+}:terminate_string;
{{;;}2$+if}:_and;
{{;;}2$+\if}:_or;
{1$1$}:branch;
{(@(@={\match}_and}:match_literal;
{0=0=\0=0=*}:match_terminator;
{(92={match_literal}_and}:match_escape;
{(63={\({\match}_and}_and}:match_wildcard;
{(43={\({\branch match{'+'\+match}_or}_and}_and}:match_wildcard_plus;
{(42={branch match{\({\'*'\+match}_and}_or}_and}:match_wildcard_star;
{branch match_wildcard{branch match_wildcard_plus{branch match_wildcard_star{branch match_escape{branch match_terminator{match_literal}_or}_or}_or}_or}_or}:match;
{terminate_string\terminate_string match}:glob;

```

**tests**

```
{2$2$glob = "test passed: " "test FAILED: " if print \ print ' ; ' print print "\n" print}:test_case;

'abc' 'abc' 1 test_case
'abc' 'abcdef' 0 test_case
'a??' 'aww' 1 test_case
'a*b' 'ab' 1 test_case
'a*b' 'agwijgwbgioeb' 1 test_case
'a*?' 'a' 0 test_case
'?*' 'def' 1 test_case
'5+' '5ggggg' 1 test_case
'+' '' 0 test_case

```
> 1 votes

# Answer
# C# (251 chars)

```
static bool g(string p,string i){try{char c;System.Func<string,string>s=t=>t.Remove(0,1);return p==i||((c=p[0])==92?p[1]==i[0]&g(s(s(p)),s(i)):c==42?g(s(p),i)||g(p,s(i)):c==43?g(s(p),s(i))|g(p,s(i)):g(s(p),s(i))&(c==i[0]|c==63));}catch{return false;}}

```

### Slightly more readable:

```
static bool g(string p /* pattern */, string i /* input string */)
{
    // Instead of checking whether we’ve reached the end of the string, just
    // catch the out-of-range exception thrown by the string indexing operator
    try
    {
        char c;

        // .Remove(0,1) is shorter than .Substring(1)...
        System.Func<string, string> s = t => t.Remove(0, 1);

        // Note that every glob matches itself!† This saves us having to write
        // “(p=="" & i=="")” which would be much longer — very convenient!
        return p == i || (

            // backslash escapes
            (c = p[0]) == 92 ? p[1] == i[0] & g(s(s(p)), s(i)) :

            // '*' — need “||” so that s(i) doesn’t throw if the first part is true
            c == 42 ? g(s(p), i) || g(p, s(i)) :

            // '+'
            c == 43 ? g(s(p), s(i)) | g(p, s(i)) :

            // '?' or any other character
            g(s(p), s(i)) & (c == i[0] | c == 63)
        );
    }

    // If we ever access beyond the end of the string, we know the glob doesn’t match
    catch { return false; }
}

```

<sub> I know, I know... except for globs containing the backslash. Which is really unfortunate. It would have been really clever otherwise. :(</sub>
> 1 votes

---
Tags: code-golf, interpreter, regular-expression
---


title: "list comprehension" in php.

text:
# Question
Title: "list comprehension" in php.
PHP has closures, let's play around with them.

I have some arrays similar to, `$wannabelist = array (1, 2, 3, 4, 5, 6)`.

I want to do this: `compr( expression($params), $wannabelist, $wannabilist2 ...)`.

compr() should do the following:

1. Take all the possible combinations of elements of the arrays given as parameters;
2. Pass each of them to the expression passed as first parameter;
3. Yield the result.

A particularly satisfying function will:

1. Avoid changing the value of any variable;
2. Be elegant;
3. Contain an inordinate amount of nested parenthesis/brackets;
4. Avoid foreach() loops.

# Answer
First, a few neat things about list comprehensions, from a Haskell perspective:

* The list monad in Haskell is set up so any list comprehension can be transformed into do notation rather easily:

```
> [(i,j) | i <- [1..3], j <- [1..3]]
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
> do {i <- [1..3]; j <- [1..3]; return (i,j)}
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

```
* Haskell has a `sequence` function that takes a list of "actions" in a monad and returns a list of the results:

```
> sequence [getLine, getLine, getLine]
one
two
three
["one","two","three"]

```
* Consequently, using `sequence` with the list monad gives you combinations for free:

```
> do {i <- [1..3]; j <- [1..3]; return [i,j]}
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
> sequence [[1..3], [1..3]]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

```

Hence, the `sequence` function is very similar to the `compr` function asked for. It just needs to be wrapped and mapped a bit:

```
function compr()
{
    $args = func_get_args();
    $f = $args[0];
    $call_f = function($array) use ($f) {
        return call_user_func_array($f, $array);
    };
    return array_map($call_f, sequence(listMonad(), array_slice($args, 1)));
}

```

Now, without further ado, here is a nearly direct translation of the list monad and `sequence` function from Haskell to PHP:

```
# instance  Monad []  where
#     m >>= k          = concat (map k m)
#     return x         = [x]
#     fail s           = []
function listMonad()
{
    return (object) array(
        'bind'   => function($m, $k) {
            return call_user_func_array('array_merge', array_map($k, $m));
        },
        'return' => function($x) { return array($x); },
        'fail'   => function($s) { return array(); }
    );
}

# sequence       :: Monad m => [m a] -> m [a]
# sequence       =  foldr mcons (return [])
#                     where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
function sequence($monad, $list)
{
    $mcons =
        function($p, $q) use ($monad) {
            return call_user_func($monad->bind, $p,
                function($x) use ($monad, $q) {
                    return call_user_func($monad->bind, $q,
                        function($y) use ($monad, $x) {
                            return call_user_func($monad->return, cons($x, $y));});});};
    return foldr($mcons, call_user_func($monad->return, array()), $list);
}

# foldr            :: (a -> b -> b) -> b -> [a] -> b
# foldr f z []     =  z
# foldr f z (x:xs) =  f x (foldr f z xs)
function foldr($f, $z, $xs)
{
    if (empty($xs))
        return $z;
    return call_user_func($f, $xs[0], foldr($f, $z, array_slice($xs, 1)));
}

function cons($x, $xs)
{
    return array_merge(array($x), $xs);
}

```

I believe this meets all four of your criteria, especially the "inordinate amount of nested parenthesis/brackets" part.

Test code:

```
function printList($show, $list)
{
    echo showList($show, $list) . "\n";
}

function showList($show, $list)
{
    $str = "[";
    foreach($list as $x) {
        if ($str !== "[")
            $str .= ",";
        $str .= call_user_func($show, $x);
    }
    return $str . "]";
}

# Count in binary
printList('strval',
    compr(function($a, $b, $c, $d) {
        return "$a$b$c$d";
    }, array(0,1), array(0,1), array(0,1), array(0,1)));

# Combinations of items
printList(function($a) {return showList('strval', $a);},
    compr(function($a, $b, $c) {
        return array($a, $b, $c);
    }, array(1, 2), array(3, 4, 5), array(6, 7, 8, 9)));

```

Output:

```
[0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111]
[[1,3,6],[1,3,7],[1,3,8],[1,3,9],[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,3,6],[2,3,7],[2,3,8],[2,3,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9]]

```
> 10 votes

# Answer
Implemented using simple modulus/division.

```
function compr() {
    $args = func_get_args();
    $callback = array_shift($args);

    $total_length = array_product(array_map(function($arr) {
        return count($arr);
    }, $args));

    $return = array();
    for ($i = 0; $i < $total_length; $i++) {
        $params = array();
        $_i = $i;
        for ($j = 0; $j < count($args); $j++) {
            $base = count($args[$j]);
            $params[] = $args[$j][$_i % $base];
            $_i /= $base;
        }
        $return [] = call_user_func_array($callback, $params);
    }

    return $return;
}

```

Test:

```
$array = compr(function($a, $b, $c) {
    return $a + $b + $c;
}, array(1, 2), array(3, 4, 5), array(6, 7, 8, 9));

print_r($array);

```

Output:

```
Array
(
    [0] => 10
    [1] => 11
    [2] => 11
    [3] => 12
    [4] => 12
    [5] => 13
    [6] => 11
    [7] => 12
    [8] => 12
    [9] => 13
    [10] => 13
    [11] => 14
    [12] => 12
    [13] => 13
    [14] => 13
    [15] => 14
    [16] => 14
    [17] => 15
    [18] => 13
    [19] => 14
    [20] => 14
    [21] => 15
    [22] => 15
    [23] => 16
)

```
> 3 votes

---
Tags: code-challenge, php
---


title: Find all Super Powers

text:
# Question
Title: Find all Super Powers
A positive number is said to be super power when it is the power of at least two different positive integers. Write a program that lists all super powers in the interval \[1, 264) (i.e. between 1 (inclusive) and 264 (exclusive)).

Sample Output

```
1
16
64
81
256
512
.
.
.
18443366605910179921
18444492376972984336
18445618199572250625

```

Constraints:

1. The program should not take more than 10 secs.
2. There are 67385 super powers below 264.
3. The shortest code wins.

# Answer
# GolfScript 52 characters

```
64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/

```

I golfed this pretty heavily, here is a compilation of midway solutions:

```
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$0\{.@={}{.p}if}/;
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$.&{p}/
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;4.{64<}{;)..,1>{2$\%*}*!*}/0-\;{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;64,4>{.,1>{2$\%*}*!*},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;64,4>{.,1>{2$\%*}*{1.{16.?<}{;).2$?}/~}or]2>~}%$.&{p}/
64,4>{.,1>{2$\%*}*!\1.{16.?<}{;).2$?}/\;\;*~}%$.&{p}/
64,4>{1.{16.?<}{;).2$?}/\;\.,1>{2$\%*}*!\;*~}%$.&{p}/
64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/

```

GolfScript seems to have some problem with outputting large arrays, therefore I step through the result array using `{p}/` rather than just inject the needed lineshifts using `n*`.

The first 5 versions work by first generating an array of nonprimes from 4 to 63 (code before `{1.`), then for each element of that list all N^nonprime less than 2^64 is calculated (`1.{16.?<}{;).2$?}/`). Finally the result is sorted, duplicates are removed and the result is output.

In the 6th version the 2 first functions are put in the same loop.

In the 7th version the N^nonprime array is generated no matter if the nonprime is actually a nonprime, the array is then thrown away if needed.

In the 8th and 9th version the order has been switched so the N^nonprime array is generated before nonprime status is asserted.

By the way, a^b where a\>0, b\>1 and b is nonprime is probably a more programming-friendly way of describing super powers.
> 5 votes

# Answer
## Ruby, ~~97~~ 93 characters

```
puts (r=2..32).map{|j|r.map{|i|(1..2**(64.0/j/i)).map{|a|a**(j*i)}}}.flatten.uniq.sort[0..-2]

```

I'm pretty sure this should be correct.

```
$ time ruby1.9 perfectpower.rb > out

real    0m0.199s
user    0m0.160s
sys     0m0.030s

$ wc -l out
67385 out

$ head -6 out
1
16
64
81
256
512

$ tail -3 out
18443366605910179921
18444492376972984336
18445618199572250625

```
> 5 votes

# Answer
## Python, 107 chars

```
R=range
for x in sorted(set(i**(j*k)for i in R(65536)for j in R(2,32)for k in R(2,64/j)))[1:67386]:print x

```

Takes about 40 seconds on my machine, though.
> 3 votes

---
Tags: code-golf, math
---


title: Ascii art equation visualizer

text:
# Question
Title: Ascii art equation visualizer
Dealing with equations in the absence of a good equation editor is messy and unpleasant. For example, if I wanted to express an integral and its solution, it might look something like this:

Integral\[x^3 e^(-m x^2 b /2), dx\] = -((2 + b*m*x^2)/(b^2\*e^((b*m*x^2)/2)\*m^2))

At integrals.wolfram.com, this is called "input form." No one likes to see an equation in "input form." The ideal way of visualizing this equation would be:

(Wolfram calls this "traditional form")

For this codegolf, write a program that will take some equation in "input form" as input and visualize that equation in an ascii representation of "traditional form." So, for this example we might get something like this:

```
       /\      3
       |      x
       | ------------  dx =
       |       2
      \/   (m x  b)/2
          e

              2
     2 + b m x
-(-----------------)
            2
   2  (b m x )/2  2
  b  e           m

```

Requirements:

1. Don't shuffle, simplify or rearrange the input in any way. Render it in exactly the same form it was described by the input.
2. Support the four basic mathematical operations (+,-,\*,/). When not multiplying two adjacent numbers the * symbol is implied and should be omitted.
3. Support for integration (as shown in the example above) is **not** required. Being able to support input with functions like Integrate\[...\] or Sqrt\[...\] is a bonus.
4. Support powers as shown in the example above (the nth root can be modeled by raising to the 1/nth power).
5. Redundant parenthesis (like those around the denomentator and numerator of the large fraction in the example above) should be omitted.
6. The expression in the denominator and numerator of a fraction should be centered above and below the horizontal division line.
7. You can choose whether or not to start a new line after an equal sign. In the example above, a new line is started.
8. Order of operations must be exactly the same in the output as it is in the input.

Some examples of input and associated output for testing your solution:

**Input:**

```
1/2 + 1/3 + 1/4

```

**Output:**

```
1   1   1
- + - + -
2   3   4

```

**Input:**

```
3x^2 / 2 + x^3^3

```

**Output:**

```
   2     3
3 x     3
---- + x
 2

```

**Input:**

```
(2 / x) / (5 / 4^2)

```

**Output:**

```
2
-
x
--
5
--
 2
4

```

**Input:**

```
(3x^2)^(1/2)

```

**Output:**

```
    2 1/2
(3 x )

```

# Answer
## Python 2, 1666 chars

The layout is actually pretty easy - it's the parsing of the input that's a royal pain. I'm still not sure it is completely correct.

```
import re,shlex
s=' '
R=range

# Tokenize.  The regex is because shlex doesn't treat 3x and x3 as two separate tokens.  The regex jams a space in between.
r=r'\1 \2'
f=re.sub
x=shlex.shlex(f('([^\d])(\d)',r,f('(\d)([^\d])',r,raw_input())))
T=[s]
while T[-1]:T+=[x.get_token()]
T[-1]=s

# convert implicit * to explicit *
i=1
while T[i:]:
 if(T[i-1].isalnum()or T[i-1]in')]')and(T[i].isalnum()or T[i]in'('):T=T[:i]+['*']+T[i:]
 i+=1

# detect unary -, replace with !
for i in R(len(T)):
 if T[i]=='-'and T[i-1]in'=+-*/^![( ':T[i]='!'
print T

# parse expression: returns tuple of op and args (if any)
B={'=':1,',':2,'+':3,'-':3,'*':4,'/':4,'^':5}
def P(t):
 d,m=0,9
 for i in R(len(t)):
  c=t[i];d+=c in'([';d-=c in')]'
  if d==0and c in B and(B[c]<m or m==B[c]and'^'!=c):m=B[c];r=(c,P(t[:i]),P(t[i+1:]))
 if m<9:return r
 if'!'==t[0]:return('!',P(t[1:]))
 if'('==t[0]:return P(t[1:-1])
 if'I'==t[0][0]:return('I',P(t[2:-1]))
 return(t[0],)

# parenthesize a layout
def S(x):
 A,a,b,c=x
 if b>1:A=['/'+A[0]+'\\']+['|'+A[i]+'|'for i in R(1,b-1)]+['\\'+A[-1]+'/']
 else:A=['('+A[0]+')']
 return[A,a+2,b,c]

# layout a parsed expression.  Returns array of strings (one for each line), width, height, centerline
def L(z):
 p,g=z[0],map(L,z[1:])
 if p=='*':
  if z[1][0]in'+-':g[0]=S(g[0])
  if z[2][0]in'+-':g[1]=S(g[1])
 if p=='^'and z[1][0]in'+-*/^!':g[0]=S(g[0])
 if g:(A,a,b,c)=g[0]
 if g[1:]:(D,d,e,f)=g[1]
 if p in'-+*=,':
  C=max(c,f);E=max(b-c,e-f);F=C+E;U=[s+s+s]*F;U[C]=s+p+s;V=3
  if p in'*,':U=[s]*F;V=1
  return([x+u+y for x,u,y in zip((C-c)*[s*a]+A+(E-b+c)*[s*a],U,(C-f)*[s*d]+D+(E-e+f)*[s*d])],a+d+V,F,C)
 if'^'==p:return([s*a+x for x in D]+[x+s*d for x in A],a+d,b+e,c+e)
 if'/'==p:w=max(a,d);return([(w-a+1)/2*s+x+(w-a)/2*s for x in A]+['-'*w]+[(w-d+1)/2*s+x+(w-d)/2*s for x in D],w,b+e+1,b)
 if'!'==p:return([' -  '[i==c::2]+A[i]for i in R(b)],a+2,b,c)
 if'I'==p:h=max(3,b);A=(h-b)/2*[s*a]+A+(h-b+1)/2*[s*a];return(['  \\/|/\\  '[(i>0)+(i==h-1)::3]+A[i]for i in R(h)],a+3,h,h/2)
 return([p],len(p),1,0)

print'\n'.join(L(P(T[1:-1]))[0])

```

For the big input in the question, I get:

```
 /\         2                     2
 |     - m x  b          2 + b m x
 |     --------    = - -------------
 |  3      2                    2
\/ x  e         dx         b m x
                           ------
                        2     2    2
                       b  e       m

```

Here's some more tricky test cases:

```
I:(2^3)^4
O:    4
  / 3\
  \2 /

I:(2(3+4)5)^6
O:             6
  (2 (3 + 4) 5)

I:x Integral[x^2,dx] y
O:   /\ 2
  x  | x  dx y
    \/

I:(-x)^y
O:     y
  (- x)

I:-x^y
O:     y
  (- x)

```

That last one is wrong, some precedence error in the parser.
> 10 votes

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


# Question
Title: Obtain a number from 4 numbers using any combination of mathematical operations
Given 4 numbers n1, n2, n3, n4, and a goal n5, obtain n5 using n1 through n4 combined with any operations.

Eg. Given four numbers 2,3,4,5 and the goal as 8, output (one of many) is `2-3+4+5`

EDIT: This is a variation of a game played at my son's school. Paranthesis, powers, unary operations (log, factorial) are allowed; the expressions tend to get complicated. However, unary operations can be applied only once on a number. Essentially, the tree should be:

```
                          goal
                           /\
                          /  \
                         /    \
                expression1   expression2
                   /\                /\
                  /  \              /  \
                 /    \            /    \
               term1  term2     term3  term4

```

where *term#i* is either
1. one of the numbers, or 2. one of the numbers with an unary operation.

# Answer
## Python (159)

```
from itertools import*
f=lambda*l:[a+f+b+g+c+h+d for f,g,h in product('+-/*',repeat=3)for a,b,c,d in permutations(map(str,l[:4]))if eval(a+f+b+g+c+h+d)==l[4]]

```

**Example:**

```
>>> f(2,3,4,5,8)
['2+4+5-3', '2+5+4-3', '4+2+5-3', '4+5+2-3', '5+2+4-3', '5+4+2-3', '2+5+4/3',
'3+5+2/4', '5+2+4/3', '5+3+2/4', '2+4-3+5', '2+5-3+4', '4+2-3+5', '4+5-3+2',
'5+2-3+4', '5+4-3+2', '3+5-2/4', '4+5-3/2', '5+3-2/4', '5+4-3/2', '2+4/3+5',
'3+2/4+5', '5+2/4+3', '5+4/3+2', '2+4*5/3', '2+5*4/3', '2-3+4+5', '2-3+5+4',
'4-3+2+5', '4-3+5+2', '5-3+2+4', '5-3+4+2', '3-2/4+5', '4-3/2+5', '5-2/4+3',
'5-3/2+4', '2/4+3+5', '2/4+5+3', '4/3+2+5', '4/3+5+2', '3/5+2*4', '3/5+4*2',
'5/3*2*4', '5/3*4*2', '2*4+3/5', '4*2+3/5', '2*4-3/5', '4*2-3/5', '4*5/3+2',
'5*4/3+2']

```
> 2 votes

# Answer
## Python - 146 chars

```
from itertools import*
f=lambda*l:[s for s in((3*"%s%%s"+"%s")%a%o for o in product(*['+-/*']*3)for a in permutations(l[:4]))if eval(s)==l[4]]

```
> 3 votes

# Answer
# Ruby1.9.1 - 158 chars

```
g=->a,&b{a.permutation.each &b}
f=->*a{t=a.pop
g.(a){|n|g.(['+','-','*','/']*3){|k|s=[n[0],k[9],n[1],k[10],n[2],k[11],n[3]].join ''
return s if eval(s)==t}}}

```

Lambda function `f` returns the first solution it finds. eg.

```
f[2,3,4,5,8] #gives "2-3+4+5"

```
> 1 votes

# Answer
## Perl

Not golfed as this is a code-challenge and not code-golf.

Aiming for complete solution; uses reverse polish notation.

Enjoy cryptic variable names and weird coding style ;)

```
#!perl -l
use strict;
use warnings;
use Math'Combinatorics;
use Math'RPN;

my @do=qw(add sub mul div mod pow);
my @uo=qw(sqrt sin cos tan log exp);

sub u(@){my%h;$h{"@$_"}=$_ for@_;values%h}

sub ms ($$$) {
    my($c,$d,$f)=@_; my @r;
    my $o = new Math'Combinatorics count => $c, data => $d, frequency => $f;
    while (my @x = $o->next_multiset) {push @r, [@x]}
    @r;
}

my $r = shift;
my $a = ~~@ARGV;

my @p = u permute @ARGV;
my @d = ms $a-1, \@do, [(~~@do) x @do];
my @u = ms $a, \@uo, [(~~@uo)x@uo];
my @t;

push @t, [unpack "(A)$a", sprintf "%0${a}b", $_] for 0..2**$a-1;

my @pu = ();

for my $pp (@p) {
    for my $uoo (@u) {
        for my $tt (@t) {
            my @opu = ();
            for my $g (0..$a-1) {
                push @opu, $pp->[$g];
                push @opu, $uoo->[$g] if $tt->[$g];
            }
            push @pu, \@opu;
        }
    }
}

@pu = u @pu;

for my $ppu (@pu) {
    for my $doo (@d) {
        my @e = (@$ppu,@$doo); my $z;
        eval {$z=rpn(@e)};
        $z = $r-1 if $@;
        print "@e = $z" if $z==$r;
    }
}

```

usage example:

```
> perl ./mc.pl 14 3 4 4
4 sqrt 3 4 add mul = 14
4 sqrt 4 3 add mul = 14
4 exp 3 exp 4 exp mod mod = 14
4 exp 3 exp 4 sqrt mul mod = 14

```
> 1 votes

---
Tags: code-challenge, arithmetic
---


title: Solve 2-SAT (boolean satisfiability)

text:
# Question
Title: Solve 2-SAT (boolean satisfiability)
The general SAT (boolean satisfiability) problem is NP-complete. But 2-SAT, where each clause has only 2 variables, is in . Write a solver for 2-SAT.

Input:

A 2-SAT instance, encoded in CNF as follows. The first line contains V, the number of boolean variables and N, the number of clauses. Then N lines follow, each with 2 nonzero integers representing the literals of a clause. Positive integers represent the given boolean variable and negative integers represent the variable's negation.

## Example 1

### input

```
4 5
1 2
2 3
3 4
-1 -3
-2 -4

```

which encodes the formula *(x1 or x2) and (x2 or x3) and (x3 or x4) and (not x1 or not x3) and (not x2 or not x4)*.

The only setting of the 4 variables that makes the whole formula true is *x1=false, x2=true, x3=true, x4=false*, so your program should output the single line

### output

```
0 1 1 0

```

representing the truth values of the V variables (in order from *x1* to *xV*). If there are multiple solutions, you may output any nonempty subset of them, one per line. If there is no solution, you must output `UNSOLVABLE`.

## Example 2

### input

```
2 4
1 2
-1 2
-2 1
-1 -2

```

### output

```
UNSOLVABLE

```

## Example 3

### input

```
2 4
1 2
-1 2
2 -1
-1 -2

```

### output

```
0 1

```

## Example 4

### input

```
8 12
1 4
-2 5
3 7
2 -5
-8 -2
3 -1
4 -3
5 -4
-3 -7
6 7
1 7
-7 -1

```

### output

```
1 1 1 1 1 1 0 0
0 1 0 1 1 0 1 0
0 1 0 1 1 1 1 0

```

(or any nonempty subset of those 3 lines)

Your program must handle all N,V \< 100 in a reasonable time. Try this example to make sure your program can handle a big instance. Smallest program wins.

# Answer
## Haskell, 278 characters

```
(∈)=elem
r v[][]=[(>>=(++" ").show.fromEnum.(∈v))]
r v[]c@(a:b:_)=r(a:v)c[]++r(-a:v)c[]++[const"UNSOLVABLE"]
r v(a:b:c)d|a∈v||b∈v=r v c d|(-a)∈v=i b|(-b)∈v=i a|1<3=r v c(a:b:d)where i w|(-w)∈v=[]|1<3=r(w:v)(c++d)[]
t(n:_:c)=(r[][]c!!0)[1..n]++"\n"
main=interact$t.map read.words

```

Not brute force. Runs in polynomial time. Solves the hard problem (60 variables, 99 clauses) quickly:

```
> time (runhaskell 1933-2Sat.hs < 1933-hard2sat.txt)
1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0

real 0m0.593s
user 0m0.502s
sys  0m0.074s

```

*And actually, most of that time is spent compiling the code!*

Full source file, with test cases and quick-check tests available.

**Ungolf'd:**

```
-- | A variable or its negation
-- Note that applying unary negation (-) to a term inverts it.
type Term = Int

-- | A set of terms taken to be true.
-- Should only contain  a variable or its negation, never both.
type TruthAssignment = [Term]

-- | Special value indicating that no consistent truth assignment is possible.
unsolvable :: TruthAssignment
unsolvable = [0]

-- | Clauses are a list of terms, taken in pairs.
-- Each pair is a disjunction (or), the list as a whole the conjuction (and)
-- of the pairs.
type Clauses = [Term]

-- | Test to see if a term is in an assignment
(∈) :: Term -> TruthAssignment -> Bool
a∈v = a `elem` v;

-- | Satisfy a set of clauses, from a starting assignment.
-- Returns a non-exhaustive list of possible assignments, followed by
-- unsolvable. If unsolvable is first, there is no possible assignment.
satisfy :: TruthAssignment -> Clauses -> [TruthAssignment]
satisfy v c@(a:b:_) = reduce (a:v) c ++ reduce (-a:v) c ++ [unsolvable]
  -- pick a term from the first clause, either it or its negation must be true;
  -- if neither produces a viable result, then the clauses are unsolvable
satisfy v [] = [v]
  -- if there are no clauses, then the starting assignment is a solution!

-- | Reduce a set of clauses, given a starting assignment, then solve that
reduce :: TruthAssignment -> Clauses -> [TruthAssignment]
reduce v c = reduce' v c []
  where
    reduce' v (a:b:c) d
        | a∈v || b∈v = reduce' v c d
            -- if the clause is already satisfied, then just drop it
        | (-a)∈v = imply b
        | (-b)∈v = imply a
            -- if either term is not true, the other term must be true
        | otherwise = reduce' v c (a:b:d)
            -- this clause is still undetermined, save it for later
        where
          imply w
            | (-w)∈v = []  -- if w is also false, there is no possible solution
            | otherwise = reduce (w:v) (c++d)
                -- otherwise, set w true, and reduce again
    reduce' v [] d = satisfy v d
        -- once all caluses have been reduced, satisfy the remaining

-- | Format a solution. Terms not assigned are choosen to be false
format :: Int -> TruthAssignment -> String
format n v
    | v == unsolvable = "UNSOLVABLE"
    | otherwise = unwords . map (bit.(∈v)) $ [1..n]
  where
    bit False = "0"
    bit True = "1"

main = interact $ run . map read . words
  where
    run (n:_:c) = (format n $ head $ satisfy [] c) ++ "\n"
        -- first number of input is number of variables
        -- second number of input is number of claues, ignored
        -- remaining numbers are the clauses, taken two at a time

```

In the golf'd version, `satisfy` and `format` have been rolled into `reduce`, though in order to avoid passing `n`, `reduce` returns a function from a list of variables (`[1..n]`) to the string result.

---

* Edit: (330 -\> 323) made `s` an operator, better handling of the newline
* Edit: (323 -\> 313) first element from a lazy list of results is smaller than a custom short-circuit operator; renamed main solver function 'cause I like using  as an operator!
* Edit: (313 -\> 296) keep clauses as a single list, not a list of lists; process it two elements at a time
* Edit: (296 -\> 291) merged the two mutually recursive functions; it was cheaper to inline  so test now renamed
* Edit: (291 -\> 278) inlined output formatting into results generation
> 6 votes

# Answer
# J, 119 103

```
echo'UNSOLVABLE'"_`(#&c)@.(*@+/)(3 :'*./+./"1(*>:*}.i)=y{~"1 0<:|}.i')"1 c=:#:i.2^{.,i=:0&".;._2(1!:1)3

```
* Passes all test cases. No noticeable runtime.
* Brute force. Passes test cases below, oh, N=20 or 30. Not sure.
* Tested via completely brain-dead test script (By visual inspection)

**Edit:** Eliminated `(n#2)` and thus `n=:`, as well as eliminating some rank parens (thanks, isawdrones). Tacit-\>explicit and dyadic-\>monadic, eliminating a few more characters each. `}.}.` to `}.,`.

**Edit:** Whoops. Not only is this a non-solution for large N, but `i. 2^99x` -\> "domain error" to add insult to stupidity.

Here's the ungolfed original version and brief explanation.

```
input=:0&".;._2(1!:1)3
n =:{.{.input
clauses=:}.input
cases=:(n#2)#:i.2^n
results =: clauses ([:*./[:+./"1*@>:@*@[=<:@|@[{"(0,1)])"(_,1) cases
echo ('UNSOLVABLE'"_)`(#&cases) @.(*@+/) results

```
* `input=:0&".;._2(1!:1)3` cuts input on newlines and parses numbers on each line (accumulating the results into input).
* n is assigned to `n`, clause matrix assigned to `clauses` (don't need the clause count)
* `cases` is 0..2n-1 converted to binary digits (all test cases)
* `(Long tacit function)"(_,1)` is applied to each case in `cases` with all of `clauses`.
* `<:@|@[{"(0,1)]` gets a matrix of the operands of the clauses (by taking abs(op number) - 1 and dereferencing from case, which is an array)
* `*@>:@*@[` gets clause-shaped array of 'not not' bits (0 for not) via abuse of signum.
* `=` applies the not bits to the operands.
* `[:*./[:+./"1` applies `+.` (and) across the rows of the resulting matrix, and `*.` (or) across the result of that.
* All of those results end up as a binary array of 'answers' for each case.
* `*@+/` applied to results gives a 0 if there are results and 1 if there are none.
* `('UNSOLVABLE'"_)` ``(#&cases) @.(*@+/) results` runs constant function giving 'UNSOLVABLE' if 0, and a copy of each 'solution' element of cases if 1.
* `echo` magic-prints the result.
> 4 votes

# Answer
## \- 89

The same method as the J solution.

```
n:**c:.:'0:`;`0::[#b:t@&&/+|/''(0<'c)=/:(t:+2_vs!_2^n)@\:-1+_abs c:1_ c;5:b;"UNSOLVABLE"]

```
> 3 votes

# Answer
# OCaml + Batteries, 438 436 characters

Requires an OCaml Batteries Included top-level:

```
module L=List
let(%)=L.mem
let rec r v d c n=match d,c with[],[]->[String.join" "[?L:if x%v
then"1"else"0"|x<-1--n?]]|[],(x,_)::_->r(x::v)c[]n@r(-x::v)c[]n@["UNSOLVABLE"]|(x,y)::c,d->let(!)w=if-w%v
then[]else r(w::v)(c@d)[]n in if x%v||y%v then r v c d n else if-x%v then!y else if-y%v then!x else r v c((x,y)::d)n
let(v,_)::l=L.of_enum(IO.lines_of stdin|>map(fun s->Scanf.sscanf s"%d %d"(fun x y->x,y)))in print_endline(L.hd(r[][]l v))

```

I must confess, this is a direct translation of the Haskell solution. In my defense, that in turn is a direct coding of the algorithm presented here \[PDF\], with the mutual `satisfy`-`eliminate` recursion rolled into a single function. An unobfuscated version of the code, minus the use of Batteries, is:

```
let rec satisfy v c d = match c, d with
| (x, y) :: c, d ->
    let imply w = if List.mem (-w) v then raise Exit else satisfy (w :: v) (c @ d) [] in
    if List.mem x v || List.mem y v then satisfy v c d else
    if List.mem (-x) v then imply y else
    if List.mem (-y) v then imply x else
    satisfy v c ((x, y) :: d)
| [], [] -> v
| [], (x, _) :: _ -> try satisfy (x :: v) d [] with Exit -> satisfy (-x :: v) d []

let rec iota i =
    if i = 0 then [] else
    iota (i - 1) @ [i]

let () = Scanf.scanf "%d %d\n" (fun k n ->
    let l = ref [] in
    for i = 1 to n do
        Scanf.scanf "%d %d\n" (fun x y -> l := (x, y) :: !l)
    done;
    print_endline (try let v = satisfy [] [] !l in
    String.concat " " (List.map (fun x -> if List.mem x v then "1" else "0") (iota k))
    with Exit -> "UNSOLVABLE") )

```

(the `iota k` pun I hope you'll forgive).
> 3 votes

# Answer
## Ruby, 253

```
n,v=gets.split;d=[];v.to_i.times{d<<(gets.split.map &:to_i)};n=n.to_i;r=[1,!1]*n;r.permutation(n){|x|y=x[0,n];x=[0]+y;puts y.map{|z|z||0}.join ' 'or exit if d.inject(1){|t,w|t and(w[0]<0?!x[-w[0]]:x[w[0]])||(w[1]<0?!x[-w[1]]:x[w[1]])}};puts 'UNSOLVABLE'

```

But it's slow :(

Pretty readable once expanded:

```
n,v=gets.split
d=[]
v.to_i.times{d<<(gets.split.map &:to_i)} # read data
n=n.to_i
r=[1,!1]*n # create an array of n trues and n falses
r.permutation(n){|x| # for each permutation of length n
    y=x[0,n]
    x=[0]+y
    puts y.map{|z| z||0}.join ' ' or exit if d.inject(1){|t,w| # evaluate the data (magic!)
        t and (w[0]<0 ? !x[-w[0]] : x[w[0]]) || (w[1]<0 ? !x[-w[1]] : x[w[1]])
    }
}
puts 'UNSOLVABLE'

```
> 2 votes

---
Tags: code-golf
---


title: GolfScript - The missing function

text:
# Question
Title: GolfScript - The missing function
The GolfScript language has one serious lack, no float or fixed point handling. Remedy this by creating a function F for converting an integer number, given as a string, to a string representing 1 / 10 000 000 000 of it's value. The function must handle both positive and negative values as well as leading `0`s.

The following pretty-print rules apply:

No trailing `0`s.
No `.` if the result is integer.
No leading `0`s, except for numbers with no integer part, they should have 1 leading `0`.
The result must be output as a single string.

Examples:

`123` -\> `0.0000000123`
`-00` -\> `0`
`012345678901234567890` -\> `1234567890.123456789`
`-123` -\> `-0.0000000123`
`10000000000001` -\> `1000.0000000001`
`123000000000000` -\> `12300`

The competition is only between GolfScript submissions using no Ruby functionality. Solutions in other languages may be posted, but they are not eligible for winning, these may not use any fixed or float point functionality that the language offers, and must accept arbitrarily large inputs.

# Answer
### 55 chars

```
{~.0<"-"*\abs 10.?..3$@%+`-1%~`)[3-]1$,!!*+-1%@@/\++}:F

```

Negative numbers are a bit of a pain - responsible for about 13 chars of the 55. Trailing 0s are handled by using a 1 to stand for the decimal point, reversing as a string, converting to an int, and back again, and re-reversing.
> 8 votes

# Answer
### 50 characters

```
{..~0<<\~abs`.,11\-,,0`*\++-10/(~.!!\"."+*\+-1%}:F

```

The most noteworthy trick in this solution is probably `-10/`, detach the last 10 characters and inverse, so that the trailing `0`s can be culled by conversion by conversion to integer.
> 4 votes

---
Tags: code-golf, math, floating-point, golfscript
---


# Question
Title: Implement a sorting algorithm with no change.
In this task, you have to write a program, that reads a string with a length of up to 1024 characters and prints it out sorted. In order to make an interesting task from a boring one, I set a few restrictions:

You must not change the contents of any variable. A variable can be assigned only once and must not be changed afterwards. For instance, all of the following constructs are forbidden:

```
int a = 0;
a = 1;

a = 10;
for (a-->0);

string[12] = a

```

and many more. What is changing a variable and what not is judged by me.

Additionally, you must not use any sorting function or any library function, that must be "imported" somehow. The only library functions, that are allowed to import are those to print out the result and read in the string, if they are not available whithout importing them.

# Answer
> 5 votes
# Perl, 89 characters

```
sub t{return if!@_;my$c=shift;t(grep{$_ lt$c}@_),$c,t(grep{$_ ge$c}@_)}print t split//,<>

```

This exploits the fact that QuickSort is effectively equivalent to the recurrence relation:

```
sorted x = () if x is empty, otherwise
           sorted (elements in x less than x[0]) :: x[0] ::
           sorted (elements in x greater than or equal to x[0] except for x[0] itself)

```

### Edit

I originally misread the question and thought I had to sort the input strings, not the characters *within* a string. Hence my solution grows from 80 to 89 characters.

# Answer
> 5 votes
## Python

```
s=raw_input()
print chr(0)*s.count(chr(0))+chr(1)*s.count(chr(1))+chr(2)*s.count(chr(2))+chr(3)*s.count(chr(3))+chr(4)*s.count(chr(4))+chr(5)*s.count(chr(5))+chr(6)*s.count(chr(6))+chr(7)*s.count(chr(7))+chr(8)*s.count(chr(8))+chr(9)*s.count(chr(9))+chr(10)*s.count(chr(10))+chr(11)*s.count(chr(11))+chr(12)*s.count(chr(12))+chr(13)*s.count(chr(13))+chr(14)*s.count(chr(14))+chr(15)*s.count(chr(15))+chr(16)*s.count(chr(16))+chr(17)*s.count(chr(17))+chr(18)*s.count(chr(18))+chr(19)*s.count(chr(19))+chr(20)*s.count(chr(20))+chr(21)*s.count(chr(21))+chr(22)*s.count(chr(22))+chr(23)*s.count(chr(23))+chr(24)*s.count(chr(24))+chr(25)*s.count(chr(25))+chr(26)*s.count(chr(26))+chr(27)*s.count(chr(27))+chr(28)*s.count(chr(28))+chr(29)*s.count(chr(29))+chr(30)*s.count(chr(30))+chr(31)*s.count(chr(31))+chr(32)*s.count(chr(32))+chr(33)*s.count(chr(33))+chr(34)*s.count(chr(34))+chr(35)*s.count(chr(35))+chr(36)*s.count(chr(36))+chr(37)*s.count(chr(37))+chr(38)*s.count(chr(38))+chr(39)*s.count(chr(39))+chr(40)*s.count(chr(40))+chr(41)*s.count(chr(41))+chr(42)*s.count(chr(42))+chr(43)*s.count(chr(43))+chr(44)*s.count(chr(44))+chr(45)*s.count(chr(45))+chr(46)*s.count(chr(46))+chr(47)*s.count(chr(47))+chr(48)*s.count(chr(48))+chr(49)*s.count(chr(49))+chr(50)*s.count(chr(50))+chr(51)*s.count(chr(51))+chr(52)*s.count(chr(52))+chr(53)*s.count(chr(53))+chr(54)*s.count(chr(54))+chr(55)*s.count(chr(55))+chr(56)*s.count(chr(56))+chr(57)*s.count(chr(57))+chr(58)*s.count(chr(58))+chr(59)*s.count(chr(59))+chr(60)*s.count(chr(60))+chr(61)*s.count(chr(61))+chr(62)*s.count(chr(62))+chr(63)*s.count(chr(63))+chr(64)*s.count(chr(64))+chr(65)*s.count(chr(65))+chr(66)*s.count(chr(66))+chr(67)*s.count(chr(67))+chr(68)*s.count(chr(68))+chr(69)*s.count(chr(69))+chr(70)*s.count(chr(70))+chr(71)*s.count(chr(71))+chr(72)*s.count(chr(72))+chr(73)*s.count(chr(73))+chr(74)*s.count(chr(74))+chr(75)*s.count(chr(75))+chr(76)*s.count(chr(76))+chr(77)*s.count(chr(77))+chr(78)*s.count(chr(78))+chr(79)*s.count(chr(79))+chr(80)*s.count(chr(80))+chr(81)*s.count(chr(81))+chr(82)*s.count(chr(82))+chr(83)*s.count(chr(83))+chr(84)*s.count(chr(84))+chr(85)*s.count(chr(85))+chr(86)*s.count(chr(86))+chr(87)*s.count(chr(87))+chr(88)*s.count(chr(88))+chr(89)*s.count(chr(89))+chr(90)*s.count(chr(90))+chr(91)*s.count(chr(91))+chr(92)*s.count(chr(92))+chr(93)*s.count(chr(93))+chr(94)*s.count(chr(94))+chr(95)*s.count(chr(95))+chr(96)*s.count(chr(96))+chr(97)*s.count(chr(97))+chr(98)*s.count(chr(98))+chr(99)*s.count(chr(99))+chr(100)*s.count(chr(100))+chr(101)*s.count(chr(101))+chr(102)*s.count(chr(102))+chr(103)*s.count(chr(103))+chr(104)*s.count(chr(104))+chr(105)*s.count(chr(105))+chr(106)*s.count(chr(106))+chr(107)*s.count(chr(107))+chr(108)*s.count(chr(108))+chr(109)*s.count(chr(109))+chr(110)*s.count(chr(110))+chr(111)*s.count(chr(111))+chr(112)*s.count(chr(112))+chr(113)*s.count(chr(113))+chr(114)*s.count(chr(114))+chr(115)*s.count(chr(115))+chr(116)*s.count(chr(116))+chr(117)*s.count(chr(117))+chr(118)*s.count(chr(118))+chr(119)*s.count(chr(119))+chr(120)*s.count(chr(120))+chr(121)*s.count(chr(121))+chr(122)*s.count(chr(122))+chr(123)*s.count(chr(123))+chr(124)*s.count(chr(124))+chr(125)*s.count(chr(125))+chr(126)*s.count(chr(126))+chr(127)*s.count(chr(127))+chr(128)*s.count(chr(128))+chr(129)*s.count(chr(129))+chr(130)*s.count(chr(130))+chr(131)*s.count(chr(131))+chr(132)*s.count(chr(132))+chr(133)*s.count(chr(133))+chr(134)*s.count(chr(134))+chr(135)*s.count(chr(135))+chr(136)*s.count(chr(136))+chr(137)*s.count(chr(137))+chr(138)*s.count(chr(138))+chr(139)*s.count(chr(139))+chr(140)*s.count(chr(140))+chr(141)*s.count(chr(141))+chr(142)*s.count(chr(142))+chr(143)*s.count(chr(143))+chr(144)*s.count(chr(144))+chr(145)*s.count(chr(145))+chr(146)*s.count(chr(146))+chr(147)*s.count(chr(147))+chr(148)*s.count(chr(148))+chr(149)*s.count(chr(149))+chr(150)*s.count(chr(150))+chr(151)*s.count(chr(151))+chr(152)*s.count(chr(152))+chr(153)*s.count(chr(153))+chr(154)*s.count(chr(154))+chr(155)*s.count(chr(155))+chr(156)*s.count(chr(156))+chr(157)*s.count(chr(157))+chr(158)*s.count(chr(158))+chr(159)*s.count(chr(159))+chr(160)*s.count(chr(160))+chr(161)*s.count(chr(161))+chr(162)*s.count(chr(162))+chr(163)*s.count(chr(163))+chr(164)*s.count(chr(164))+chr(165)*s.count(chr(165))+chr(166)*s.count(chr(166))+chr(167)*s.count(chr(167))+chr(168)*s.count(chr(168))+chr(169)*s.count(chr(169))+chr(170)*s.count(chr(170))+chr(171)*s.count(chr(171))+chr(172)*s.count(chr(172))+chr(173)*s.count(chr(173))+chr(174)*s.count(chr(174))+chr(175)*s.count(chr(175))+chr(176)*s.count(chr(176))+chr(177)*s.count(chr(177))+chr(178)*s.count(chr(178))+chr(179)*s.count(chr(179))+chr(180)*s.count(chr(180))+chr(181)*s.count(chr(181))+chr(182)*s.count(chr(182))+chr(183)*s.count(chr(183))+chr(184)*s.count(chr(184))+chr(185)*s.count(chr(185))+chr(186)*s.count(chr(186))+chr(187)*s.count(chr(187))+chr(188)*s.count(chr(188))+chr(189)*s.count(chr(189))+chr(190)*s.count(chr(190))+chr(191)*s.count(chr(191))+chr(192)*s.count(chr(192))+chr(193)*s.count(chr(193))+chr(194)*s.count(chr(194))+chr(195)*s.count(chr(195))+chr(196)*s.count(chr(196))+chr(197)*s.count(chr(197))+chr(198)*s.count(chr(198))+chr(199)*s.count(chr(199))+chr(200)*s.count(chr(200))+chr(201)*s.count(chr(201))+chr(202)*s.count(chr(202))+chr(203)*s.count(chr(203))+chr(204)*s.count(chr(204))+chr(205)*s.count(chr(205))+chr(206)*s.count(chr(206))+chr(207)*s.count(chr(207))+chr(208)*s.count(chr(208))+chr(209)*s.count(chr(209))+chr(210)*s.count(chr(210))+chr(211)*s.count(chr(211))+chr(212)*s.count(chr(212))+chr(213)*s.count(chr(213))+chr(214)*s.count(chr(214))+chr(215)*s.count(chr(215))+chr(216)*s.count(chr(216))+chr(217)*s.count(chr(217))+chr(218)*s.count(chr(218))+chr(219)*s.count(chr(219))+chr(220)*s.count(chr(220))+chr(221)*s.count(chr(221))+chr(222)*s.count(chr(222))+chr(223)*s.count(chr(223))+chr(224)*s.count(chr(224))+chr(225)*s.count(chr(225))+chr(226)*s.count(chr(226))+chr(227)*s.count(chr(227))+chr(228)*s.count(chr(228))+chr(229)*s.count(chr(229))+chr(230)*s.count(chr(230))+chr(231)*s.count(chr(231))+chr(232)*s.count(chr(232))+chr(233)*s.count(chr(233))+chr(234)*s.count(chr(234))+chr(235)*s.count(chr(235))+chr(236)*s.count(chr(236))+chr(237)*s.count(chr(237))+chr(238)*s.count(chr(238))+chr(239)*s.count(chr(239))+chr(240)*s.count(chr(240))+chr(241)*s.count(chr(241))+chr(242)*s.count(chr(242))+chr(243)*s.count(chr(243))+chr(244)*s.count(chr(244))+chr(245)*s.count(chr(245))+chr(246)*s.count(chr(246))+chr(247)*s.count(chr(247))+chr(248)*s.count(chr(248))+chr(249)*s.count(chr(249))+chr(250)*s.count(chr(250))+chr(251)*s.count(chr(251))+chr(252)*s.count(chr(252))+chr(253)*s.count(chr(253))+chr(254)*s.count(chr(254))+chr(255)*s.count(chr(255))

```

# Answer
> 4 votes
## Haskell (70 103 94 82 71 60)

Insertion sort.

```
m%(x:y)|x>m=m:x:y|2>1=x:m%y
m%_=[m]
main=interact$foldr(%)[]

```

**Edit:** Forgot I/O

**Edit:** Use pattern guards to get rid of if

**Edit:** Revisions suggested by MtnViewMark

**Edit:** Replace `s` with a fold

**Edit:** Reorder clauses, so base case can match with `_`

**Edit:** Change main to implement FUZxxl's suggestion.

# Answer
> 3 votes
## C

Simply by using recursion instead of loops. ~~This particular version only works on characters between '0' and 'z', but that's just to keep the stack from overflowing too often.~~ Supporting all of ASCII.

```
#include <stdio.h>

void walk(char *s, char m){
    if (*s == '\0') return;
    if (*s == m) putchar(m);
    walk(s+1,m);
}

void sort(char *s, char m){
  walk(s,m);
  if (m<127) sort(s,m+1);
}

int main(int argc, char**argv){
  if (argc > 1) {
    printf("%s: ",argv[1]);
    sort(argv[1],1);
    printf("\n");
  }
}

```

Sample run:

```
$ ./a.out  thingamabob
thingamabob: aabbghimnot
$ ./a.out  supercalifragilisticexpalodoucious
supercalifragilisticexpalodoucious: aaacccdeefgiiiiilllooopprrssstuuux
$ ./a.out  "The quick red fox jumped over the lazy brown dog"
The quick red fox jumped over the lazy brown dog:          Tabcdddeeeeefghhijklmnoooopqrrrtuuvwxyz

```

Too easy, really.

# Answer
> 3 votes
## C++ (with libgc)

This isn't code-golf, so I went for speed. This implements counting sort. Rather than updating an array (which isn't allowed), it updates a 4-way trie by reconstructing nodes as necessary. It allocates trie nodes on the stack and copies them to the heap every 1000 characters, yielding a 600% performance boost.

This requires libgc, a garbage collector for C/C++. To work on large files (without stack-overflowing), it also requires the compiler to optimize tail recursion so it won't leak memory and/or stack-overflow.

Despite all the object fiddling and garbage collection, this manages to run about 25-40% as fast as a simple array-based counting sort (see below).

```
#include <gc/gc_cpp.h>
#include <stdio.h>

template<class T>
struct Node : public gc
{
    T a, b, c, d;

    Node(T a, T b, T c, T d)
        : a(a), b(b), c(c), d(d)
        {}

    Node(T s)
        : a(s), b(s), c(s), d(s)
        {}

    T get(int n) {
        switch (n) {
            case 0:  return a;
            case 1:  return b;
            case 2:  return c;
            case 3:  return d;
            default: return NULL;
        }
    }
};

typedef Node<int> TrieC;
typedef Node<TrieC*> TrieB;
typedef Node<TrieB*> TrieA;
typedef Node<TrieA*> Trie;

static Trie *initialize();
static Trie *sortInput(Trie *root);
static Trie *sortUsingStack(Trie *orig, Trie *root, int c, int count);
template<class T> static Node<T> *merge(Node<T> *node, Node<T> *base);
static Node<int> *merge(Node<int> *node, Node<int> *base);
static void  print(Trie *trie);
static void  repeat(int c, int n);

static Trie *initialize()
{
    return new Trie(new TrieA(new TrieB(new TrieC(0))));
}

static Trie *sortInput(Trie *root)
{
    int c = getchar();
    if (c == EOF)
        return root;
    else
        return sortInput(sortUsingStack(root, root, c, 1000));
}

static Trie *sortUsingStack(Trie *orig, Trie *root, int chr, int count)
{
    if (chr == EOF)
        return merge(root, orig);

    int a = (chr >> 6) & 3;
    int b = (chr >> 4) & 3;
    int c = (chr >> 2) & 3;
    int d =  chr       & 3;

    TrieA *na = root->get(a);
    TrieB *nb = na->get(b);
    TrieC *nc = nb->get(c);
    int    nd = nc->get(d);

    int nd2 = nd + 1;

    TrieC nc2(
        d == 0 ? nd2 : nc->a,
        d == 1 ? nd2 : nc->b,
        d == 2 ? nd2 : nc->c,
        d == 3 ? nd2 : nc->d);

    TrieB nb2(
        c == 0 ? &nc2 : nb->a,
        c == 1 ? &nc2 : nb->b,
        c == 2 ? &nc2 : nb->c,
        c == 3 ? &nc2 : nb->d);

    TrieA na2(
        b == 0 ? &nb2 : na->a,
        b == 1 ? &nb2 : na->b,
        b == 2 ? &nb2 : na->c,
        b == 3 ? &nb2 : na->d);

    Trie root2(
        a == 0 ? &na2 : root->a,
        a == 1 ? &na2 : root->b,
        a == 2 ? &na2 : root->c,
        a == 3 ? &na2 : root->d);

    if (count > 0)
        return sortUsingStack(orig, &root2, getchar(), count - 1);
    else
        return merge(&root2, orig);
}

/* Copy tree, but use nodes from base if they're the same. */
template<class T> static Node<T> *merge(Node<T> *node, Node<T> *base)
{
    if (node == base)
        return node;
    else
        return new Node<T>(merge(node->a, base->a),
                           merge(node->b, base->b),
                           merge(node->c, base->c),
                           merge(node->d, base->d));
}

static Node<int> *merge(Node<int> *node, Node<int> *base)
{
    (void) base;
    return new Node<int>(node->a, node->b, node->c, node->d);
}

static void printC(TrieC *t, int start)
{
    repeat(start, t->a);
    repeat(start + 1, t->b);
    repeat(start + 2, t->c);
    repeat(start + 3, t->d);
}

static void printB(TrieB *t, int start)
{
    printC(t->a, start);
    printC(t->b, start + 4);
    printC(t->c, start + 8);
    printC(t->d, start + 12);
}

static void printA(TrieA *t, int start)
{
    printB(t->a, start);
    printB(t->b, start + 16);
    printB(t->c, start + 32);
    printB(t->d, start + 48);
}

static void print(Trie *t)
{
    printA(t->a, 0);
    printA(t->b, 64);
    printA(t->c, 128);
    printA(t->d, 192);
}

/* Print the character c, n times. */
static void repeat(int c, int n)
{
    if (n > 0) {
        putchar(c);
        repeat(c, n-1);
    }
}

int main(void)
{
    print(sortInput(initialize()));
    putchar('\n');
    return 0;
}

```

The array-based counting sort I used for comparison (getchar/putchar is the bottleneck):

```
#include <stdio.h>

int main(void)
{
    int tally[256] = {};
    int c, i, j;

    while ((c = getchar()) != EOF)
        tally[c]++;

    for (i = 0; i < 256; i++)
        for (j = 0; j < tally[i]; j++)
            putchar(i);
    putchar('\n');

    return 0;
}

```

# Answer
> 3 votes
## Haskell

This implements a counting sort by building a 4-way trie. It's an adaptation of my C++ answer, and is roughly 25% faster than it.

```
import Data.Bits
import Data.List
import Data.Word

import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L

data Node a = Node !a !a !a !a

sortByteString :: L.ByteString -> L.ByteString
sortByteString s = fromTrie $ L.foldl' f z s
    where
        f n x =
            let a = (x `shiftR` 6) .&. 3
                b = (x `shiftR` 4) .&. 3
                c = (x `shiftR` 2) .&. 3
                d =  x             .&. 3
             in (chg a . chg b . chg c . chg d) (+1) n
        z = let n a = Node a a a a
             in (n . n . n . n) 0

        chg :: Word8 -> (a -> a) -> Node a -> Node a
        chg 0 f (Node a b c d) = Node (f a) b c d
        chg 1 f (Node a b c d) = Node a (f b) c d
        chg 2 f (Node a b c d) = Node a b (f c) d
        chg 3 f (Node a b c d) = Node a b c (f d)

        fromTrie t =
            let gather (Node a b c d) = [a, b, c, d]
                counts = gather t >>= gather >>= gather >>= gather
             in L.concat $ zipWith (L.replicate) counts [0..]

main = L.interact ((`L.snoc` 10) . sortByteString)

```

# Answer
> 3 votes
## Scala

```
object Sort extends Application
{
    def merge(s1:String,s2:String):String=
    {
        if(s1.isEmpty) return s2
        if(s2.isEmpty) return s1
        if(s1.head<s2.head)
            return s1.head+merge(s1.tail,s2)
        else
            return s2.head+merge(s1,s2.tail)
    }
    def mergesort(s:String):String=
    {
        if(s.length<=1)
            return s
        else
            return merge(mergesort(s take(s.length/2)),mergesort(s drop(s.length/2)))
    }
    print(mergesort(Console.readLine))
}

```

# Answer
> 2 votes
## SED

```
s/$/\n !"#$%\&'()*+,-.\/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~/;:a;s/\(.\)\(.*\)\(.\)\(.*\n.*\3.*\1\)/\3\1\2\4/;ta;s/\n.*//

```

Doesn't modify anything but pattern space (script would be pointless otherwise)

Lookup table borrowed from http://sed.sf.net/grabbag/scripts/sodelnum.sed

# Answer
> 2 votes
## Ruby (71 chars)

Shamelessly stole the idea from gnibbler, but improved it, a lot

```
def s x
return if x>255
print x.chr*(ARGV[0].count x.chr)
s x+1
end
s 0

```

Usage:

```
$ ruby codegolfsort.rb "supercalifragilisticexpalodoucious"
aaacccdeefgiiiiilllooopprrssstuuux

```

# Answer
> 1 votes
## Python

```
S=lambda x:S([y for y in x if y<x[0]])+x[0]*x.count(x[0])+S([y for y in x if y>x[0]])if x else''
print S(raw_input())

```

# Answer
> 1 votes
## Ruby

```
s=gets
puts 0.chr*(s.count 0.chr)+1.chr*(s.count 1.chr)+2.chr*(s.count 2.chr)+3.chr*(s.count 3.chr)+4.chr*(s.count 4.chr)+5.chr*(s.count 5.chr)+6.chr*(s.count 6.chr)+7.chr*(s.count 7.chr)+8.chr*(s.count 8.chr)+9.chr*(s.count 9.chr)+10.chr*(s.count 10.chr)+11.chr*(s.count 11.chr)+12.chr*(s.count 12.chr)+13.chr*(s.count 13.chr)+14.chr*(s.count 14.chr)+15.chr*(s.count 15.chr)+16.chr*(s.count 16.chr)+17.chr*(s.count 17.chr)+18.chr*(s.count 18.chr)+19.chr*(s.count 19.chr)+20.chr*(s.count 20.chr)+21.chr*(s.count 21.chr)+22.chr*(s.count 22.chr)+23.chr*(s.count 23.chr)+24.chr*(s.count 24.chr)+25.chr*(s.count 25.chr)+26.chr*(s.count 26.chr)+27.chr*(s.count 27.chr)+28.chr*(s.count 28.chr)+29.chr*(s.count 29.chr)+30.chr*(s.count 30.chr)+31.chr*(s.count 31.chr)+32.chr*(s.count 32.chr)+33.chr*(s.count 33.chr)+34.chr*(s.count 34.chr)+35.chr*(s.count 35.chr)+36.chr*(s.count 36.chr)+37.chr*(s.count 37.chr)+38.chr*(s.count 38.chr)+39.chr*(s.count 39.chr)+40.chr*(s.count 40.chr)+41.chr*(s.count 41.chr)+42.chr*(s.count 42.chr)+43.chr*(s.count 43.chr)+44.chr*(s.count 44.chr)+45.chr*(s.count 45.chr)+46.chr*(s.count 46.chr)+47.chr*(s.count 47.chr)+48.chr*(s.count 48.chr)+49.chr*(s.count 49.chr)+50.chr*(s.count 50.chr)+51.chr*(s.count 51.chr)+52.chr*(s.count 52.chr)+53.chr*(s.count 53.chr)+54.chr*(s.count 54.chr)+55.chr*(s.count 55.chr)+56.chr*(s.count 56.chr)+57.chr*(s.count 57.chr)+58.chr*(s.count 58.chr)+59.chr*(s.count 59.chr)+60.chr*(s.count 60.chr)+61.chr*(s.count 61.chr)+62.chr*(s.count 62.chr)+63.chr*(s.count 63.chr)+64.chr*(s.count 64.chr)+65.chr*(s.count 65.chr)+66.chr*(s.count 66.chr)+67.chr*(s.count 67.chr)+68.chr*(s.count 68.chr)+69.chr*(s.count 69.chr)+70.chr*(s.count 70.chr)+71.chr*(s.count 71.chr)+72.chr*(s.count 72.chr)+73.chr*(s.count 73.chr)+74.chr*(s.count 74.chr)+75.chr*(s.count 75.chr)+76.chr*(s.count 76.chr)+77.chr*(s.count 77.chr)+78.chr*(s.count 78.chr)+79.chr*(s.count 79.chr)+80.chr*(s.count 80.chr)+81.chr*(s.count 81.chr)+82.chr*(s.count 82.chr)+83.chr*(s.count 83.chr)+84.chr*(s.count 84.chr)+85.chr*(s.count 85.chr)+86.chr*(s.count 86.chr)+87.chr*(s.count 87.chr)+88.chr*(s.count 88.chr)+89.chr*(s.count 89.chr)+90.chr*(s.count 90.chr)+91.chr*(s.count 91.chr)+92.chr*(s.count 92.chr)+93.chr*(s.count 93.chr)+94.chr*(s.count 94.chr)+95.chr*(s.count 95.chr)+96.chr*(s.count 96.chr)+97.chr*(s.count 97.chr)+98.chr*(s.count 98.chr)+99.chr*(s.count 99.chr)+100.chr*(s.count 100.chr)+101.chr*(s.count 101.chr)+102.chr*(s.count 102.chr)+103.chr*(s.count 103.chr)+104.chr*(s.count 104.chr)+105.chr*(s.count 105.chr)+106.chr*(s.count 106.chr)+107.chr*(s.count 107.chr)+108.chr*(s.count 108.chr)+109.chr*(s.count 109.chr)+110.chr*(s.count 110.chr)+111.chr*(s.count 111.chr)+112.chr*(s.count 112.chr)+113.chr*(s.count 113.chr)+114.chr*(s.count 114.chr)+115.chr*(s.count 115.chr)+116.chr*(s.count 116.chr)+117.chr*(s.count 117.chr)+118.chr*(s.count 118.chr)+119.chr*(s.count 119.chr)+120.chr*(s.count 120.chr)+121.chr*(s.count 121.chr)+122.chr*(s.count 122.chr)+123.chr*(s.count 123.chr)+124.chr*(s.count 124.chr)+125.chr*(s.count 125.chr)+126.chr*(s.count 126.chr)+127.chr*(s.count 127.chr)+128.chr*(s.count 128.chr)+129.chr*(s.count 129.chr)+130.chr*(s.count 130.chr)+131.chr*(s.count 131.chr)+132.chr*(s.count 132.chr)+133.chr*(s.count 133.chr)+134.chr*(s.count 134.chr)+135.chr*(s.count 135.chr)+136.chr*(s.count 136.chr)+137.chr*(s.count 137.chr)+138.chr*(s.count 138.chr)+139.chr*(s.count 139.chr)+140.chr*(s.count 140.chr)+141.chr*(s.count 141.chr)+142.chr*(s.count 142.chr)+143.chr*(s.count 143.chr)+144.chr*(s.count 144.chr)+145.chr*(s.count 145.chr)+146.chr*(s.count 146.chr)+147.chr*(s.count 147.chr)+148.chr*(s.count 148.chr)+149.chr*(s.count 149.chr)+150.chr*(s.count 150.chr)+151.chr*(s.count 151.chr)+152.chr*(s.count 152.chr)+153.chr*(s.count 153.chr)+154.chr*(s.count 154.chr)+155.chr*(s.count 155.chr)+156.chr*(s.count 156.chr)+157.chr*(s.count 157.chr)+158.chr*(s.count 158.chr)+159.chr*(s.count 159.chr)+160.chr*(s.count 160.chr)+161.chr*(s.count 161.chr)+162.chr*(s.count 162.chr)+163.chr*(s.count 163.chr)+164.chr*(s.count 164.chr)+165.chr*(s.count 165.chr)+166.chr*(s.count 166.chr)+167.chr*(s.count 167.chr)+168.chr*(s.count 168.chr)+169.chr*(s.count 169.chr)+170.chr*(s.count 170.chr)+171.chr*(s.count 171.chr)+172.chr*(s.count 172.chr)+173.chr*(s.count 173.chr)+174.chr*(s.count 174.chr)+175.chr*(s.count 175.chr)+176.chr*(s.count 176.chr)+177.chr*(s.count 177.chr)+178.chr*(s.count 178.chr)+179.chr*(s.count 179.chr)+180.chr*(s.count 180.chr)+181.chr*(s.count 181.chr)+182.chr*(s.count 182.chr)+183.chr*(s.count 183.chr)+184.chr*(s.count 184.chr)+185.chr*(s.count 185.chr)+186.chr*(s.count 186.chr)+187.chr*(s.count 187.chr)+188.chr*(s.count 188.chr)+189.chr*(s.count 189.chr)+190.chr*(s.count 190.chr)+191.chr*(s.count 191.chr)+192.chr*(s.count 192.chr)+193.chr*(s.count 193.chr)+194.chr*(s.count 194.chr)+195.chr*(s.count 195.chr)+196.chr*(s.count 196.chr)+197.chr*(s.count 197.chr)+198.chr*(s.count 198.chr)+199.chr*(s.count 199.chr)+200.chr*(s.count 200.chr)+201.chr*(s.count 201.chr)+202.chr*(s.count 202.chr)+203.chr*(s.count 203.chr)+204.chr*(s.count 204.chr)+205.chr*(s.count 205.chr)+206.chr*(s.count 206.chr)+207.chr*(s.count 207.chr)+208.chr*(s.count 208.chr)+209.chr*(s.count 209.chr)+210.chr*(s.count 210.chr)+211.chr*(s.count 211.chr)+212.chr*(s.count 212.chr)+213.chr*(s.count 213.chr)+214.chr*(s.count 214.chr)+215.chr*(s.count 215.chr)+216.chr*(s.count 216.chr)+217.chr*(s.count 217.chr)+218.chr*(s.count 218.chr)+219.chr*(s.count 219.chr)+220.chr*(s.count 220.chr)+221.chr*(s.count 221.chr)+222.chr*(s.count 222.chr)+223.chr*(s.count 223.chr)+224.chr*(s.count 224.chr)+225.chr*(s.count 225.chr)+226.chr*(s.count 226.chr)+227.chr*(s.count 227.chr)+228.chr*(s.count 228.chr)+229.chr*(s.count 229.chr)+230.chr*(s.count 230.chr)+231.chr*(s.count 231.chr)+232.chr*(s.count 232.chr)+233.chr*(s.count 233.chr)+234.chr*(s.count 234.chr)+235.chr*(s.count 235.chr)+236.chr*(s.count 236.chr)+237.chr*(s.count 237.chr)+238.chr*(s.count 238.chr)+239.chr*(s.count 239.chr)+240.chr*(s.count 240.chr)+241.chr*(s.count 241.chr)+242.chr*(s.count 242.chr)+243.chr*(s.count 243.chr)+244.chr*(s.count 244.chr)+245.chr*(s.count 245.chr)+246.chr*(s.count 246.chr)+247.chr*(s.count 247.chr)+248.chr*(s.count 248.chr)+249.chr*(s.count 249.chr)+250.chr*(s.count 250.chr)+251.chr*(s.count 251.chr)+252.chr*(s.count 252.chr)+253.chr*(s.count 253.chr)+254.chr*(s.count 254.chr)+255.chr*(s.count 255.chr)

```

---
Tags: code-challenge, sorting
---


title: Numerical Integration through Plotting

text:
# Question
Title: Numerical Integration through Plotting
Inspired by this on Spiked Math:

<sub>(source: spikedmath.com)</sub>

In this code golf, you are going to write a numerical integrator. Instead of weighting, you first plot on a graphic canvas pixel-by-pixel or plot on a 2D array, then calculate the integral by counting the colored pixels.

You are implementing a function with the following arguments:

* `f`: the function, in lambda or function pointer
* `xmin`, `xmax`: the interval, also the familiar window settings on a typical graphic calculator
* `ymin`, `ymax`: window settings for y-axis, note: it is the caller's responsibility to choose ymax, because the function can go over ymax, and the parts went over will not be counted.
* `xres`, `yres`: resolution of the plot: size of the canvas or the dimensions of the 2D array

Here is an explanation:

To integrate `sin(x)` from 1.0 to 8.0 with y = -1.0 to 1.0, and resolution 30 * 15, first plot

```
 ++++                       ++
++++++                     +++
+++++++                   ++++
++++++++                 +++++
++++++++                 +++++
+++++++++               ++++++
+++++++++              +++++++
          -------------
           -----------
           -----------
            ---------
            --------
             -------
              -----

```

Count the total number of `+`s: 83 total number of `-`s: 64 and N = 83 - 64 = 19

(the formula for N is actually notice `xres-1`, x never equal to `xres`, don't make this off-by-one error )

and calculate the integral:

```
N / canvas size * window area
= (N / (xres * yres) ) * ((ymax - ymin) * (xmax - xmin))
= 19 / (30 * 15) * ((1 - (-1)) * (8 - 1))
~= 0.5911

```

Shortest code wins.

Test cases:

```
| f(x)       |  xmin |  xmax |  ymin | ymax  | xres | yres | S f(x) dx |
| 3          |  0.0  |  10.0 |   0.0 |   2.0 |   25 |   25 |  20.0     |
| 3          |  0.0  |  10.0 |   0.0 |   5.0 |    5 |    5 |  30.0     |
| 3          |  0.0  |  10.0 |   0.0 |   4.0 |    5 |    5 |  32.0     |
| 2x + 2     | -5.0  |   5.0 | -10.0 |  10.0 |   50 |   50 |  18.72    |
| 2x + 2     | -5.0  |   5.0 | -20.0 |  20.0 |  500 |  500 |  20.1648  |
| x^2        |  0.0  |  10.0 |   0.0 | 120.0 |   10 |   10 | 348.0     |
| x^2        |  0.0  |  10.0 |   0.0 | 120.0 |  100 |  100 | 335.88    |
| x^2        |  0.0  |  10.0 |   0.0 | 120.0 |  500 |  500 | 333.6768  |
| x^2 sin(x) | -3.14 |  3.14 |  -5.0 |   5.0 |   50 |   50 |   0.60288 |
| x^2 sin(x) | -3.14 |  3.14 |  -5.0 |   5.0 | 1500 | 1500 |   0.60288 |
| sin(x^2)   |  0.0  | 10.0  |  -1.0 |   1.0 |  250 |   50 |   0.7808  |
| sin(x^2)   |  0.0  | 10.0  |  -1.0 |   1.0 | 1000 | 1000 |   0.59628 |

```

# Answer
**Lua, 219 chars**

Done it all in 1 step, no need for an intermediate table. Plots the function too ;)

```
function I(f,x,X,y,Y,r,R)I=io.write N=0 for k=R-1,0,-1 do for l=0,r-1 do v=f(x+l*(X-x)/r) K=y+k*(Y-y)/R c=(K<0 and K>v)and'-'or(K>0 and K<v and'+')or' 'N=c=="+"and N+1 or(c=="-"and N-1 or N)I(c)end I'\n'end return N end

```

Test code:

```
assert(I(math.sin,1.0,8.0,-1,1,30,15)==19)

```
> 2 votes

---
Tags: code-golf, calculus
---


# Question
Title: Fastest alphabetical list sort given the following limitations:
Your function must have an input that takes in an array containing 10000 random names, and must sort these names in alphabetical order. Names have a random length of up to 128 characters. ISO/IEC 8859-1 character set assumed to be used for the list of names.

Usable list of names can be found at http://www.opensourcecf.com/1/2009/05/10000-Random-Names-Database.cfm (firstNameFirst column).

You may not use any native sorting functions available to your language.

The winner will be based purely on speed.

Language used must be compilable/runnable on a standard \*nix box.

# Answer
## C - B-tree sort

This sorts randomNames.csv in about 5.8ms on my Core 2 T5500 @ 1.66GHz. My testing utility is here.

It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like trieing.

```
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Btree Btree;

static void btree_insert(Btree **btree, const char *key);
static void btree_emit_and_free(Btree *btree, const char ***out);

void sort(const char **strings, size_t count, const char **out)
{
    size_t i;
    Btree *tree = NULL;
    const char **out_start = out;

    for (i = 0; i < count; i++)
        btree_insert(&tree, strings[i]);

    btree_emit_and_free(tree, &out);

    assert(out - out_start == (ssize_t) count);
}

/*
 * Maximum (U) and minimum (L) number of *keys* per B-tree node.
 *
 * The maximum number of *branches* a B-tree may have is U+1 :
 *
 *       KEY   KEY
 *     /     |     \
 * branch  branch  branch
 */
#define U 20
#define L (U / 2)

struct Btree {
    /* Number of keys (rather than branches). */
    unsigned char count;

    /* 0 if node is a leaf, 1 if it has leaf children, etc. */
    unsigned char depth;

    const char *keys[U];

    /* Allocated to U+1 items if this is an internal node. */
    Btree *branches[];
};

static Btree *allocLeaf(void)
{
    return malloc(sizeof(Btree));
}

static Btree *allocInternal(void)
{
    return malloc(sizeof(Btree) + (U+1) * sizeof(Btree *));
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr);
static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr);
static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x);

static void btree_insert(Btree **btree, const char *key)
{
    if (*btree == NULL) {
        Btree *root = allocLeaf();
        root->count = 1;
        root->depth = 0;
        root->keys[0] = key;
        *btree = root;
    } else {
        const char *new_x;
        Btree *new_xr;

        if (insert(*btree, key, &new_x, &new_xr)) {
            Btree *root = allocInternal();
            root->count = 1;
            root->depth = (*btree)->depth + 1;
            root->keys[0] = new_x;
            root->branches[0] = *btree;
            root->branches[1] = new_xr;
            *btree = root;
        }
    }
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr)
{
    unsigned int k = find_insertion_point(node->keys, node->count, x);
    Btree *xr;

    if (node->depth == 0)
        xr = NULL;
    else if (insert(node->branches[k], x, new_x, new_xr))
        x = *new_x, xr = *new_xr;
    else
        return false;

    return insert_item(node, k, x, xr, new_x, new_xr);
}

static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr)
{
    unsigned int i;
    bool internal = xr != NULL;

    if (node->count < U) {
        /* Enough case */
        for (i = node->count; i-- > k;)
            node->keys[i + 1] = node->keys[i];
        node->keys[k] = x;
        if (internal) {
            for (i = node->count + 1; i-- > k + 1;)
                node->branches[i + 1] = node->branches[i];
            node->branches[k + 1] = xr;
        }
        node->count++;
        return false;
    } else {
        Btree *r = internal ? allocInternal() : allocLeaf();

        node->count = L;
        r->count = L;
        r->depth = node->depth;

        if (k < L) {
            /* Left case */
            *new_x = node->keys[L - 1];
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            for (i = L - 1; i-- > k;)
                node->keys[i + 1] = node->keys[i];
            node->keys[k] = x;
            if (internal) {
                for (i = 0; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
                for (i = L; i-- > k + 1;)
                    node->branches[i + 1] = node->branches[i];
                node->branches[k + 1] = xr;
            }
        } else if (k == L) {
            /* Central case */
            *new_x = x;
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                r->branches[0] = xr;
                for (i = 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        } else {
            /* Right case */
            *new_x = node->keys[L];
            for (i = 0; i < k - L - 1; i++)
                r->keys[i] = node->keys[i + L + 1];
            r->keys[k - L - 1] = x;
            for (i = k - L; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                for (i = 0; i < k - L; i++)
                    r->branches[i] = node->branches[i + L + 1];
                r->branches[k - L] = xr;
                for (i = k - L + 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        }

        *new_xr = r;
        return true;
    }
}

static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x)
{
    unsigned int start = 0;
    unsigned int middle;

    while (count) {
        middle = count >> 1;
        if (strcmp(x, keys[start + middle]) < 0) {
            count = middle;
        } else {
            start += middle + 1;
            count -= middle + 1;
        }
    }

    return start;
}

static void btree_emit_and_free(Btree *btree, const char ***out)
{
    unsigned int i;

    if (btree->depth == 0) {
        for (i = 0; i < btree->count; i++)
            *(*out)++ = btree->keys[i];
    } else {
        for (i = 0; i < btree->count; i++) {
            btree_emit_and_free(btree->branches[i], out);
            *(*out)++ = btree->keys[i];
        }
        btree_emit_and_free(btree->branches[btree->count], out);
    }

    free(btree);
}

```
> 1 votes

---
Tags: sorting, fastest-code
---


title: Determine if a polygon is convex

text:
# Question
Title: Determine if a polygon is convex
Write a program to determine if the input polygon is convex. The polygon is specified with one line containing *N*, the number of vertices, then *N* lines containing the *x* and *y* coordinates of each vertex. The vertices will be listed clockwise starting from an arbitrary vertex.

## example 1

### input

```
4
0 0
0 1
1 1
1 0

```

### output

```
convex

```

## example 2

### input

```
4
0 0
2 1
1 0
2 -1

```

### output

```
concave

```

## example 3

### input

```
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

```

### output

```
convex

```

*x* and *y* are integers, *N\<1000*, and *|x|,|y|\<1000*. You may assume that the input polygon is simple (none of the edges cross, only 2 edges touch each vertex). Shortest program wins.

# Answer
# J, 105

```
echo>('concave';'convex'){~1=#=(o.1)([:>-.~)(o.2)|3([:-/12 o.-@-/@}.,-/@}:)\(,2&{.)j./"1}.0&".;._2(1!:1)3

```

Passes all three tests above.

**Edit:** (111-\>115) Handle co-linear points by eliminating angles of pi. Gained a few characters elsewhere.

**Edit:** (115-\>105) Less dumb.

Explanation for the J-impaired:

* `(1!:1)3` read STDIN to EOF. (I think.)
* `0&".;._2` is a nice idiom for parsing this kind of input.
* `j./"1}.` lop off first line of input (N 0) and convert pairs to complexes.
* `(,2&{.)` tack first two points onto the end of the list.
* `3(f)\` applies f to sliding window of length 3 (3 points for an angle)
* `[:-/12 o.-@-/@}.,-/@}:` is a verb that transforms each 3 points into an angle between -pi and pi.
    + `-@-/@}.,-/@}:` produces (p1 - p2),(p3 - p2). (Recall that these are complexes.)
    + `12 o.` gives an angle for each complex.
    + `[:-/(...)` gives the difference of the two angles.
* `(o.1)([:>-.~)(o.2)|` mod 2 pi, eliminate angles of pi (straight segments), and compare to pi (greater than, less than, doesn't matter unless the points are supposed to be wound in one direction).
* `1=#=` if all those comparison result 1 or 0 (With self-classify. This seems dumb.)
* `echo>('concave';'convex'){~` print convex.
> 4 votes

# Answer
## Python - 149 chars

```
p=[map(int,raw_input().split())for i in[0]*input()]*2
print'ccoonncvaevxe'[all((a-c)*(d-f)<=(b-d)*(c-e)for(a,b),(c,d),(e,f)in zip(p,p[1:],p[2:]))::2]

```
> 3 votes

# Answer
## Ruby 1.9, 147 133 130 124 123

```
gets
puts ($<.map{|s|s.split.map &:to_i}*2).each_cons(3).any?{|(a,b),(c,d),(e,f)|(e-c)*(d-b)<(d-f)*(a-c)}?:concave: :convex

```
> 2 votes

# Answer
### scala: 297 chars

```
object C{class D(val x:Int,val y:Int)
def k(a:D,b:D,c:D)=(b.y-a.y)*(c.x-b.x)>=(c.y-b.y)*(b.x-a.x)
def main(a:Array[String]){val s=new java.util.Scanner(System.in)
def n=s.nextInt
val d=for(x<-1 to n)yield{new D(n,n)}print((true/:(d:+d.head).sliding(3,1).toList)((b,t)=>b&&k(t(0),t(1),t(2))))}}

```
> 1 votes

---
Tags: code-golf, math, geometry, decision-problem
---


title: Lossy Text Compression

text:
# Question
Title: Lossy Text Compression
## Background

Of the 256 possible characters that a byte can represent, only a few of these are used under most circumstances. Couldn't we somehow take advantage of this, and make our text files smaller by eliminating the need for the rarely used letters?

Many letters don't add any value in most situations, and can be replaced by more common letters. For example, a lower-case "L", capital "I", and the number "1" look nearly identical in most situations, so they can be consolidated.

There is little need for capital letters, so they can be dispensed with. The decompression/display program could even automatically capitalize the first letter of every sentence, common names, etc.

## Rules

Entries will be judged on:

* compression ratio
* readability after de-compression

Entries will be tested against the plain text version of this article: http://en.wikipedia.org/wiki/Babbage and a randomly selected BBC News article.

Extra marks will be awarded for; preserving any mark-up, beautifying after de-compression (i.e. Capitalising sentences etc).

### Languages

* Any you like, but must easily compile (or be interpreted) on a basic \*nix box.

# Answer
# Perl

Very inefficient and has bad rates. Requires `/usr/share/dict/words`.

## Compressor

```
#!/usr/bin/perl

$M = 2;
$N = 1;
$Min = 3;
$Max = 8;

while (<>) {
  for (split /\s+/) {
    s/[^a-z]//i;
    ($p) = m/([^a-z]*)$/;
    $_ = lc $_;
    $l = (length $_) - (length $p);
    s/^and$/A/;
    s/^he$/H/;
    s/^in$/I/;
    s/^of$/O/;
    s/^you$/U/;
    s/^the$/Z/;
    if (length $_ >= $Min) {
      if (length $_ <= $Max) {
        s/ed/D/g;
        s/ing\b/N/g;
        s/er/R/g;
        s/'s/S/g;
        s/th/T/g;
        s/[aeo]{1,2}//g;
        $_ .= $l;
      } else {
        s/^(.{$M})(.+)(\w{$N})$/$1.(length$2).$3/e;
      }
    }
    $a .= $_ . $p . ' ';
  }
}
print $a;

```

## Decompressor

```
#!/usr/bin/perl

$M = 2;
$N = 1;

open D, '/usr/share/dict/words';
chomp, push @W, $_ while <D>;
close D;

while (<>) {
  for (split /\s+/) {
    ($_, $p) = m/^(.+)([^a-z]*)$/;
    s/^A$/and/;
    s/^H$/he/;
    s/^I$/in/;
    s/^O$/of/;
    s/^U$/you/;
    s/^Z$/the/;
    if ($_ =~ m/^(\w{$M})(\d+)(\w{$N})$/) {
      $r = '^' . quotemeta($1) . ('\w' x $2) . quotemeta($3) . '$';
      ($_) = (grep /$r/, @W);
      $_ .= $4;
    } else {
      ($_, $l) = m/^(.+)(\d+)$/;
      s/D/ed/g;
      s/N/ing/g;
      s/R/er/g;
      s/S/'s/g;
      s/T/th/g;
      $r = '[aeo]{0,2}';
      for $y(split //) { $r .= (quotemeta $y) . '[aiueo]{0,2}' }
      ($_) = (grep /^(?=[a-z]{$l})$r$/, @W);
    }
    $a .= $_ . $p . ' ';
  }
}
print $a;

```
> 10 votes

# Answer
## Bash, 5 chars

My lazy entry that just might win:

```
bzip2

```

Lossless, so it preserves readability perfectly and gets all the extra marks! Compression ratio on the Babbage html is 4.79x (153804 to 32084 bytes).
> 2 votes

# Answer
## Perl, 0 chars

Compression ratio of infinity, though not that readable after decompression so it will lose some marks.
> 2 votes

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