text:
Solve Aristotle's Number Problem
Aristotle's number puzzle is the challenge of populating each of 19 cells in a hexagonal grid with a unique integer between 1 and 19 such that the total along every axis is 38.
You can picture the game board looking like this:

And the puzzle, in essence, is the solution to the following set of fifteen equations:
((a + b + c) == 38 && (d + e + f + g) == 38 && (h + i + j + k + l) ==
   38 && (m + n + o + p) == 38 && (q + r + s) == 38 && (a + d + h) ==
   38 && (b + e + i + m) == 38 && (c + f + j + n + q) ==
   38 && (g + k + o + r) == 38 && (l + p + s) == 38 && (c + g + l) ==
   38 && (b + f + k + p) == 38 && (a + e + j + o + s) ==
   38 && (d + i + n + r) == 38 && (h + m + q) == 38)

Where each variable is a unique number in the set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}.
There are multiple possible solutions, and are 19! possible combinations of integers, so naive brute force will be impractical.
Rules:

No hardcoding the answer or looking up the answer elsewhere; your code needs to find it on its own
Speed doesn't matter, but you do have to show your results, so code that takes 1000 years to run won't help you
Find all the answers
Treat answers that are identical under rotation as identical
Deduct 5% of your total byte count if you output the results in an attractive honeycomb
Fewest bytes wins

Great question, looking forward to working a solution to it.

Do you consider rotated answers as unique? E.g. let's assume a, b, c = 1, 18, 19 indexes a particular solution, if we set c, g, l = 1, 18, 19 and all other values are "rotated" to match, do you consider this a unique solution?

@ProgrammerDan Rotated answers are identical. I will clarify.

A hexagon has more symmetries than just rotations. What about answers which are identical under a combination of rotaation and reflection?

Interested to see a solution to this one using self-organising maps.

possible duplicate of Code Solution for the Magic Hexagon

@PeterTaylor Might be self-serving, as this question does appear to be a close duplicate, but I believe this is much better described and has a better "win" condition, and other features that highlight it as a better question, and as such should remain open.

Wondering why an answer with a higher byte count was accepted for code-golf?

@bazzargh That answer must not have been there when I gave the checkmark, or it was subsequently improved. Or I missed it. Anyway, fixed it now.

Haskell 295 289
import Data.List
t=38
y a b=[max(19-b)(a+1)..19]
w=y 0 t
x=filter((==w).sort)$[[a,b,c,d,e,f,g,h,i,t-a-e-o-s,k,l,m,t-d-i-r,o,p,q,r,s]|a<-[1..14],c<-y a a,l<-y a c,s<-y a l,q<-y a s,h<-y c q,e<-w,let{f=t-g-e-d;i=t-b-e-m;o=t-r-k-g;k=t-p-f-b;b=t-a-c;g=t-l-c;p=t-l-s;r=t-q-s;m=t-q-h;d=t-a-h}]

Another similar answer, using arithmetic to get the intermediate hexes. Unlike the other solutions, I don't test for those sums being > 0, testing that the sorted hexes are equal to the range [1..19] is enough. a, c and h are restricted so that only uniquely rotated/mirrored solutions are allowed. The solution appears after a few seconds, then there's a wait of a minute or so while it decides there's no more.
Usage in ghci:
ghci> x
[[3,19,16,17,7,2,12,18,1,5,4,10,11,6,8,13,9,14,15]]

Edited to shave a few chars. 'y 0 t' produces [1..19].

Actually I'm doing the same thing in my C answer :) damn how could I not see that Haskell is the perfect tool for the job :P +1

I get to miss out your x>0 check, because I sort the list including negatives instead of incrementing an array? On the other hand, I have to restrict the ranges (my y a b) to get Haskell to perform, which costs me a few chars. But there's bound to be another language that has built-in sort that'll beat me working the same way (looking at you, Mathematica).

Yes, sorting in C unfortunately is not as simple as in Haskell. The problem with Mathematica is that it's not compiled and thus so damn slow :(

I always do these in Haskell for practice, even if another language would be better.

I actually program Haskell as a side job, so I'm stumped at that it didn't even occur to me to use it here :D It's a really great language, even in the real/impure world

Java (1517 - 75.85) = 1441.15 (1429 - 71.45) = 1357.55 (1325 - 66.25) = 1258.75
This was fun.
Prints all unique solutions w.r.t. mirroring and rotation, in a pleasant honeycomb (hence 5% reduction)
Runtime: ~0.122s (122 milliseconds) on my 4 year old laptop.
Golfed code (edit realized I was stupidly repeating my printfs, reduced them to a single printf for maximum golf) (new edit Reduced calls to Set functions into clever smaller functions, some other micro-optimizations):
import java.util.*;class A{boolean c(Set<Integer>u,int z){return!u.contains(z);}Set<Integer>b(Set<Integer>c,int...v){Set<Integer>q=new HashSet<Integer>(c);for(int x:v)q.add(x);return q;}void w(){Set<Integer>U,t,u,v,w,y,z;int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,X,Z;X=20;Z=38;for(a=1;a<X;a++)for(b=1;b<X;b++)if(b!=a)for(c=1;c<X;c++)if(c!=a&&c!=b&&a+b+c==Z){U=b(new HashSet<Integer>(),a,b,c);for(d=1;d<X;d++)if(c(U,d))for(h=1;h<X;h++)if(h!=d&&c(U,h)&&a+d+h==Z){t=b(U,a,b,c,d,h);for(m=1;m<X;m++)if(c(t,m))for(q=1;q<X;q++)if(q!=m&&c(t,q)&&h+m+q==Z){u=b(t,m,q);for(r=1;r<X;r++)if(c(u,r))for(s=1;s<X;s++)if(s!=r&&c(u,s)&&q+r+s==Z){v=b(u,r,s);for(p=1;p<X;p++)if(c(v,p))for(l=1;l<X;l++)if(l!=p&&c(v,l)&&s+p+l==Z){w=b(v,p,l);for(g=1;g<X;g++)if(c(w,g)&&l+g+c==Z)for(e=1;e<X;e++)if(e!=g&&c(w,e))for(f=1;f<X;f++)if(f!=e&&f!=g&&c(w,f)&&d+e+f+g==Z){y=b(w,g,e,f);for(i=1;i<X;i++)if(c(y,i))for(n=1;n<X;n++)if(n!=i&&c(y,n)&&d+i+n+r==Z&&b+e+i+m==Z){z=b(y,i,n);for(o=1;o<X;o++)if(c(z,o))for(k=1;k<X;k++)if(k!=o&&c(z,k)&&m+n+o+p==Z&&r+o+k+g==Z&&b+f+k+p==Z)for(j=1;j<X;j++)if(c(z,j)&&j!=o&&j!=k&&a+e+j+o+s==Z&&c+f+j+n+q==Z&&h+i+j+k+l==Z){System.out.printf("%6d%4d%4d\n\n%4d%4d%4d%4d\n\n%2d%4d%4d%4d%4d\n\n%4d%4d%4d%4d\n\n%6d%4d%4d\n\n",a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s);return;}}}}}}}}}public static void main(String[]a){(new A()).w();}}

 Brute force is passe, but clever use of the fact that only a very small set of solutions exists led me to an iteration based answer, where within each loop of the iteration I only consider integers that have not been "assigned" yet. I make use of Java's HashSet to gain O(1) lookups for numbers that have been used previously. Finally, there are exactly 12 solutions, but when you discount both rotation and mirroring this reduces to just one unique solution, so when the first solution is encountered, I print it out and terminate. Check out my less-golfed code at github for a bit of a clearer view into how I am approaching this solution.

Enjoy!

Well, you lie in your spoiler, there are more different solutions, so your answer is invalid.

Strong claim, can you back it up with an answer of your own to prove it? I'm certainly not aware of any intentional lies in my spoiler.

so when the first solution is encountered, I print it out and terminate rule no. 3 tells tells to find all answers. There 19 as OP said, not sure if it is really 19, but I have run into similar task before, so know that there is more then one.

You need to read my entire spoiler. I found 12 solutions. Then you need to read the entire comments attached to the question. The OP says that answers that are equal w.r.t rotation are equivalent, and should be skipped. Another person asked if answers equal w.r.t mirroring should be skipped. Although the OP has to date not replied to this query, both my and all the other solutions to date assume the answer is "yes". Hence, my solution is fully complete, fully accurate, and there are no "lies" here. However, if you would like to see all 12 solutions, remove the return; statement.

Finally, this is code golf. Considering adding an arbitrary return; statement increases my code length by 7, it would be insane for me to add it if the true answer included all 12 solutions that are simply rotated/mirrored versions of each other. Although insanity cannot be ruled out, in this case, the addition of return; was intentional, and as I described, based on the the full question and comments dialog, which you should take care to review before tossing accusations. Thanks!

@ST3 That's just wrong, there are exactly 12 solutions and only one unique solution modulo reflection and rotation.

C, 366 bytes (C++ 541 450)
#define R(i)for(int i=19;i;--i)
#define X(x)if(x>0&&!V[x]++)
#define K(X)X(a)X(b)X(c)X(d)X(e)X(f)X(g)X(h)X(i)X(j)X(k)X(l)X(m)X(n)X(o)X(p)X(q)X(r)X(s)
Q(x){printf("%d ",x);}
T=38,V[99];main(){R(h)R(c)R(s)R(a)R(l)R(q)R(e){int d=T-a-h,b=T-a-c,g=T-c-l,p=T-l-s,r=T-q-s,m=T-h-q,f=T-g-e-d,i=T-b-e-m,n=T-d-i-r,o=T-p-n-m,k=T-g-o-r,j=T-h-i-k-l;R(C)V[C]=0;K(X)K(+Q),exit(0);}}

Compile with gcc -std=c99 -O3.
Prints all unique solutions modulo rotation and mirroring, in the format a b c d ..., one per line.
Runtime: 0.8 seconds on my computer.

 We enumerate the cells in the order h -> c -> s -> a -> l -> q -> e for maximum prunability. In fact the version above just tries every 20^7 assignments for those variables. Then we can compute all the other cells. There is only one unique solution modulo rotation/mirroring. An older, less golfed and ~20 times faster (due to pruning) C++ version can be found on Github

I love the largely arithmetic approach here. Bravo! +1

Matlab: 333 320 characters
This is a pretty dumb near-brute-force approach that doesn't use recursion. It builds up partial solutions in z, which is printed out at the end. Each column is a solution; elements are listed a-z from top to bottom. Runtime is 1-2 hours.
z=[];
a='abc adh hmq qrs spl lgc defg beim mnop dinr rokg pkfb hijkl aejos cfjnq';while a[k,a]=strtok(a);n=length(k);x=nchoosek(1:19,n)';s=[];for t=x(:,sum(x)==38)s=[s,perms(t)'];end
m=0.*s;m(19,:)=0;m(k(1:n)-96,:)=s(1:n,:);y=[];for p=m for w=z m=[];l=w.*p~=0;if p(l)==w(l) y(:,end+1)=w+p.*(~l);end
end
end
z=[m,y];end
z

