text:
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.

Most dynamic languages have a sort function that doesn’t require any sort of import.

@Tmwi: All kinds of sorting function are forbidden.

So any functional implementation is OK?

You know, there are plenty of languages that don't even know the concept of a variable. Furthermore, some languages have control-structure-like constructs that are not syntax, but could be considered library functions (e.g. cmdlets in PowerShell). Are those forbidden, too?

Not really possible to do in assembly then.

@Skizz: There is LLVM. AFAIK, it is designed to use only non-mutable variables. They will be allocated to registers by the llvm compiler.

And the analyzer will re-use registers as needed, which points out the silliness of the constraint: every solution is re-using memory, it's just hidden under one or more layers of language abstraction. In the case of my solution, the stack gets overwritten time and time again or if the compiler does tail call elimination it's the return value that gets overwritten.

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.

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

And now adapt it for Unicode :P

print''.join(map(lambda x:unichr(x)*s.count(unichr(x)),range(0x10000))) would be a lot more compact, but a lot less entertaining.

@Joey: Assuming it's written the same way as this, that solution would be 36771719 characters.  Unicode goes from 0 to 1114111.  Interestingly enough, 1114111 is also a prime number.

Err, wait, it didn't occur to me that chr only works on 0-255.

taps foot impatiently

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.

Your answer is neither a complete program nor do you use pattern guards to shorten the code.

main=getLine>>=putStrLn.s and defining i as an operator: m%[]=[m] etc... will save some characters

Replace s with a fold: main=getLine>>=putStrLn.foldr(%)[]

You may consider using interact like this: main=interact$foldr(%)[]

I didn't suggest interact originally before because it will cause the newline character to be sorted in as well. However, now re-reading the question, it is totally silent about handling of newlines. So, yes, great idea!

114-character merge sort version: c[x]=x;c x=c.d$x;d(x:y:z)=x%y:d z;d x=x;[]%x=x;x%[]=x;x@(a:b)%y@(c:d)|a>c=c:x%d|1>0=a:b%y;main=interact$c.map(:[])

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.

You sad, it stack-overflows too often? Then your algorithm is probably not good for this task.

@FUZxxl: Actually, I never made it overflow the stack, and the size of the stack is an implementation detail. I wouldn't worry about it on Mac System 6 or an Apple ][. More to the point if you set a silly task you get silly answers.

@dmckee: Maybe this task was really silly. I had the idea of giving a task to implement something using only constant variables, and chose sorting for this.

You misspelt supercalifragilisticexpialidocious! :)

@Timwi: LOL. You may be shocked if I every spell anything like that right.

@FUZxxl: This shouldn't stack-overflow at all if the compiler optimizes tail recursion.

@Joey: Hey! I hadn't noticed that I did that. I'm using gcc, which can.

Well, as long as you use -O2.

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

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)

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

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

+1 :) Impressive! Don't try this at home :) with a too big file (3600 bytes).

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

You also misspelled supercalifragilisticexpialidocious.  I think if one more person does it, it counts as a meme.

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())

I believe the for loop modifies the value of y, so I think it is not allowed...

The same could be said for any of the recursive solutions.

Would you be happier if I used filter(lambda y:y<x[0],x)?  Or is that not allowed also?

I can’t speak for the OP, but personally I would allow that: after all, my solution does that too :)

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)


text:
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.

So PowerShell is out? Bummer.

Haskell: main = interact (\x -> take 90 x ++ " yada yada yada")

Note also that "readability after decompression" is a fairly subjective criterion.

Especially on a Unix-Box, we need the distinction upper case, lower case. :) And finding the beginning of a sent. Isn't trivial, if the u. Uses abbrev.! :)

Do we want to compress the alphabet or the text? :) L = l = 1 compresses the characters needed to represent our thoughts. But "one apple" = "1 apl" compresses the text.

remove all vowels and reduce inflections, then in decompression, use dictionary to find the correct full word

Assuming the input consists only of printable ASCII (7-bit) characters, we don't need any of the non-printable ASCII chars. Replacing \r\n with \n, replacing \t with some spaces, converting all upper-case letters to lower-case, and ignoring or substituting 6 seldomly used special characters, we're left with 64 characters that we need to encode -- in other words, a 4-bit encoding would be sufficient. We could therefore store 2 characters per byte, saving up to 50%. If we take 8-bit input (like ISO-8859 letters with diacritic marks) we would need to convert them to plain ASCII beforehand.

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;

Perl, 0 chars
Compression ratio of infinity, though not that readable after decompression so it will lose some marks.

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).

Somehow I knew that was coming with that challenge ;-)

That's going to be hard to beat.

Hah! I beat it in both length and compression ratio ;)

xz, even shorter and better ratio :)

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Manchester encode a data stream
Manchester coding is a telecom protocol used in radio communications that guarantees bit transitions at a regular interval so a receiver can recover the clock rate from the data itself. It doubles the bitrate, but is cheap and simple to implement.  It is widely used by amateur radio operators.
The concept is very simple: at a hardware level, the clock and data lines are simply XORed together.  In software, this is portrayed as converting an input stream of bits into a double-rate output stream, with each input '1' translated to a '01' and each input '0' translated to a '10'.
This is an easy problem, but open to a lot of implementations because of its bitstream nature.  That is, the encoding is conceptually a bit-by-bit process instead of a byte-by-byte process.  So we all agree on endianness, the least significant bits of the input become the least significant byte of the output.
Golfing time!  Write a function that, given an arbitrary length array of bytes, returns an array of that data manchester encoded.
Input and output should be considered little-endian, least significant byte first, and least significant BIT first in the bit stream.
ASCII bitstream drawing:
bit #      5 4 3 2 1 0                                5  4  3  2  1  0
IN ------- 1 0 1 0 1 1 ---> [manchester encoder] ---  01 10 01 10 01 01 ----> OUT

Examples:
Example 1 (hex):
       LSB              MSB     <-- least sig BYTE first
IN : [0x10, 0x02]
OUT: [0xAA, 0xA9, 0xA6, 0xAA]

