text:
The number of possible numeric outcomes of parenthesizations of 2^2^...^2
Consider an expression 2^2^...^2 with n operators ^. Operator ^ means exponentiation ("to the power of"). Assume that it has no default assosiativity, so the expression needs to be fully parenthesized to become unambiguous. The number of ways to parenthesize the expression are given by Catalan numbers C_n=(2n)!/(n+1)!/n!.
Sometimes different parenthesizations give the same numeric outcome, for example (2^2)^(2^2)=((2^2)^2)^2, so the number of different possible numeric outcomes for a given n is less than C_n for all n>1. The sequence starts as 1, 1, 2, 4, 8, ... as opposed to Catalan numbers 1, 2, 5, 14, 42, ...
The problem is to write the fastest program (or function) that accepts n as an input and returns the number of different possible numeric outcomes of the expression 2^2^...^2 with n operators ^. The performance should not significantly deteriorate as n grows, so direct calculation of high power towers is probably a bad idea.

I'm just sharing an idea here, but it seems that it should be possible to exclusively use addition and multiplication, as the answer will always be of the form 2^n, and it therefore would be unnecessary to keep track of anything except n. I.e., just using the rules of exponentiation seems wise. However, there surely is a smarter and completely algebraic way to do this.

@Fors I guess n is still way too big to compute. Still, well noted. Maybe a recursive representation in the form "1 or 2^(...) or (...)+(...)"; but you still have the problem of how to normalize such representation of a number (or compare two representations for value equality).

"Search: seq:1,1,1,2,4,8
Displaying 1-10 of 108 results found." -- I think I'm on the right track. Let's see what are the other entries...

@JanDvorak, A002845 (no closed form given)

@PeterTaylor oh... at least we have a test suite

Related http://oeis.org/A003018/a003018.pdf

@Vladimir Reshetnikov: I think there is an off-by-one error in your formula. When you have n twos and C_n=(2n)!/(n+1)!/n! should be the number of parenthesizations, then for n=3 it should be 5, correct? I see (2^2)^2 and 2^(2^2), but what are the other three combinations? I think C_n gives you the number of parenthesizations for n+1 twos.

@moose Thanks, you are right!

Python 2.7
This approach takes advantage of the following considerations:
Any integer can be represented as a sum of powers of two.  The exponents in the powers of two can also be represented as powers of two.  For example:
8 = 2^3 = 2^(2^1 + 2^0) = 2^(2^(2^0) + 2^0)

These expressions that we end up with can be represented as sets of sets (in Python, I used the built-in frozenset):

0 becomes the empty set {}.
2^a becomes the set containing the set representing a.  E.g.: 1 = 2^0 -> {{}} and 2 = 2^(2^0) -> {{{}}}.
a+b becomes the concatenation of the sets representing a and b.  E.g., 3 = 2^(2^0) + 2^0 -> {{{}},{}}

It turns out that expressions of the form 2^2^...^2 can easily be transformed into their unique set representation, even when the numerical value is much too large to be stored as an integer.

For n=20, this runs in 8.7s on CPython 2.7.5 on my machine (a bit slower in Python 3 and much slower in PyPy):
"""Analyze the expressions given by parenthesizations of 2^2^...^2.

Set representation:  s is a set of sets which represents an integer n.  n is
  given by the sum of all 2^m for the numbers m represented by the sets
  contained in s.  The empty set stands for the value 0.  Each number has
  exactly one set representation.

  In Python, frozensets are used for set representation.

  Definition in Python code:
      def numeric_value(s):
          n = sum(2**numeric_value(t) for t in s)
          return n"""

import itertools

def single_arg_memoize(func):
    """Fast memoization decorator for a function taking a single argument.

    The metadata of <func> is *not* preserved."""

    class Cache(dict):
        def __missing__(self, key):
            self[key] = result = func(key)
            return result
    return Cache().__getitem__

def count_results(num_exponentiations):
    """Return the number of results given by parenthesizations of 2^2^...^2."""
    return len(get_results(num_exponentiations))

@single_arg_memoize
def get_results(num_exponentiations):
    """Return a set of all results given by parenthesizations of 2^2^...^2.

    <num_exponentiations> is the number of exponentiation operators in the
    parenthesized expressions.

    The result of each parenthesized expression is given as a set.  The
    expression evaluates to 2^(2^n), where n is the number represented by the
    given set in set representation."""

    # The result of the expression "2" (0 exponentiations) is represented by
    # the empty set, since 2 = 2^(2^0).
    if num_exponentiations == 0:
        return {frozenset()}

    # Split the expression 2^2^...^2 at each of the first half of
    # exponentiation operators and parenthesize each side of the expession.
    split_points = xrange(num_exponentiations)
    splits = itertools.izip(split_points, reversed(split_points))
    splits_half = ((left_part, right_part) for left_part, right_part in splits
                                           if left_part <= right_part)

    results = set()
    results_add = results.add
    for left_part, right_part in splits_half:
        for left in get_results(left_part):
            for right in get_results(right_part):
                results_add(exponentiate(left, right))
                results_add(exponentiate(right, left))
    return results

def exponentiate(base, exponent):
    """Return the result of the exponentiation of <operands>.

    <operands> is a tuple of <base> and <exponent>.  The operators are each
    given as the set representation of n, where 2^(2^n) is the value the
    operator stands for.

    The return value is the set representation of r, where 2^(2^r) is the
    result of the exponentiation."""

    # Where b is the number represented by <base>, e is the number represented
    # by <exponent> and r is the number represented by the return value:
    #   2^(2^r) = (2^(2^b)) ^ (2^(2^e))
    #   2^(2^r) = 2^(2^b * 2^(2^e))
    #   2^(2^r) = 2^(2^(b + 2^e))
    #   r = b + 2^e

    # If <exponent> is not in <base>, insert it to arrive at the set with the
    # value: b + 2^e.  If <exponent> is already in <base>, take it out,
    # increment e by 1 and repeat from the start to eventually arrive at:
    #   b - 2^e + 2^(e+1) =
    #   b + 2^e
    while exponent in base:
        base -= {exponent}
        exponent = successor(exponent)
    return base | {exponent}

@single_arg_memoize
def successor(value):
    """Return the successor of <value> in set representation."""
    # Call exponentiate() with <value> as base and the empty set as exponent to
    # get the set representing (n being the number represented by <value>):
    #   n + 2^0
    #   n + 1
    return exponentiate(value, frozenset())

def main():
    import timeit
    print timeit.timeit(lambda: count_results(20), number=1)
    for i in xrange(21):
        print '{:.<2}..{:.>9}'.format(i, count_results(i))

if __name__ == '__main__':
    main()

(The memoization decorator's concept is copied from http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/ .)
Output:
8.667753234
0...........1
1...........1
2...........1
3...........2
4...........4
5...........8
6..........17
[...]
19.....688366
20....1619087

Timings for different n:
 n    time
16    0.240
17    0.592
18    1.426
19    3.559
20    8.668
21   21.402

Any n above 21 results in a memory error on my machine.
I'd be interested if anyone can make this faster by translating it into a different language.
Edit: Optimized the get_results function.  Also, using Python 2.7.5 instead of 2.7.2 made it run a bit faster.

I made a C# translation but using sorted arrays and doing the addition in order rather than by set contains checks. It's much slower, and I haven't yet profiled to see whether that's due to not memoising the successor function or due to the cost of comparisons.

I haven't profiled @flornquake's (brilliant) code, but I'd assume much of the CPU time is spent doing set membership tests and set manipulation operations, which are both fairly well optimized in Python, using its ubiquitous hash table and hash key routines. Memoization is certainly a big thing, with an exponential algorithm such as this. If you left that out, you can expect exponentially slower performance.

@Tobia, actually I found that in C# memoising the successor function made it slower. I also found that a more literal translation (using set operations) was significantly slower than my lower level addition. The only real improvement I've found over my original code was to take into account (a^b)^c = (a^c)^b, and it's still much slower than this Python implementation.

@PeterTaylor: Edit: As far as I can see, flornquake's algorithm relies on building sets of trees, where a tree is a set of trees itself, and so on. All the pieces of these trees, from the smallest empty set to the largest set of sets, are memoized. This means that all these trees contain "repeated structure" that is only computed once (by the CPU) and stored once (in RAM). Are you sure that your "addition in order" algorithm is identifying all of this repeated structure and computing it once? (what I called exponential complexity above) See also http://en.wikipedia.org/wiki/Dynamic_programming

@Tobia, we overlapped. I've posted the code.

@PeterTaylor, the approach to take into account (a^b)^c = (a^c)^b sound interesting, I wonder if that would work if combined with my approach.  Thanks for the bounty.

C#
This is a translation of flornquake's Python code to C# using a lower level addition routine which provides a moderate speedup over a direct translation. It's not the most optimised version I have, but that is quite a bit longer because it has to store the tree structure as well as the values.
using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
    class PowerTowers {
        public static void Main() {
            DateTime start = DateTime.UtcNow;
            for (int i = 0; i < 17; i++)
                Console.WriteLine("{2}: {0} (in {1})", Results(i).Count, DateTime.UtcNow - start, i);
        }

        private static IList<HashSet<Number>> _MemoisedResults;

        static HashSet<Number> Results(int numExponentations) {
            if (_MemoisedResults == null) {
                _MemoisedResults = new List<HashSet<Number>>();
                _MemoisedResults.Add(new HashSet<Number>(new Number[] { Number.Zero }));
            }

            if (numExponentations < _MemoisedResults.Count) return _MemoisedResults[numExponentations];

            HashSet<Number> rv = new HashSet<Number>();
            for (int i = 0; i < numExponentations; i++) {
                IEnumerable<Number> rhs = Results(numExponentations - 1 - i);
                foreach (var b in Results(i))
                    foreach (var e in rhs) {
                        if (!e.Equals(Number.One)) rv.Add(b.Add(e.Exp2()));
                    }
            }
            _MemoisedResults.Add(rv);
            return rv;
        }
    }

    // Immutable
    struct Number : IComparable<Number> {
        public static Number Zero = new Number(new Number[0]);
        public static Number One = new Number(Zero);

        // Ascending order
        private readonly Number[] _Children;
        private readonly int _Depth;
        private readonly int _HashCode;

        private Number(params Number[] children) {
            _Children = children;
            _Depth = children.Length == 0 ? 0 : 1 + children[children.Length - 1]._Depth;

            int hashCode = 0;
            foreach (var n in _Children) hashCode = hashCode * 37 + n.GetHashCode() + 1;
            _HashCode = hashCode;
        }

        public Number Add(Number n) {
            // "Standard" bitwise adder built from full adder.
            // Work forwards because children are in ascending order.
            int off1 = 0, off2 = 0;
            IList<Number> result = new List<Number>();
            Number? carry = default(Number?);

            while (true) {
                if (!carry.HasValue) {
                    // Simple case
                    if (off1 < _Children.Length) {
                        if (off2 < n._Children.Length) {
                            int cmp = _Children[off1].CompareTo(n._Children[off2]);
                            if (cmp < 0) result.Add(_Children[off1++]);
                            else if (cmp == 0) {
                                carry = _Children[off1++].Add(One);
                                off2++;
                            }
                            else result.Add(n._Children[off2++]);
                        }
                        else result.Add(_Children[off1++]);
                    }
                    else if (off2 < n._Children.Length) result.Add(n._Children[off2++]);
                    else return new Number(result.ToArray()); // nothing left to add
                }
                else {
                    // carry is the (possibly joint) smallest value
                    int matches = 0;
                    if (off1 < _Children.Length && carry.Value.Equals(_Children[off1])) {
                        matches++;
                        off1++;
                    }
                    if (off2 < n._Children.Length && carry.Value.Equals(n._Children[off2])) {
                        matches++;
                        off2++;
                    }

                    if ((matches & 1) == 0) result.Add(carry.Value);
                    carry = matches == 0 ? default(Number?) : carry.Value.Add(One);
                }
            }
        }

        public Number Exp2() {
            return new Number(this);
        }

        public int CompareTo(Number other) {
            if (_Depth != other._Depth) return _Depth.CompareTo(other._Depth);

            // Work backwards because children are in ascending order
            int off1 = _Children.Length - 1, off2 = other._Children.Length - 1;
            while (off1 >= 0 && off2 >= 0) {
                int cmp = _Children[off1--].CompareTo(other._Children[off2--]);
                if (cmp != 0) return cmp;
            }

            return off1.CompareTo(off2);
        }

        public override bool Equals(object obj) {
            if (!(obj is Number)) return false;

            Number n = (Number)obj;
            if (n._HashCode != _HashCode || n._Depth != _Depth || n._Children.Length != _Children.Length) return false;
            for (int i = 0; i < _Children.Length; i++) {
                if (!_Children[i].Equals(n._Children[i])) return false;
            }

            return true;
        }

        public override int GetHashCode() {
            return _HashCode;
        }
    }
}