Running from within Matlab:
>> aristotle;
>> z(:,1)

ans =

    9
   11
   18
   14
    6
    1
   17
   15
    8
    5
    7
    3
   13
    4
    2
   19
   10
   12
   16


text:
Transpose a 3x3 matrix across the anti-diagonal
Write a program which takes a 3x3 matrix on stdin and prints its transpose along the anti-diagonal to stdout. You may assume that all elements of the matrix will be integers. Columns are space-separated and rows are newline-separated.
Example
Input:
1 2 3
3 4 5
1 2 3

Output:
3 5 3
2 4 2
1 3 1

Input:
1 2 3
4 5 6
7 8 9

Output:
9 6 3
8 5 2
7 4 1

Your example output seems incorrect; it has only been transposed along the second diagonal.

Also, what are the matrix elements? Digits? Positive integers? Any integers? Floats? Any strings? If numbers, is there an upper limit?

@IlmariKaronen edited

So, you're effectively saying that the matrix should be transposed twice along the first diagonal (once in step 1, then again in step 2) as well as along the second diagonal (in step 2)? That's the only way I can make sense of your example output.

@IlmariKaronen well yes

Your first answer has a symmetry so it's easier to perform the transformation. My code works on this example but not on the second one.

What if the language of choice uses newline to mark end of input? Is [1 2 3; 3 4 5; 1 2 3] an acceptable input format?

APL - 7
⌽⍉⌽3 3⍴

Example input:
⌽⍉⌽3 3⍴1 2 3 3 4 5 1 2 9
> 9 5 3
  2 4 2
  1 3 1

ngn APL demo

Could the downvoter please explain themself? Thanks.

God love APL. Nice solution!

@mniip ANy chance you can explain how this works? It's so... concise! I love it!

3 3⍴ converts input to a 3x3 matrix. ⌽ reverses it along first dimension, ⍉ transposes it, and then ⌽ reverses it again.

Why do you need to include 3 3⍴? Let the program take a matrix as input. Also, this isn't a program or function, but rather just a snippet.

Function (4 bytes in Dyalog Unicode): ⌽∘⍉⌽, Full program (4): ⌽⍉⌽⎕, Full program (8, raveled input): ⌽⍉⌽3 3⍴⎕.

Mathematica, 31 28 20 bytes
(r=Reverse)[r@#]&

The  is Mathematica's transpose operator (which is displayed as a superscript T in Mathematica).

Sage, 39
Runs in the interactive prompt
matrix(input()[::-1]).transpose()[::-1]

Sample input:
[[1,2,3],[3,4,5],[1,2,3]]

Sample output:
[3 5 3]
[2 4 2]
[1 3 1]

GolfScript, 18 / 15 / 11 chars
~]-1%3/zip{' '*n}%

This is the straightforward implementation, following pretty much the exact steps given in the question.  There's a clever arithmetic trick one could use instead, but it turns out to need more characters.
Sample input:
1 2 3
3 4 5
1 2 9

Sample output:
9 5 3
2 4 2
1 3 1