Example 1 (binary):
      msb  lsb                      msb  lsb  <-- translated hex, so msb first
BIN: [00010000, 00000010]                     <-- least sig NIBBLE...
BIN: [10101010, 10101001, 10100110, 10101010] <-- becomes least sig BYTE
         LSB                           MSB

Example 2
IN :  [0xFF, 0x00, 0xAA, 0x55]
OUT: [0x55, 0x55, 0xAA, 0xAA, 0x66, 0x66, 0x99, 0x99]

Example 3
IN : [0x12, 0x34, 0x56, 0x78, 0x90]
OUT: [0xA6, 0xA9, 0x9A, 0xA5, 0x96, 0x99, 0x6A, 0x95, 0xAA, 0x69]

Example 4
IN : [0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]
OUT: [0xA9, 0xAA, 0xA6, 0xAA, 0xA5, 0xAA, 0xA9, 0x55, 0xA6, 0x55, 0xA5, 0x55]

Rules:

Solution only requires algorithm to convert input to output.
Acquiring input and printing output are NOT a required part of the solution, but may be included.  You are encouraged to provide your test/print code if not included in your solution.
Input is an array of 8-bit bytes (whatever that may mean in your language of choice), NOT a text string.  You can use strings as the storage format if convenient in your language, but non-printable characters (i.e. 0xFF) must be supported.  Input can also take a length if necessary.
Memory for output must be allocated by your routine, not provided. edit: unnecessary requirement
Output is also an array of 8-bit bytes, and a length if necessary.
Must support at least 16KB input
Performance must not be too horrible: < 10s for 16KB
Least-significant byte first in memory.

Side-channel challenge:

Challenge another user's answer by proving your code is faster, more memory efficient, or produces a smaller binary!

Get golfing!  Shortest code wins!

"Memory for output must be allocated by your routine, not provided." That seems like quite a strange requirement since many languages have completely automatic memory allocation.

What on Earth possessed you to use such a bizarre bit order?

The bit order makes sense when you consider the physical medium this is used for; this algorithm is for a stream of individual bits travelling through the air.  The fact that we have to store it in memory, and that we write hex msb->lsb, makes it a little tricky to keep track of.

GolfScript 28 characters
{2{base}:|~4|43691-~256|~\}%

Equivalent version without obfuscating optimization:
{2base 4base 43691-~256base~\}%

The code accept input as an array of integers, and return ditto.
For each number in the array the number is converted to base 2 array form, it is then converted back to a number as if it was base 4, this has the effect of spacing out the bits with a 0 in between each. 43691 is then subtracted from the number, and the result is binary inverted, this is equivalent to subtracting the number from 43690 (43690 = 0b1010101010101010). The number is then split into two parts by converting it to a base 256 array, the array is decomposed and the order of the two resulting numbers is inverted.
Example input:
[1 2 3 241 242 243]

Example output:
[169 170 166 170 165 170 169 85 166 85 165 85]

That's ridiculously short, and very clever!  Though it doesn't seem to meet the 16KB in <10s performance suggestion, at least for me; yours takes 43s on my dual-core Mac to convert an array of 16384 1's.  In comparison, my massive (2419 char) python implementation takes 0.06s for 16KB.

It takes less than 5 seconds on my machine (Win 7), and most of that is converting the array to text output, which as far as I read your question isn't part of the requirement, but GolfScript does so automatically with anything left on the stack after execution. One could simply make the code drop the result rather than print it (add ; to the end of the code). If you want to see the output (though that is not part of the question specs.) I know two tricks for speeding it up, redirect it to a file, and print it explicitly in small chunks using print commands: {2{base}:|~4|43691-~256|~p p}%

In an ubuntu vm (on windows), I get 8s for 16kb. On a mac with a better cpu it took 1m18. I'd guess the ruby than ships with OSX is just terribly slow

Looks like the ruby printing is disgustingly slow on my machine.  Only 2s with printing turned off and Ruby 1.9 (and 5s with the native OSX version). That's much better!

c -- 224 characters
I believe that this is functional, including the allocation of memory requirement since dropped.
#include <stdlib.h>
int B(char i){int16_t n,o=0xFFFF;for(n=0;n<8;++n)o^=((((i>>n)&1)+1))<<(2*n);
return o;}char* M(char*i,int n){char*o=calloc(n+1,2),*p=o;do{int r=B(*i++);
*p++=0xFF&r;*p++=(0xFF00&r)>>8;}while(--n);return o;}

The working part of the code is a loop over the bits of each character, noting that ((bit+1) exclusive-or 3) is the output bit pair, and applying lots of shifting and masking logic to get everything to line up.
As is c's wont, it works on the data as characters. The test scaffold won't accept 0 bytes (because c treats them as string ending), but the working code has no such limitation.
It might be golfed  little more by copy the byte conversion work inline.
Test run (with improved test scaffold):
$ gcc -g manchester_golf.c
$ ./a.out AB xyz U
'AB':
[ 0x41, 0x42 ]
[ 0xa9, 0x9a, 0xa6, 0x9a ]
'xyz':
[ 0x78, 0x79, 0x7a ]
[ 0x6a, 0x95, 0x69, 0x95, 0x66, 0x95 ]
'U':
[ 0x55 ]
[ 0x99, 0x99 ]

Commented, less machine dependent, and with test scaffold
/* manchester.c
 *
 * Manchester code a bit stream least significant bit first
 *
 * Manchester coding means that bits are expanded as {0,1} --> {10, 01}
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdint.h>
#include <string.h>

/* Caller must insure that out points to a valid, writable two byte
   buffer filled with 0xFF */
int16_t manByte(char i){
  int16_t n,o=0xFFFF;
  printf("Manchester coding byte 0x%hx...\n",i);
  for(n=0; n<CHAR_BIT; ++n)
    o ^= (
      (
       (
        (i>>n)&1) /* nth bit of i*/
       +1) /* +1 */
      ) <<(2*n) /* shifted up 2*n bits */
      ;
  printf("\tas 0x%hx\n",o);
  return o;
}