text:
Shortest common superstring
Given a list of strings s_0, s_1, ..., s_n find the shortest string S that contains each of s_0, s_1, ..., s_n as a substring.
Examples:

S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')='SEDOLOREMAGNAD'
S('ABCDE', 'BCD', 'C')='ABCDE'

Write the shortest program (or function) that solves this problem. You can represent strings as arrays or lists of characters/integers if you want. Standard libraries are OK. For input/output you can use whatever is more convenient: STDIN/STDOUT, user prompt, parameter/return value of a function etc.
Performance is not critical - let's say, for an input of total length < 100 characters the result must be computed in < 10 second on average modern hardware.

+1 Nice question. I suggest you include some additional examples of expected outcomes so people can easily judge whether the submissions are able to handle a variety of cases.

How should input/output be handled? Should the result be printed or returned from a function?

so, no "for every string, if it contains all of ..., return it " is not a valid solution?

I doubt there's going to be an answer. This question might fit on [so] (without the code-golf part) quite well.

Is this problem in P?

Python 2, 170 153/157/159
Shortened thanks to some of Baptiste's ideas.
from itertools import*
print min((reduce(lambda s,w:(w+s[max(i*(s[:i]==w[-i:])for i in range(99)):],s)[w in s],p)
for p in permutations(input())),key=len)

The second line break is not needed.
Input: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Output: SEDOLOREMAGNAD
Even with long input strings, this runs in less than 2 seconds if there are at most 7 input strings (as is the case in the example given, which runs in 1.7 1.5 seconds on my machine).  With 8 or more input strings, however, it takes more than 10 seconds, since the time complexity is O(n!).
As Baptiste pointed out, range(99) needs to be replaced with range(len(w)) if arbitrary input lengths should be supported (making the total length of the code 157 characters).  If empty input strings should be supported, it has to be changed to range(len(w)+1).  I think range(99) works correctly for any total input length less than 200, though.
More tests:
>>> "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

>>> 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM

Mathematica 337 418 372
After trying unsuccessfully to implement using Mathematica's LongestCommonSubsequencePositions, I turned to pattern matching.
v=Length;
p[t_]:=Subsets[t,{2}];
f[w_]:=Module[{c,x,s=Flatten,r={{a___,Longest[y__]},{y__,b___}}:>{{a,y},{y,b},{y},{a,y,b}}},
c=p@w;
x=SortBy[Cases[s[{#/.r,(Reverse@#)/.r}&/@c,1],{_,_,_,_}],v[#[[3]]]&][[-1]];
Append[Complement[w,{x[[1]],x[[2]]}],x[[4]]]]

g[r_]:=With[{h=Complement[r,Cases[Join[p@r,p@Reverse@r],y_/;!StringFreeQ@@y:>y[[2]]]]},
FixedPoint[f,Characters/@h,v@h-1]<>""]

The pattern-matching rule,
r={{a___,Longest[y__]},{y__,b___}}:> {{a,y},{y,b},{y},{a,y,b}}},

takes an ordered pair of words (represented as lists of characters) and returns: (1) the words,{a,y} and {y,b} followed by (2) the common substring,y,  that links the end of one word with the beginning of the other word, and, finally, the combined word {a,y,b} that will replace the input words.  See Belisarius for a related example: https://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution
Three consecutive underscore characters signify that the element is a sequence of zero or more characters.
Reverse is employed later to ensure that both orders are tested.  Those pairs that share linkable letters are returned unchanged and ignored.
Edit:
The following removes from the list words that are  "buried" (i.e. fully contained) in another word, (in response to @flornquake's comment).
h=Complement[r,Cases[Join[p@r,p@Reverse@r],x_/;!StringFreeQ@@x:> x[[2]]]]

Example:
 {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}} /. r

returns

{{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}, {"L", "O",
     "R", "E"}, {"D", "O", "L", "O", "R", "E", "M"}}

Usage
g[{"LOREM", "ORE", "R"}]

AbsoluteTiming[g[{"AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"}]]

"LOREM"
{0.006256, "SEDOLOREMAGNAD"}

Does this work for input "LOREM", "ORE", "R"?

(I.e., does it produce the correct output "LOREM"?)

@flornquake.  Nice catch.  I addressed it in the current version.  I hope I haven't missed any other cases. Thanks.

Python 2, 203 187 200
from itertools import permutations as p
def n(c,s=''):
 for x in c:s+=x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if s.endswith(l)),0):]
 return s
print min(map(n,p(input())),key=len)

Input: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Output: SEDOLOREMAGNAD
Edit
Using reduce and some dirty import trickery, I can reduce this further (and to one line only!):
print min((reduce(lambda a,x:a+x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],P,'')for P in __import__('itertools').permutations(input())),key=len)

Edit 2
As flornquake noted, this gives incorrect results when one word is contained in another. The fix for this adds another 13 chars:
print min((reduce(lambda a,x:a+(x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],'')[x in a],P,'')for P in __import__('itertools').permutations(input())),key=len)

Here's the cleaned up version:
from itertools import permutations

def solve(*strings):
    """
    Given a list of strings, return the shortest string that contains them all.
    """
    return min((simplify(p) for p in permutations(strings)), key=len)

def prefixes(s):
    """
    Return a list of all the prefixes of the given string (including itself),
    in ascending order (from shortest to longest).
    """
    return [s[:i+1] for i in range(len(s))]
    return [(i,s[:i+1]) for i in range(len(s))][::-1]

def simplify(strings):
    """
    Given a list of strings, concatenate them wile removing overlaps between
    successive elements.
    """
    ret = ''
    for s in strings:
        if s in ret:
            break
        for i, prefix in reversed(list(enumerate(prefixes(s)))):
            if ret.endswith(prefix):
                ret += s[i+1:]
                break
        else:
            ret += s
    return ret

print solve('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')

It's possible to shave off a few characters at the cost of theoretical correctness by using range(99) instead of range(len(x)) (credits to flornquake for thinking of this one).

If you're willing to sacrifice correctness then you might as well use the greedy approach or the polynomial approximation factor of 2 approach.

Nice solution! You need to check if new words are already in the superstring, though: 'LOREM', 'ORE', 'R' incorrectly produces the output LOREMORER.

@flornquake Good catch. I managed to fix it but it adds 13 characters.

Haskell, 121
import Data.List
a p []=[(length p,p)]
a p s=[r|w<-s,t<-tails w,isInfixOf w$p++t,r<-a(p++t)(s\\[w])]
s=snd.minimum.a ""

Minus two if the function doesn't need to be bound to a name

Python, 144 chars
S=lambda A,s:min(S(A-set([a]),s+a[i:])for a in A for i in range(len(a)+1)if i==0 or s[-i:]==a[:i])if A else(len(s),s)
T=lambda L:S(set(L),'')[1]

S takes a set of words A that still need placing and a string s containing words placed so far.  We pick a remaining word a from A and overlap it from 0 to len(a) characters with the end of s.
Takes only about 0.15 seconds on the given example.

Really nice! But like some other solutions, this doesn't work for input like ['LOREM', 'ORE', 'R'].
I've taken the liberty to fix that and golf your solution some more:  S=lambda A,s='':A and min((S(A-{a},(s+a[max(i*(s[-i:]==a[:i])for i in range(len(a))):],s)[a in s])for a in A),key=len)or s (a second line is not needed).  Usage: S({'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'}) returns 'SEDOLOREMAGNAD'.

source: Stack Exchange

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

sort: votes


text:
Print an arch of ascending / descending numbers
I figured an "arch" was the best way to describe this pattern of numbers:
1234567887654321
1234567  7654321
123456    654321
12345      54321
1234        4321
123          321
12            21
1              1

Formally defined, each line consists of the numbers 1 through 9-n, (n-1)*2 spaces, and the numbers 9-n through 1 (where n is the current line).
Your task is to write, using the shortest code possible, a small script/program that prints the above pattern subject to the following restrictions:

You may not hardcode the entire pattern. You may only hardcode a single line of the pattern at most.
Your program must print a newline (any combination of \n or \r) at the end of each line.

Ready... set.... go!

Additional little trick would be available with upper line 123456787654321 as it equals to 11111111^2  ;-)

@EgorSkriptunoff 11111111^2 == 123465787654321 != 1234567887654321 (notice the repeated 8)