Ps. If I can use the same output format as in ace's answer (i.e. extra with square brackets around each row), I can save three chars for a total of 15 chars:
~]-1%3/zip{`n}%

If a one-line output format like [[9 5 3] [2 4 2] [1 3 1]] is allowed, I can shrink that further to just 11 chars:
~]-1%3/zip`

If I understand your code correctly, I think you misinterpreted the question. For the matrix [[1,2,3],[4,5,6],[7,8,9]], your program should output [[9,6,3],[8,5,2],[7,4,1]], not [[3,6,9],[2,5,8],[1,4,7]].

@ace: Yeah, I noticed that. Stupid symmetric example. Fixed.

You may save one character in each of the first two cases if you include the newline in the map, e.g. {' '*n}%.

@Howard: Edited, thanks! That'll give me an extra blank line at the end of the output, but I suppose that's acceptable.

J - 16 (?) char
Taking the 3x3 matrix as a grid from stdin, we get the 16 character:
|:&.|.".1!:1]3#1

This can be made shorter if the input is made more flexible, as in the Sage and APL answers:
|:&.|.".1!:1]1   NB. if stdin input form can be  1 2 3, 4 5 6,: 7 8 9
|:&.|.           NB. if used as an expression like the APL answer

The key is in the |:&.|. portion: this is what transposes the matrix. It reads Transpose (|:) Under (&.) Reverse (|.), meaning you reverse the matrix, transpose it, and then undo your initial reverse.
Demo:
   |:&.|.".1!:1]3#1          NB. three lines input, three output
1 2 3
4 5 6
7 8 9
9 6 3
8 5 2
7 4 1

   1 2 3,3 4 5,:1 2 9        NB. a matrix
1 2 3
3 4 5
1 2 9
  |:&.|. 1 2 3,3 4 5,:1 2 9  NB. the logic
9 5 3
2 4 2
1 3 1

K, 3/7/20(?) bytes
K is similar enough to APL that a character-for-character transliteration of @mniip's solution works:
|+|3 3#

In action:
  |+|3 3#1 2 3 3 4 5 1 2 9
(9 5 3
 2 4 2
 1 3 1)

This behaves identically, modulo the way output is prettyprinted. However, I should note that neither this solution nor the solution it is based on actually operate on stdin/stdout. To implement this as per a stricter interpretation of the spec in Kona-compatible K3 it's necessary to use 0: and jump through some hoops:
`0:,/'2$|+|3 3#. 0:`

Write to stdout (`0:) the join over each (,/') of the two-wide string format (2$) of the anti-diagonal transpose (|+|) of the 3x3 reshape (3 3#) of the eval (.) of stdin (0:`).
In action:
indigo:kona je$ ./k antidiag.k
K Console - Enter \ for help

  1 2 3 3 4 5 1 2 9
 9 5 3
 2 4 2
 1 3 1

There's a pretty good reason that APL-family programmers tend to avoid problems that force the use of stdin/stdout. Arguably, with flexible IO requirements, this could be solved with simply |+|:
  |+|(1 2 3;3 4 5;1 2 9)
(9 5 3
 2 4 2
 1 3 1)

Vyxal, 4 bytes
RÞTR

Try it Online!
R    # Vectorised reverse
 ÞT  # Transpose
   R # Vectorised reverse

Brain-Flak -c, 2628 bytes
(()()()()){({}[()]<{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<>)<>>)}{}){{}(<(<()>)>)}{}}{}({}<>)<>>)}{}(<>({})<>){(({}))((()()()()()){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}(<>({})<>)({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<><>{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}{(({}))((()()()()()){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}{}{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<>)<>>)}{}){{}(<(<()>)>)}{}}{}<>{(({}))((()()()()()){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<>)<>>)}{}){{}(<(<()>)>)}{}}{}([(((()()())()){}{}){}]{}){(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}({}<>){(({}))((()()()()()){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>({}<>)<>(()()){({}[()]<{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<>)<>>)}{}){{}(<(<()>)>)}{}}{}({}<>)({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}<>{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>{(({}))((()()()()()){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<>)<>>)}{}){{}(<(<()>)>)}{}}{}({}<>)({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}<>([]){({}[()]<({}<>)<>>)}<>(()()()){({}[()]<{(({}))((((()()()()){}){}){})({}[{}])((){[()](<{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}){{}(<(<()>)>)}{}}{}({}<(([])<{{}({}<>)<>([])}{}<>>)<>>)<>{({}[()]<({}<>)<>>)}{}<>>)}{}

If it weren't for IO requirements this could have been 842 bytes but hey it was a good challenge :P I'm sure there's a lot that can be golfed here and I will see if I can find some of those spots later but right now I need to stop staring at brackets.
Try it online!

BQN, 3 bytes
⌽˘⌽

Try it online!
Explanation
⌽˘⌽
  ⌽ 1. Reverse over [leading axis][1]
⌽˘  2. Reverse over "major cells"

MATLAB, 15 bytes
Rotate the matrix 180 degrees, and transpose it. This takes the input where columns are space separated and rows are newline separated. Outputs on the same format.
@(A)rot90(A,2)'

ans([1 2 3
4 5 6
7 8 9])

ans =

     9     6     3
     8     5     2
     7     4     1

Racket, 42 bytes
(λ(m[r reverse])(r(apply map list(r m))))

Takes a list of lists of numbers as input, and outputs the same type.
Thought I might as well find a use case for some of the tips I'd written up some years ago!
Try it online!

Thunno, \$6\log_{256}(96)\approx\$ 4.94 bytes
.rZt.r

Attempt This Online!
.r reverses each row; Zt transposes; .r reverses each row.

Fortran (GFortran), 87 98 101 bytes
integer A(3,3);read*,((A(i,j),j=1,3),i=1,3);print'(3i3)',((A(4-i,4-j),i=1,3),j=1,3)
end

Try it online!
  98b
101bytes

JavaScript (Node.js), 83 97 bytes

-14 bytes thanks to @noodleman !

Input and output are the matrixes exactly in the string format specified by OP.

This surely is the shortest JS answer using this format!
s=>s.split(/\s/).map((e,i,a)=>a[i+(2-i%3-(i/3|0))*4]+(i%3<2?` `:i>6?``:`
`)).join``

Try it online!

Let me explain a bit:
First we split the input string on all whitespaces, which gives us a one-dimensional array.

Then, we switch each item with their corresponding targets by transforming the current value of the (one-dimensional) index this way:
i+(2-i%3-(i/3|0))*4.

And finally, we concatenate all the elements while adding the   and \n after the right items (but specifically not after the last item).

Replace the whole .split .join .split thing with .split(/\s/) to save 14 bytes: Try it online!

@noodleman Oh wow, thank you! I really should learn about regex, i never think about it!

Well since you don't know, \s matches any whitespace character.

R, 78
write.table(matrix(rev(unlist(strsplit(readLines(),' '),' ')),3),qu=F,r=F,c=F)
# Copy and paste the input
# If the prompt is not on a new line, press `enter` after the last line
# Type `Ctrl+D`

I discovered the rev() function on SO, it helped me to understand than the transformation is just reversing the input and putting it in the matrix from top to bottom, and left to right.
I also discovered that the argument row.names=T (T for true) can be shortened to r=T, saving 16 chars.
Explanations:

readLines() reads STDIN and return a vector with 3 elements (each one is a string)
strsplit() splits the strings in the vector by using space as a separator
unlist() makes a flat list from a vector
rev() puts the list in reverse order
matrix([list], 3) creates a matrix from the list, the argument 3 indicates that there is 3 elements per row
write.table([matrix], qu=F, r=F, c=F) prints the matrix without quotes, rows and columns labels

TI-BASIC, 50
Input A:rowSwap(A,1,dim(A
AnsT→A:rowSwap(A,1,dim(A

This will throw an error when you try to store a matrix to the real variable A.

In addition, it doesn't take input in the right format, which should be space-separated numbers.

CJam, 13 bytes
q~]W%3/zSf*N*

Test it here.
CJam is newer than this challenge. This solution is very similar to the GolfScript one.
Explanation
q~   e# Read input and evaluate, pushing all 9 numbers on the stack.
]    e# Wrap them in an array.
W%   e# Reverse it - this performs a 180° rotation.
3/   e# Split into rows of length 3.
z    e# Transpose.
Sf*  e# Join integers in each row with spaces.
N*   e# Join the rows with linefeeds.

If there was no constraint on 3x3 inputs, we could either compute the line width with a square root:
q~]W%_,mQ/zSf*N*

Or we could perform the anti-diagonal transpose as vertical flip, transpose, vertical flip (like my Mathematica answer does):
qN/Sf/W%zW%Sf*N*

In either case, we'd have 16 bytes.

R, 37 bytes
write(scan()[rep(9:7,e=3)-3*0:2],1,3)

Try it online!
Simply changes the order of the elements of the input vector.
Well, actually a basic approach is shorter:
R, 35 bytes
write(matrix(rev(scan()),3,,T),1,3)

Try it online!

05AB1E, 7 (or 3) bytes
|€#øRí»

Try it online.
With less strict I/O rules it would be 3 bytes instead, with I/O being a 3x3 matrix of integers:
øRí

Try it online.
Explanation:
         #  e.g. input = "1 2 3\n4 5 6\n7 8 9"
|        # Take all input-lines as a list of strings
         #  STACK: ["1 2 3","4 5 6","7 8 9"]
 €#      # Split each line by spaces
         #  STACK: [["1","2","3"],["4","5","6"],["7","8","9"]]
   ø     # Zip the matrix, swapping rows with columns
         #  STACK: [["1","4","7"],["2","5","8"],["3","6","9"]]
    R    # Reverse the order of rows in the matrix
         #  STACK: [["3","6","9"],["2","5","8"],["1","4","7"]]
     í   # Reverse each row of the matrix
         #  STACK: [["9","6","3"],["8","5","2"],["7","4","1"]]
      »  # Join each row by spaces, and then everything by newlines
         #  STACK: "9 6 3\n8 5 2\n7 4 1"
         # (after which it is output implicitly)

Here some alternatives with different order of operations:
øíR
Ríø
íRø
íøí
RøR

Jelly, 3 bytes
ṚZṚ

Try it online!
Uses Python list format for I/O.

Japt, 3 bytes
yÔÔ

Try it
yÔÔ     :Implicit input of 2D array
y       :Transpose
 Ô      :Reverse rows
  Ô     :Reverse array

Factor + math.matrices, 27 bytes
[ anti-flip simple-table. ]

anti-flip postdates build 1525, the one TIO uses, so here's a picture of running this in Factor's REPL:

Note that in a standard output context, simple-table. outputs its elements with spaces in between. In the REPL, it's a little fancier.

flax, 2 bytes
Ṙ∝

ATO doesn't have the lastest commit of flax (because I keep discovering bugs). So here is an image of it in action:

JavaScript, 103 bytes
Expects string input and outputs string
s=>(s=s.split`
`.map(x=>x.split` `))[0].map((_,c)=>s.map((_,r)=>s[2-r][2-c])).map(x=>x.join` `).join`
`

Try it:

f=s=>(s=s.split`
`.map(x=>x.split` `))[0].map((_,c)=>s.map((_,r)=>s[2-r][2-c])).map(x=>x.join` `).join`
`

;[
`1 2 3
3 4 5
1 2 3`,
`1 2 3
4 5 6
7 8 9`
].forEach(x=>console.log(f(x)))

JavaScript, 45 bytes
Expects 2D array input and outputs 2D array
m=>m[0].map((_,c)=>m.map((_,r)=>m[2-r][2-c]))

Try it:

f=m=>m[0].map((_,c)=>m.map((_,r)=>m[2-r][2-c]))

;[
  [
    [1, 2, 3],
    [3, 4, 5],
    [1, 2, 3]
  ],
  [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
  ]
].forEach(x=>console.log(JSON.stringify(f(x))))

source: Stack Exchange

license: 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/

sort: votes


text:
Format a US address
Your task is to format an address given in all lowercase to a friendlier format. Here's the catch, no regexes.
Addresses will be given in the following format:
123 serpentine pl ne shoreline wa 98199
The expected output is the following: (notice the period and commas)
123 Serpentine Pl. NE, Shoreline WA, 98199
Formatting Rules

Cardinal directions should be capitalized, e.g. "e" --> "E", "nw" -->
"NW".
Abbreviations for streets, avenues, etc. should have the first letter
capitalized with the abbr. followed by a period (".")  e.g "st" --> "St.", "ave" --> "Ave.".
State abbreviation should be in all caps
A comma is placed after each section. i.e. after the street address and state and city.
Capitalize the city and street/avenue/place.

EDIT:
Addresses will always be given in the above format except with or without a cardinal direction.
Your code should also be able to handle "st" and "ave". The input is given through stdin. This is code-golf so the shortest code in bytes wins.

Please provide an explanation of the formatting rules that should be used.  It's not at all obvious from your example why "ne" and "wa" should be fully capitalized and followed by commas, while "pl" should have only the first letter capitalized and be followed by a period.

@IlmariKaronen added rules.

Could you please provide a full list of st ave pl things?

Also, will addresses always have this form with all the components <number> <street> <st/ave/pl> <direction> <city> <state> <zip>? Or may parts be omitted (e.g. can the address not have a St/Ave/Pl postfix, or a cardinal direction).

The US Postal Service prefers no punctuation except for the hyphen in 9-digit zip codes and, all caps: http://pe.usps.gov/text/pub28/welcome.htm

How can Capitalize give NW, Caps give state abbreviation and Capitalize give Serpentine? Can you clarify that? Presumably there are streetnames with more than one element in addition to the description of the stree? And cities with more than one element? Can you include some examples?

There are a lot more possible ways to enter in the given addresses - and a lot more possible variations in addresses - than is covered here. For example: 123 Serpentine Place NE, Shoreline Washington 98199 or 123 Serpentine Pl NE, Apartment 6, Shoreline Wa 98199 or 123 Serpentine Pl, 98199. How do we handle those, or are we to only expect addresses strictly in the formats already given without any more or less detail?

1681 broadway new york ny 10036

Perl 6: ??? characters
The simplest Perl 6 solution is probably: (61 characters)
$/=get.wordcase.words;"$0 $1 $2. $3.uc(), $4 $5.uc(), $6".say

Unfortunately, I don't feel comfortable using this, since .wordcase and .words are both implemented internally using regexes. Thus: (also, oddly, 61 characters)
$/=get.split(' ')».tc;"$0 $1 $2. $3.uc(), $4 $5.uc(), $6".say

BUT this only handles the specific address given in the problem. Consider:
42 awesome ln dogeland hi 96899

I see this as valid under to be formatted given the rules above, and this should be formatted as 42 Awesome Ln., Dogeland HI, 96899 rather than 42 Awesome Ln. DOGELAND, Hi 96899,. So let's fix the case that a cardinal direction isn't included: (136 characters)
my@a=get.split(" ")».tc;@a[3].=uc if @a[3] eq tc any "n","s","" X~ "e","w","";@a[2]~=".";say "@a[0..*-4], @a[*-3] @a[*-2].uc(), @a[*-1]"

Lua - 462
_=_G d={n=_,nw=_,sw=_,s=_,se=_,e=_,ne=_,al=_,ak=_,az=_,ar=_,ca=_,co=_,ct=_,de=_,dc=_,fl=_,ga=_,hi=_,id=_,il=_,["in"]=_,ia=_,ks=_,ky=_,la=_,me=_,md=_,ma=_,mi=_,mn=_,ms=_,mo=_,mt=_,nv=_,nh=_,nj=_,nm=_,ny=_,nd=_,oh=_,ok=_,["or"]=_,pa=_,ri=_,sc=_,sd=_,tn=_,tx=_,ut=_,vt=_,va=_,wa=_,wv=_,wi=_,wy=_}l={pl=_,st=_,ave=_,hw=_}print((io.read"*a":gsub("%w+",function(x)if d[x]then return x:upper()..","end return x:sub(1,1):upper()..x:sub(2):lower()..(l[x]and"."or"")end)))

The first is a list of states and directions, the second is a list of places.
One might argue that gsub is using regular expressions, but lua uses patterns, that are close, but not exactly are regexes. They cannot match regular languages and don't even have a proper Klenee star.
Example:
 $ lua % <<< '123 serpentine pl ne shoreline wa 98199'
 123 Serpentine Pl. NE, Shoreline WA, 98199

Javascript
b="123 serpentine pl ne shoreline wa 98199".split(" ");
c=[];
cap = function(l){var code=parseInt(l.charCodeAt(0));if(code>=97&&code<=122){l=String.fromCharCode(code-32);}return l;}
c[0]=b[0];
c[6]=b[6];
b.forEach(function(txt,index){
 tx=txt.split("");
 switch(index){
     case 1:case 4:tx[0]=cap(tx[0]);c[index]=tx.join("");break;
     case 2:case 3:case 5:tx.forEach(function(t,idx){
            tx[idx]=cap(t);
        });
        c[index]=tx.join("");
        break;
      }
});

//now
output=c[0]+" "+c[1]+" "+c[2]+". "+c[3]+", "+c[4]+" "+c[5]+", "+c[6];

Python3 137 122
i=input().split()
c=lambda x:x.capitalize()
print(i[0],c(i[1]),c(i[2])+".",i[3].upper()+",",c(i[4]),i[5].upper()+",",i[6])

>python main.py
123 serpentine pl ne shoreline wa 98199  #Pasted
123 Serpentine Pl. NE, Shoreline WA, 98199  #Output
>

I think using input() would give you a lower char count (you don't need sys) and it would fit the rules better. ("The input is given through stdin.")

Python2
(based on other python3 answer)
i=raw_input().split()
i=map(lambda x:x.capitalize(),i)
print " ".join((i[0],i[1],i[2]+".",i[3].upper()+",",i[4] ,i[5].upper()+",",i[6]))

running in Windows cmd
C:\Python27>python main.py
123 serpentine pl ne shoreline wa 98199 #Pasted
123 Serpentine Pl. NE, Shoreline WA, 98199 #Output

Powershell v4
$h=Read-Host
$i=(Get-Culture).TextInfo.ToTitleCase($h).Split()
($i[0..2 ] -join " ")+". "+$i[-4].ToUpper()+", "+$i[-3]+" "+$i[-2].ToUpper()+",",$i[-1]

running
C:\>powershell .\address.ps1
123 serpentine pl ne shoreline wa 98199 #Pasted
123 Serpentine Pl. NE, Shoreline WA, 98199 #Output

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


text:
Kolmogorov-mania
The Kolmogorov complexity of a string s is defined as the length of the shortest program P that outputs s. If the length of P is shorter than the length of s, then s is said to be compressible, otherwise s is incompressible. Most strings are incompressible ...
Write the shortest program that outputs this string (without spaces and without newlines):
d9 a6 b6 33 56 a7 95 4b 29 b0 ac 7f 2a aa 6d 19 b8 4b 4c f8 b6 2a ac 95
a1 4b 4e a5 9d b3 e7 c9 4c 49 59 ec 94 b3 aa 6c 93 8f 11 5a 4d 39 75 82
ec ea 24 cc d3 2d c3 93 38 4e b7 a6 0d d2 b5 37 23 54 ad 1b 79 aa 6e 49
55 52 94 5a a7 3a 6a e9 e4 52 cd 2d 79 ad c6 12 b5 99 5b b4 76 51 17 4e
94 f3 9a a2 e7 15 6a 55 14 4d 4e 4a a3 5c 2f ab 63 cc b5 a6 a4 92 96 8a
2e c3 d8 88 9b 8c a9 16 f5 33 22 5b a2 e2 cc 1b 27 d4 e8 db 17 a4 39 85
ca aa 5b 4f 36 24 d3 c6 f6 94 ad d7 0f 71 24 e1 b1 c5 ef 65 35 6c 8d d7
1a 87 1e 25 df 5d c0 13 b2 6f 5a 57 28 98 bd 41 66 04 ed a2 52 c9 ac 83
b3 6c 56 7e d1 c6 cc 53 4a 62 c5 59 a9 b2 d4 af 22 a5 a9 f4 b2 99 23 32
f8 fb ae 48 6a 8a 9a b5 46 7a 36 59 9f 92 d3 25 b5 19 bd 8a 4a 49 62 a5
e4 59 fb e5 ba a2 35 dd a9 36 1d a9 c9 69 89 77 6a b2 34 2d 1d 22 61 c5
c2 66 1c e2 76 74 52 a5 d9 84 b9 8a a6 b5 14 ec 29 58 b2 bc 96 16 16 48
f5 c5 bd 2f 32 1b 3d 4f 4b 2e b2 6b 9a d9 32 a4 4b 5c bc 92 b7 b3 26 39
fa 42 2d 64 ed 1a 79 49 4c a3 b7 85 b2 a6 e2 8c d9 55 90 e1 a8 87 4b 60
a6 e1 ba c4 bb ec 32 39 76 90 a6 b4 c6 65 79 61 91 aa 3d 54 b7 18 3d 15
4b 06 db 30 8a 4d 4a a1 35 75 5d 3b d9 98 ac 55 5b 10 dd b3 e2 cc f1 5e
b3 2b 53 90 b6 ee 2b ac 8f 88 8d 95 5a 75 df 59 2d 1c 5a 4c e8 f4 ea 48
b9 56 de a0 92 91 a9 15 4c 55 d5 e9 3a 76 8e 04 ba e7 b2 aa e9 ab 2a d6
23 33 45 3d c4 e9 52 e3 6a 47 50 ba af e4 e5 91 a3 14 63 95 26 b3 8b 4c
bc aa 5a 92 7a ab ad a6 db 53 2e 97 06 6d ba 3a 66 49 4d 95 d7 65 c2 aa
c3 1a 92 93 3f ca c2 6c 2b 37 55 13 c9 88 4a 5c 62 6b a6 ae cc de 72 94

The output should look like:
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Note: no user input is allowed, nor web access, nor libraries (except the one required for printing the output).
Edit I: the sequence seems random ... but it turns out to be highly compressible handling a little bit of prime numbers ...
Edit II: Well done! I'll review the answers in the next hours, then assign the bounty.
This is my idea on how it could be solved:

If you try to compress the data you don't go far away ...
In internet you can find the (well-known?) On-Line Encyclopedia of Integer Sequences (OEIS) ;
trying the first hexadecimal digits d9, a6, b6, 33, ... (or their decimal representation) give no result;
but if you convert the numbers to binary (1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) and searching them on OEIS, you get this result.
As noted by Claudiu, I also gave a little hint in the question (Edit I above) ... :-)

The winner is: Peter Taylor (GolfScript, 50), with a special mention for Claudiu (Python, 92), the first who "solved" it.

How is this more interesting than other [tag:komogorov-complexity] questions?

@Doorknob: perhaps nothing ... at least until someone will post an answer :-)

Do I understand correctly we are allowed internet access?

@JanDvorak I think implicitly standard loopholes apply here. And for the asker: link this in the question

Note: googling the first few bytes finds nothing but this question.

Is this supposed to be a game of "Guess the constant"?

Funny thing...I can't copy+paste this string properly when all the spaces and newlines are removed

why this string in particular? is it random?

@xem presumable because it isn't very compressable...I can get it to 744 characters using gzdeflate

also, "shortest program", in bytes or in characters?

@xem: I assume 1 character = 1 byte.

This still seems like a hide-and-seek kind of challenge...."Do you see what I did there?" isn't really the same as code-golf

@DavidWilkins: do you suggest to reveal how to generate the sequence?

@MarzioDeBiasi wouldn't that change the challenge to "write this code shorter than I did" ?  I'm not sure what I'd recommend, other than using the meta sandbox (http://meta.codegolf.stackexchange.com/questions/1303/proposed-question-sandbox-mark-xi) to proof your challenge before posting it

The obvious standard tool is the inverse symbolic calculator, but that draws a complete blank for 0.8502000689828988668429023263735528272644799.

Don't give in the the peer pressure. This challenge has prompted me to learn something about cryptography. For that, I gave you an upvote.

Too bad you just changed the question... I had it in 139 with import re,urllib.request as r;print(re.split('</?code>',r.urlopen('http://codegolf.stackexchange.com/questions/24909').read().decode())[1])

@MathieuRodic: "no web access" was one of the first edit :-)

@Rusher: don't worry, even if I give the solution it can be interesting; however I think that this is not the right place for mind-juggling puzzles :-)

Don't give the solution! People are working on it :-)

Has anyone tried converting this number from Hex to Decimal, then calculating prime factors? It's a 1200 digit number, so it shouldn't be that difficult, it just requires a decent computer and an app which can handle such huge numbers.

@NateKerkhofs I'm more in the way of print f(prime[i])%255

I got the answer in 92 characters, but as soon as I post it the cat's out of the bag... what should I do? I could provide the sha-256 of the code and offer the code once an answer is accepted.

@Claudiu: yeah, I think you should post the hash and then wait a little. Maybe the OP can set a deadline!

I recommend a deadline as well

I have the answer in 98 characters in Python and 106 characters in Haskell. Should I still post them (well, their hashes) even though there's a shorter solution already?

@immibis: IMO you can post the Haskell one ... if you found "how to do it" you deserve some upvotes :-)

of course, if I only post the hash, there's no evidence that I didn't just post a random hex string

I think the contest should be in two parts. First part is a prize given to those who found the answer. Second part is a prize given to those who really know how to compress the code and generate the smallest. Right now, it's more of a "guess my algorithm" question, which excludes dullards like me, but also real code golfing pros, (which I'm not either), and those who know APL and the other terse languages (still not me).

@NateKerkhofs - Factoring only has a real benefit if you express the number as products of powers of primes with a substantial number of powers > 1. The number (which we'll call N) has a few small factors, but then ends up with a 1152 digit composite which is way beyond our current capabilities of about 220 digits. You can also express N as p(n1)p(n2)... with p the prime function and n the ordinal (e.g. first prime p(1) = 2, second prime p(2) = 3, nth prime p(n)). This will compress to log(N/ln(N)) characters which is actually not much smaller than log(N) characters, so minimal compression!

@immibis: True but what'd be the point of that? Some ill-gotten rep points? This is supposed to be for fun =)

Is base conversion included under "the [library] required for printing the output"?

@PeterTaylor: no, sorry. The only library function allowed is the one used to print the output.

That is what I was wondering. Using libraries (and interpreters for that matter) is code being used to generate output. It all has to be counted I think.

PS. looking at answers so far, and ignoring machine code and microcode, it could be argued that only language constructs can be allowed - no libraries can be used unless their source code is counted as well. So richer languages are at an advantage. Even better if your chosen language has a print statement that supports hashing - which just isn't cricket.

@what do you mean with "print statement that support hashing?"

@MarzioDeBiasi: Oh I didn't realize that I can't use base-conversion functions.. I use hex, for example, which is a built-in (I don't import anything), but I also use range and all, which are the same status (also built-in functions).. my program won't win anyway but should I technically not have used any of those?

@philcolbourn: Hashing has nothing to do with solving the problem. It's just a proof to avoid releasing the code prior to the end of the contest.

@Claudiu: Well hex isn't a "library function", it's just built-in. So I think you're ok.

@Claudiu I really misunderstood these answers then, didn't I. I read them as finding a small message that when hashed gave resulting long string. But have I misunderstood Kolmogorov complexity as well?

@MarzioDeBiasi - My error. I thought all these hash functions were part of answers so I thought that only way to not count hashing code was for some language to include it in print function. I feel a bit silly now.

It was that easy to find in OEIS?! Aaargh. I converted to indexes 0,1,3,4,7,8,10,13,14,..., tried simple linear transforms of that, tried working from the other end, tried inverting the mask (2,5,6,9,11,12,15,...) and finally found A138970... and then realised that my very first search on OEIS would have turned up A138971 if I'd omitted the 0.

@MarzioDeBiasi Now that you've picked the winner, you should click the green tick on Peter Taylor's solution.

@ChrisJester-Young: I accepted his answer; should I click on the +100, too or does the bounty automatically get assigend to the accepted answer?

GolfScript (50 bytes)
$ wc -c codegolf24909.min.gs
50 codegolf24909.min.gs
$ md5sum codegolf24909.min.gs
ce652060039fba071d17333a1199fd72  codegolf24909.min.gs
$ time golfscript.rb codegolf24909.min.gs
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

real    365m11.938s
user    364m45.620s
sys     0m6.520s

Since everyone else is now revealing their code, I will also pre-empt OP's request to unobfuscate:
38200,{:x,{)x\%!},,2=},4/{3\{2&!!1$++}/.57>39*+}%+

Overview dissection

Compute primes smaller than N with N=38200: this gives the first 4032 primes: 38200,{:x,{)x\%!},,2=},
We want one bit per prime, with a hex conversion, so split them into groups of 4: 4/
For each group, map each prime p to p&2 != 0, and do a base-2 to base-16 conversion: {3\{2&!!1$++}/.57>39*+}% (this is where the interesting tricks are)
We now have an array of ASCII values, plus the empty string from stdin; concatenate them to get a single string for output: +

More detailed dissection of the base conversion
Given a stack holding an empty string and a list of primes, we need to do two conversions:

Convert each prime to a bit indicating whether it's equal to 2 or 3 (mod 4)
Convert the bits into hex digits

There are lots of equally long ways to do 1; e.g.
{4%1>}%
{4%2/}%
{2/1&}%
{2/2%}%
{2&!!}%

or even
{2&}% followed by a 2/ after the base conversion

For 2, the obvious approach is
2base 16base{'0123456789abcdef'=}%+

But base is a long word, and since 16 = 24 we can easily save a few chars with
4/{2base'0123456789abcdef'=}%+

Now the most obvious waste is the 18 chars devoted to that string. We just want a function from digit to ASCII code.
We want to map 0 to '0' = 48, ..., 9 to '9' = 57, 10 to 'a' = 97, ... 15 to 'f' = 102.
4/{2base.9>39*+48+}%+

But now throw into the mix a ban on base. We need to implement it ourselves. The obvious implementation (in this direction, the easy one) is that k base is a fold {\k*+}*. The slightly longer alternative is a straightforward iteration, which needs a base case: 0\{\k*+}/. Base 2 is slightly special: 1$++ is equivalent to \2*+ for the same length, and I've taken that approach.
Both of those are longer than the 5-char 2base, but since we're now iterating over the values we can pull in part 1 to have a single loop. We replace
{2&!!}%4/{2base.9>39*+48+}%+

with
4/{{2&!!1$++}*.9>39*+48+}%+

for a nice 1-char saving, or
4/{0\{2&!!1$++}/.9>39*+48+}%+

for a 1-char loss.
But although that 1-char loss looks like a step backwards, consider what happens to that 0.
It's multiplied by 16 and added to the base-conversion output. And the final thing we do is to add a multiple of 16 to the output.
So we can combine the two as
4/{3\{2&!!1$++}/.57>39*+}%+

Joint shortest and the bonus cleverness makes it more interesting.

360 minutes! That's quite a while. Wonder what approach you took.. mine takes <1 min

@Claudiu, I could make it a lot faster, but it would add about 5 characters, and this is [tag:kolmogorov-complexity] rather than code-golf with time constraints.

How much could you get it down if you used base? All the other solutions use an equivalent (mine uses hex, the C one uses printf("%x"), haskell uses showHex)

@Claudiu, actually my current best approach with base is longer than this one, because I did most of the optimisation after clarifying that I couldn't use it. base gives me a value from 0 to 15, so it still needs some work to convert to 0-9a-f. I might revisit using base at some point, but not tonight.

Python, 92 characters
Here it is ladies and gentlemen, the code itself!
>>> code = "R=range;print hex(int(''.join(`i/2%2`for i in R(38198)if all(i%x for x in R(2,i))),2))[2:-1]"
>>> len(code)
92
>>> exec code
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294
>>> import hashlib; hashlib.sha256(code).hexdigest()
'60fa293bbe895f752dfe208b7b9e56cae4b0c8e4cdf7c5cf82bf7bab60af3db6'

Marzio left a clever hint by saying that "it turns out to be highly compressible handling a little bit of prime numbers". I was sure the "little bit" wasn't italicized by accident, so I converted the hex string to bits and tried to find patterns. I thought that at first he was representing all the primes as bits and concatenating them together, but that didn't work out. Then maybe taking only a few digits, or dropping all the zeroes in the bit string - still no. Maybe it's a bitstring of the least-significant-bit of the first few primes? Not quite. But eventually I found the one that worked - it's a bitstring of the second-least-significant bit from the first however-many primes.
So, my code does just that: generate just enough primes, take the second bit of each (i/2%2), concatenate them as a binary string, then convert it to base-10 (int(..., 2)) and then to base-16 (hex(...)).

Great! I'm new to code golf, but the hash stuff is a good way to let other people have fun in discovering "how to do it". I'll wait two days, then open a bounty (that I'll reward on trust :).

@MarzioDeBiasi: Sure that works! Or maybe better to say you'll reward it on the day before the bounty is due, and if the winner doesn't reveal his answer the 2nd in place wins, etc... why rely on trust when you don't have to?

Why has code in hashlib not been counted? Isn't it code being run to generate output?

@philcolbourn: No the code doesn't use hashlib. It's just to generate the sha256 hash so tomorrow I can prove I wrote the code when I first posted this. You will see tomorrow!

@Claudiu: Now you should explain me how did you crack the problem! Well done!

@rubik: Hehe sure, I added the story behind it.

C, 136 116 109 103 characters
OK then, here's my effort:
i;p;q;main(n){for(;n++,q<4032;){for(i=1;++i<n&&n%i;);if(i==n)p+=p+(n&2)/2,p=++q&3?p:printf("%x",p)*0;}}

MD5 hash = f638552ef987ca302d1b6ecbf0b50e66

Since printf returns the number of character written, which is always non-zero here, you can use !printf(...) instead of printf(...)*0 to save one char.

@ace *slaps forehead* Ah, why didn't I think of that?? Thanks ace, as always :-)  (May as well leave the code as it is, since it's supposed to match the MD5 hash.)

Haskell, 105
SHA1 hash: a24bb0f4f8538c911eee59dfc2d459194ccb969c
Output:
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

Edit: Code:
import Numeric;f(x:z)s=f[y|y<-z,0/=mod y x]$s*2+quot(mod x 4)2;f[]s=s;main=putStr$showHex(f[2..38198]0)""

I missed the rule about not using any library functions except for printing (putStr). I would assume that mathematical operators, while they're technically functions, are allowed.

JS, 764
if we consider this string as base64, we can have a smaller version using the un-base-64-ed version:
btoa("wÖºo÷ç¦»÷ÛÖôiÎßÙ¦éÝ}oÎáÇüoiÏyk^áæ¹õÖ÷{·=áÎ=ç×÷÷i®÷×^ZáÝýï6yÇÛw}swßÎo¶ºÑ×voûÛ~xiÝ[ïÖéî=çv÷Zk½Úé§½{vqÝïÖsvo}å¶øï®u×¾÷÷õ¦¶{½yé®y×áîk~\Ùöëwoºkv÷¯Ùç7wÏ<õ¿kÝz÷Ûn[kg¶qÍ[Û·x{Ç[×¶¸ßß9q¦å¾ß¸ww:¯xi×{ÑþõÛµoW9yþ¹ßñ×{Õ¯;Õí¹uþ]sMwonå®{ÛÏ|mÞ5ë8yÖ¶çg=iÏ7o~ç®ÞwW:qÎwá®¶s}kÖöwÛf¹k×øoo}Û}öÇÛiî<é¯õ¦ùã®Úß®}õÿvw}¹o}mßá®=ëf¹{}}·¹m¦¶ß]kÝúÕÖ½sÞ½óÞûé¦ößÕÝ¶ëW9snºÕÇ¶ï®øçf¹wß8oßk¦ù×ÛÞ|ofÜ÷z×®<9mÝßm[ÝÞá½onõ§}ßf¸á¾\mÏvo¶÷Ûý}®6ÙÞ¸yÝZïÞ=áÆ·o¿9ofº{owÞy÷GµkÏ;á¾´k§µm§8m·ßmýï¯tk¦øs®¹ïÞµ÷VÝÞxo½|ÝÝyá½:u½ôñ®á¦µßùåÝÛwß|iÎyå½tuÖ÷{g^^o}çto§Ù¶ñÿ<ñßyå®ùuþ}ÙÝ\å®{Çøy®<oÞzuæ´÷oukÝyáÎyw½Ý®úñí8m§»of{ÖÙ§zÛ}÷ãÝs½çg·é®;çFÚi÷¸{uk}xëyÛ¦÷ñ¾mÆå¯ví¦iÖºu¾wÙï{Ó®mÚë®=áßyw¾¹sfs}Z÷owÝ÷snÙ½ûçwsß<á®\ënk¦qÇ^ïox")

But I think that the author wants us to find the logic behind this non-random string instead.

to avoid the "downvotes rush" I added some details in the question :-)

Mathetmatica - 56
The mystery is already solved, so just implementing the idea
⌊.5Prime@Range@4032⌋~Mod~2~FromDigits~2~IntegerString~16

Nice. I'm curious what the shortest possibility is now that the cat's out of the bag

Do you call that "no libraries (except the one required for printing the output)"?

@PeterTaylor Yep, no imports - no libraries.

Judging by the comments, I don't think that's how OP intended it to be interpreted.

J - 46 char
Don't mind me, just logging the J golf here for posterity. Wasn't clever enough to figure out the trick.
4[1!:2&4'0123456789abcdef'{~#.2|<.-:p:i.1007 4

Explained:

p:i.1007 4 - Create a 1007-row, 4-column matrix of the integers from 0, then take the prime numbers corresponding to those integers. Yes, p: is a J builtin. Yes, we're four primes short.
2|<.-: - Halve each number (-:), floor it (<.), and take that modulo 2 (2|). This is the same as taking the next-to-lease significant bit.
#. - Convert each row of the result from base 2 into an integer. This gives us 1007 numbers from 0 to 15 inclusive.
'0123456789abcdef'{~#. - Take each row of this matrix of bits as the binary for a number, and use that number to select from the list of hex digits. This converts every four bits into the hex.
1!:2&4 - The J interpreter has a problem with outputting strings longer than 256 chars, so we have to send this data directly to stdout. You win some, you lose some.
4[ - Finally, discard the result from 1!:2 and instead output the missing 4 from the output. We do this because it's shorter than including those last four primes and returning an empty result here.

JS, 503
Following @xem idea:
s='Ù¦¶3V§K)°¬*ªm¸KLø¶*¬¡KN¥³çÉLIYì³ªlZM9uìê$ÌÓ-Ã8N·¦\nÒµ7#TyªnIURZ§:jéäRÍ-yÆµ[´vQNó¢çjUMNJ£\/«cÌµ¦¤.ÃØ©õ3"[¢âÌ'+"'"+'ÔèÛ¤9Êª[O6$ÓÆö×q$á±Åïe5l×%ß]À²oZW(½Afí¢RÉ¬³lV~ÑÆÌSJbÅY©²Ô¯"¥©ô²#2øû®HjµFz6YÓ%µ½JIb¥äYûåº\n5Ý©6©Éiwj²4-"aÅÂfâvtR¥Ù¹¦µì)X²¼HõÅ½/2=OK.²kÙ2¤K\¼·³&9úB-díyIL£·²¦âÙUá¨K`¦áºÄ»ì29v¦´Æeyaª=T·=KÛ0MJ¡5u];Ù¬U[Ý³âÌñ^³+S¶î+¬ZußY-ZLèôêH¹VÞ ©LUÕé:vºç²ªé«*Ö#3E=ÄéRãjGPº¯äå£c&³L¼ªZz«¦ÛS.mº:fIM×eÂªÃ?ÊÂl+7UÉJ\bk¦®ÌÞr'
r=''
for(var i=0;i<s.length;i++) r+=s.charCodeAt(i).toString(16);
console.log(r)

Mathematica, 55
Prime~Array~4031~BitAnd~2~FromDigits~2~IntegerString~16

Tested on Mathematica 8. This makes use of two observations:

Mathematica's FromDigits doesn't actually check the range of the digits given, so if you apply it to a list of the form {2,0,2,2,0,...} you just get twice the result as if applying to {1,0,1,1,0,...}. But that's exactly the form generated by BitAnding the primes with 2.
The last bit of the number whose hexadecimal representation we want happens to be zero (as evidenced by the string ending in an even digit), so it is just two times the number you'd get with one prime less. But a factor of two is exactly what we get from using the previous observation, so everything perfectly fits together.


text:
Fillomino Solver
Fillomino is a puzzle where you fill a grid with polyominoes. Each polyomino is an area of contiguous cells. The grid representation shows what size polyomino is covering each cell. For example, a pentomino(5) would be shown as 5 in each of five contiguous cells (see below). Two polyominoes of the same size cannot share a border, but may border diagonally.
For each puzzle, you're started with a number of givens and must fill in the remaining cells. An easy example puzzle and solution:

Your task: Given a square puzzle, solve it and output the answer. Input may be via stdin, a single command line argument, or text file. Input will be given as an integer n, followed by n lines of n digits each. Empty cells will be given as periods(.). For the example puzzle above, it would be:
5
3..66
5.4.6
.54.6
.1.6.
..312

Output is the solved puzzle, given on n lines of n digits, to console or text file:
33366
55446
55466
51462
33312

If the puzzle is not valid, output 0. A puzzle could be invalid if the input is malformed or there is no solution. If there are multiple solutions, you may output any one or all of them.
Since each cell is represented by a single digit, all puzzles will consist of polyominoes size 9 and under only. If it is not possible to solve without larger polyominoes, consider it invalid.
Valid answers will solve any given puzzle, not simply output solutions to test cases. No external resources, be it online or local. If there happens to be a language with a built-in fillomino solving function, you can't use it. In short, play fair.
Test Case:
Input:
9
..21.3..5
.5...5..5
.1.44.334
...53.4..
2.3.3..5.
1.15.5.15
..45..1..
.24.53.53
....2....

Output (a possible solution):
322133315
355445555
315443334
235531444
233135551
141535515
344553155
324553553
321223133

Remember that some polyominoes have no given numbers, and some have more than one. There is not a one-to-one relationship between the number of givens and the number of polyominoes.
Score is standard code-golf, size of the program in bytes.

Is a recursive approach a valid answer if it works for a 9x9 board but will run out of memory for some larger size board?

Yes.I don't expect you to be able to feasibly run a 31x31 or anything. Just so that you can actually run both the 5x5 and 9x9 above(to give output for the test cases), and would theoretically work for larger with the same algorithm (given a crap-ton of resources).

4882 characters - Java
Not a very golfed solution (ie 4800 characters is a lotttttttttttt)
Could be golfed a bit more in that 1 or 2 debug printlines are still in there. I think I can reduce a fair bit still in terms of useless/optimized code.
import java.util.*;import java.awt.Point;public class G{public static void main(String[]args){new G();}Scanner z=new Scanner(System.in);public G(){s=z.nextInt();z.nextLine();int g[][]=new int[s][s];for(int i=0;i<s;i++)Arrays.fill(g[i],-1);for(int i=0;i<s;i++){String line=z.nextLine();for(int j=0;j<s;j++)if(line.charAt(j)!='.')g[i][j]=Integer.parseInt(Character.toString(line.charAt(j)));}System.out.println();if(y(g)){for(int i=0;i<s;i++)for(int j=0;j<s;j++)System.out.print(g[i][j]);System.out.println();}else System.out.println(0);}private boolean x(Collection<Point>c,int[][]d){if(c.size()==0)return true;int j=0;for(Iterator<Point>k=c.iterator();k.hasNext();k.next(),j++){for(int sol=9;sol>=0;sol--){int[][]a=new int[s][s];for(int i=0;i<s;i++)a[i]=Arrays.copyOf(d[i],s);List<Point>b=new ArrayList<Point>();for(Point p:c)if(!b.contains(p))b.add(new Point(p));a[b.get(j).x][b.get(j).y]=sol;if(w(a,b.get(j))){if(x(b,a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);c.clear();c.addAll(b);return true;}}}}return false;}int s;private boolean y(int[][]d){int[][] a=new int[s][s];for (int i = 0; i<s;i++)a[i]=Arrays.copyOf(d[i],s);List<Point> incomplete=new ArrayList<Point>();if(r(a)&&s(a)){a(a);System.exit(0);}else if(!r(a)){q("INVALID FROM MAIN, ",12);return false;}for(int i=0;i<s;i++)for(int j=0;j<s;j++){if(a[i][j]!=-1)if(t(new Point(i,j),a,null,a[i][j]).size()!=a[i][j]){if(w(a,new Point(i,j))){a(a);if(y(a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);return true;}else return false;}else return false;}}for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(a[i][j]==-1){Set<Point>c=t(new Point(i,j),a,null,-1);if(x(c,a)){if(y(a)){for(int i=0;i<s;i++)d[i] = Arrays.copyOf(a[i], s);return true;}else return false;}else return false;}q("How did you get here",1);return false;}private boolean w(int[][]d,Point b){List<Point>c;Set<Point>a;a=t(b,d,null,d[b.x][b.y]);c=new ArrayList<Point>(u(b,d,null,d[b.x][b.y]));int h=d[b.x][b.y];int g=h-a.size();if(c.size()<g){return false;}else if(v(c,h,h,new ArrayList<Point>(a),0,d))return true;else return false;}private boolean v(List<Point>c,int h,int g,List<Point>e,int f,int[][]d){if(e==null)e=new ArrayList<Point>();int[][]a=new int[s][s];for(int i=0;i<s;i++)for(int k=0;k<s;k++)a[i][k]=d[i][k];if(f<g&&e.size()<g){for(int i=0;i<c.size();i++){if(!e.contains(c.get(i))){if(d[c.get(i).x][c.get(i).y]==h){for(Point c:e){a[c.x][c.y]=h;}Set<Point> u=t(e.get(0),a,null,h);Set<Point>v=t(c.get(i),a,null,h);if(!Collections.disjoint(u,v)){u.addAll(v);List<Point>uList=new ArrayList<Point>(u);if(v(c,h,g,uList,f+1,a)){q("this e sucess",2);if(y(d)){e.addAll(uList);return true;}}else;}for(int l=0;l<s;l++)for(int k=0;k<s;k++)a[l][k]=d[l][k];}else if(e.add(c.get(i))){if(v(c,h,g,e,f+1,d)){q("this e sucess",2);if(y(d))return true;}}if(e.contains(c.get(i)))e.remove(c.get(i));}}return false;}else if(f>g||e.size()>g){if(f>g){q("Your over the g. ");return false;}else return false;}else{for(Point c:e){a[c.x][c.y]=h;}if(r(a)){if(y(a)){for(int i=0;i<s;i++)d[i]=Arrays.copyOf(a[i],s);q("complete(a) is true, ",4);return true;}else{return false;}}else{return false;}}}private void q(String out,int i){System.err.println(out+". exit code: "+i);System.exit(i);}private void q(String a){q(a,0);}private boolean r(int[][] d){for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(d[i][j]!=-1){Set<Point>same=t(new Point(i,j),d,null,d[i][j]);if(same.size()>d[i][j]){return false;}Set<Point>fae=u(new Point(i,j),d,null,d[i][j]);if(u(new Point(i,j),d,null,d[i][j]).size()<d[i][j]){return false;}}return true;}private Set<Point> u(Point p,int[][]d,Set<Point>u,int i){u=(u==null)?new HashSet<Point>():u;if(d[p.x][p.y]==i||d[p.x][p.y]==-1)u.add(p);int x=p.x,y=p.y;Point t=new Point();if(x+1<s&&(d[x+1][y]==i||d[x+1][y]==-1)){if(u.add(new Point(x+1,y)))u=u(new Point(x+1,y),d,u,i);}if(y+1<s&&(d[x][y+1]==i||d[x][y+1]==-1)){if(u.add(new Point(x,y+1)))u=u(new Point(x,y+1),d,u,i);}if(x-1>=0&&(d[x-1][y]==i||d[x-1][y]==-1)){if(u.add(new Point(x-1,y)))u=u(new Point(x-1,y),d,u,i);}if(y-1>=0&&(d[x][y-1]==i||d[x][y-1]==-1)){if(u.add(new Point(x,y-1)))u=u(new Point(x,y-1),d,u,i);}return u;}private Set<Point> t(Point p,int[][]d,Set<Point>u,int i){u=(u==null)?new HashSet<Point>():u;if(d[p.x][p.y]==i)u.add(p);int x=p.x,y=p.y;Point t=new Point(p);if(x+1<s&&d[x+1][y]==i){if(u.add(new Point(x+1,y)))u=t(new Point(x+1,y),d,u,i);}if(y+1<s&&d[x][y+1]==i){if(u.add(new Point(x,y+1)))u=t(new Point(x,y+1),d,u,i);}if(x-1>=0&&d[x-1][y]==i){if(u.add(new Point(x-1,y)))u=t(new Point(x-1,y),d,u,i);}if(y-1>=0&&d[x][y-1]==i){if(u.add(new Point(x,y-1)))u=t(new Point(x,y-1),d,u,i);}return u;}private boolean s(int[][]d){for(int i=0;i<s;i++)for(int j=0;j<s;j++)if(t(new Point(i,j),d,null,d[i][j]).size()!=d[i][j])return false;return true;}private void a(int[][]d){for(int i=0;i<s;i++){for(int j=0;j<s;j++){System.out.printf("%1s",d[i][j]==-1?".":Integer.toString(d[i][j]));}System.out.println("");}}}

Having never seen Polyominoes before this, I read up on what they are and without looking at solving alrogithms just made up my own (quite slow).
Basically, uses recursion a lot... Finds a Polyomino that's incomplete, tries to complete it.
Finds an empty space, Loops 1-9 through all squares in the pocket, sets that pocket to that value. If the pocket is complete, it tries to find another pocket, then repeats until finished. I couldn't get it to work for a grid of size 9... I have at least one optimisation in mind that could make it work within a reasonable time for 9. Might try to put that in place soon.

How are you compiling this? I'm getting duplicate variable errors in a few places.


text:
Circles dividing the plane
Task
You will be given a set of circles in the plane with their centers on the line y=0. It is guaranteed that no pair of circles has more than one common point.
Your task is to determine into how many regions into which the circles divide the plane. A region is an inclusion-maximal contiguous set of points not intersecting any of the circles.
You should write a program that computes this answer when given a description of the circles.

Here's an example:

On the left side you see the circles drawn in the plane. However, in the right half of the picture, the regions produced by the circles are colored distinctly (one color per region). There are six regions in this example.

Input
The first line of the input contains a number, N, the number of circle descriptions to follow. This line is optional, if your solution works without it, it's fine.
The following N lines each contain two integers, xi and ri > 0, representing a circle with center (xi, 0) and radius ri.
It is guaranteed that no pair of circles has more than one common point. It is further guaranteed that xi and ri do not exceed 10^9 in absolute value (so they comfortably fit into a 32-bit integer).

The input may be:

read from STDIN
read from a file named I in the current directory

Alternatively, the input could be:

available as a string (including newlines) in a global variable
on the stack

Output
This should be a single integer, the number to regions produced. This should be written to STDOUT or a file named O in the current directory.

Rules

Shortest code in bytes wins
+200 byte penalty if your code does not have a runtime + space complexity polynomial in n
-100 byte bonus for worst-case expected runtime + space complexity O(n log n)
-50 byte bonus for worst-case expected runtime + space complexity O(n)
-100 byte bonus for deterministic runtime + space complexity O(n)

While assessing the runtime:

Assume that hash tables have O(1) expected runtime for insert, delete and lookup, regardless of the sequence of operations and the input data. This may or may not be true, depending on whether the implementation uses randomization.
Assume that the builtin sort of your programming language takes deterministic O(n log n) time, where n is the size of the input sequence.
Assume that arithmetic operations on input numbers take only O(1) time.
Do not assume that input numbers are bound by a constant, although, for practical reasons, they are. This means that algorithms like radix sort or counting sort are not linear time. In general, very large constant factors should be avoided.

Examples
Input:
2
1 3
5 1

Output: 3

Input:
3
2 2
1 1
3 1

Output: 5
4
7 5
-9 11
11 9
0 20

Input:
9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2

Output: 11

Hints
We can use the following idea for a very compact solution. Lets intersect the set of circles with the X axis and interpret the intersection points as nodes in a planar graph:

Every circle produces exactly 2 edges in this graph and up to two nodes. We can count the number of nodes by using a hash table to keep track of the total number of distinct left or right borders.
Then we can use the Euler characteristic formula to compute the number of faces of a drawing of the graph:
V - E + F - C = 1
F = E - V + C + 1
To compute C, the number of connected components, we can use a depth-first search.

Note: This problem idea is borrowed from a recent Croatian programming contest, but please don't cheat by looking at the solution outlines. :)

Are some of those bonuses decoys?

@user2357112 Don't assume it can't be done unless you can prove it ;)

Well, with inputs guaranteed to fit in a machine integer, we could use a radix sort and call it O(n). I hate assuming restricted input size, because strictly speaking, it means there are finitely many possible inputs.

@user2357112 No, I said you cannot assume the integers to be bounded while assessing the asymptotics, so neither radix sort nor counting sort would be linear time and space. That they fit into a word is just to make arithmetics "real" O(1) and for practical reasons (bounded variable width in most languages)

@NiklasB. if I have an algorithm in which the only component with superlinear complexity is the sorting, to I have to implement merge sort if my language uses quick sort, in order to get the n log n bonus? Also, I do have new conceptually new solution. Should I post a new answer of replace the old one? (I'd prefer the former, in case my new solution isn't actually correct)

@m.buettner no, sorting is fine, you will grt the bonus. Yes, you can make a new answer

@NiklasB. Please tell me what bonus I might get below.  I think it's -150, but is it -250?

Mathematica, 125 122 - 150 = -28 chars
I don't know the complexity of the built-in function ConnectedComponents.
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

Usage:
1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

11

I think we can safely assume that ConnectedComponents has linear expected worst-case complexity, so if there are O(n) components, this would be fine. I don't understand Mathematica, so I can't tell whether it is O(n) overall and qualifies for the -150 bonus? I think it does. Do I just run it with input in STDIN?

@NiklasB. his input method is just passing a string variable to an anonymous function. so I think that should qualify. as for the output, in Mathematica this will simply result in the number ending up in console output, so that should probably be fine, too.

I've verified the correctness of this, so I think with a score of -28 this is the new leader. Congratulations!

@NiklasB. why only 150? Which part of the algorithm has superlinear worst-case complexity?

@m.buettner 150 is for O(n) expected time. For graphs with arbitrary numbers as nodes, implicitly defined like here, you just can't find the number of CCs in linear time, which can be shown by reducing element distinctness to connected components. I think we can also reduce element distinctness to the original problem

@NiklasB. isn't the time complexity for finding connected components in general O(V+E)? In our case E is equal to n and V is at most 2n. So shouldn't we get O(3n) = O(n)?

@m.buettner Even without any edges, you need to solve element distinctness (find the number of unique elements), so no, that's not possible. O(V+E) assumes that you can check in O(1) if you have already visited a node, which is generally not possible

@NiklasB. ah I see, thanks for the clarification.

+1, for golfing with less than 0 chars ;)

Ruby - 312 306 285 273 269 259 characters
This answer has been superseded by my other approach which uses considerably less characters and runs in O(n log n).
Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take O(n^2) at worst and O(n log n) at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take O(n). So I have overall complexity O(n^2) and qualify for neither reward nor penalty.
This code expects the input without the number of circles to be stored in a variable s:
t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a

Ungolfed version (expects input in variable string):
list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_i
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas

@NiklasB. yes that test case would be nice. The relation that defines the edges in my tree is simply inclusion of one circle in another. Since on circle can't be contained in two circles that don't contain each other (due to the "one intersection" condition), I don't see how this could be a DAG.

Are a node's grandchildren also its children?

@user2357112 no, because they can only split their direct parent

@NiklasB. If I run it with the example in your question, I get 11. For the one in your comment 9.

@NiklasB. wait, I actually get 10 and 8 with my ungolfed version, but 11 and 9 with my current golfed version :D

Also your golfed version would need to output the value, so probably you need an additional 2 bytes

@NiklasB. oh, if you make it a function body in ruby, then the last evaluated expression is returned, which is why I added that a at the end. If you actually want stdout then it's two more bytes for adding p and a space. But since you said you weren't fussed about I/O I assumed, having the result in a would be enough (and I even added the two bytes for the a at the end so it could be used as a function body). Sooooo, could you clarify the rules on that? :D PS: found the bug

I changed the input part, not the output part. Somehow the program needs to write its result, either to STDOUT or file

@NiklasB. alright, it wasn't mentioned in the question. I'll add it.

Cheers, that's already a good start :) Nice solution

Ruby, 203 183 173 133 - 100 = 33 characters
So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes O(n log n) (well, Ruby uses quick sort, so actually O(n^2) but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only O(n) giving a total complexity of O(n log n) which qualifies for the 100 character reward.
This snippet expects the input to be supplied via a file in the command-line arguments without the number of circles:
l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

Ungolfed version (expects input in a variable string):
list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas

Unfortunately this fails for all the larger testcases. It is fast though ;) I don't have a small failing example this time, but you can find the test data on the contest website I linked to (it's contest #6)

The first failing testcase is kruznice/kruznice.in.2 which is the first "real" test case so I assume there is something fundamentally wrong woth the algorithm or implementation. Does it work correct with arbitrarily nested circles?

@NiklasB. thanks, I'll have a look into the test cases (might take me until tomorrow night to fix it though)

@NiklasB. I figured out the problem and the minimum failing example requires 5 circles: -1 1 1 1 0 2 4 2 0 6. I'll think about how to fix this by tomorrow night (hopefully).

Your complexity analysis seems to assume that associative array access is constant time. That seems unlikely to be true in the worst case.

@NiklasB. I was actually able to fix it quite quickly. I don't have the time right now to run it against the entire test suite. If you don't get around to do that, I'll try myself tomorrow.

@PeterTaylor Hm yes I did assume a perfect hash map, that's true. I'll need to find some data about the complexity of Ruby's implementation there. Then again, the keys are only integers, so I could as well use a simple array, offset by the left-most position.

Then you run into problems with the time taken allocating the array. In C you might be able to claim that you can allocate an arbitrarily sized array in constant time, but in any language which zeros the contents you can't.

@PeterTaylor I see, my complexity would then actually depend on the size of circles, such that doubling a given problem would actually double the required storage and run-time. Hmmm. I'll have to think on this.

@PeterTaylor note that even if hashing takes O(log n) the overall complexity is still O(n log n).

@Peter I think since associative arrays can easily implemented with O(log n) worst case, this is perfectly fine. I updated the question so that expected O(n log n) worst case is explicitely allowed. My intention was not to disallow randomized solutions using hashing or quicksort, which even in the worst case have a good expected run time.

Clarified the question

The program now passes all but one test case (kruznice.in.6) Maybe a precision problem?

Yep, it's due to the use of floating point numbers. I have a fix which leaves the byte count intact but is precise.

@NiklasB. fixed it, saving two bytes. :)

What? Ruby has rationals? Nice. Now this is the current leader :)

@NiklasB. in terms of complexity or golfing? :)