char* manBuf(const char*i, int n){
  char*o=calloc(n+1,2),*p=o;
  do{
    int16_t r=manByte(*i++);
    *p++= 0xFF&r;
    *p++=(0xFF00&r)>>8;
  } while(--n);
  return o;
}

void pbuf(FILE* f, char *buf, int len){
  int i;
  fprintf(f,"[");
  for(i=0; i<len-1; i++)
    fprintf(f," 0x%hhx,",buf[i]);
  fprintf(f," 0x%hhx ]\n",buf[len-1]);
}

int main(int argc, char**argv){
  int i;
  for(i=1; i<argc; i++){
    int l=strlen(argv[i]);
    char *o=manBuf(argv[i],l);
    printf("'%s':\n",argv[i]);
    pbuf(stdout,argv[i],l);
    pbuf(stdout,o,l*2);
    free(o);
  }
  return 0;
}

J, 36
,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)

Outline of explanation (See J Vocabulary for reference):

,@:(3 :'...'"0) applies the ... to each input "byte" as y, resulting in two bytes (integers) each. The result is flattened by ,.
y#:~8#2 is equivalent to 2 2 2 2 2 2 2 2 #: y, or vector of the 8 least significant base-2 digits of y.
4|. swaps the front and back 4 bits by rotating by 4 positions.
(,.~-.) is equivalent to 3 :'(-. y) ,. y', or not of the argument 'stitched' to the argument (taking on shape 8 2).
#.2 8$, flattens the result giving the bitstream, reshapes to 2 rows of 8, and converts from base 2.

Example usage (J, interactive):
    ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
169 170 166 170 165 170 169 85 166 85 165 85

Speed information (J, interactive):
   manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
   data =: 256 | i. 16384
data =: 256 | i. 16384
   100 (6!:2) 'manchester data'
100 (6!:2) 'manchester data'
0.243138

Mean time for 16kb is just under .25s, Intel Core Duo 1.83Ghz or similar.

OCaml + Batteries, 138 117 characters
let m s=Char.(String.(of_enum[?chr(170-Enum.sum[?d land
p*p|p<-List:[1;2;4;8]?])|c<-enum s/@code;d<-List:[c;c/16]?]))

Tests:
With
let hex s = String.(enum s/@(Char.code|-Printf.sprintf "%02x")|>List.of_enum|>join" ")

The results are:
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x10\x02" |> hex;;
- : string = "aa a9 a6 aa"
m "\xFF\x00\xAA\x55" |> hex;;
- : string = "55 55 aa aa 66 66 99 99"
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x01\x02\x03\xF1\xF2\xF3" |> hex;;
- : string = "a9 aa a6 aa a5 aa a9 55 a6 55 a5 55"

As a benchmark, with:
let benchmark n =
  let t = Unix.gettimeofday() in
  assert(2*n == String.(length (m (create n))));
  Unix.gettimeofday() -. t

I get:
# benchmark 16_384;;
- : float = 0.115520954132080078

on my MacBook.

Haskell, 76 characters
import Bits
z a=170-sum[a.&.p*p|p<-[1,2,4,8]]
y a=[z a,z$a`div`16]
m=(>>=y)

Test runs:
> testAll
input      [10, 02]
encoded    [AA, A9, A6, AA]
  pass
input      [FF, 00, AA, 55]
encoded    [55, 55, AA, AA, 66, 66, 99, 99]
  pass
input      [12, 34, 56, 78, 90]
encoded    [A6, A9, 9A, A5, 96, 99, 6A, 95, AA, 69]
  pass
input      [01, 02, 03, F1, F2, F3]
encoded    [A9, AA, A6, AA, A5, AA, A9, 55, A6, 55, A5, 55]
  pass

Performance is well within spec. at 1MB in ~1.2s on my oldish laptop. It suffers because the input is convert to and from a list, rather then processed as a ByteArray.
> dd bs=1m count=1 if=/dev/urandom | time ./2040-Manchester > /dev/null
1+0 records in
1+0 records out
1048576 bytes transferred in 1.339130 secs (783028 bytes/sec)
        1.20 real         1.18 user         0.01 sys

The source, 2040-Manchester.hs, includes the code, tests, and main function for a command line filter.

Python, 87 chars
M is the function requested in the problem.  It calls N for each nybble and splices everything back into a list.
N=lambda x:170-(x&1|x*2&4|x*4&16|x*8&64)
M=lambda A:sum([[N(a),N(a>>4)]for a in A],[])

print map(hex,M([0x10,0x02]))
print map(hex,M([0xff,0x00,0xaa,0x55]))
print map(hex,M([0x12, 0x34, 0x56, 0x78, 0x90]))
print map(hex,M([0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]))

generates
['0xaa', '0xa9', '0xa6', '0xaa']
['0x55', '0x55', '0xaa', '0xaa', '0x66', '0x66', '0x99', '0x99']
['0xa6', '0xa9', '0x9a', '0xa5', '0x96', '0x99', '0x6a', '0x95', '0xaa', '0x69']
['0xa9', '0xaa', '0xa6', '0xaa', '0xa5', '0xaa', '0xa9', '0x55', '0xa6', '0x55', '0xa5', '0x55']

APL (Dyalog Extended), 22 bytes
∊(⌽(2⍴256)⊤43690-4⊥⊤)¨

Try it online!
Port of the GolfScript answer.
∊(⌽(2⍴256)⊤43690-4⊥⊤)¨       Monadic train:
  ⌽(2⍴256)⊤43690-4⊥⊤         Define a helper function taking an integer n:
                    ⊤           Convert n to base 2. Monadic ⊤ is an Extended feature.
                  4⊥            Convert the result from base 4.
                                This puts the 1 digits of n
                                in odd indices of the intermediate result.
            43960-              Subtract from 43690.
    (2⍴256)⊤                    Convert to 2 base-256 digits, corresponding to
                                nibbles of n.
  ⌽                            Reverse the order of these bytes.
 (                   )¨       Call the helper function for each element of the input
∊                             and flatten the results into a list.

C, 164 bytes
Takes in a series of hex bytes and converts to manchester binary stream.
#include <stdio.h>
main(int c,char **v){int i,b,x,j=0;while(++j<c{sscanf(v[j],"%x",&b);x=b^0xff;for(i=9;--i;){printf("%d%d",x&1,b&1);x=x>>1;b=b>>1;}printf("\n");}}

#include <stdio.h>
main(int c,char **v){
int i,b,x,j=0;
while(++j<c){
    sscanf(v[j],"%x",&b);
    x=b^0xff;
    for(i=9;--i;){
        printf("%d%d",x&1,b&1);
        x=x>>1;b=b>>1;}
    printf("\n");}}

Test:
./a.out 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0

Output:
1010101010101010
0110101010101010
1001101010101010
0101101010101010
1010011010101010
0110011010101010
1001011010101010
0101011010101010
1010100110101010
0110100110101010
1001100110101010
0101100110101010
1010010110101010
0110010110101010
1001010110101010
0101010110101010
1010101010101010
1010101001101010
1010101010011010
1010101001011010
1010101010100110
1010101001100110
1010101010010110
1010101001010110
1010101010101001
1010101001101001
1010101010011001
1010101001011001
1010101010100101
1010101001100101
1010101010010101
1010101001010101

16kb test data set generator:
test_data.c:
#include <stdio.h>
void main()
{
int i=16*1024;
while(i--)
{
    printf("0x%02x ", i&0xFF);
}
printf("\n");
}

cc test_data.c -o test_data

1.6G i5dual core time trial:
time ./a.out `./test_data` > test.out
real    0m0.096s
user    0m0.090s
sys 0m0.011s

Nice first post, but we generally don't try to obfuscate our code.  Shorter yes, harder to read no.

PHP, 156 bytes
function f($i){foreach($i as$n){$b=str_split(str_replace([0,1,2],[2,'01',10],
str_pad(decbin($n),8,0,0)),8);$o[]=bindec($b[1]);$o[]=bindec($b[0]);}return$o;}

Given the input [0, 1, 2, 3, 4, 5], it returns:
[170, 170, 169, 170, 166, 170, 165, 170, 154, 170, 153, 170]

It encodes 16 KiB of data in 0.015 seconds and 1 MiB of data in about 0.9 seconds.
The ungolfed code, another implementation (longer and about twice slower) and the test cases can be found on my code-golf solutions page on Github.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
For 2 arrays, subtract every element in one array from the position-matching element in the other
For 2 arrays each with X elements, what is the SHORTEST code to subtract every element in the second from every element in the first, 1 to 1
so, for example:
A1 = [10,11,12]
A2 = [1,2,3]
A1 "-" A2 should == [9,9,9]

Come on. Code golf should have enough complexity for the competitors to exercise some creativity. Really.

dmckee: Exactly my thoughts. This one is way too trivial to make a good task (see the R solution, for example). Now if only people could stop by the Sandbox on meta before posting a task ...

Though I agree that this question is lousy for golf I find it very unfair that it has at the same time a negative vote count but 5 questions of +14.

GP, GAP, J, Fortran, Maxima, ... solution: "A1 - A2"

R, 3 chars
(following Chris' counting method that includes the variable names in the count)
a-b

a and b can be defined as follows:
a <- c(10,11,12)
b <- c(1,2,3)

(c is the array construction function in R)

Is this the normal way for defining arrays in R? and if not, what would the code be, if you have a and b already defined.

@Samer, yes that's the normal way. The code would be exactly the same. In fact, you can even do c(10,11,12)-c(1,2,3). So theoretically it's only a single character.

J, 1 char
I will answer too because finally I don't have to use 2 bytes worth of enclosing brackets for J. :)
   -

   10 11 12 - 1 2 3
9 9 9

Scheme, 11 chars
Assume the lists are named a and b:
(map - a b)

Example:
(map - '(10 11 12) '(1 2 3))  ; => (9 9 9)

ES6, 20
a.map((x,i)=>x-b[i])

In Haskell (10):
zipWith(-)

will do the job. Please note, that the lists will be truncated, if their length isn't equal.

Well, the task states that they are of equal length x, so I guess that can be neglected.

Lists? Doesn't Haskell have Arrays?

@user unknown: They exists, but aren't used very often. In this case, using arrays would blow up my solution by about 30 chars.

:) That's why I'm asking. :)

>>> class L(list):
...  def __sub__(self, other):
...   return map(int.__sub__,self, other)
...
>>> a=L([10,11,12])
>>> b=L([1,2,3])
>>> a-b
[9, 9, 9]
>>>

In Python (24):
map(lambda a,b:a-b,a,b)

Smaller (21):
map(int.__sub__,a,b)

Groovy:
List a = [1,2,3]
List b=[2,7,9]
[0,1,2].each { println(a[it]-b[it]) }

Scala, 51 chars
Array(10,11,12) zip Array(1,2,3)map(x=>x._1-x._2)

(but includes initialisation, Array-Declaration)
(10 to 12).zip (1 to 3)map(x=>x._1-x._2)

is a bit shorter, but produces an Vector.
a zip b.map(x=>x._1-x._2)

is even shorter, but of course I could do
a zip b.map f

then. Or just
g

CJam, 10 bytes
CJam is newer than this challenge, but I thought it's funny how uncompetitive it is for once:
l~]z{~-}%p