This is sort-of the inverse of Print this diamond

It looks rather like a curtain.

Python 2, 65 55 53 51
s=12345678
while s:r='%-8d'%s;print r+r[::-1];s/=10

Shortened using some of ugoren's ideas.

Heh, I knew there was room for improvement :P

You can save a lot by s=s[1:] per loop and while s:

GolfScript (25 chars)
8,{.~10,<1>\' '*.2$-1%n}/

 APL (18)
k,⌽k←↑↑∘(1↓⎕D)¨⌽⍳8

Explanation:

1↓⎕D: the string of digits ("0123456789") minus its first element
↑∘(1↓⎕D)¨⌽⍳8: select the first [8..1] characters ('12345678', '1234567'...)
↑: format as matrix (filling the unused characters with blanks)
k,⌽k←: store in k, and display k followed by the vertical mirroring of k

Befunge - 3 x 18 = 54
I felt I had to do something with befunge, it's been too long since I last used it.
This problem felt the most appropriate for the language.
It is horrendously slow due to the print loop that takes about 8 actions per character (counting styles differ).
80v >#v"12345678"<
>5 *^ >,#$:_$:1-:v
^2< 0p0+7\*48\_@#<

JavaScript, 71
s='1234567887654321',i=10;while(--i)console.log(s=s.split(i).join(' '))

s="1234567887654321";for(i=10;--i;)console.log(s=s.split(i).join(" "))
for 70 characters, @SteveWorley

Ruby: 61 50 characters
s="87654321";s.chars{|c|puts s.reverse+s;s[c]=" "}

Sample run:
bash-4.2$ ruby -e 's="87654321";s.chars{|c|puts s.reverse+s;s[c]=" "}'
1234567887654321
1234567  7654321
123456    654321
12345      54321
1234        4321
123          321
12            21
1              1

C, 83 chars
main(a,b,n){
    for(a=12345678,n=1e8,b=n-a-1;a;a/=10)
        printf("%-8d%8d\n",a,b),
        b%=n/=10;
}

Python 2, 75 62
It won't beat Volatility's answer, but here's another approach using python's mutable strings (bytearray):
s=bytearray('1234567887654321')
for i in range(8):s[8-i:8+i]=i*'  ';print s

Edit
I found a shorter version, using str.replace:
s='1234567887654321'
for c in s[8:]:print s;s=s.replace(c,' ')

Mathematica 92 85 67 54 51
Method #1: (54 chars) Makes array using row#, col#, and distance from left-right edge.
Grid@Array[If[#2<9,#2,17-#2]/.x_/;x+#>9:>" "&,{8,16}]

Method #2: (67 chars) Pad ever-shortening ranges.
Print@@@Table[Join[k = PadRight[Range@i, 8, " "], Reverse@k], {i, 8, 1, -1}];

Method #3: (85 chars) Selectively fill each row of an array.
Start with list of 8 space characters. Replace positions 1 and 16 with "1"; replace "2" at positions 2 and 15, etc.
p = 0; q = 16;
Print @@@Reverse@Rest@NestList[ReplacePart[#, {++p -> p, q-- -> p}]&,Array[" "&,q], 8];

Method #4: (86 chars) Selectively empty each row of an array.
p=8;q=9;
Print@@@NestList[ReplacePart[#,{p---> " ",q++-> " "}]&,Join[k=Range@8,Reverse@k],7];

Method #5: Using strings (92 chars)
p=8;s="12345678";
Print[#,StringReverse@#]&/@NestList[StringReplace[#,ToString@p-- ->  " "]&,s,7];

That new one is slick!  I'd +1 again if I could. :-)  btw, you can drop the (), and replace #1 with #: Grid@Array[If[#2<9,#2,17-#2]/.x_/;x+#>9:>" "&,{8,16}]

Thanks for the tips. Yes, Array can sometimes make nice tables without one's having to add iterators.

Perl, 41
plus -E switch. Total characters on the command line: 50
requires at least perl5, version 10.
perl -E'say@!=1..8-$_,$"x(2*$_),reverse@!for-0..7'

I would say this is 42, due to the fact that the standard look on -E is a one-byte addition to the program.

PHP, 68
(Inspired by HamZa's answer)
for($n=8;$n;$r[]=$n--)echo str_replace($r," ","1234567887654321\n");
Plays on the fact that PHP's str_replace can accept an array for search and a string for replace, it'll replace every item in the array with the given string.
After each iteration, the current number is added to the search array, removing it from the next loop.
Example of the code in action: http://ideone.com/9wVr0X

hehe nice +1

doesn't appear to put the right number of spaces in the middle though

@nathanhayfield: How so?  First line has 0 spaces, second has 2, then 4, 6, 8, etc.

not when i ran it on http://writecodeonline.com/php/

That's because the output wasn't wrapped in
 tags.  When interpreted as html text, the spaces are collapsed and the newlines are ignored, but if you check the source you'll see otherwise.

Marbelous 165
@0
08
>0
LN
--
@0
:LN
}0}0}0}0
..SAPSSD0A
{0
:PS
}0
~~09
..//
<<@0
\\>0
&0//
--@1
@020
&0/\&0
@1
:SA
@0
}0
>0!!
--00@1
@0++//
+O/\@1
+O
:SD
}0@0
\\>0\/
--/\+O
@0..+O

Pseudocode:
MB():
    for x in 8..1:
        LN(x)
LN(x):
    SA(x)
    PS(x)
    SD(x)
    print "\n"
PS(x):
    print " "*(8-x)*2
SA(x):
    for n in 1..x:
        print n
SD(x):
    for n in x..1:
        print n

GoRuby 2.1
36 chars
8.w(1){|x|a=[*1..x].j.lj 8;s a+a.rv}

Ungolfed
8.downto(1) do |x|
  a = [*1..x].join.ljust(8)
  puts a + a.reverse
end

K 20
{x,'|:'x:|x$,\$1+!x}

q)k){x,'|:'x:|x$,\$1+!x}8
"1234567887654321"
"1234567  7654321"
"123456    654321"
"12345      54321"
"1234        4321"
"123          321"
"12            21"
"1              1"

Can trim a byte by using {x,|x}' instead of x,'|:'x:.

Python 2.x - 73 65 63 61 chars
c=1;s='87654321'
while c<9:print s[::-1]+s;s=' '*c+s[c:];c+=1

PHP, 76
for($i=9;$i>1;){$r[]=$i--;echo str_replace($r,' ','1234567887654321')."\r";}

K, 28
-1_a,'|:'a:8$'{-1_x}\,/$1+!8

.
k)-1_a,'|:'a:8$'{-1_x}\,/$1+!8
"1234567887654321"
"1234567  7654321"
"123456    654321"
"12345      54321"
"1234        4321"
"123          321"
"12            21"
"1              1"