Both actually :)

@NiklasB. I thought so :D ... I'll see what I can think of.

A few suggestions: You can use tuple unpacking at two places in the lambda argument lists and you could use $<.each instead of s.lines.map. And you use c[1] instead of x at one place

And the ! in sort_by! is superfluous :)

@NiklasB. right, $< assumes file/console input... I could probably change that. I had already fixed the tuple unpacking. And I didn't find sort_by in the doc, because I only looked at Array and not Enumerable. Thanks for the hints! :)

I have another suggestion that brings the size down by around 10 bytes: It involves using sort instead of sort_by and making use of the lexicographical order that Ruby uses for comparing arrays. Ruby is a pretty cool language :) Almost as nasty as Perl

@NiklasB. sweet! :D ... I'm actually still learning a lot of Ruby basics. This is the second thing I've ever written in Ruby (with the first one being another challenge from earlier this week).

Julia - 260 -100(bonus?) = 160

 Interpreting the circles as figures with vertices (intersections), edges, and faces (areas of the plane) we can relate each other using Euler characteristic, so we only need to know the number of "vertices" and "edges" to have the number of "faces" or regions of the plane with the formula written below:

UPDATE: By thinking a while i figured out that the problem with my method was only when circles where not connected, so i came with an idea, why not artificially connect them? So the whole will satisfy the Euler formula.