This is an STDIN to STDOUT program, reading input like [10 9 8] [1 2 3]. I know everyone else is answering in snippets, but that wouldn't really be shorter here, because you'd have to replace ] by something like a\a\+.

TI-BASIC, 5 bytes
L1-L2

Input lists are stored in the L1 and L2 tokens.  (TI-BASIC doesn't have STDIN or equivalent.)
Answer is stored in Ans.
Example:
{10,11,12→L1
      {10 11 12}
{1,2,3→L2
         {1 2 3}
L1-L2
         {9 9 9}

Not counting USE: syntax math sequences ; ! because it's not needed (on the REPL).
Factor: [ - ] 2map

And... what language should that be?

Not the shortest, but this is what I came up with in javascript...
t=0;
ar=[];
for(i=0;i<ar.length;i++){
   t=a[i]-b[i];
   ar.push(temp);
};

Input: a = [10,11,12], b = [1,2,3]
Output: [9,9,9]

You can shorten your code by removing unnecessary whitespace, using one-character variable names, and dropping the var keyword when creating a variable.

You're welcome! Actually, you don't need newlines and indentation in JavaScript, so you can save some more characters if you remove some whitespace and if you use c instead of ar. Also, please include the character count in your answer.

Java 8, 29 bytes
I got creative with I/O types for this. It's a lambda (curried) from an ordered IntStream (A1) to a lambda from a mutable List<Integer> (implementing remove(int), e.g. ArrayList) (A2) to IntStream. Assign to Function<IntStream, Function<List<Integer>, IntStream>>.
s->l->s.map(n->n-l.remove(0))

Try It Online
Yeah, that's right; I'm using stateful lambdas. I could lose 4 byes by taking A2 as a Stack and using pop, but I'm hesitant to stray that far from the List interface.

8th, 10 bytes
Code
' n:- a:op

Explanation
a:op takes two arrays and invokes the word n:- to the corresponding elements of "a1" and "a2", producing a new array "a3".
Example
ok> [10,11,12] [1,2,3] ' n:- a:op .
[9,9,9]

Note: Non-competing is no longer a thing

@Shaggy - Thank for your comment. A new rule to learn.

Java 8, 45 bytes
a->b->{for(int i=0;i<a.length;a[i]-=b[i++]);}

Modifies the first input-array instead of returning a new one to save bytes.
Explanation:
Try it here.
a->b->{            // Method with two integer-array parameters and no return-type
  for(int i=0;     //  Start at index 0
      i<a.length;  //  Loop over the input arrays by index
    a[i]-=b[i++]   //   Modify array `a` by subtracting the values of `b` on the same index
  );               //  End of loop
}                  // End of method

Pyt, 3 bytes
←←-

Takes arrays as input; alternatively, if the arrays are already on the stack, with the second one on the top, it's one character:
-

Explanation:
←        Get first array
 ←       Get second array
  -      Get elementwise difference (as an array)

Try it online!

Funky, 27 bytes
a=>b=>a::map((n i)=>n-b[i])

Try it online!

Jelly, 1 byte
_

Try it online!

Add++, 7 bytes
L*,BcB_

Try it online!
Auto vectorisation is so boring.

Zsh, 27 bytes
That's right, you can zip arrays in your shell scripts!
Input: arrays a and b
Output: stdout
for x y (${a:^b}) <<<$[x-y]

Try it online! (It takes more code to read stdin into arrays than it does to pairwise subtract!)
If the output must be another array, either 27 or 29 bytes.
for x y (${a:^b}) c+=$[x-y]    # if c was declared as an array
for x y (${a:^b}) c+=($[x-y])  # if c was not declared

SmileBASIC, 13 bytes
ARYOP 1,A,A,B

Inputs: A, B
Output: A

Japt, 3 bytes
í-V

Try it
í-V     :Implicit input of arrays U & V
í V     :Interleave both
 -      :Reduce each pair by subtraction


text:
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.

Define "trivially calculated". Are you saying that we can apply mathematical identities to optimise it up to some cutoff point? If so, what precisely is the cutoff point?

@ralu Instead of giving a PC specification, you can also say print the maximum sum of fibonacci numbers before it times out on http://www.ideone.com/ . That way everyone will have a common ground. The time limit there is 5 secs.

did not knew. That looks fair

What kind of input values are you talking about?

The question is still unclear to me. For arbitrary input, each machine will reach a limit in 10s, so does 'as many as possible' mean, that the program shall interrupt, and print the sum so far? If you have a timelimit, the program could be interrupted from outside, and show, what it reached.

Again a question: How do you decide who has won from 9 digits?

@user, to the second question, I interpreted "input value" as meaning that your program should print the number of terms added. I.e. you need to output n and F(n+2)-1.

And what is n? Do you start (0, 1, ...) or (1, 1, ...)? And count index from 0 or 1? So f(8)=13?

@Peter: So most answers are wrong, since they output a random something - not related to the input. The question should be rephrased: "Print the sum of all fibonacci-number up to i [% 10^(9+n)] (fib(0)=0, fib(1)=1, ...). Make your program as fast as possible. Time-measurement will be made from outside. After 10s on an (REFERENCE-PC-SPEC), it will be interrupted if not ready. Winner is, who reaches the highest, correct value in that time, and only correct results along the way."

@user, n is the number of Fibonacci numbers counted. The question doesn't specify whether 1,1 is F(0),F(1) or F(1),F(2), so I chose the one which gives the nicest properties (the second). Keith has interpreted the question slightly differently to me - he takes actual input i and outputs F(ki + 2) - 1; I think his answer and mine are both correct. But it's pointless getting fussed about it because it's a bad question: I don't think @ralu realised that the sum of Fibonacci numbers is so easily reduced to computing one Fibonacci number, or that the period mod N is so short.

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.

A very nice illustration of the point behind my question about what "trivially calculated" means. You could, of course, extend it to take any i and calculate the sum.

Indeed, the sum of the first i is the same as the sum of the first i % 1.5e9.

Your program has to work whit different input values

@ralu: it does, pass it any integer you'd like...

@Keith, and you could also expand "Turns out" a bit. The sum of the Fibonacci numbers to F(n) is F(n+2)-1, so for any non-trivial N for which the period of F(i) mod N is P_N, the sum of the first P_N Fibonacci numbers is 0 mod N.

I didn't get any of it. Care to explain to those without a degree in CS as of now?

@the_drow: If you look at the low-order 9 decimal digits of the Fibonacci numbers, there is a pattern - they repeat every 1.5 billion entries (why?  I'm not sure, but I wrote a program to see how long it took for a repeat).  So the last 9 digits go like 0,1,1,2,3,5,8,... (about 1.5 billion later) 5,999999997,2,999999999,1,0,1,1,2,3,5,8,...  So no matter what contiguous chunk of 1.5 billion numbers you take, it contains the same set of numbers as any other contiguous chunk of 1.5 billion numbers, so all such contiguous chunks have the same sum.

Write a program to sum up the first 1.5 billion chunk, and you'll see that that sum is 0.

@KeithRandall: Extermely clever. How does the Fibonacci sequence produce negative numbers to eventually produce a sum of 0?

@the_drow: sorry, I mean they sum to a number with 0 in the low-order 9 digits.  You're right, the Fibonacci numbers are all positive.

See also http://mathworld.wolfram.com/PisanoPeriod.html

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 nth 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

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

I know that the question says just "print a sum of as many Fibonacci numbers as possible" without saying anything about them being unique, consecutive, or starting at 1, but I think it's implicit that it should be a sum of consecutive Fibonacci numbers starting 1, 1, 2. If you put an alert inside your loop you'll see that the values you output start 2, 5, 12, 29, 70. They should be 2, 4, 7, 12, 20.

@Peter Taylor That can be easily fixed just by changing the initial value of fib2 to 0.

That gives 1, 2, 5, 12, 29, 70. Still broken.

@Peter Taylor I fixed it, I think. I changed sum += fib1 + fib2 to sum = fib1 + fib2.

Almost there. But now what values does sum take? Still not 2, 4, 7, 12, 20, ...

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".


text:
Intersection of Two Lines
Given equation of two lines in the format Ax+By=C, determine their intersection point. If they are parallel print 'parallel' without quotes. For input/output format refer sample input/output.
Input
1x+1y=1
1x-1y=1

Output
(1.00,0.00)

Input
0x+1y=0
1x+0y=0

Output
(0.00,0.00)

-1000000 <= A,B,C <= 1000000.
Note their intersection point may not be integer. Print upto two decimal places.
Shortest solution wins.

Is a function call valid? example : f[1x+1y=1, 1x-1y=1]

@belisarius Yes, but the solution should be entire program.

Is the format always Ax+By=C or can it also be Ax-By=C or even -Ax+By=C? Are negative numbers for A, B or C even allowed? »Print up to two decimal places« implies that less can be printed, your examples do not suggest that. If the output is locale-dependent (which can happen with plenty languages in formatted output), can we assume en-US or C as locale? (I.e. anything that uses a decimal point and not a comma).

@Joey Yes A,B and C can be negative. Ax-By=C is already given in one of the examples. The points should have 2 decimal places.

@Joey Edited the question to show that. Thanks for pointing that out.

I know this is an old question, but can we take input as two lists containing [A,B,C]?

Ruby - 119 chars
a,b,c,d,e,f=(gets+gets).scan(/-?\d+/).map &:to_f
puts (t=a*e-b*d)==0?'parallel':"(%.2f,%.2f)"%[(e*c-b*f)/t,(a*f-c*d)/t]

It's odd but my ruby 1.9.x shows -0.00, :-\ and you can use gets(p) instead of 2 gets, it will read the entire contents (assuming it was piped)

gets(2) would get two bytes of input, as opposed to two lines on input.

Python, 148 146 chars
import re
I=raw_input
a,b,p,c,d,q=eval(re.sub('x|y=','.,',I()+','+I()))
D=a*d-b*c
print'(%.2f,%.2f)'%((p*d-q*b)/D,(a*p-c*q)/D)if D else'parallel'

Python+sympy - 161 chars
from sympy import*
x,y=symbols('xy')
e=lambda:eval(raw_input().replace('x','*x').replace('y=','*y-'))
r=solve([e(),e()],[x,y])
print r and`r[x],r[y]`or'parallel'

Python+sympy - 143 chars (different output format)
from sympy import*
x,y=symbols('xy')
e=lambda:eval(raw_input().replace('x','*x').replace('y=','*y-'))
print solve([e(),e()],[x,y])or'parallel'

output format for 143 char version is slightly different from the spec
In:
1x+1y=1
1x-1y=1

Out:
{x: 1, y: 0}

In:
0x+1y=0
1x+0y=0

Out:
{x: 0, y: 0}

sage - 162 chars
x,y=var('x,y')
e=lambda:eval(raw_input().replace('x','*x').replace('y','*y='))
try:r=solve([e(),e()],[x,y])[0];print`r[0].rhs(),r[1].rhs()`
except:print'parallel'

J, 146 132 134 124
echo'parallel'"_`(1|.')(',[:(,',',])&(0j2&":)/[:,,.@{:%.}:)@.([:*@|[:-/ .*}:)|:".>{.`(<@}:@;@(1 2&{))`{:(`:0)"1;:;._2(1!:1)3

Parsing this is awful.
Edit: Realized that my output is basically broken, although it works for the examples given and parallels...
Edit: Posting the shorter version I already had.
Edit: Fixed without too much pain...
Edit: Fixed a weird issue where the program was spread across multiple lines.
Somewhat ungolfed version:
words =: ;:;._2(1!:1)3
NB. Leverage J's parser itself to split each line into e.g. ax + by = c
lines =: ".>{.`(<@}:@;@(1 2&{))`{:(`:0)"1 words
NB. Use a 3-part gerund (`) to get boxed strings 'ax';'b';'c', unbox and parse
calc_and_format =: 1|.')(',[:(,',',])&(0j2&":)/[:,,.@{:%.}:
NB. %. (matrix multiply) first two rows (a d/b e) by third row turned (c/f)
NB. And then format laboriously. 0j2&": formats numbers with 2 decimals.
det_nonzero =: [:*@|[:-/ .*}:
NB. 1 if determinant (-/ .*) of (a b/d e) is nonzero (*@|)
echo'parallel'"_`calc_and_format@.det_nonzero|: lines
NB. transpose parsed input to get (a d/b e/c f).
NB. If det_nonzero, call calc_and_format, otherwise constant 'parallel'
NB. Print

OCaml + Batteries, 163 characters
As straightforward as it gets:
Scanf.scanf"%fx%fy=%f\n%fx%fy=%f\n"Float.(fun a b c d e
f->Printf.(fun u->if u=0.then printf"parallel"else
printf"(%.2f,%.2f)"((b*f-c*e)/u)((d*c-a*f)/u))(b*d-a*e))

Edit:

Initial version, 169
Use Batteries for delimited overloading of operators, 164
Lambda binding of u, 163

C-149 bytes
Not much of golfing just the basics.
float a,b,c,d,m,n,t;main(){scanf("%fx%fy=%f%fx%fy=%f",&a,&b,&m,&c,&d,&n);t=b*c-a*d;t?printf("(%.2f,%.2f)",(b*n-d*m)/t,(c*m-a*n)/t):puts("parallel");}

Here is the ideone link for testing.
Instead of printing 'parallel' an alternative could be to print the orthogonal distance between the lines when they are parallel.

Vyxal, 10 bytes
∆Q:[vt|`ċ₃

Try it Online!
8 if the format can be ⟨ ⟨ `x` | xval ⟩ | ⟨ `y` | yval ⟩ ⟩
. Returns fraction representation of all numbers if not integer.
Explained
∆Q:[vt|`ċ₃
∆Q          # Solve the two input equations simultaneously
  :[        # If there's a solution
    vt      #   get the last values of each two item tuple
      |`ċ₃  # else, push the string "parallel"

In Vyxal, can we not close If Statement?

@lesobrod that's right. You don't need to if it's at the end of a program


text:
Choosing Languages for Golfing
What are some tips for choosing the right language to golf?
What factors affect the language to be chosen?
Here are some example problem types:

Problems that require I/O solution, either console or file
Problems that require parsing
Problems that requires you to write your solution as a function definition
Math problems
Problem dealing with prime numbers
Solving number puzzles
Performing numerical methods
String processing
Array processing
Tricky 2D array problems
Computational geometry
Recursion
2D graphics
3D graphics
Audio
Networking / web
Parallel processing

Don't simply say things like "Use GolfScript|J" because you like them.

For some problems it's the type system. E.g. if you need to deal with integers greater than 64 bits, you want languages which have that built in (e.g. Golfscript, Haskell) rather than languages which make them expensive (e.g. Java).

I've made this a wiki in keeping with our policy on "Tips" type questions.

99 bottles is helpful if you need a language beginning with a specific letter...

Kudos to ace, trimsty, algorithmshark and hosch250 for helping to make this thread a better resource. Please keep the submissions coming! It was a tough bounty call between algorithmshark and hosch250, who both gave a lot of detailed effort, but in the end Herr Shark gets the nod for leading the way.

Choose whatever language you want. It's also a competition within languages. More unique, interesting solutions in more languages is good.

I'm voting to close this question as primarily opinon-based; it's not a good, objective on-topic question within the scope defined in the help center

There is Advocate languages to golf in on meta, which has a similar goal.

I think the best way to answer is to check the languages common for top solutions on this site.

Depends on what one needs, C/C++ is fast, but you have to code more of the work yourself.
Python and Ruby are slower but are a lot easier to code with built in methods that shortens a lot of work and they automatically handle infinitely large values (if one has the RAM).
Using a functional language like Haskell is great for purely mathematical functional use if one can frame the problem that way.

As a primarily python user, in Py you pay for your ease of use in character count although there are some really hacky tricks which can save characters. Haskel and Lisp, while fun, tend to run even longer than Python.

This probably shouldn't be the accepted answer. The description about high vs low level languages doesn't actually have anything to do with character count.

Yes, it is real fair to hold an 2011 answer to a question edited on the 23 Feb 2017. Maybe we should stop changing the questions after it has been answered?

Putting my two cents in on array programming languages, J and APL in particular.
K/Kona, Q, and Nial fall in this category too, but they generally have the same benefits and criticisms. Use discretion. I will use J examples below, mostly because these are ASCII and thus easy to type--remember than APL characters count as single bytes, so don't let that be your problem with the language as choice for golfing.

Math problems
Solving number puzzles
Performing numerical methods
Tricky 2D array problems

These two are very good math and data-manipulation languages, because they toss arrays around a high level, and a lot of looping is done implicitly, by saying, e.g. add ten to each of 3, 4, and 5 (10 + 3 4 5) or sum each row of an array (+/"1 arr--the looping is in the "1).

Problem dealing with prime numbers

With prime number problems in particular, J has fast and short builtin primitives, as do some dialects of APL. (Edit: I'm thinking of Nars2000, which is part dialect and part completely different implementation. APL has no builtin for primes.) N-th prime (p:), no. of primes up to (_1&p:), factoring (q:), GCD and LCM (+. and *.), and so on, there's a lot there. However, in practice, the question will often specify that you have to cook your own prime implementations, so these don't see too much use. There are still neat and fancy ways of getting the prime stuff you need, it just becomes a little less cut-and-paste.

String processing
Array processing

Array and string processing is a bit of a mixed bag: if it's something that APL/J is good at or has a primitive or common idiom for, it's nearly trivial; if it's something that's very sequential and not very parallelizable, you're going to have a bad time. Anything in between is up in the air, though usually they will respond favourably.

Problems that require I/O solution, either console or file
Problems that requires you to write your solution as a function definition

IO is weird. APL has a single-character input expression, but with J you have to spend at least 8 to read in a number: ".1!:1]1. Output is a little less verbose, but you're still looking at 6 or 7 characters wasted, in practice. J in particular really likes it a lot if you can take in the input as arguments to a function, instead of having to muck around with IO itself.
In practice, with J and APL, usually the solution is written as a function that you invoke at the console. With APL, you can basically just put in variable names for your arguments and wrap the expression you were working with in curly braces and call it a day.
But with J, there's a bit of an overhead for defining functions explicitly--3 :'...', and you have to escape any strings inside--so what is usually done is something called tacit programming: you program at the function level, combining primitives in a manner not unlike that of Haskell. This can be both a blessing and a curse, because you don't have to spend as many characters referring to your arguments, but it's easy to drown in parentheses and end up losing tens of characters trying to hack your otherwise short and clever solution into something that works.

Problems that require parsing
Computational geometry

I don't have experience with golfing these particular problems, but I will say this: in the end, array programming languages are very good at piping and transforming lots of data in the same way. If you can turn the problem into an exercise in number shuffling, you can make it an APL/J problem, no sweat.
That said, not everything is an APL/J problem. Unlike Golfscript, APL and J just happened to be good for golfing, alongside their other benefits ;)

Excellent contribution! Thank you for being the first into the pool.

Why hasn't Perl been praised yet? It's an excellent golfing language, for nearly every one of these, especially string related stuff (regex).
Burlesque is good for number-related programs, while Ruby is great for simpler text manipulation.
There's actually a list of languages and golfing scores over here.

I don't know squat about Perl, but I agree.

I like using obscure programming languages to (try to) get the job done.
Here are my favorites for the details you listed:
Problems that require I/O solution, either console or file
Languages like TI-Basic work well, but I prefer Ruby because of puts
Problems that require parsing
GolfScript will definitely aid you here
Problems that requires you to write your solution as a function definition
TI-84 Table - allows functions as Y= e.g. Y=|X| returns the absolute value of X
Math problems
TI-Basic - made for a calculator, so it includes math ;)
Problem dealing with prime numbers
Nothing special; Mathematica is probably the right tool for the job
Solving number puzzles
TI-Basic as it automatically loops through arrays
Performing numerical methods
TI-Basic or Mathematica
String processing
Python - has some great string functions.
No matter how good you think TI-Basic is, don't use it for strings...
Array processing
TI-Basic - automatically loops through arrays; e.g. increment all values in the array - L1+1→L1
Ruby - also has very powerful array features, and of course the ! will help compress code also
Tricky 2D array problems
Ruby or Python works best here, as TI-Basic doesn't support 2D arrays
Computational geometry
TI-Basic has geometric features and can be used for most math up to Calculus and Linear Algebra

BONUS
Looping
Either Arduino or Quomplex. Arduino has a built-in void loop(){} and Quomplex has the infinite loops contained by brackets ([])
Drawing/GUI
Game Maker Language has very powerful drawing features, and TI-Basic is also a generally useful tool because of the support for drawing on the graph.
Quines
Either HQ9+ or Quomplex because HQ9+ has the Q to output the program's source code and Quomplex will automatically print out its source code unless * (output) is specified or it produces no output, defined with #

If you're solving a math problem and you don't have Mathematica, try Sage. It is based on Python, so if you already know Python you don't need much time to learn its syntax.
Examples:

Solving a system of linear equations
Primes
Base conversions
Drawing Platonic solids

It is also useful for graph plotting and equation solving (e.g. you can use the solve() function in Sage, or if that is forbidden by the rules, it allows an easy implementation of the Newton Raphson process because it has the diff() function that can perform symbolic differentiation).
Besides, if you are a Python2 programmer, using Sage may allow you to cheat by skipping the long import statements. For example, math and sys are already imported by default. (Note that this may not work if your Python2 program depends on integer division.)

Good info! Thanks for contributing.

I know three languages - Java, C++, and Python 3.  I know none of these at a high level, but this is my experience with them.
Java:
I would never use Java for golfing again.  It takes over 80 characters just to write Hello World!.  However, it does have its strengths:

Input requires creation of a Scanner object.  It is difficult to input a single character.  It requires specification of what types you are inputting.
  Parsing is simple enough because of the for loop.  The enhanced for loop is excellent for this.
  Java supports methods, but the method declaration is quite long.
  Java is excellent at math, as well as all other high-level languages.
  Java is difficult to use when the problem involves modifying strings.  You cannot make modifications to an existing string.
  Java's arrays are simple to use.
  Java is good at recursion.
  Java includes built-in graphics.  They are very easy to use.

C++
C++ is a very strong language, but it is somewhat lengthily when trying to golf at 56 characters for Hello world!.

Input and output are easy.  You need not specify what types you are inputting - that is done automatically.  However, you must include the iostream library.
  Parsing is very easy.
  Function declaration is simple, but eats a lot of important characters.
  C++ excels at math, but it does not include PI or E, as Java does.
  C++'s strings are easy to use and change as needed.
  I use vectors where possible instead of arrays, but both are easy to use.
  C++ is good at recursion.
  C++ does not include built-in graphics.

Python 3
Python 3 is similar to C++ and Java.  It is much shorter as it is not strongly-typed - in other words, it just guesses at what the variables are.

Input is easy, but everything is input as strings.  You must manually convert all input to whatever values you want.
  Parsing and looping is very simple.
  Python function declarations are quite simple and short.
  Python is good at math.
  Python's strings are simple to use.
  Arrays are simple to use.
  Python is good at recursion.
  Python does not include built-in graphics.

I guess by enhanced for-loop, you're talking about a range-for loop. C++ supports this since C++11 (http://en.cppreference.com/w/cpp/language/range-for). It's syntactically similar to the Java for-range loop and requires the iteratable object's class to implement begin() and end() or begin(T) and end(T) to be overloaded for the given object. It's also implemented for C-style strings and built-in arrays and works for all standard library containers.

@foobar Yes, I was talking about that.  Thanks for the info, I've wished for that ever since I took Java.

Java now has a 61-byte solution, but your point still stands.


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

(source: spikedmath.com)
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 |

This is not well specified. Will the function be supplied as a function argument? Or is the code supposed to parse some expression syntax? Is the aim a function, or a program that takes text input and output? Does the code need to actually plot into a 2D array, or just calculate the number of pixels that would be turned on? If the output of the plot is optional, then no one will do it.

So quadrature by the midpoint rule?

no, integrate by counting pixels on the plot, something like (blue pixels - red pixels) / (total pixels) * (xmax - xmin) * (ymax - ymin)

Ok, so it's left point rather than midpoint and quantised. What correctness constraints are there? I'm sure I could construct a test case which distinguishes different ways of looping over the x-values.

It's Monte Carlo without randomness :D

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)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/