You could generalise it for 36: {-1_a,'|:'a:(#*m)$'m:{-1_x}\,/$1+!x}
k){-1_a,'|:'a:(#*m)$'m:{-1_x}\,/$1+!x} 5
"1234554321"
"1234  4321"
"123    321"
"12      21"
"1        1"
q)k){-1_a,'|:'a:(#*m)$'m:{-1_x}\,/$1+!x} 15
"123456789101112131415514131211101987654321"
"12345678910111213141  14131211101987654321"
"1234567891011121314    4131211101987654321"
"123456789101112131      131211101987654321"
"12345678910111213        31211101987654321"
"1234567891011121          1211101987654321"
"123456789101112            211101987654321"
"12345678910111              11101987654321"
"1234567891011                1101987654321"
"123456789101                  101987654321"
"12345678910                    01987654321"
"1234567891                      1987654321"
"123456789                        987654321"
"12345678                          87654321"
"1234567                            7654321"
"123456                              654321"
"12345                                54321"
"1234                                  4321"
"123                                    321"
"12                                      21"
"1                                        1"

Javascript, 67 chars
Insipired by steveworley's answer (I would comment if I could):
Code snippet

a='1234567887654321\n',b='',c=10;while(--c)b+=a=a.split(c).join(' ')
Display

...

The presence of the last newline does follow the rules.
update: cut 2 chars by removing parentheses (operator precedence) and 1 by removing an unneeded space
It seemed like it's trolling me, because no matter how many different ways I tried to shorten or simplify by un-hardcoding a segment of code, the length stayed the same until I let the "I think this counts" rule written below apply.
(If printing counts as what comes back when this is executed in the chrome console)

It doesn't look like the other answer, the numbers are not aligned on the right column.

@A.L. The alert isn't necessary if you read what output comes out of the consonle btw.

To align right column, there should be 1 space instead of 2 in join's string argument. With 2 spaces it is correct aligned in chrome-based browser alert.

I updated your post (the edit should be accepted) to display the result in a snippet without a JS alert, only one space is needed in this case.

Brainfuck: 542 Bytes
-[----->+<]>--.+.+.+.+.+.+.+..-.-.-.-.-.-.-.>++++++++++.[->+++++
<]>-.+.+.+.+.+.+.+[-->+<]>++++..----[->++<]>-.-.-.-.-.-.-.>++++++++++.[->+++++
<]>-.+.+.+.+.+.[-->+<]>+++++....-----[->++<]>.-.-.-.-.-.>++++++++++.[->+++++
<]>-.+.+.+.+.--[--->++<]>--......-----[->++<]>-.-.-.-.-.>++++++++++.[->+++++
<]>-.+.+.+.-[--->++<]>--........++[-->+++<]>+.-.-.-.>++++++++++.[->+++++
<]>-.+.+.[--->++<]>--..........++[-->+++<]>.-.-.>++++++++++.[->+++++
<]>-.+.--[--->++<]>............[-->+++<]>++.-.>++++++++++.[->+++++
<]>-.-[--->++<]>..............[-->+++<]>+.

PostScript: 105 characters
String handling is not easy in PS but can make for relatively simple code:
0 1 7{(1234567887654321)dup
8 3 index sub(              )0 6 -1 roll 2 mul getinterval putinterval =}for

A slightly longer version at 120 chars but can generate different number arches by replacing the 8 at the start of the second line with any number in the range 1 to 9:
/D{dup}def/R{repeat}def/P{=print}def
8 D -1 1{1 1 index{D P 1 add}R pop 2 copy sub{(  )P}R D{D P 1 sub}R pop()=}for pop

Its nice to see that I'm not the only one who loves PostScript out there.

TSQL, 148
Edit: down to 148 with manatwork's suggestion and tweak to ORDER BY.
Readable:
WITH t AS(
    SELECT 1n, CAST(1 AS VARCHAR(MAX)) o
 UNION ALL
    SELECT n+1,o+CHAR(n+49)
    FROM t
    WHERE n<8
)
SELECT o  + SPACE(16-2*n) + REVERSE(o)
FROM t
ORDER BY 1 DESC

Golfed:
WITH t AS(SELECT 1n,CAST(1AS VARCHAR(MAX))o UNION ALL SELECT 1+n,o+CHAR(n+49)FROM t WHERE n<8)SELECT o+SPACE(16-2*n)+REVERSE(o)FROM t ORDER BY 1DESC

Output:
1234567887654321
1234567  7654321
123456    654321
12345      54321
1234        4321
123          321
12            21
1              1

Nice one. But could you please post it also in the format in which you counted 153 characters? Anyway, you can spare 2 characters by using numeric 1 instead of string '1' where you immediately cast it into varchar. This gives me 149 characters: with t as(select 1n,cast(1as varchar(max))o union all select n+1,o+char(n+49)from t where n<8)select o+space(16-2*n)+reverse(o)from t order by o desc.

@manatwork: I couldn't reproduce the 153 number, because I kept getting lower. Applied your suggestion, though. Thanks!

Haskell, 79
r n x|x>n=' '|True=x
t="87654321"
main=mapM(putStrLn.(`map`("12345678"++t)).r)t

This works by replacing characters > n with ' ', where characters n are sourced from "87654321" (which happens to be the tail of the string to perform substitution on).

Haskell, 84
A starting point for someone to improve:
mapM_ putStrLn[let l=take(8-i)"12345678"++replicate i ' 'in l++reverse l|i<-[0..7]]

Most likely part would be to make the l++reverse l point free, letting us get rid of the let-statement, but I'll I could find was ap, which requires imports.

Mathematica, 59
61 using my own ideas:
Grid[Clip[#~Join~Reverse@#&@Range@8,{1,9-#},{," "}]&~Array~8]

Or 59, borrowing from David's answer:
Grid@Array[Join[k=PadRight[Range[9-#],8," "],Reverse@k]&,8]

I just saved 4 chars by using Grid, inspired by your entry.

R: 52
for(i in 8:1)cat(1:i,rep(" ",16-2*i),i:1,"\n",sep="")

Tcl: 91 characters
set i 10
set n 1234567887654321
while {[incr i -1]} {puts [set n [string map "$i { }" $n]]}

k, 33 chars
{|:{x,'|:'x}a$,/'$:{1+'!x}'1+!a:x}9

PHP: 61 chars (or 60 chars if you replace the \n by a real ASCII newline)
(Inspired by GigaWatt's and HamZa's answer)
for($n=9;$n;$r[$n--]=" ")echo strtr("1234567887654321\n",$r);

http://ideone.com/FV1NXu

PowerShell: 38
Golfed code
8..1|%{-join(1..$_+"  "*(8-$_)+$_..1)}

Walkthrough
8..1|%{...} pipe integers from 8 to 1 into a ForEach-Object loop.
-join(...) joins output of the nested code into a single string with no delimiters.
1..$_ outputs integers ascending from 1 to the current integer in the loop.
+"  "*(8-$_) adds a double-space, multiplied by the difference between 8 and the current integer, to the output.
+$_..1 adds integers, descending from the current integer to 1, to the output.

Javascript with lambdas, 147
(s="12345678")[r="replace"](/./g,i=>s[r](RegExp(".{"+(i-1)+"}$"),Array(i*2-1).join(" ")))[r](/\d{1,8} */g,m=>m+(Array(m%10+1).join(m%10+1)-m)+"\n")

Can be checked in Firefox.

CJam, 22 characters
Not a valid answer (as language was developed after the question), and not the shortest either, but here goes:
8,{S*_,9-~,:)\_2$W%N}%

Try it online here

Jelly, 11 bytes
RURz⁶Zm0$€Y

Try it online!
RURz⁶Zm0$€Y  Main Link
RU           Inverse Range
  R          Range ([1...x], [1..x-1], [1..x-2], ..., [1])
   z⁶Z       Zips, filling by spaces, and then zips back (pads)
         €   Map...
      m0$    ...appending the reverse of each element to itself
          Y  Newline-delimited

Vyxal j, 9 bytes
8ɾɾṘƛṅ8↲m

Try it Online!
8ɾ        # 1...8
  ɾ       # 1...{1...8}
   Ṙ      # {1...8}...1
    ƛ     # For each
     ṅ    # Join
      8↲  # Pad to length 8 with spaces
        m # Mirror
          # (j flag) join by newlines

Pip -l, 13 bytes
RF\,8X8-,8ZDs

Try it online!
Explanation
        ,8     Numbers 0 through 7
      8-       Subtract each from 8, giving numbers 8 through 1
     X         Repeat that many times
  \,8          the corresponding number from 1 through 8
               We now have the list [11111111 2222222 ... 77 8]
RF             Reflect, appending a reversed copy of the list
          ZDs  Transpose, padding shorter elements with a default value of space
               Autoprint with each row on its own line (-l flag)

Stax, 9 bytes
éúß8╕t±╫k

Run and debug it
gaming

APL, 15 Chars, 29 Bytes
a,⌽a←⊃⌽,\⍕10⊥⍳8

⍕10⊥⍳8 produces string '12345678' and ,\ gives all prefixes.
 1 12 123 1234 12345 123456 1234567 12345678

⌽ reverses the array and ⊃ builds a matrix:
12345678
1234567
123456
12345
1234
123
12
1

a,⌽a concatenates each row with its reverse and gives the results.
Works on GNU APL and APLX. For Dyalog APL, change ⊃ to ↑, or set migration level to 2 ⎕ML←2.

K 27
q)k)f:{{x,'|:'x}x$,/'$1+!:'|1+!x}
q)f 8
"1234567887654321"
"1234567  7654321"
"123456    654321"
"12345      54321"
"1234        4321"
"123          321"
"12            21"
"1              1"

J: 34 31 characters
(,.|."1)|.(>:i.8){."0 1(49}.a.)

Been a while since I've coded in J.  I'm sure I can shave off some characters somewhere.

Lua, 62
s='1234567887654321'for i=8,1,-1 do print(s)s=s:gsub(i,' ')end

Java, 127
void a(){for(int y=0;y<8;System.out.println(y++==9?"":""))for(int c=0,x=1;c<16;System.out.print(y+(x=++c<=8?c:8-c+9)>8?"":x));}

Haskell, 71 bytes
d="87654321"
main=mapM putStrLn[do x<-reverse d++d;max" "[x|x<=y]|y<-d]

Try it online!

Canvas, 7 6 bytes
８｛Ｒ］⇵║

Try it here!

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:
Compute the number of ways how you can express a number as a sum
For a given natural number n, compute the number of ways how one can express n as a sum of positive natural numbers. For example, for n = 1 there is just one way. For n = 4 we have 5 possible ways:
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
2 + 2
4

The ordering of terms in a sum doesn't matter, so 1 + 3 and 3 + 1 are considered the same. Your program should be effective enough to return the result for n = 1000 in order of minutes.
The winner will the solution with most up-votes in (at least) 2 weeks.

For people who remember having already done it on Project Euler: Problem 76

Why is this a popcon rather than [tag:code-golf]?

@ppperry Honestly I don't remember exactly. In general I favor nice code over golfed code, so this is probably the reason. I guess [fastest-code] or [fastest-algorithm] might also be good for the question.

Haskell, 170 148
An efficient Haskell version using a generating function with Memoization. Solve instantaneously the problem for n = 1000. No precision issues even with large numbers:
time ./partitions 10000
36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144
./partitions 10000  17.02s user 0.00s system 100% cpu 17.021 total

The code
generalizedPentagonal = map pentagonal $ [1..] >>= \i->[i,-i]
    where pentagonal n = (3*n^2-n)`quot`2

partitions = (map partitions' [0..] !!)
    where partitions' 0 = 1
          partitions' n = sum . alternate . map partitions . takeWhile (>=0) . map (n-) $ generalizedPentagonal
          alternate = zipWith (*) (concat . repeat $ [1,1,-1,-1])

Code-golf version
p=(map a[0..]!!)where a 0=1;a n=sum.zipWith(*)(concat.repeat$[1,1,-1,-1]).map p.takeWhile(>=0).map(n-).map(\n->(3*n^2-n)`quot`2)$[1..]>>= \i->[i,-i]

Efficiency improvements
Replace the memoization with an Array instead of a list:
import Data.Array
[...]
bnd = (0,10000)
partitions = (array bnd [(i, partitions' i) | i <- range bnd] !)
[...]

Time for partitions 10000 drop from 17s to 960ms
Results
Interpreted:
partitions 1000
24061467864032622473692149727991
(0.11 secs, 21833064 bytes)

Compiled:
time ./partitions 1000
24061467864032622473692149727991
./partitions 1000  0.08s user 0.00s system 99% cpu 0.084 total

Useful links

The generating function
Generalized pentagonal numbers

Nice. You can shorten a few things, for instance you don't need where. concat[[i,-i]|i<-[1..]] is more concisely [1..]>>= \i->[i,-i] (where you might as well directly build in the pentagonal call).

Mathematica 25 11
PartitionsP

Usage
PartitionsP[4]
(*
5
*)

Calculating the result for n = 1000 is instantaneous
Timing[PartitionsP@1000]
(*
 {0., 24061467864032622473692149727991}
*)

I was going to propose this solution but thought it was a bit too ready-made.

@DavidCarraher All APL solutions seems like that to me :D

I know just what you mean.

JavaScript
var partition = function(n) {
    var sigma=[], p=[1], i,j;
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j+=i)
            sigma[j] = (sigma[j]||0) + i;
    for (i=1; i<=n; i++) {
        p[i] = 0;
        for (j=1; j<=i; j++)
            p[i] += p[i-j] * sigma[j];
        p[i] /= i;
    }
    return p[n];
}

This computes the partition function A000041 as the Euler transform of the sequence A000012 (1,1,1,...). The intermediate sequence sigma is A000203, the sum-of-divisors function.
For n=1000 it takes approx 0.05 seconds in Node on my 2GHz machine, although since it's working with JS numbers it runs into precision issues. A slightly more complex version (online demo, it's a bit long to paste) adds a naïve big integer implementation and takes approx 0.5s in Node.

JavaScript, 105 103
for(n=prompt(a=[b=1]);b<=n;a[b++]=s)for(s=0,k=1,j=b-1;j>-1;j-=k&1?k:k/2)s+=++k&2?a[j]:-a[j];alert(a[n])

Calculation takes less than 250ms for n=1000. The result isn't precise, because JS doesn't have arbitrary precision numbers, but the order of the result is correct.

GolfScript, table recurrence
[[1]]\({..[[{1$,1$,-=}%0@0=+]zip{{+}*}:^%]\+}*0=^

Assumes input as an integer on the stack: leaves the result on the stack. Online demo counting partitions of 10.
This isn't as efficient as the other answers (it computes the partitions of 1000 in approximately 30 seconds), but the mathematical background is much simpler.
Instead of considering just the number of partitions of n, consider the number of partitions of n into k parts: p(n, k). Each such partition either contains a 1 or doesn't. The number of partitions which contain a 1 is easily seen to be the same as the number of partitions of n-1 into k-1 parts. For the partitions which don't contain a 1, we can subtract 1 from each part without getting any zeroes, so their number is equal to the number of partitions of n-k into k parts. So we have the recurrence p(n, k) = p(n-1, k-1) + p(n-k, k).
This program builds the table of p(n, k) starting from p(1, 1) = 1, and then at the end adds up the partitions of n into 1..n parts to get the result.
Dissection:
# Initialise the table p(x,k) with the row for x=1
# Note that we will prepend new rows to the table, so it is built backwards
[[1]]
# Repeat n-1 times
\({
    # We need a couple of copies for the two parts of the sum in the recurrence
    ..
    # Collect in an array...
    [
        # Collect in an array...
        [
            # First an array of p(x-k, k) for k = 1 to x-1
            # x is the length of the current table plus one
            # We iterate over the rows of the table
            {
                # Stack: table table row
                # Row x-k is of length x-k, so k = x - length(row)
                # But because the row is indexed from 0, we want to find k - 1
                #   = length(table) - length(row)
                1$,1$,-
                =
            }%
            # Stack: table table [p(x-1,1) ... p(1,x-1)]
            # (Although actually it will be shorter, only until about p(x/2, x/2))
            0@0=+
        ]
        # Stack: table [[p(x-1,1) ... p(1,x-1)] [0 p(x-1,1) ... p(x-1,x-1)]]
        # Vector sum. Note that we store the array-sum operation in ^ for later use.
        zip{{+}*}:^%
    ]
    # Prepend to the table
    \+
}*
# Take the first row of the table and sum it
0=^

(NB If this were code-golf then I would save 1 char by repeating the loop n times and taking the second row of the table at the end).

Python2, 110 (Bruteforce O(n^n) implementation)
A bruteforce implementation in python which takes the input of stdin:
from itertools import*
n=input()
print len(set(frozenset(p)for p in product(range(n+1),repeat=n)if sum(p)==n))

Computing the result for n=8 takes 10 seconds on my machine. Anything over that is way over a few minutes.

GolfScript
2,\.,{[2+.2&(0@,{.2%!)/+}/]}%`{0\{~.4$,<*~)3$=*+}/+}+*-1=

Just because we need a GolfScript entry. Thanks to Peter for several ideas.
Example:
1000 2,\.,{[2+.2&(0@,{.2%!)/+}/]}%`{0\{~.4$,<*~)3$=*+}/+}+*-1=
# => 24061467864032622473692149727991

Why ..+ near the start? Doesn't .) give you enough pentagonal numbers?

@PeterTaylor It does ;-)

Calculating the pentagonal numbers as partial sums of A026741 gives a considerable simplification: replace ),...%1> with ,{[2+.2&(0@,{.2%!)/+}/]}%

@PeterTaylor Pushing it inside the loop shortens even further ... but unfortunately makes it slower also.

I was thinking along similar lines to your change to the second half, but using negative indexing into arrays. Your reversal is nicer, though, because it lets you extract the first rather than the last element for the final result.

Aha! Your original approach of calculating an index or zero combines with a fake initial zero in the array. Change [1] at the start to 2, and then the second main loop is 0\{~~).4$,+0>*3$=*+}/+ (and back to -1= to extract the final result).

@PeterTaylor Ah, you beat me again. Was working on a similar idea but didn't get around the reversals.

~).4$,+0>* is better as .4$,<*~)

JavaScript Hardy-Ramanujan-Rademacher
This depends on a BigNumber implementation which supports the following functions: plus, minus, times, div, sqrt, isZero, lt, gt, round). It also uses config to control the precision used in divisions and to set the rounding mode.
var partition = function(n) {
    // Hardy-Ramanujan estimate to set the precision with appropriate margin
    BigNumber.config((5 + 1.115 * Math.sqrt(n) + Math.log(n) / Math.log(100))|0, 6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        one = new BigNumber(1),
        // \sum_{i=0}^\infty 2^{i+1} i!^2 / {2i+1}!
        PI = function(){ var t = new BigNumber(2), s=t, i=1; while (!t.isZero()) s = s.plus(t = t.times(i).div((i+ ++i))); return s }(),
        A = new BigNumber(n).minus(one.div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        gcd = function(x, y) { return y ? gcd(y, x % y) : x },
        genexp = function(x, a, b, c, d) {
            // \sum_{i=0}^\infty ax^{4i}/(4i)! + bx^{4i+1}/(4i+1)! + cx^{4i+2}/(4i+2)! + dx^{4i+3}/(4i+3)!
            var res = zero, z = one, i;
            for (i=0; !z.isZero(); i+=4) {
                res = res.plus(z.times(a)); z = z.times(x).div(i+1);
                res = res.plus(z.times(b)); z = z.times(x).div(i+2);
                res = res.plus(z.times(c)); z = z.times(x).div(i+3);
                res = res.plus(z.times(d)); z = z.times(x).div(i+4);
            }
            return res;
        },
        p = zero, q = 0, C, L, Psi_, h, k, s, max_L = zero;
    for (;;) {
        // Adaptive precision calculation for performance
        if (++q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);

        L = zero;
        for (h = 0; h < q; h++) {
            if (gcd(h,q) > 1) continue;
            for (k=s=0; k < q; k++) s+= (2*(h*k %q) - q) * k - 4*h*n;
            // NB The %(4*q*q) is critical for performance
            L = L.plus(genexp(new BigNumber(s % (4*q*q)).div(2*q*q).times(PI),1,0,-1,0));
        }
        if (L.gt(max_L)) max_L = L;

        C = B.div(q);
        Psi_ = genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt());
        p = p.plus(L.times(Psi_));
        if (Psi_.times(max_L).abs().lt(ABsqrt12)) break;
    }
    return p.div(ABsqrt12).round();
};

It computes partition(10000) in about 0.67 seconds using Node on a 3.5GHz PC.


text:
Write 'hello world' to standard output without using certain common words - C# only
The challenge is to write the string hello world to your processes standard output, using as few characters of code as possible.
The following restrictions apply:

The following words may not appear anywhere in the code in any casing (this includes as part of another word)

Console
Debug
Write
Print
Line
Put

Your code must compile as C# 4/4.5
No external libraries are permitted.
Your process may not spawn any new processes.

A working (but not necessarily the shortest) solution will be provided after a number of answers have been provided.
The winner is the author of the shortest code by character count that satisfies the above criteria.

There is at least one solution to this in the answers to http://codegolf.stackexchange.com/questions/5550/shortest-hello-world-program-with-no-semi-colons

@PeterTaylor - none of the C# answers posted for that challenge satisfy the word usage restriction.

w0lf's one does. There are also some answers in http://codegolf.stackexchange.com/questions/307/obfuscated-hello-world which demonstrate a technique which could be applied to the trivial hello world program (and which I see Johannes Kuhn has used in his answer).

@JohannesKuhn how is it a duplicate? The restrictions are completely different.

Not exactly. You may violate 1 rule of the other question, and for C# it have to be rule 1 (class is needed). All of the words you list here except put violate rule 2. That means the difference is that on the other question put and other languages are allowed and here the characters eor0127 are allowed. Not very big.

75 chars
New answer, new approach.
class M{static void Main(){System.\u0043onsole.\u0057rite("hello world");}}

It looks like you can hide every character with a \uXXXX sequence. Which makes this thing...
Easy.

183 chars
Without reflection "cheats"! (but using the deprecated overload of FileStream to avoid using SafeFilePointer)
using System;using System.IO;public class M{static void Main(){new MemoryStream(Convert.FromBase64String("SGVsbG8gV29ybGQ=")).CopyTo(new FileStream(new IntPtr(-11),(FileAccess)2));}}

Ok, I try my luck:
118 chars
class M{static void Main(){System.Type.GetType("System.\x43onsole").GetMethods()[78].Invoke(0,new[]{"hello world"});}}

Based on this solution.
Idone
As noted in the original answer, the index of the Write method might be different on your system.

'Object of type 'System.String' cannot be converted to type 'System.Int32'' You were right about the index not being the same. Since it doesn't run for me I can't accept this particular answer.

It runs on Idone. You have to change the index. Try 78.

Here's my current best that runs anywhere:
158 Characters
using System;class M{static void Main(){Type.GetType("System.\x43onsole").GetMethod("\x57rite\x4cine",new[]{typeof(string)}).Invoke(0,new[]{"hello world"});}}

.Invoke ignores the first param entirely if its a static method, so you can use 0 instead of null to save 3 characters.
Additionally, a variation that bans the use of the \ character:
234 Characters
using System;using System.Linq;class M{static void Main(){Func<string,string>f=(i)=>new string(i.Reverse().ToArray());Type.GetType(f("elosnoC.metsyS")).GetMethod(f("eniLetirW"),new[]{typeof(string)}).Invoke(0,new[]{"hello world"});}}


text:
Encode a program with the fewest distinct characters possible
The goal is to write a program that encodes an other program (input) with the fewest character possible.
Scoring

The score is equal to the different number of characters needed for the output.
Lower score is better.

Rules

No target languages with a limited set of commands. (No Brainf**k, Whitespace etc)
Edit: I mean at least 26 significant characters, A doesn't change the way a brainf**k program operates, so you can't count this character. Same applies to whitespace.
The target language must exist at the time where this question is written.
You have to include a small explanation how you achieve your score.
The input program is valid.
The encoded program must be a valid program in the same language as the input.
The encoded program must do the same job as the original program.
Your encoder must work for every valid program in that language.
Include some sample input and output.

Notes

The encoder might be written in any language, not only in the language it targets.
This is not code-golf, readable programs are encouraged.
The great goal is to see how many different characters are needed to write anything in that language. I disallowed BF etc because there would be no challenge.
This was inspired by Print a string in as few distinct characters as possible, you could take it as metagolf for that question.

Example
In Java, you can use \uXXXX instead other characters. A valid entry encodes every character from the input this way. This would have a score of 18. (\ 0-9a-f)
Code in Tcl, encodes a Java program:
set res {}
foreach char [split [read stdin] {}] {
    append res [format \\u%04x [scan $char %c]]
}
puts $res

sorry for the vote to close... thought this was a duplicate of http://codegolf.stackexchange.com/questions/6974/ but that one's python-specific.

With you Java score and your encoder: I don't speak much Tcl, but doesn't gets read a single line of input only? And you missed the u in your encoder (but on the other hand you don't need the space and thus the score remains the same).

Maybe you should add a rule along the lines encoded program should (under reasonable constraints) perform the same task as the original version. It is never stated and thus I could transform anything to any (constant) program.

Do you rule out a simple conversion to binary, converting the digits to characters and removing the resulting spaces?

@Graham In which language would that result be a valid program?

@Howard I guess I should have read rule 5 more carefully if that means it should run as is in its encoded form :(

possible duplicate of Print a string in as few distinct characters as possible

Don't all programming languages have a "limited set of commands"? Where do you draw the line?

try to make a new command in brainfuck.

I'm voting to close this because it has a broken victory condition patched over by a very unclear ban on languages. If Unary wasn't banned, it'd score 1. If brainfuck wasn't banned, it'd score 7 (note that the language itself naturally has 8 commands + 248 comment characters). So where's the line between naturally having too few commands, and having enough to be legitimate.

Even languages like Python have a limited set of commands. You can't "make a new one", you simply create a new function or something, but the reserved words stay the same. The definition of "command" is unclear. The question could possibly be fixed by not limiting languages (just don't upvote trivial answers), and requiring that the set of characters used must be a proper subset of those in the language.

so a cat program submitted to this would have a score of 2^30?

Is CJam allowed? It has only 26 variables that can be redefined, which could contain blocks (commands). It's not limited to the original set of commands, but the maximum number of commands is still finite.

And how are subroutine labels in Whitespace, which are not significantly different from C functions, not new commands?

I hope my edit solves your concerns.

"at least 26 significant characters" seems to still allow a Beatnik-based answer with a score of 2... or even a Lenguage-based answer with a score of 1! (Neither language truly ignores any characters: Beatnik splits a program into chunks of consecutive alphabetical characters and executes commands based on their Scrabble scores, and a Lenguage program encodes a brainfuck program in its length disregarding any other information.)

Extremely confusing rules! Sometimes it speaks about commands, then about characters. Most languages use several characters to form a command. What about a language with unlimited commands (because you can define own commands, with the whole unicode range being significant), if you don't use these possibilities?

GolfScript / GolfScript, score 4
"'',,"\{"'"\","*"',+"}%"''+~"

The encoder itself is a GolfScript program which takes the original code on STDIN and transforms it into a sequence of characters ',+~. This output itself is valid GolfScript code which performs the same operations as the original version.
The basic method consists of an encoding of the code as a string (using chars ',+, see below) and then evaluate this string using the eval command ~.
If one concatenates any string together with an array of numbers in GolfScript the numbers are converted to code points and the result is a string itself. Thus the string encoding simply builds a list of numbers (from the code points of the input code) and then concatenates all those with an empty string.
Example:
The input code
"hi"
p

is translated into (note: line breaks and comments added for readability)
# initialize an empty array []
'',,

# append number 34 (length of string ',,, ... ,,,')
',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',+

# ... other numbers
',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',+
',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',+
',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',+
',,,,,,,,,,',+
',,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',+

# result is array [34 104 105 34 10 112]

# append empt string, i.e. convert array to string (results in "\"hi\"\np")
''+

# evaluate
~

Python -> Python, 8 distinct characters
def minimal_python(input_code):
    """Convert Python code to minimal Python code."""

    # Create a list of the ordinal numbers of <input_code>'s characters.
    # '%' signs have to be treated specially and are represented with -1.
    ords = []
    num_escaped_chars = 0
    for char in input_code:
        if char == '%':
            ords.append(-1)
        else:
            ords.append(ord(char))
            num_escaped_chars += 1

    modulo_sign_escape = '%' * 2**num_escaped_chars
    def formatters():
        num_escaped_chars_so_far = 0
        for o in ords:
            if o == -1:
                yield modulo_sign_escape
            else:
                yield '%' * 2**num_escaped_chars_so_far + 'c'
                num_escaped_chars_so_far += 1
    format_str = "'" + ''.join(formatters()) + "'"

    values_str = ''.join('%' + '-~'*o + '0' for o in ords if o != -1)

    return 'exec' + format_str + values_str

This uses modulo formatting to rebuild the input string. For example, print 1 results in this program:
exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

In theory you can encode any program like this, but the resulting program will always have more than 2n characters, where n is the number of characters in the input, not including % symbols.

The lower bound of the resulting program is 2**n+3*n-1 + 6 characters, including all input characters (if you assume every character is a NUL byte). This is taken from OEIS A132074, plus 6 for exec''. If you assume characters must be printable ASCII, then the lower bound is higher. https://repl.it/EHEN

There's another answer (on another challenge -- unfortunately, there are too many similar challenges) that takes only 7 bytes. https://codegolf.stackexchange.com/a/110722

CJam -> CJam, score: 3
CJam is newer than the question so it's not eligible to win.
q{[{_'(>{'(-')*''\+}{is'c+T}?}%{"+"T}*'~]}:T~

It uses ')~. ') is the character ), and each extra ) increments it by one. ~ can evaluate a character or a string. The complete program is evaluated after concatenating all the characters by evaluating +. And an integer of the character value and a number-to-character operation is evaluated for each character less than ).
Examples
XX{_2$+}I*]N*

is translated into:
'))))))))))))))))))))))))))))))))))))))))))))))))'))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~'))))))))))')))~')))))))))))'))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))')))~'))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))')))~'))))))))))))))))))))))))))))))))))))))')))~'))')))~~