F = 2+E-V (V=6, E=9)
[Dont work with nested circles, so its not an answer of the problem for general cases]
Code:
s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
    a=int(split(s[i+1]))
    c[i,1]=a[1]-a[2]
    c[i,2]=a[1]+a[2]
    if i==1 t=[c[1]]end
    append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices

I think your program will fail for 2 -10 1 10 1.

"It is guaranteed that no pair of circles has more than one common point." so i think it will not apply :)

@CCP They have zero common points. n=2, the circles are (C=(-10,0), r=1) and (C=(10,0), r=1)

@NiklasB. Didnt see the "-"! And You're right, but the idea i think it was right, let me fix the problem and i will edit the answer.

Doesn't the graph have to be connected to apply the Euler characteristic?

Thats why when its not connected i subtract 1.

What if there are 5 connected components?

Now works with all the example cases and "2 -10 1 10 1" case.

Well yeah, but not for the general case. Check the comments above

Can you write an example with answer to see if its true?

As I said, the problematic case is already described in a comment here. Maybe you can generalize the -10 1 10 1 sample so that it breaks your program. Look closely at the variables involved in your formula

I dont see any problem with 5 connected circles, the output its 6 like it should be(?)  Graph: 00000

You should look more in the direction of non-connected circles

"5 connected components" means "5 parts of the graph that are connected within themselves, but not connected to each other". 5 0 1 10 1 20 1 30 1 40 1 would be an example of that.

Ok , i think i solved that case! ;)

Also whitespace counts for this challenge, so your current version has 238 bytes

I used http://bytecount.bluebus112.com/ to count, why my solution didnt win the other bonuses?

That webapp doesn't count newlines and leading whitespace it seems. Use wc or any file browser to see the size in bytes

If it is O(n log n), you get -150. But currently it is not correct.

The solution or the speed?

The solution is not correct. Also your program doesn't give any output when I run it

Why the -1?. I already edited the answer solving the 5 ring problem, generalizating for n ring. Its another case where my solution its wrong? (Julia diplays last line statement in console)

Yes, there are lots of cases where the program fails. The basic idea is interesting, but your implementation is not correct

Well this problem was very fun and i think that the idea of using Euler characteristic its intresting. But i think iam not able to see the cases you are talking about. So i think i'll leave the problem unfinished :(.

I could give you a large testcase where it fails, but I don't think that would help you a lot. Maybe you can use the other correct solution from above and test your program against it with random input?

Ah, here is a simple case: 4 0 2 1 1 10 2 11 1 But I don't think I can give you a lot more test cases, that would be a bit unfair

Yes i think you're right.. The formula works with connected circles, if they are not it will give some other cases where the algorithm fails (F=2+E-V). The instersection problem will not be difficult to solve, but i think i need to change all the algorithm to do it. So i think i will not continue to improve the answer, what would be the better way to proceed? delete the answer or let it as unfinished?.