and
q{[{_'(>{'(-')*''\+}{is'c+T}?}%{"+"T}*'~]}:T~

is translated into:
')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))'))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))'))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')')))~'))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))')))~'))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))')))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))'))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~')))')))~')))))))))))'))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~'))')))~')))))))))))')))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~')))~'))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))')))~')))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~'))))))))))))))))))')))~'))))))))))))))))))))))))))))))))))))))))))))')))~'))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))')))~~

APL (score: 10)
'⍎⎕AV[',(⊃,/{'(⍴',(⍵/'⍬'),')'}¨⎕AV⍳⍞),']'

Characters used in encoding: ⍎⎕AV[(⍴⍬)]
The APL program to encode must restrict itself to the APL charset and not use any extra Unicode.
Encoding for the program 42 (which outputs the answer to Life, the Universe, and Everything):
⍎⎕AV[(⍴⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬)(⍴⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬⍬)]

How it works: ⍬ is the empty list, ⍬⍬⍬⍬ is therefore a list of four empty lists, ⍴⍬⍬⍬⍬ is the length of the list of four empty lists, which is four. Dyadic ⍴ is reshape, so the length-of-list-of-lists instructions must be wrapped in parenthesis, giving the final encoding of character number four as (⍴⍬⍬⍬⍬).
These numbers are then looked up in ⎕AV which is the character set, and ⍎ executes the resulting string.
(At first sight it looks like the score could be brought to 9 by using ⎕UCS instead of ⎕AV and saving [], but that doesn't work, because (⍴⍬)(⍴⍬)  is a list of lists of scalars, i.e [[1], [1]] instead of the [1, 1] that would be required, and working around that would require interspersing the encoded values with commas, bringing the score back up to 10.)

Lenguage, score 1
The program consists of \$1{,}517{,}807\$ of any characters. These can be any characters you want, as Lenguage only depends on the length of a program. This does not break rule 1 as all characters are significant in Lenguage because of this fact.
This is one of the extremely few useful Lenguage programs that fits into the observable universe. Here is one of the \$1{,}114{,}112^{1{,}517{,}807}\$ possible Lenguage self-encoders.
Explanation
Lenguage starts by calculating the program's length and converting it to binary. 1517807 in binary is 101110010100011101111. Next, it left-pads that number with zeros until the length of that number is a multiple of three. The length of 101110010100011101111 is 21, which is already a multiple of three, so we don't need to worry about this. After that, it splits it into chunks of three. This becomes 101 110 010 100 011 101 111. Finally, it is translated to BF using this simple table:

BF
Translated Lenguage

+
000

-
001

>
010

<
011

.
100

,
101

[
110

]
111

And then evaluated as BF code. Here, 101 110 010 100 011 101 111 becomes ,[>.<,]. Here's what it does:
,[>.<,]  # full program
,        # input* to current cell
 [    ]  # while current cell is nonzero...
  >      # move pointer right
   .     # output current cell as a char
    <    # move pointer left
     ,   # input to current cell

This outputs a null byte for every character inputted. This doesn't change the execution of the inputted program since, as I said, the program is only dependant on the length of the program. Why a null byte, you ask? Because the tape initially starts out filled with zeros, and it's easier to just output the null byte that can already be output from the second cell than to set the second cell to some other value and output that every time. If you don't understand, here's an example:
Say the input is \$23{,}855\$ $s. This is one of the many variations of a cat program in Lenguage. It decodes to ,[.,], which is the standard BF cat. Here's the tape through each command:

36
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
…

^

,

36
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
…

^

[>
.

36
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
…

^

<,]

etc.
As you can see, each . command ends up on a 0, outputting a null byte for each character inputted.
*This program assumes that EOF is a null byte.

RProgN, 7 Distinct Characters, Noncompeting
RProgN is newer than this question.
' do.Lc
Convert the program to 'oooo...' L c 'ooooo...' L c 'oo...' L c . . . do, where each 'oo...' represents the character code in o's, surrounded by apostrifies to make a string out of them. L c then turns them into a number constant. After all the strings are placed on the stack, a chain of .'s equal to the amount of characters in the encoded string minus one rebuild the encoded string, and do executes it.
Encoder, also written in RProgN.
'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo' L c 'ooooooooooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooo' L c 'oooooooooooooooooooooooooooooooooooooooooooooo' L c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . do

Try it online!

Ruby -> Ruby, 8
#Convert a number from 0 to 255 to the form "111+11+11+1+1+1"
def byte_to_ones(byte)
  output = []
  ones = [111,11,1]
  ones.each do |one|
    while byte>=one
      byte-=one
      output<<one
    end
  end
  output.join('+')
end

bytes = $<.each_byte.map { |byte| byte_to_ones(byte) }

puts "eval''<<#{bytes.join('<<')}"

Sample:
puts "Hello, world!" => eval''<<111+1<<111+1+1+1+1+1+1<<111+1+1+1+1+1<<111+1+1+1+1<<11+11+1+1+1+1+1+1+1+1+1+1<<11+11+11+1<<11+11+11+11+11+11+1+1+1+1+1+1<<11+11+11+11+11+11+11+11+11+1+1<<11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1<<11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1<<111<<11+11+11+11<<11+11+1+1+1+1+1+1+1+1+1+1<<111+1+1+1+1+1+1+1+1<<111<<111+1+1+1<<11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1<<11+11+11+11+11+11+11+11+11+1<<11+11+11<<11+11+11+1<<1+1+1+1+1+1+1+1+1+1

Implements the Ruby solution given in the linked problem and replaces I/O with eval.

It was already linked in the question body; I wasn't using your comment. It's non-trivial to port answers over from there since you need to reverse-engineer them.

I missed the reference to that question in the question body. I still don't think it's very interesting to just transform answers from it, but I withdraw my previous comment with apologies.

05AB1E, 8 4 distinct bytes
[„)\ìNú₅ö©g₅Qi®ƒ„.g}¤…B.VJ?q

No TIO of the actual program, since the output would be way too big. It basically encodes the input-program into a program using the approach I've also used in the Fewest (distinct) characters for Turing Completeness challenge.
Try it online (with ƒ„.g}¤…B.V replaced with "D>gB.V" so we push the number instead of that many .g or try it online (with ® replaced with 9 as an example).
Explanation:
[                            # Start an infinite loop:
 „)\ì                        #  Prepend ")\" in front of the (implicit) input
     Nú                      #  Pad it with the loop-index amount of leading spaces
       ₅ö                    #  Convert it from a base-255 string to a number
         ©                   #  Store this number in variable `®` (without popping)
          g₅Qi               #  If the length of this number is 255:
              ®ƒ„.g}         #   Push `®` + 1 amount of ".g" to the stack
                    ¤        #   Tail (without popping): pushes "g"
                     …B.V    #   Push "B.V"
                         J   #   Join the stack together
                          ?  #   Output it without trailing newline
                           q #   And stop the program

This will produce a program with the 4 distinct bytes .gBV in the following format:
Loads and loads of .g to push a huge number. Then one additional .g+g to push 255, followed by B.V.

Loads of .g: Push the amount of items on the stack, which will become one larger every time, where only the last two are relevant
g: Pop the top number, and push its length (which will always be 255)
B: Convert the large number to base-255, resulting in the original input-program with prepended )\, to clean the stack from all the numbers we've pushed with .g () wraps the entire stack into a list and \ discards it)
.V: Execute it as 05AB1E code