Does this work for arbitrarily nested circles? It looks like it doesn't

Sorry to say, but this still does not work for the general case. Remember that circles can be arbitrarily nested and the same problems can occur inside a large circle

Spidermonkey JS, 308, 287, 273  - 100 = 173
I think if I rewrote this in Ruby or Python I could save characters.
Code:
for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)

Algorithm:
n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".
       // values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
  n += key[numLeftBounds] // each circle that opens has at least one space.
  k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
  k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
  if !a.empty():
     set the innermost circle (top of stack) to false (not never alone)
  fi
loop

I'm not terribly great at big O notation, but I think that's O(n) since I'm effectively looping through each circle 3 times (create, left, right) and also sorting the map's keys (and I sort for O(n log n) but that disappears).  Is this deterministic?

If anyone has any advice on how to combine the r loop and the l loop into one statement, i'd appreciate it.

Cheers :) Looks to me like your runtime is indeed O(n log n), due to the sort, which would be -100. I will let you know whether it passes all test cases.

Nice, your program passes all test cases on the first try. I think something like this (sweepline with some state maintained in a stack) was the official solution from the problem authors. Your program gets a total score of 173

I was trying a much more robust solution with overlapping circles.... then I saw that they could only intersect at one point.

sorry about that, but I thought I had made that clear enough