Try such a program for Aû (with the many .g replaced with a huge number plus additional D>). Aû will push the lowercase alphabet & palindromizes it.

Knight, score 5 4
AE+1
Using the ASCII function, we can assemble arbitrary strings using +A(whitespace)1. However, since we know that all Knight programs will always be printable ASCII, tab, CR, or LF, we can always assume codepoints will be >= 9.
Therefore, to avoid whitespace, we can use EVAL.
+ can be used to both concatenate strings and do addition, A converts an integer to a string with its ASCII value, and 1 is used to add a bunch of 1's together to get any non-zero integer (strings with null bytes are illegal in Knight).
For example, if we wanted a string with a tab (ASCII 9) followed by a newline (ASCII 10) we would do this:
+A++++++++E1E1E1E1E1E1E1E1E1A+++++++++E1E1E1E1E1E1E1E1E1E1

Now, we can simply encode a Knight program using this method and evaluate it with E.
Here is the conversion program in Knight. It adds a leading newline and leaves out the trailing newline, but otherwise encodes a functionally equivalent program.
This could be further optimized if we used 111 and 11, but this isn't code-golf despite the question being tagged it...
# start with empty string
; = acc ""
# slurp the entirety of stdin and concatenate with newlines
; WHILE(= tmp PROMPT)
    : = acc + + acc ASCII(10) tmp
# First output the E to evaluate the next expression
# note: #"# is just to fix syntax highlighting
; OUTPUT("E\") #"#
# Now output length - 1 `+`'s to build the string one ASCII at a time
; OUTPUT(+ * "+" (- LENGTH(acc) 1) "\") #"#
# Now loop through the string
: WHILE(acc)
    # Grab the ASCII value of the first character in acc
    ; = char ASCII(acc)
    # snip off the first character of acc
    ; = acc SUBSTITUTE(acc 0 1 "")
    # output the ASCII keyword
    ; OUTPUT("A\") #"#
    # output n - 1 pluses
    ; OUTPUT(+* "+" (- char 1) "\") #"#
    # output n ones
    : OUTPUT(+*"E1" char "\") #"#

Julia 0.7, score 12
function f(a)
    u = unique("eval(parse(-*))")
    d = Dict{Union{Char,Int},String}(u .=> repr.(u))

    while a ⊈ keys(d)
        d2 = empty(d)
        for (k1,v1) in d
            for (k2,v2) in d
                try
                    d2[k1-k2] = "($v1-$v2)"
                catch
                end
            end
        end
        merge!((x,y)->x,d,d2)
    end

    if length(a) == 1
        return "eval(parse(*($(d[a[1]]))))"
    elseif length(a) > 1
        return "eval(parse(" * join(getindex.([d],[a...]),'*') * "))"
    else
        return ""
    end
end

print(f(read(stdin,String)))

Try it online!

the 12 used characters are eval(prs-*')

parse("string") parses a string into an expression (AST)

eval evaluates an expression

we use character arithmetic to compute any character ('b'-'a'==1, 'b'-1=='a')

characters are combined into a string with multiplication ('a'*'b'=="ab")

d stores every character and number for which we have found a representation with the allowed characters

every combination of d[k1]-d[k2] is computed and added to d until all the  characters of the input are found

in Julia 1.x, parse is replaced with Meta.parse, which would add 3 to the score

there is a warning in stderr due to the usage of parse instead of Meta.parse, which can be disabled with --depwarn=no if it is a problem for this challenge

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


text:
ASCII-visualize a graph
Your mission, should you choose to accept it, is to input a series of point pairs that form a graph, like this:

A,B C,A B,A A,D A,E F,G C,G

You must then output an ASCII visualization of the graph.
For example, A,B C,A C,D could be:
A-----------------B
 \
  \
   C---------D

Edit: As per the comments, here are some input constraints:

each node has at most 5 connections (+20 if you can handle more)
the graph is planar, i.e. no lines cross (+200 if you can handle even one crossover!)
there are at most 16 nodes (+20 if you can handle more)

Your score is 999 - (your code length) + (any bonuses).
Start your engines :)

code-golf, code-challenge, or what ? And what is/are the winning criterion/criteria ?

code-golf /10char

Is the graph guaranteed to be planar? Is the ASCII representation required to be planar? (If so, this is quite a challenging task).

@PeterTaylor Could you explain what you mean by "planar"?

@SohamChowdhury: Planar means it can be drawn without crossing lines.

This is an extremely broad and hard challenge at the moment. Tools such as graphviz and http://search.cpan.org/~tels/Devel-Graph-0.12/lib/Devel/Graph.pm have been designed for this kind of job. I also tried doing something similar in the past but failed. Extra rules that the graph is planar and nodes have at most 4 connections would make this a much more sensible code golf challenge.

As the question stands although I think there are still some problems (you can get all the bonuses coding special cases), the problem is interesting and valid.

Python 3, 168 chars, Score = 999- 168 + 240 = 1071
Just shortening Keith Randalls great answer.

In Python 3, print is a function, and therefore can be abbreviated by p=print. Saves 3 * (4 - 1) - 8 = 1 character.
In Python 3, input is used instead of raw_input, saves 4 characters.
Instead of ' '*len(V) you can use ' '*80 (or something similar). This leads to an increased number of trailing spaces, but who cares... if it saves another 4 characers!
Now it gets interesting: Instead of strings, use lists! This makes the updating of S much easier, but complicates printing somewhat. I'll call the list T so I'll not confuse it with the string S from marinus.
Let's start by turning the vertices into a list, not a space-seperated string, which saves 4 characters. The output line T has to become a list (T=[' ']*40), which costs 2 characters.
The printing of the current line T becomes 5 characters longer: I need brackets to concatenate the lists of strings correctly, I need two more - characters (because x and y are only about half as large now), and I need a * to make the print function take the elements of the list as seperate arguments and print them out seperated by spaces (and not as a list!). (This step was hard.)
The current line can be updated with a simple T[x]=T[y]="|" instead of S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:], which saves 19 characters.
For printing T again, and for the final spaced printing of the vertices, asterisks are needed, which costs 2 characters.
And just while I am typing this, I see that there is no harm in having an unconnected invisible vertex (' '). This allows to create the set of vertices much shorter, saving 4 more characters.

Altogether, the saving is 1 + 4 + 4 + 4 - 2 - 5 + 19 - 2 + 4 = 27.
R=input()
p=print
V=list(set(R)-{','})
T=[' ']*40
for e in R.split():x,y=sorted(map(V.index,e[::2]));p(*T[:x]+["+"+"--"*(y-x-1)+"-+"]+T[y+1:]);T[x]=T[y]="|";p(*T)
p(*V)

Example showing the effect of 9.: input A,B A,C leads to output
+-----+
|     |
+---+ |
|   | |
A   C B

I originally had S and T as lists, but in python 2 you need the ''.join() garbage which made it longer.  I didn't know that *T thing existed in python3.  Next golf...

APL (171 166 162 chars, all bonuses: 999 - 171 166 162  + 20 + 20 + 200 = 1068 1073 1077)
This is the longest golfed APL program I've written so far. This might be slightly cheating, but there's nothing in the question that actually disallows this. What I'm doing is putting all the nodes on a vertical line and drawing the graph as an arc diagram. It is obviously still a graph though.
It still took me a few hours.
V←' '⍴⍨99,⍨2×⍴P←∪,C←(2,⍨2÷⍨⍴G)⍴G←G/⍨⎕A∊⍨G←⍞⋄V[2×⍳⍴P;50]←P⋄M←1⋄G←⍴D←{⍵[⍋⍵]}¨↓P⍳C⋄{V[A B←⍵;L←50+M×⌽⍳G]∘←'-'⋄V[A+⍳B-A;⊃L]∘←'|'⋄V[⍵;⊃L]∘←'+'⋄M×←¯1⋄G-←1}¨2×D[⍒|-/↑D]⋄V

The nodes must be single uppercase letters, so it supports 26 nodes maximum. It can handle crossed lines, and each node can have as many connections as the display will handle.
Example output:
A,B C,A C,D

      +-A--+
      |    |
      +-B  |
           |
        C+-+
         |
        D+

A,B C,A B,A A,D A,E F,G C,G

          +--A-+-+-+
          |    | | |
          |  B-+ | |
          |      | |
        +-+--C   | |
        |        | |
        |    D---+ |
        |          |
        |    E-----+
        |
        |   +F
        |   |
        +---+G

 T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S

               +---+----------T
               |   |
               |   +-------+--H
               |           |
               |           +--E---------+-------+
               |                        |       |
               |              Q---------+       |
               |                                |
               |     +--------U---------------+ |
               |     |                        | |
               |     +--------I               | |
               |                              | |
               |              C-------+       | |
               |                      |       | |
               |              K-------+       | |
               |                              | |
               |       +------B               | |
               |       |                      | |
               +-------+------R               | |
                                              | |
             +----------------O-----+-----+-+ | |
             |                      |     | | | |
             |                W-----+     | | | |
             |                            | | | |
             |           +----N           | | | |
             |           |                | | | |
             |           +----F           | | | |
             |                            | | | |
             |                X-----------+ | | |
             |                              | | |
             |                J-------------|-+ |
             |                              |   |
             |                M---+         |   |
             |                    |         |   |
             |                P---+         |   |
             |                              |   |
             |   +------------S-------------+   |
             |   |                              |
             |   |            V-----------------+
             |   |
             |   |            L-+
             |   |              |
             |   |            A-+
             |   |
             |   |           +Z
             |   |           |
             |   |           +Y
             |   |
             +---|------------D
                 |
                 +------------G

That's roughly what I was thinking of doing (and may yet do). Only obvious short way of handling it.

It's a mystery to me how people write APL. +1

how on earth....

Python, 195 chars, score = 999 - 195 + 20 + 200 + 20 = 1044
R=raw_input()
V=' '.join(set(R)-set(' ,'))
S=' '*len(V)
for e in R.split():x,y=sorted(map(V.index,e[::2]));print S[:x]+'+'+'-'*(y-x-1)+'+'+S[y+1:];S=S[:x]+'|'+S[x+1:y]+'|'+S[y+1:];print S
print V

Each edge gets a row.  S is a string with the vertical connections we need to keep as we build the graph.
Here are some sample input/output:
A,B C,A B,A A,D A,E F,G C,G
+---+
|   |
+-+ |
| | |
+---+
| | |
+-------+
| | |   |
+-----+ |
| | | | |
| | | | | +-+
| | | | | | |
| +-------+ |
| | | | | | |
A C B E D G F

and stolen from marinus:
T,H E,Q U,I C,K B,R O,W N,F O,X J,U M,P S,O V,E R,T H,E L,A Z,Y D,O G,S
                +-----------------------+
                |                       |
      +-----------------------+         |
      |         |             |         |
      |       +-----------------------+ |
      |       | |             |       | |
  +---------------+           |       | |
  |   |       | | |           |       | |
  | +-------------------------------+ | |
  | | |       | | |           |     | | |
  | | |       | | |       +---------------+
  | | |       | | |       |   |     | | | |
  | | |     +---------------+ |     | | | |
  | | |     | | | |       | | |     | | | |
  | | |     | | | |       +---------------------+
  | | |     | | | |       | | |     | | | |     |
  | | |     | | | | +-----------------+ | |     |
  | | |     | | | | |     | | |     | | | |     |
  | | |     | | | | | +---------+   | | | |     |
  | | |     | | | | | |   | | | |   | | | |     |
  | | |     | | | | | |   +-------+ | | | |     |
  | | |     | | | | | |   | | | | | | | | |     |
  | | +-------------------------------------+   |
  | | |     | | | | | |   | | | | | | | | | |   |
  | | |     | | | | | |   | | | | | +---+ | |   |
  | | |     | | | | | |   | | | | | | | | | |   |
  | | +---------+ | | |   | | | | | | | | | |   |
  | | |     | | | | | |   | | | | | | | | | |   |
+-----------------------+ | | | | | | | | | |   |
| | | |     | | | | | | | | | | | | | | | | |   |
| | | |     | | | | | | | | | | | | | | | | | +---+
| | | |     | | | | | | | | | | | | | | | | | | | |
| | | | +-----------------+ | | | | | | | | | | | |
| | | | |   | | | | | | | | | | | | | | | | | | | |
| | | | | +-----------------------+ | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | |
A C B E D G F I H K J M L O N Q P S R U T W V Y X Z


text:
Find real roots of a polynomial
Write a self-contained program which when given a polynomial and a bound will find all real roots of that polynomial to an absolute error not exceeding the bound.
Constraints
I know that Mathematica and probably some other languages have a one-symbol solution, and that's boring, so you should stick to primitive operations (addition, subtraction, multiplication, division).
There is certain flexibility on the input and output formats. You may take input via stdin or command-line arguments in any reasonable format. You may allow floating point or require that some representation of rational numbers be used. You may take the bound or the reciprocal of the bound, and if you're using floating point you may assume that the bound will not be less than 2 ulp. The polynomial should be expressed as a list of monomial coefficients, but it may be big- or little-endian.
You must be able to justify why your program will always work (modulo numerical issues), although it's not necessary to supply full proofs inline.
The program must handle polynomials with repeated roots.
Example
x^2 - 2 = 0 (error bound 0.01)

Input could be e.g.
-2 0 1 0.01
100 1 0 -2
1/100 ; x^2-2

Output could be e.g.
-1.41 1.42

but not
-1.40 1.40

as that has absolute errors of about 0.014...
Test cases
Simple:
x^2 - 2 = 0 (error bound 0.01)

x^4 + 0.81 x^2 - 0.47 x + 0.06 (error bound 10^-6)

Multiple root:
x^4 - 8 x^3 + 18 x^2 - 27 (error bound 10^-6)

Wilkinson's polynomial:
x^20 - 210 x^19 + 20615 x^18 - 1256850 x^17 + 53327946 x^16 -1672280820 x^15 +
    40171771630 x^14 - 756111184500 x^13 + 11310276995381 x^12 - 135585182899530 x^11 +
    1307535010540395 x^10 - 10142299865511450 x^9 + 63030812099294896 x^8 -
    311333643161390640 x^7 + 1206647803780373360 x^6 -3599979517947607200 x^5 +
    8037811822645051776 x^4 - 12870931245150988800 x^3 + 13803759753640704000 x^2 -
    8752948036761600000 x + 2432902008176640000  (error bound 2^-32)

NB This question was in the Sandbox for approximately 3 months. If you think it needed improving before posting, visit the Sandbox and comment on the other proposed questions before they are posted on Main.

"You must be able to justify why your program will always work" Just in case someone needs help with that

@belisarius, ??

was intended as a joke :(

I know this is an old challenge, so don't feel obliged to answer if you don't feel like reopening it.
(a) Can we write a function, or only a full program?
(b) In case we can write a function, can we assume that the input uses some convenient data type, e.g., Python's fractions.Fraction (a rational type)?
(c) Do we have to handle polynomials of degree <1?
(d) Can we assume that the leading coefficient is 1?

(e) With regard to polynomials with repeated roots, it's worth making a distinction between roots of odd and even multiplicities (the test cases only have roots of odd multiplicities.)
While roots of odd multiplicity are not too hard to deal with, I'm not sure how tangible it is to correctly handle roots of even multiplicity numerically, especially since you only specify an error margin for the values of the roots, not for their existence. (...)

(...) Since roots of even multiplicity only do a "touch and go" with the x-axis, if p is a polynomial with a root r of even multiplicity, then p + c has a different number of roots, for an arbitrarily small constant c (either r disappears, or it turns into two roots); so, to reliably determine if there's even a root at r, we pretty much have to pinpoint it.
I think numerical solutions can only be more, or less, biased toward assuming there is, or there isn't, a root there, within some range of error.

@Ell, a) Full program. c) No, since they either have 0 roots or an infinite number. d) No, although it's a good point that I'm missing test cases. e) This might be a strong push towards using rationals rather than floating point, at least for an initial step of reduction to square-free polynomials.

My 100 point bounty was just thrown away. Wonderful.

Mathematica, 223
r[p_,t_]:=Module[{l},l=Exponent[p[x],x];Re@Select[NestWhile[Table[#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}],{i,l}]&,Table[(0.9+0.1*I)^i,{i,l}],2*Max[Table[Abs[#1[[i]]-#2[[i]]],{i,l}]]>t&,2],Abs[Im[#]]<t^.5&]]

This solution implements the Durand–Kerner method for solving polynomials. Note that this is not a complete solution (as will be shown below) because I cannot yet handle Wilkinson's Polynomial to the specified precision. First an explanation of what I'm doing:

#[[i]]-p[#[[i]]]/Product[If[i!=j,#[[i]]-#[[j]],1],{j,l}]&:
Thus function computes for each index i the next Durand-Kerner approximation. Then this line is encapsulated in a Table and applied using a NestWhile to the input points generated by Table[(0.9+0.1*I)^i,{i,l}]. The condition on the NestWhile is that the max change (over all terms) from one iteration to the next is greater than the specified precision. When all terms have changed less than this, the NestWhile ends and Re@Select removes the zeros that do not fall on the real line.
Example output:
> p[x_] := x^2 - 2
> r[p, .01]
{1.41421, -1.41421}

> p[x_] := x^4 - 8 x^3 + 18 x^2 - 27
> r[p, 10^-6]
{2.99999, 3., 3.00001, -1.}

> p[x_] := x^20 - 210 x^19 + ... + 2432902008176640000 (Wilkinson's)
> Sort[r[p, 2^-32]]
{1., 2., 3., 4., 5., 6., 7.00001, 7.99994, 9.00018, 10.0002, 11.0007, \
11.9809, 13.0043, 14.0227, 14.9878, 16.0158, 16.9959, 17.9992, \
19.0001, 20.}

As you can probably see, when the degree grows higher this method begins to bounce around the correct values, never really homing in completely. If I set the stopping condition of my code to be anything stricter than "from one iteration to next the guesses changed by no more than epsilon" then the algorithm never stops. I guess I should just use Durand-Kerner as input to Newton's method?

Durand-Kerner also has potential problems with multiple roots. (Newton's method might not help much either - Wilkinson's polynomial is specifically chosen to be ill-conditioned).

You are quite correct: I abandoned that course of action after zooming on on Wilkinson's near x=17, it's an absolute mess. I worry that I'll have to go for a symbolic solution with a Groebner basis to get much more accuracy.