@NiklasB. You did.  No worries.  It was over-engineering on my part

I emphasized that part a bit more. Hope you still enjoyed solving the problem :)

JavaScript (ES6) - 255 254 Characters - 100 250 Bonus = 155 4
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Assumes that the input string is in the variable S and outputs the number of regions to the console.
R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
                                    // All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
    X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
                                    // Create an object with w (width), l (left boundary)
                                    // and r (right boundary) attributes.
    l=k<l?k:l;                      // Update the minimum left boundary.
    w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
                                    // sparse array indexed so that the elements are
                                    // sorted by ascending left boundary then descending
                                    // width.
                                    // If there are N circles then only N elements are
                                    // created in the array and it can be treated as if it
                                    // is a hashmap (associative array) with a built in
                                    // ordering and as per the rules set in the question
                                    // is O(1) per insert so is O(N) total cost.
                                    // Since the array is sparse then it is still O(N)
                                    // total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

The time complexity is now O(N).
Test Case 1
S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 3
Test Case 2
S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 5
Test Case 3
S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 6
Test Case 4
S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 11
Test Case 5
S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 105
Previous Version
C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1

With comments:
C=S.split('\n');                    // Split the input into an array on the newlines.
                                    // O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
                                    // if there are N disjoint circles then there will be
                                    // N+1 regions.
                                    // At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
                                    // O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
                                    // O(1) per line = O(N) total.
  .map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
                                    // radius and the right boundary.
                                    // O(1) per line = O(N) total.

  .sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
                                    // Sort the circles on increasing left boundary and
                                    // then descending radius.
                                    // O(1) per comparison = O(N.log(N)) total.
  .map(x=>{                         // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

The total time complexity is O(N) for everything except the sort which is O(N.log(N)) - however replacing this with a bucket sort, this will reduce the total complexity to O(N).
The memory required is O(N).
Guess what is next on my todo list... bucket sort in less than 150 characters. Done

Bucket sort has only average complexity O(n) (in fact O(n+k)), but O(n^2) or O(n log n) worst case depending on the sorting algorithm used within buckets, so you'd need to do it in 50 characters.

@m.buettner - Bucket sort can be done in O(N) worst-case complexity. It relies on careful choice of the buckets and an O(1) algorithm to assign to buckets. I've done it before (and proved it) and I just need to transfer the code to JavaScript. The algorithm above is already O(N.log(N)) so the only improvement is to get an O(N) sorting algorithm.

I'd be interested in that proof and corresponding choice of buckets. :)

http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf (on page 556) gives an example of an O(N) bucket sort. https://archive.org/stream/PlanarityTestingByPathAddition/PlanarityTestingByPathAddition-MartynGTaylor-2012-05-30#page/n95/mode/2up (page 75) gives an example of a O(N) combined DFS search and bucket sort (time complexity is discussed on page 76).

@Mt0 hold on there, you might to read my addition to the complexity section of the question. With unbounded numbers sorting in linear time is most definitely impossible

The construction in those papers work because you only have O (|V|) different values

Passes all my testcases as well :)

There's no such thing as a "hashmap (associative array) with a built in ordering" that still supports O(1) expected time operations (let alone deterministic). Your first version gets a higher score and is correct, so I would suggest you to restore it

Also your updated version throws an error on some larger test cases and returns the wrong answer on some others. You can find the test data at the contest homepage. It's the task "KRUZNICE" from Contest #6.

I just checked and it seems that Javascript does not have any guarantee that numbers as properties are automatically sorted: In Chrome, var x ={"111111111111111111":5, "11111112222222":6}; x outputs Object {111111111111111111: 5, 11111112222222: 6}. Is there something about that in the ES6 standard that will make me eat my own words? I still think that a data structure that does this would not qualify as a hash table, which naturally has no order, so it's not really relevant anyway

Firstly, x={}; defines an object not an array. If you want an array then you need to do something like this x=[];x[11111]=1;x[1122]=2;x.forEach(x.forEach(function(a,i){console.log(a,i)}) which will show it as ordered in both Chrome and FireFox. Secondly, Chrome does not support ES6 - FireFox is the only browser that does (at the moment).

Or rather: x=[];x[11111]=1;x[1122]=2;x.forEach(function(a,i){console.log(a,i)})

KRUZNICE 2, 3 & 4 all give the correct answer in FireFox - the others seem to be too big to paste the input string into the console and just hang FireFox on my machine. However, the two versions are identical after sorting the array (and the sorting is done using different methods but is functionally identical).

@MT0 Unfortunately the code fails test cases 5, 6, 8 and 9. I used SpiderMonkey 24 to test it, which I think is the current Firefox JS engine.

Now that I realize the confusion about arrays vs. objects, I also realize why your code seemed to be so slow in my tests. You in fact use an array, not an object. Try executing x=[];x[1000000000]=1;x.forEach(function(x) { print(x); }); Your code is in fact Ω(M) where M is the maximum input number, so it is not even polynomial in n and gets a +200 penalty... As I wrote in the question: "you can not assume that input numbers are bounded by a constant (although they are for practical reasons)" I would suggest you to go with the original version

And if arrays were in fact implemented as sparse arrays, then you could either have O(1) expected access time or ordering, but not both

Try using .map() (as I do in my code) rather than .forEach() - there is a huge difference in performance as .forEach() is the same as for(i=0;i<x.length;i++) whereas .map() will only run on the elements which are there - which is why it is not O(m). (Also note that SpiderMonkey is only released up to version 24 but FireFox is version 27)

I am not aware of a way to test on version 27, so please feel free to show me how to do that. I can't imagine it makes a difference though. Now assuming the best case for your cause, that arrays are indeed implemented as sparse arrays, as I said, you cannot have both. Either you have ordering or you have O(1) expected time for the operations. In any case, you would not achieve the same score as your original attempt, so 155 is the score I give to this answer for now. I don't know where you got the -250 from, that would mean Javascript can solve element distinctness in O(n), which is impossible

@MT0 Also, have you tried what happens if you do var x = []; x[1000000000] = 4; var N = 0; x.map(function(a) { N += a; }); N;? It just leaves N = 0, because map returns a lazy array and does not execute the function at all. That happens if x is beyond a certain size (there seems to be a threshold) and I guess that is why your script only works for small inputs.