text:
Shortest code to sort walking points
The challenge is to, given a list of points, sort in a way that, when they are connected in this order, they never intersect.
Input format (read from stdin):
X Y
1 2
3 4
5 6
...

Output should be the same as input, but sorted.
Rules:

You can start from any point.
The last point must be same as first one, making a close circuit.
It should be  done considering the Cartesian grid.
You may assume that the input points do not all lie on a single line.
The endpoints of each line do not count as intersecting.

For further help:

I would say it is impossible, if the dots are located on one line. For example, there are two dots given. You can go from one dot to the other, but never back without reusing the previous connection.

First of all, a closed circuit is guaranteed to intersect, so that requirement just had to go. I also removed the phrase "Shortest code to" from your title, since it is synonymous with the code-golf tag.

If the points are on one line, it's still unsolvable. But I think the condition sufficient, if there are three points that make a triangle and no duplicate points.

@HeikoOberdiek "Every input will be solvable" was added three minutes prior to your last comment.

All languages are allowed.

Is the input always integers? Also, is there an implicit line from the last point to the first, or not? Eg in your first example, does that draw three lines or 4 (making a square)?

What happened to the closed loop requirement? Sure, it invalidates some inputs, but this problem is trivial without it. /: in J has this behaviour by default, in fact.

@Rusher Why are closed circuits guaranteed to intersect? (the OP's example doesn't)

If it's just a line, then an elementary solution is sorting by first and second coordinate, a default sort for pairs, so it's just sorting and nothing more fancy here.

@Rusher: A closed circuit does not necessarily self-intersect, except in the trivial sense that the start and end points are the same: the "good" picture in the post shows a non-self-intersecting closed circuit. Further, without the closed circuit requirement, this challenge becomes completely trivial; I can solve it in six characters of GolfScript, five of which are I/O handling.

@m.buettner In Euclidean geometry, the intersection of two lines may be nothing, a point, or a line. In a closed loop, the start and end are the same point. Therefore, the intersection is a point.

@ilmariKaronen I'm confused. You claim that a closed circuit does not self-intersect, and then you immediately claim that it DOES intersect and it does so in a trivial sense. If the removal of an incorrect requirement made the challenge too easy for you, then perhaps you should reinstate it but redefine the word "intersection" so that it fits what we learned in middle school. Don't be afraid of the edit button. It probably takes a few people to write a good challenge anyway.

@Rusher: You could equally well claim that any two successive lines in the path must always intersect, since they share an endpoint. Such "intersections" (of which the "intersection" at the endpoints of a closed loop is one example) are trivial, and cannot be counted in any meaningful definition of a "non-self-intersecting path". (Anyway, if you really want to be pedantic, just define each line segment to include its starting point but not its endpoint. Problem solved.)

@Rusher: Oh, and editing an ongoing challenge back and forth in a way that changes the validity of existing solutions is generally a bad idea. Yes, sometimes it can't really be avoided, but we should at least attempt to minimize it. If we do come up with a wording that matches the original intent and that you don't consider incorrect, I'll be happy to edit it in.

The question as edited deserved to be closed as too trivial. Edits should not remove all the challenge from a problem. I've therefore rolled it back. If anyone disagrees, I'll willingly discuss this on meta.

@Rusher what Ilmari said. Yes, the intersection may be a point (which is also the case for the "invalid" example posted by the OP). But unless you're defining each section to be a semi-open set of points, you'll have to change the specification to use at most 2 points, because two consecutive sections will overlap just as well as the ones that close the loop. And since that's probably not what you intend, each section is a semi-open interval such that there is no intersection where the loop closes. But passing through a point twice does create an intersection again and all is well.

Just so nobody thinks I am playing edit tug-of-war, please notice that this time I only added a single small exception for endpoints. This should be an acceptable middle ground.

Mathematica - 20 30 chars
Just the sorting part
SortBy[%, ArcTan @@ # &]

Whole testing code, that consists of generating 100 random points and plotting the line
RandomReal[{-10, 10}, {100, 2}];
SortBy[%, ArcTan @@ # &];
ListPlot@% /.
 Point[p_] :> {EdgeForm[Dashed], FaceForm[White], Polygon[p],
   PointSize -> Large, Point[p]}

+26 chars
If you demand proper input/ouput, then
"0 0
 4 4
 0 4
 4 0";
Grid@SortBy[%~ImportString~"Table", ArcTan @@ # &]

+2 chars
Just adding N@
Grid@SortBy[%~ImportString~"Table", ArcTan @@ N @ # &]

because above code works only on real numbers and not on integers due to Mathematica's weird behavior when sorting symbolic expressions
N@Sort[{ArcTan[1], ArcTan[-2]}]
Sort[N@{ArcTan[1], ArcTan[-2]}]

{0.785398, -1.10715}
{-1.10715, 0.785398}

EDIT I just realized if the points are not around the origin it won't work, so it also requires shift to the center of points
SortBy[%, ArcTan @@ N[# - Mean@%] &]

I was trying to find a counter-example where you have three points in line with the "centre of mass". They would all have the same arctangent, so there order is not determined by your code, which might lead to their connections overlapping. However, your snippet always seems to sort those cases from inside out, although their ArcTan result is actually identical down to the last bit. Do you know why that is? (here is such a case if you want to play around with it {{1, 2}, {2, 4}, {3, 6}, {-5, 5}, {-6, -12}, {5, -5}}).

@m.buettner From SortBy documentation: If some of the f[e_i] are the same, then the canonical order of the corresponding e_i is used.

How convenient! :)

The question has changed, thus this answer contains different versions, with and without a closed path.
Perl, open path, 69 bytes
print"@$_$/"for sort{$$a[0]<=>$$b[0]||$$a[1]<=>$$b[1]}map{[/\S+/g]}<>

Each point is expected in STDIN as line, with the coordinates separated by white space.
Any number format is supported that Perl interprets as number (including floating point numbers).
Example:
0 0
4 4
0 4
4 0
-2 1
2 -2
2 4
3.21 .56
.035e2 -7.8
0 2

Output:
-2 1
0 0
0 2
0 4
2 -2
2 4
3.21 .56
.035e2 -7.8
4 0
4 4

Ungolfed:
print "@$_$/" for            # print output line
    sort {                   # sort function for two points $a and $b
        $$a[0] <=> $$b[0]    # compare x part
        || $$a[1] <=> $$b[1] # compare y part, if x parts are identical
    }
    map { [/\S+/g] }         # convert input line to point as array reference
    <>                       # read input lines

Circuit variants
In the first question version, there was a connection between the last and first point to make a circuit.
Center is not existing point, 253 bytes
This variant can fail, if the center is one of the points, see example 3.
Edits:

In his answer swish noticed, that the points should be centered around the origin to ensure a cross-free circuit:

Sorting needs transformed coordinates.
The original string representation of the numbers need to be kept for
the output.

Bug fix: the special case for the negative x-axis had included the positive x-axis.

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;(!$X&&!$Y?-1:0)||!$x&&!$y||!$Y&&!$y&&$X<0&&$x<0&&$X<=>$x||atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

Example 1:
4 4
-2 0
2 0
1 1
4 0
-2 -2
-3 -1
1 -2
3 0
2 -4
0 0
-1 -2
3 3
-3 0
2 3
-5 1
-6 -1

Output 1:
0 0
-6 -1
-3 -1
-2 -2
-1 -2
1 -2
2 -4
2 0
3 0
4 0
1 1
3 3
4 4
2 3
-5 1
-3 0
-2 0

Example 2:
Testing number representation and coordinate transformation.
.9e1 9
7 7.0
8.5 06
7.77 9.45

Output 2:
7 7.0
8.5 06
.9e1 9
7.77 9.45

Ungolfed:
print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    (!$X && !$Y ? -1 : 0) ||       # origin comes first, test for $a
    !$x && !$y ||                  # origin comes first, test for $b
    !$Y && !$y && $X < 0 && $x < 0 && $X <=> $x ||
        # points on the negative x-axis are sorted in reverse order
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

Without restriction, 325 bytes
print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$O/9,$$_[1]-$P/9,$$_[2],$$_[3]]}map{$O=$$_[0]if$$_[0]>0&&($O>$$_[0]||!$O);$P=$$_[1]if$$_[1]>0&&($P>$$_[1]||!$P);[@$_]}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

In the previous version, the center is put at the begin and the last points on the negative axis are sorted in reverse order to get cross-free to the center
again. However, this is not enough, because the last points could lie on a different line. Thus the following example 3 would fail.
This is fixed by moving the centered origin a little to the top and right.
Because of centering, there must be at least one point with positive x value and a point with positive y value. Thus the minimums of the positive x and y values are taken and reduced to a ninth (a half or third could be enough).
This point cannot be one of the existing points and is made the new origin.
The special treatments of the origin and the negative x-axis can be removed, because there is any point that lies on the new origin.
Example 3:
-2 -2
-1 -1
-2 2
-1 1
2 -2
1 -1
2 2
1 1
0 0

Output 3:
0 0
-1 -1
-2 -2
1 -1
2 -2
1 1
2 2
-2 2
-1 1

Example 1 is now differently sorted:

Ungolfed:
print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed coordinates
    $$_[0] - $O/9, $$_[1] - $P/9,  # new transformed coordinate
    $$_[2],  $$_[3]                # keep original coordinate
] }
map {
    # get the minimum positive x and y values
    $O = $$_[0] if $$_[0] > 0 && ($O > $$_[0] || !$O);
    $P = $$_[1] if $$_[1] > 0 && ($P > $$_[1] || !$P);
    [ @$_ ]               # pass tuple through
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

+1 for including a circuit variant (I suspect the requirement will eventually find its way into the question again, once Rusher responds)

GolfScript, 6 / 13 chars (open path; 49 chars for closed path)

Note: This solution is for the current version of the challenge as edited by Rusher. It is not a valid solution to the original challenge, which required that the line from last point back to the first also should not intersect the other lines.  The 49-char solution below is valid for the original challenge too.

~]2/$`

The code above assumes that the output can be in any reasonable format.  If the output format has to match the input, the following 13-character version will do:
~]2/${" "*n}/

Explanation:

~ evaluates the input, turning it into a list of numbers; ] gathers these numbers into an array, and 2/ splits this array into two-number blocks, each representing one point.
$ sorts the points in lexicographic order, i.e. first by the x-coordinate and then, if there are ties, by the y-coordinate.  It is easy to show that this will guarantee that the lines drawn between the points do not intersect, as long as the path does not need to loop back to the beginning.
In the 5-character version, ` stringifies the sorted array, producing the native string representation of it (e.g. [[0 0] [0 4] [4 0] [4 4]]).  In the longer version, {" "*n}/ joins the coordinates of each point by a space, and appends a newline.

Online demo: short version / long version.

Ps. Here's a 49-char solution to the original problem, where the path is required to be closed:
~]2/$.0=~:y;:x;{~y-\x-.+.@9.?*@(/\.!@@]}${" "*n}/

It works in a similar manner as Heiko Oberdiek's Perl solution, except that, instead of using trig functions, this code sorts the points by the slope (y − y0) / (x − x0), where (x0, y0) is the point with the lowest x-coordinate (and lowest y-coordinate, if several points are tied for lowest x).
Since GolfScript doesn't support floating point, the slopes are multiplied by the fixed constant 99 = 387420489.  (If that's not enough precision, you can replace the 9 with 99 to turn the multiplier into 9999 ≈ 3.7 × 10197.)  There's also some extra code to break ties (by the x coordinate) and to ensure that, as in Heiko's solution, points with x = x0 are sorted last, in decreasing order by y coordinate.
Again, here's an online demo.

Mathematica, 35
This works for ANY list of unique points.
s=StringSplit;Grid@Sort@s@s[%,"\n"]

You say "read from stdin", so for Mathematica, I'm assuming "read from last output".
Input (last output):
"0 0
4 4
0 4
4 0"

Output:
0 0
0 4
4 0
4 4

If input and output needn't be in the "newlines" format, this can shrink to 6 characters:
Sort@%

taking the last output as input, assuming the last output is a 2-dimensional array.
Input (last output):
{{0,0},{4,4},{0,4},{4,0}}

Ouput:
{{0,0},{0,4},{4,0},{4,4}}

Wouldn't just Sort do the same thing?

@swish I'm using SortBy so I can easily sort with respect to the "x" values and the "y" values.

But sort does the same thing, sorting by x and y.

You can save seven characters by renaming StringSplit again and using infix syntax Sort@(s=StringSplit)@%~s~"\n".

@swish Well thanks for telling me about 'Sort'. That shortened the code a lot...

@m.buettner Thanks. I renamed 'StringSplit', but it didn't work with the infix statement for me. I think because of precedence rules.

@kukac67 ah, you're right. I always get the precedence of infix and @ the wrong way round.

PHP (175 109 100 chars)
while(fscanf(STDIN,'%d%d',$a,$b))$r[]=sprintf('%1$04d %2$04d',$a,$b);sort($r);echo implode('
',$r);

OK, I admit, PHP isn't the best golfing language, but I gave it a try.
Here's some sample output:
0000 0000
0000 0004
0004 0000
0004 0004

What is does is it puts the information into a string formatted with previous zeroes.
Then it just sorts the points textually.
P.S. It fails on numbers above 9999.

Python 2.7, 42B
import sys
print''.join(sorted(sys.stdin))

Couldn't really be simpler; read STDIN, sort lines, print lines. NB I've respected the exact I/O requirements of the question, but if you're manually populating STDIN you need to press CTRL+d to end input.


text:
Find all reachable nodes in a graph
You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with  keys of nodes and values which are lists of nodes which that node has an edge to. For instance:
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}

Be reasonable. A dictionary of frozen sets is not allowed, even if it makes your code shorter. A list of lists is fine, if your language doesn't have dictionaries.
Your task is to implement a function that takes a directed graph and a starting node, and outputs all nodes reachable from the starting node. The output format is also flexible. A return value from a function is fine, so is print, etc.
Test case:
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1

R(G,s)
{1,2,3}

Fewest characters wins. I will clarify if needed.

Mathematica 63 40 37
My earlier submission was incorrect. I had misinterpreted what ConnectedComponents returns.  The present approach relies on Belisarius' suggestion to useVertexOutComponent. 3 additional chars saved by alephalpha.
The following generates an 11 by 11 adjacency matrix of 0's and 1's, where 1 indicates that the vertex with the row number is connected directly to the vertex corresponding to column number of the cell. (SeedRandom ensures that your matrix a will match mine.)
SeedRandom[21]
a = Array[RandomChoice[{0.9, 0.1} -> {0, 1}] &, {11, 11}];

Example
(37 chars)
 AdjacencyGraph@a~VertexOutComponent~4

{4, 1, 7, 8, 9, 3}

Verifying
The directed graph displays how to reach vertices {1, 7, 8, 9, 3} from vertex 4.
AdjacencyGraph[a, ImagePadding -> 30, VertexLabels -> "Name"]

Not sure. Methinks it's m = {{0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}}; ConnectedComponents[AdjacencyGraph[m, DirectedEdges -> True], 1]

I'll check and get back to you.

Nope. Mine is wrong. Not sure about yours.

This seems to work: m = {{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 1, 0}}; VertexOutComponent[AdjacencyGraph@m, 3, Infinity]. The DirectedEdges -> True isn't needed.

I forgot about VertexOutComponent.  Would you like to post?

Nah, I think one Mma answer per Q is enough. Please be my guest to use the code if that fits you :)

Is the ∞ here necessary?

Apparently [Infinity] is not needed. Thanks.

Python 2.7 - 80 65
def R(G,s):
 k=a={s}
 while k:a=a|k;k|=set(G[k.pop()])-a
 print a

GolfScript, 27 24 characters
{:G,{G{1$&},{)||}/}*}:C;

This code implements the operator C which takes starting node and graph on the stack and leaves a list of reachable notes on the stack after execution.
Example (online):
[1] [[1 [2 3]][2 [3]][3 [1]][4 [2]]] C
# returns [1 2 3]

You can get a reasonable saving with a filter. The best I've got so far is to replace the inner loop with G{1$&},{~||}/

@PeterTaylor Thank you. I was working on a different approach (.{{&}+G?)||}/) which has the same character count but I find your's a bit nicer.

J - 19 15 char
J doesn't have a dictionary type, and is generally garbage with representing things the way people are used to in other languages. This is a bit idiosyncratic with how it represents things, but that's because J and graphs don't blend well, and not because I'm looking for optimal ways of representing directed graphs. But even if it doesn't count, I think it's a concise, interesting algorithm.
~.@(],;@:{~)^:_

This is a function which takes a graph on the left and a list of nodes to start with on the right.
Graphs are lists of boxed lists, and the nodes are indices into the list that represents the graph. J indexes from zero, so nodes are nonnegative integers, but you can skip 0 and pretend to have 1-based indexing by using an empty list ('') in the 0 place. (Indented lines are input to the J console, lines flush with the margin are output.)
   2 4;1 2 4;0;0 2;1   NB. {0: [2, 4], 1: [1, 2, 4], 2: [0], 3: [0, 2], 4:[1]}
+---+-----+-+---+-+
|2 4|1 2 4|0|0 2|1|
+---+-----+-+---+-+
   '';2 3;3;1;2        NB. {1: [2, 3], 2: [3], 3: [1], 4:[2]}
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   '';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7   NB. the big Mathematica example
+++-+-+-------+---+---+-++-++-+
|||2|9|1 7 8 9|3 6|4 8|7||3||7|
+++-+-+-------+---+---+-++-++-+

Lists of numbers are just space-separated lists of numbers. In general a scalar (just one number in a row) is not the same as a one-item list, but I use only safe operations that end up promoting scalars to one-item lists, so everything's cool.
The function explained (supposing we invoke as graph ~.@(],;@:{~)^:_ nodes):

{~ - For each node in nodes, take the list of adjacent nodes from graph.
;@: - Turn the list of adjacencies into a list of nodes.
], - Prepend nodes to this list.
~.@ - Throw out any duplicates.
^:_ - Repeat this procedure with the same graph until it results in no change to the right hand argument, i.e. there are no new nodes to discover.

The verb in action:
   ('';2 3;3;1;2) ~.@(],;@:{~)^:_ (1)           NB. example in question
1 2 3
   f =: ~.@(],;@:{~)^:_                         NB. name for convenience
   (2 4;1 2 4;0;0 2;1) f 2
2 0 4 1
   ('';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7) f 4  NB. Mathematica example
4 1 7 8 9 3

If you don't like this graph representation, here's a couple quick verbs for converting to/from adjacency matrices.
   a=:<@#i.@#        NB. adj.mat. to graph
   mat=:0,0,.0 1 1 0,0 0 1 0,1 0 0 0,:0 1 0 0
   mat               NB. adj.mat. for {1:[2,3],2:[3],3:[1],4:[2]}
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
   a mat
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   A=:+/@:=&>/i.@#   NB. graph to adj.mat.
   A a mat
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0

For anyone wondering why the graph is the left argument to the verb, it's because that's the general convention in J: control information on the left, data on the right. Consider list search, list i. item, and the sequential machine dyad, machine ;: input.

APL (Dyalog Extended), 7 bytes
⌂search

Try it online!
A library function that does the job. Takes the graph on its left and the start node on its right, and gives the list of reachable nodes using breadth-first search.
Since APL has neither sets nor dicts, the closest input format is a nested vector of vectors like (2 3)(3)(1)(2). And, just by coincidence, Dyalog APL's graph library uses this exact format as the representation for graphs.
Because a built-in is boring, here is another solution without it (which is still short):
APL (Dyalog Unicode), 10 bytes
(∪/⊢,⌷⍨)⍣≡

Try it online!
Same input format and left/right argument order. Returns the same result, but nested once. Keeping one level of nesting throughout the ⍣≡-loop gives several advantages in terms of golfing.
How it works
(∪/⊢,⌷⍨)⍣≡  ⍝ Tacit infix function. left←graph, right←node
(      )⍣≡  ⍝ Repeat until the right arg converges...
     ⌷⍨     ⍝ Simulate following all possible edges from input node(s)
            ⍝ which gives a vector of nested vectors of nodes
   ⊢,       ⍝ Prepend the (nested) list of initial nodes
 ∪/         ⍝ Reduce by set union;
            ⍝ preserve the order of existing nodes by
            ⍝ having the input on the left end

Example run:
  graph←(2 3)(3)(1)(2) ⋄ node←1
  First iteration:
       ⌷⍨     ⊂2 3  ⍝ extract index 1 of graph
     ⊢,       1(2 3)
   ∪/         ⊂1 2 3
  (      )⍣≡  Converged? No.
  Second iteration:
       ⌷⍨     (2 3)(3)(1)  ⍝ extract indices 1, 2, 3 of graph
     ⊢,       (1 2 3)(2 3)(3)(1)
   ∪/         ⊂1 2 3
  (      )⍣≡  Converged? Yes, stop.

Python 2.7 (using networkx) - 71
from networkx import*
single_source_shortest_path(DiGraph(G),s).keys()

Sample Run
>>> G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
>>> s=1
>>> from networkx import*
>>> single_source_shortest_path(DiGraph(G),s).keys()
[1, 2, 3]

networkx is not really core Python.

@isaacg: I do not see any restriction to use core Python. It is an accepted practice in this forum to use libraries unless it is explicitly restricted. So I disagree with your comment and downvote.

Is that so? I must have been unclear on the accepted practice of the forum. I will remove my downvote at the next opportunity.

JavaScript (ECMAScript 6) - 70 Characters
f=(G,s)=>{y=Set([s]);y.forEach(x=>G[x].forEach(z=>y.add(z)));return y}

Test
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1
f(G,s)

Returns a set containing:
1,2,3

Mathematica, 29 chars
{s}//.l_List:>(l⋃##&@@(l/.G))

Example:
G = {1 -> {2, 3}, 2 -> {3}, 3 -> {1}, 4 -> {2}}; s = 1;
{s}//.l_List:>(l⋃##&@@(l/.G))

{1, 2, 3}

This is an awesome solution. I don't understand Mathematica, though. Could you explain?

Python – 54 52 + 7 + 7
def R(G,s,A):
    A|={s}
    for n in set(G[s])-A:R(G,n,A)

R needs to be called with an empty set as an additional argument. This set contains the output, when R has finished. Example of usage:
G = {1: [2, 3], 2: [3], 3: [1], 4:[2]}
A=set()
R(G,1,A)
print A

If you consider this way of output cheating, keep in mind that it’s very normal in C, for example. Anyway, you may want to charge 7 additional chars for the intialisation of the empty set (A=set()) and 7 for the print line.

I would allow this method, but charge you six characters for the empty set - A={[]} - and seven characters for the print A line, for a total of 67 characters. YMMV, though.

@isaacg: I accept the charge for the empty set, but why the charge for printing? Would you also charge this for a function, which returns the set/list/… in a “regular” manner?

A return value would not be charged for. Eh - it's rather borderline, I could see the A value being free. The issue I see is that you essentially just saved the output to a variable, not returned or output it.

K4 , 12 bytes
The code is:
{?,/x,G x}/1

Here's an example of its use:
  G:1 2 3 4!(2 3;3;1;2)
  {?,/x,G x}/1
1 2 3
  H:(!12)!(();();2;9;1 7 8 9;3 6;4 8;7;();3;();7)
  {?,/x,H x}/4
4 1 7 8 9 3

input is a dictionary from int to int or list of int
the basic op is G s, retrieve the child nodes for s
this is then stuffed into the built-in convergence operator /
the rest is to, at each stage, prepend the parent node, flatten the results down to a vector, and dedupe them -- this is needed to make the answer actually converge
btw, for an extra three characters, you can have all the reachability lists:
  {G(?,/,)'G x}/G
1 2 3 4!(2 3 1;3 1 2;1 2 3;2 3 1)
  {H(?,/,)'H x}/H
0 1 2 3 4 5 6 7 8 9 10 11!(();();,2;9 3;1 7 8 9 3;3 6 9 4 8 1 7;4 8 1 7 9 3;,7;();3 9;();,7)

this is the same general idea, applied to the basic op of G G

This should be the accepted answer...

Python, 72 chars
def R(G,s):
 r=[s]
 for i in G:r+=sum((G[x]for x in r),[])
 print set(r)

Terribly inefficient because nodes can appear in r multiple times.  Fortunately, not a judging criterion.

You can shave 2 characters and make it even more inefficient by changing the empty list to r and += to +.

I mean += to =.

You can shave another character by changing the for loop to and exec statement and one-lining it: def R(g,s):r=[s];exec'r=sum((G[x]for x in r),r);'*len(G);print set(r)

Haskell, 64 bytes
import Data.List
n#v=nub$id=<<length n`take`iterate(>>=(n!!))[v]

Takes input as a zero-based list of lists, try it online!
Explanation / Ungolfed
The term vertices >>= (adjacencyList !!) takes a list of vertices, looks up all reachable vertices of them and returns them as a list.
So we repeatedly do this starting with the input vertex [v]
                       iterate(>>=(n!!))[v]

take as many elements from that list as there are nodes in the graph
         length n`take`

concatenate the result
    id=<<

and finally remove all the duplicates
nub$

.

Java 10, 130 characters
A curried lambda that takes the graph as a Map<Integer, List<Integer>> and an int start node. Output is returned as a Set<Integer>.
import java.util.*;

g->s->{var o=new TreeSet();o.add(s);for(var x:g.keySet())for(var n:new TreeSet(o))o.addAll(g.get(n));return o;}

Try It Online
This carries out a slightly stupid breadth-first search just past a maximum possible non-cyclical path length (the number of graph nodes).

Clojure, 52 bytes
#(nth(iterate(fn[A](set(mapcat % A)))[%2])(count %))

This implicitly assumes that all nodes have outgoing vertices.
54 bytes
#(loop[A[%2]B[]](if(= A B)A(recur(set(mapcat % A))A)))

The nifty part is the (mapcat % A), which uses the input argument {1 [2, 3], 2 [3], 3 [1], 4 [2]} as a function (given a key it returns the corresponding value) and concatenates all the ids together. Then it is just a matter of iterating this procedure until we have converged.

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:
Generate random PESEL number
From Wikipedia:

PESEL is the
  national identification number used in Poland since 1979. It always
  has 11 digits, identifies just one person and cannot be changed to
  another one.
It has the form of YYMMDDZZZXQ, where YYMMDD is the date of birth
  (with century encoded in month field), ZZZ is the personal
  identification number, X denotes sex (even number for females, odd
  number for males) and Q is a control digit, which is used to verify
  whether a given PESEL is correct or not.
Having a PESEL in the form of ABCDEF GHIJK, one can check the
  vailidity of the number by computing the following expression:
A*1 + B*3 + C*7 + D*9 + E*1 + F*3 + G*7 + H*9 + I*1 + J*3
Then the last digit of the result should be subtracted from 10. If the
  result of the last operation is not equal to the last digit of a given
  PESEL, the PESEL is incorrect. This system works reliably well for
  catching one-digit mistakes and digit swaps.

Provide a short program to generate random, valid PESEL number:

It has to be a PESEL a person born in either 20th or 21st century
The birth birth date has to be random but doesn't have to validate leap years or number of days in a month (i.e. the numbers representing the day number have to be between 01 and 31)
All valid PESELs in this date range (01.01.1990-31.12.2099) must be possible
The shortest code (i.e. complete program code), in bytes, wins.

How random? eg, must all digits vary, must eg all 20th century birthdays be possible, and no others? Seems like this can be subverted by solutions that just coin toss between male and female.

@bazzargh, good point - let it be a PESEL for a person born in either 20th or 21st century.

Actually my point is more that 'random' can mean 'one of a fixed set of choices'. If you pick a PESEL of A001100000Q then Q=10-A, it's still 'random', with a random date, but way less code. Saying that all valid PESELs for your date range must be possible blocks tricks like this.

@bazzargh Changed the question once again.

Please correct the algorithm: The current version allows the last digit to be 10. The Polish Wikipedia version uses a modulo 10 operation to get 0 in this case.

The gender entry uses the full range 0 to 9 to encode male and female (1 bit). What's the purpose of this "random noise"? Or are there further specification on the gender field that I have missed?

The century is encoded in the month field. This is neither specified in the question or links. For example, it is explained in the Polish Wikipedia article.

Please clarify the restrictions on the date. The question says, that all dates of the 20th and 21st century must be possible. It is unclear, if invalid dates are allowed. It makes a huge difference in a code golf competition, if the date has to be validated, e.g. excluding YYYY-02-29 with YYYY not being a leap year.

See http://en.wikipedia.org/wiki/PESEL for an explanation, in English, of the PESEL encoding.

The control digit is found by taking the remainder of the number modulus 10.   It is not found by subtraction.

@DavidCarraher: Missed that, the Polish version has a nice table instead.

@DavidCarraher: The result of the expression in the question is subtracted from 10 and then the control digit is the remainder of the number modulus 10.

Isn't that the same as finding the remainder of division by 10. (I.e. the subtraction is unnecessary.)

@DavidCarraher: 136 % 10 = 7 is different from (10 - (137 % 10)) % 10 = 3. (Of course there is room for optimization in the calculation of the control digit.)

you are correct (of course)!

Perl, 162 bytes
@a=map{$==rand 10}0..9;$"='';$a[5]%=2if($a[4]%=4)==3;"@a[4,5]"||$a[5]++;$a[3]=($a[2]%=4)%2?$a[3]%3:1+$a[3]%9;$f=9;for(@a){$x+=$f*$_;$f-=$f%10==7?4:2}print@a,$x%10

Ungolfed:
# Array with random digits
# ------------------------
@a = map { $= = rand 10} 0..9;
# do not insert a space, if arrays are interpolated into strings
$" = ''; #"

# Day correction
# --------------
# The day must be in the range of "01" to "31":
# * map first digit to "0" to "3": $a[4] %= 4
# * map second digit to "0" to "1" if first digit is "3"
$a[5] %= 2 if ($a[4] %= 4 ) == 3;
# * set day to "01" if day is "00"
"@a[4,5]" || $a[5]++;

# Month correction
# ----------------
# The month must be in the range "01" to "12" or "21" to "32"
# to get a valid month and century:
# * map the month to "00" to "39"
# * if the first digit is odd (catching both centuries at once)
#   * then map the second digit to "0" to "2"      (for months: 10..12)
#   * otherwise map the second digit to "1" to "9" (for months: 01-09)
$a[3] = ($a[2] %= 4) % 2 ? $a[3] % 3: 1 + $a[3] % 9;

# Calculate the control digit
# ---------------------------
# Because of the modulo 10 operations, the formula for the calculation
# of the control digit is rewritten from
# Q = (10 - ((A + 3B + 7C + 9D + E + 3F + 7G + 9H + I + J) % 10)) % 10
# to
# Q = (9A + 7B + 3C + D - E - 3F -7G - 9H - 11I - 11J) % 10
$f = 9;
for (@a) {
    $x += $f * $_;
    $f -= $f % 10 == 7 ? 4 : 2
}

# Print the result and control digit
print @a, $x % 10

# TEST section
# ------------

;$Q = $x % 10; # remember control digit in $Q

# Pretty print PESEL
print "\n\n",
  "YY MM DD ZZZ X Q\n",
  "@a[0,1] @a[2,3] @a[4,5] @a[6,7,8] $a[9] $Q\n";
print "\n";

# Pretty print the date
$month = "@a[2,3]";
$century = "??";
$century = "19" if $month >= 1 and $month <= 12;
$century = "20" if $month >= 21 and $month <= 32;
printf "Date: $century@a[0,1]-%02d-@a[4,5]\n", $month % 20;
print "\n";

# Pretty print the gender
print "Gender: ", $a[9] % 2 ? "male" : "female", "\n";
print "\n";

# Calculate the control date the official way
print "Control digit:\n";
$sum = 0;
$f = 0;
for (my ($i, $f) = (0, 1); $i<10; $i++, $f+=2) {
    $f %= 10;
    $f += 2 if $f == 5;
    printf "  $a[$i] * $f = %2d\n", $a[$i] * $f;
    $sum += $a[$i] * $f;
}
print "  ", "-" x 10, "\n";
printf "  %10d\n", $sum;
printf "  $Q = (10 - ($sum % 10)) % 10 = %d\n", (10 - ($sum % 10)) % 10;

Examples
83102570819

YY MM DD ZZZ X Q
83 10 25 708 1 9

Date: 1983-10-25

Gender: male

Control digit:
  8 * 1 =  8
  3 * 3 =  9
  1 * 7 =  7
  0 * 9 =  0
  2 * 1 =  2
  5 * 3 = 15
  7 * 7 = 49
  0 * 9 =  0
  8 * 1 =  8
  1 * 3 =  3
  ----------
         101
  9 = (10 - (101 % 10)) % 10 = 9

20233143600

YY MM DD ZZZ X Q
20 23 31 436 0 0

Date: 2020-03-31

Gender: female

Control digit:
  2 * 1 =  2
  0 * 3 =  0
  2 * 7 = 14
  3 * 9 = 27
  3 * 1 =  3
  1 * 3 =  3
  4 * 7 = 28
  3 * 9 = 27
  6 * 1 =  6
  0 * 3 =  0
  ----------
         110
  0 = (10 - (110 % 10)) % 10 = 0

Mathematica 247 270
A bit long but there are many details to take into consideration:

Allow any valid birth date between Jan. 1, 1900 and Dec. 31, 2099;  Feb. 29 included in leap years.
Pad all numbers left with zeros: e.g. Month 3 becomes "03" so any PESEL will have exactly 11 digits.
Add 20 to month if in 21st century (2000-2099)

Ungolfed
Below the components are named for convenience.
g:=Module[{year,month,day,centuryIncrement,id,controlDigit,pesel},
{year,month,day}=DatePlus[{1900,1,1},RandomInteger[73048]];
centuryIncrement=20*Boole[year>= 2000];
Print[Row@{{year,month,day},"  ",DateString[{year,month,day},{"MonthName"," ","Day",", ","Year"}]},
"\ncentury increment: ",centuryIncrement,
"\nID: ",id=PadLeft[IntegerDigits@RandomInteger[999],3],
"\nsex: ",sex=RandomInteger[1]];
f=Flatten[{{IntegerDigits@year,PadLeft[IntegerDigits[month+centuryIncrement],2],
PadLeft[IntegerDigits@day,2]},id,sex}][[3;;12]];
Print["control digit: ",controlDigit=Mod[10-IntegerDigits[Tr@Thread[Times[f,{1,3,7,9,1,3,7,9,1,3}]]][[-1]],10],
"\nPESEL: ",""<>ToString/@PadLeft[Append[f,controlDigit]]]]

Examples
g

{1931,2,9}  February 09, 1931
  century increment: 0
  ID: {0,8,8}
  sex: 0
  control digit: 9
  PESEL: 31020908809

g

{2067,6,27}  June 27, 2067
  century increment: 20
  ID: {9,0,8}
  sex: 0
  control digit: 1
  PESEL: 67262790801

g

{1967,9,5}  September 05, 1967
  century increment: 0
  ID: {5,0,0}
  sex: 0
  control digit: 2
  PESEL: 67090550002

Golfed
g:=Module[{y,m,d,i=IntegerDigits,p=PadLeft,r=RandomInteger},{y,m,d}=DatePlus[{1900,1,1},r[73048]];
f=Flatten[{{i@y,p[i[m+20*Boole[y>= 2000]],2],p[i@d,2]},p[i@r[999],3],r[1]}][[3;;12]];
""<>ToString/@p[Append[f,Mod[10-i[Tr@Thread[Times[f,{1,3,7,9,1,3,7,9,1,3}]]][[-1]],10]]]]

Mathematica, 157 chars
""<>ToString/@Join[#,{Mod[-#.{1,3,7,9,1,3,7,9,1,3},10]}]&@Flatten@{IntegerDigits[#,10,2]&/@RandomChoice@DateRange[{1990,1,1},{2099,12,31}],9~RandomInteger~4}

PHP, 151
echo($n=date("ymd",rand(-2e9,4e9)).rand(101,999).rand()%10).(10-($n[0]+3*$n[1]+7*$n[2]+9*$n[3]+$n[4]+3*$n[5]+7*$n[6]+9*$n[7]+$n[8]+3*$n[9])%10);

See it in action: http://ideone.com/DYeXf9

It doesn't generate valid PESEL number.

Oh, ok... fixing it.

The output it too long: 14 digits instead of 11.

How do you ensure the validity of a date?

Mathematica, 220
This generates random date between 1900-01-01 and 2099-12-31, but it does not check whether the number of days in the month is valid.
Value for gender ranges from 0 - 9.
This is as few characters as I could get it:
r=RandomInteger;a=r@9;b=r@9;m=r@11+1+r@1*20;c=Floor[m/10];d=m~Mod~10;n=r@30+1;e=Floor[n/10];f=n~Mod~10;g=r@9;h=r@9;i=r@9;j=r@9;k=Mod[10-Mod[a+3b+7c+9d+e+3f+7g+9h+i+3j,10],10];StringJoin[ToString/@{a,b,c,d,e,f,g,h,i,j,k}]
Sample output:
04020506179
34230487249
26321891950
45260298217
Ungolfed:
r=RandomInteger;

a=r@9; (*year*)
b=r@9;

month=r@11+1+r@1*20;
c=Floor[month/10];
d=month~Mod~10;

day=r@30+1;
e=Floor[day/10];
f=day~Mod~10;

g=r@9; (*personal ID*)
h=r@9;
i=r@9;

j=r@9; (*gender*)

k=Mod[10-Mod[a+3b+7c+9d+e+3f+7g+9h+i+3j,10],10]; (*control digit*)

StringJoin[ToString/@{a,b,c,d,e,f,g,h,i,j,k}]

day=r@30+1 assumes that any month can have 31 days?

Matlab, 156 bytes
a=datestr(693961+randi(73049),'yyyymmdd');a(5)=a(5)+2*(a(1)>49);A=a(3:8)-48;b=randi(10,1,4);[[A b mod(10-mod(sum(('1379137913'-48).*[A b]),10),10)]+48 '']

Ungolfed with some explanation:
a=datestr(693961+randi(73049),'yyyymmdd');
  -- generates date serial number in desired range and converts do string
a(5)=a(5)+2*(a(1)>49);
  -- modifies the first digit of the month if year >= 2000 (first digit >1)
A=a(3:8)-48;
  -- gets the "YYMMDD" part and converts from string to array of numbers
b=randi(10,1,4)-1;
  -- gets remaining 4 random digits ("ZZZX")
[[A b mod(10-mod(sum(('1379137913'-48).*[A b]),10),10)]+48 '']
  -- computes the last digit and converts the whole thing to string

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


text:
Let us make a quine maker!
You are to create a program, that, given another program, and a position, will make it a quine. Namely, it needs to insert an expression at that point that evaluates to a string that is the programs input. For example:
main=do
    putStrLn "Welcome to the open source program, would you like my source code?"
    (ans:_) <- getLine
    case ans of
        'y' -> putStrLn  --Quine goes here
        'n' -> putStrLn "Okay, Good bye"
        _  -> putStrLn "Unrecongnized command. Try again." >> main

Now if I told it to put the source code at (5,24) the result would be.
main=do
    putStrLn "Welcome to the open source program, would you like my source code?"
    (ans:_) <- getLine
    case ans of
        'y' -> putStrLn ((\a b->a++(show a)++" "++(show b)++b) "main=do\n    putStrLn \"Welcome to the open source program, would you like my source code?\"\n    (ans:_) <- getLine\n    case ans of\n        'y' -> putStrLn ((\\a b->a++(show a)++\" \"++(show b)++b) " ")--Quine goes here\n        'n' -> putStrLn \"Okay, Good bye\"\n        _  -> putStrLn \"Unrecongnized command. Try again.\" >> main\n")--Quine goes here
        'n' -> putStrLn "Okay, Good bye"
        _  -> putStrLn "Unrecongnized command. Try again." >> main

Clarifications:

The program you make and the type of programs it act upon may be different if you like.
Your program may get the position in the program and its source code however it sees fit. You may put the new source code where ever you see fit.
Obviously, the new program can't simply grab its source code from its file
You may only insert things at the position the user specifies (so you may not be able to include any new modules in the new program depending on target language)

This is code golf, so shortest answer wins!
Let us see how many different languages we can make quine makers for as well.

J - 73 char
Takes input on stdin, as the 0-origin index in characters and the source, separated by a newline. Introduces a copy of the program at the specified point as a string.
((".@{.~({.,}.,~'(',')',~(LF;''',LF,''')rplc~quote@])(}.~>:))i.&LF)1!:1]3

Explained by explosion:
(                                  )1!:1]3  NB. stdin
 (                           )i.&LF         NB. find the first newline
     {.~                                    NB. the index part of input
  ".@                                       NB. convert index to integer
                      (}.~>:)               NB. the source program part
        ({.,}.,~     )                      NB. program before and after index
                ...@]                       NB. program quoted properly

For example, given input
3
abcdef'ghij'
kl mn 0p1

the output is
abc('abcdef''ghij''',LF,'kl mn 0p1')def'ghij'
kl mn 0p1

because J uses Pascal-style strings: 'Isn''t this great?'

Haskell (390 Char)
import System.Environment
import Data.List
main = do
    [p] <- getArgs
    interact $ q (read p)
q :: (Int, Int) -> String -> String
q p j=case d p j of
    (f, s) -> b (f++i) (')':s)
d (l,c) j=case splitAt (l-1) (lines j) of
    (f, (t:s)) -> case splitAt c t of
        (r,y) -> ((unlines f)++r, y++"\n"++(unlines s))
b=(\a b->a++(show a)++" "++(show b)++b)
i="((\\a b->a++(show a)++\" \"++(show b)++b) "

Not very golfed. Just an example. This takes the position as a command line argument and source code as a standard input and puts the new source code as standard output.


text:
Evolution of the 'x'
Given is a board of variable size with a maximum size of 5 times 5 fields. Every field kann be filled with an 'x'. If it is not filled with an 'x', it is filled with an 'o'.
The starting state of every board is given (see below). With each board, 10 rounds have to be played (at max, conditions: see below) and the evolution of the x must be watched.
One round works the following way:

every 'x' spreads to orthogonally bordering fields, but dissapears itself
each time two 'x' are on one field, they neutralize each other

The evolution of all 'x' in each round has to happen simultaneously.
Example:
    o o o            o x o
    o x o     ->     x o x
    o o o            o x o

With each round of evolution, you have to see if the board gets emptied of 'x'.
Is it not empty, a repeating pattern could be present. If this is also not the case,
we give up the analysis of the evolution.
Additionally you have to print out the maximum percentage of x fields for every starting board (rounded down to whole numbers).
Input:
The input data can be found here (Pastebin)
This data contains 100 starting states. As already mentioned, the boards vary in size. The number of rows is stated with number n from 1 to 5, followed by n rows that contain only 'x' and 'o', represent the starting pattern. Every row of a board has 1 to 5 fields.
Output:
The complete result must be printed out, one printed row for each starting board in the following form:
    Round {0-10}: {repetition/empty/giveup}, {0-100} percent maximum-fill

Examples:
Example 1:
    Input: 2       Starting state: x o x
           xox                     x x
           xx

                          Round 1: x x o
                                   o x

                          Round 2: x o x
                                   o x

                          Round 3: o x o
                                   o o

                          Round 4: x o x   -> The pattern repeats:
                                   o x        It is the same as in round 2,
                                              therefore we stop. Maximum fill was
                                              in the starting state with four times 'x'
                                              of 5 fields altogether,
                                              so we have 4/5 = 80 %.

    Output: Round 4: repetition, 80 percent maximum-fill

Example 2:
    Input: 1       Starting state: x x
           xx

                          Round 1: x x    ->  We already have a repetition, because
                                              the pattern is the same as in the starting
                                              state. The board is always filled 100 %.

    Output: Round 1: repetition, 100 percent maximum-fill

After eight dayst I will mark the working answer with the fewest characters as the winner. Additionally i will post the correct output for the 100 starting boards (input).
You can use your prefered (programming/scripting/whatever) language.
Have fun!
PS: If you have questions, feel free to ask.
PPS: In respect of the original creators:
For people capable of speaking german, the question was taken from DO NOT CLICK IF YOU DO NOT WANT SPOILERS
here. Since the official time for completing the challenge has ended, I wanted to see if someone could come up with a short and elegant solution.
22.04.2014:
Challenge Done! Winner marked as accepted. Correct output:
    Round 10: giveup, 50 percent maximum-fill
    Round 5: empty, 66 percent maximum-fill
    Round 1: repetition, 100 percent maximum-fill
    Round 1: empty, 100 percent maximum-fill
    Round 4: repetition, 100 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 2: repetition, 60 percent maximum-fill
    Round 4: empty, 88 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 5: repetition, 80 percent maximum-fill
    Round 10: repetition, 80 percent maximum-fill
    Round 1: empty, 80 percent maximum-fill
    Round 3: repetition, 60 percent maximum-fill
    Round 4: repetition, 48 percent maximum-fill
    Round 9: empty, 41 percent maximum-fill
    Round 10: giveup, 92 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 88 percent maximum-fill
    Round 10: giveup, 76 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill
    Round 10: giveup, 40 percent maximum-fill
    Round 10: giveup, 100 percent maximum-fill
    Round 10: giveup, 71 percent maximum-fill
    Round 2: empty, 81 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 3: empty, 80 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 83 percent maximum-fill
    Round 7: repetition, 37 percent maximum-fill
    Round 9: repetition, 85 percent maximum-fill
    Round 5: repetition, 40 percent maximum-fill
    Round 5: repetition, 60 percent maximum-fill
    Round 4: empty, 80 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 4: repetition, 46 percent maximum-fill
    Round 6: repetition, 42 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 4: repetition, 70 percent maximum-fill
    Round 4: repetition, 80 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 4: repetition, 56 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 54 percent maximum-fill
    Round 10: giveup, 66 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 2: repetition, 40 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 7: empty, 85 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 70 percent maximum-fill
    Round 2: empty, 66 percent maximum-fill
    Round 1: empty, 66 percent maximum-fill
    Round 3: empty, 100 percent maximum-fill
    Round 3: empty, 66 percent maximum-fill
    Round 8: repetition, 42 percent maximum-fill
    Round 1: empty, 60 percent maximum-fill
    Round 2: repetition, 100 percent maximum-fill
    Round 2: repetition, 83 percent maximum-fill
    Round 4: repetition, 66 percent maximum-fill
    Round 6: repetition, 75 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 10: giveup, 56 percent maximum-fill
    Round 4: empty, 66 percent maximum-fill
    Round 6: repetition, 33 percent maximum-fill
    Round 3: empty, 57 percent maximum-fill
    Round 3: repetition, 100 percent maximum-fill
    Round 6: repetition, 73 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 6: repetition, 50 percent maximum-fill
    Round 10: giveup, 73 percent maximum-fill
    Round 5: empty, 80 percent maximum-fill
    Round 10: giveup, 61 percent maximum-fill
    Round 3: repetition, 53 percent maximum-fill
    Round 10: giveup, 33 percent maximum-fill
    Round 10: giveup, 80 percent maximum-fill
    Round 10: giveup, 63 percent maximum-fill
    Round 10: giveup, 70 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 7: repetition, 70 percent maximum-fill
    Round 10: repetition, 57 percent maximum-fill
    Round 10: giveup, 55 percent maximum-fill
    Round 6: repetition, 36 percent maximum-fill
    Round 4: repetition, 75 percent maximum-fill
    Round 10: giveup, 72 percent maximum-fill
    Round 10: giveup, 64 percent maximum-fill
    Round 10: giveup, 84 percent maximum-fill
    Round 10: giveup, 58 percent maximum-fill
    Round 10: giveup, 60 percent maximum-fill
    Round 10: giveup, 53 percent maximum-fill
    Round 4: repetition, 40 percent maximum-fill
    Round 4: empty, 40 percent maximum-fill
    Round 10: giveup, 50 percent maximum-fill
    Round 10: giveup, 68 percent maximum-fill

Please tag as either code-golf or code-challenge but not both. (It should be code-golf in this case).

Someone should change this into a well defined cellular automaton. :-)

Perl, 308, 304, 305, 293, 264, 262
Edit: A bug crept in after one of recent edits, causing wrong output for empty boards (test suite output was OK). Since Round 0 in given output format can mean only that there can be empty boards in the input (though none is in test suite), the bug had to be fixed. Quick fix meant byte count increase (by 1, actually) - not an option, of course. Therefore, I had to golf it a little bit more.
Run with -p (+1 added to count), reads from STDIN. Requires 5.014 because of r substitution modifier.
(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);for$n(0..10){$_="Round $n: ".($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty).", $m percent maximum-fill\n";@a=/g/?map{$_=$a[$i=$_];y//!/cr&(s/.//r.P^P.s/.$//r^$a[$i+1]^$a[$i-1])}0..$#a:last}

i.e.
# '-p' switch wraps code into the 'while(<>){....}continue{print}' loop,
# which reads a line from STDIN into $_, executes '....' and prints contents
# of $_. We use it to read board height and print current board's result.

# First line reads board's state into @a array, a line per element, at the same
# time replacing 'o' with 'x00', 'x' with '!' and chomping trailing newlines.
# '!' was chosen because it's just like 'x01' except 5th bit (which is not important)
# but saves several characters in source code.

# Note: array is prepended with an empty line, which automatically remains in this
# state during evolution, but saves us trouble of checking if actual (any non-empty)
# line has neighboring line below.

# %h hash and $m hold seen states and maximum fill percentage for current board,
# they are initialized to undef i.e empty and 0.

(@a,%h,$m)=('',map<>=~y/ox\n/\0!/rd,1..$_);

# /
# Then do required number of evolutions:

for$n(0..10){

# Stringify board state, i.e. concatenate lines with spaces ($") as separators.
# Calculate fill percentage - divide number of '!' by number of non-spaces.
# Note: using $. magick variable automatically takes care of rounding.
# Construct output string. It's not used if loop gets to next iteration.
# Check if current state was already seen (at the same time add it to %h)
# and if fill percentage is 0.

$_="Round $n: "
    .($h{$_="@a"}++?repetition:(($.=100*y/!///y/ //c)<$m?$.:$m=$.)?giveup:empty)
    .", $m percent maximum-fill\n";

# /
# Next is funny: if output string contains 'g' (of 'giveup' word), then evolve
# further, otherwise break-out of the loop.

    @a=/g/
        ?map{

# Do evolution round. Act of evolution for a given line is none other than
# XOR-ing 4 strings: itself shifted right, itself shifted left, line above, line
# below. Result of this operation is truncated to original length using bitwise '&'.
# Note, when shifting string right or left we prepend (append) not an ascii-0,
# but 'P' character. It's shorter, and 4th and 6th bits will be annihilated anyway.

            $_=$a[$i=$_];
            y//!/cr
            &(s/.//r.P
            ^P.s/.$//r
            ^$a[$i+1]
            ^$a[$i-1])
        }0..$#a
        :last
}

Wow, a solution so fast. I'm astonished. Since I'm not familiar with PERL (I have it installed though), how do I start your script with my input data?

@DevanLoper, e.g. perl -p x.pl < input.txt if data is in a file, or perl -p x.pl and feed line by line to test single entry (terminate with ctrl-D (ctrl-Z)). Remember to check your perl is 5.014 or newer.

Thanks VadimR, now it runs. But I have a different results in two lines concerning the printed fill percentage. But that could be rounding errors.

@DevanLoper, let's check it, which entry has different percentage?

VadimR, lines 23 and 25 are different. I have 40 and 71, you have 33 and 64. But its possible, that the error is on my side.

@DevanLoper, sorry, it's my error, percentage is taken from previous iteration. I'll fix it soon.

Bug fixed, + some bytes thrown away. Tests results match those from linked site. Technically, 11 rounds are run, but state of last round is not checked nor used. It's all for brevity. I placed loop breaking conditions in the beginning to catch 1 \n o input.

C# - 1164 chars
This is my first participation in code-golf so please be indulgent ;-)
I know, I am far off the best results - really amazing by the way!
But I thought I'd share my solution in C# anyway.
using System;using System.Collections.Generic;using System.IO;using System.Linq;using System.Net;class Program{static void Main(string[] args){new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt",@"D:\in.txt");var a=File.ReadAllLines(@"D:\in.txt");int l=0;while(l<a.Length){int n=Int32.Parse(a[l]);var b=a.Skip(l+1).Take(n).ToArray();var f=new List<string[]>{b};var d=0;string g=null;while(d<10){var s=f.Last();if(s.All(e=>e.All(c=>c=='o'))){g="empty";break;}var h=new string[n];for(int r=0;r<n;r++){var k="";for(int c=0;c<b[r].Length;c++){int x=0;try{if(s[r][c-1]=='x')x++;}catch{}try{if(s[r][c+1]=='x')x++;}catch{}try{if(s[r-1][c]=='x')x++;}catch{}try{if(s[r+1][c]=='x')x++;}catch{}k+=((x%2)==1)?'x':'o';}h[r]=k;}d++;f.Add(h);var w=false;for(int i=0;i<f.Count-1;i++){var m=f[i];if (!h.Where((t,y)=>t!=m[y]).Any())w=true;}if(w){g="repetition";break;}}if(d==10&&g==null)g="giveup";File.AppendAllLines(@"D:\out.txt",new[]{string.Format("Round {0}: {1}, {2} percent maximum-fill",d,g,f.Select(z=>{int t=0;int x=0;foreach(var c in z.SelectMany(s=>s)){t++;if(c=='x')x++;}return(int)Math.Floor((double)x/t*100);}).Concat(new[]{0}).Max())});l=l+n+1;}}}

Solely the using directives already count 97 characters - so I think it is going to be quite hard to achieve the rest within less than 200 characters.
It is a fairly iterative approach, making use of LINQ in many places.
I also included the downloading of the input file and writing of the output file into the code.
Here is one little more readable version:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;

class Program
{
    static void Main(string[] args)
    {
        // Download the file
        new WebClient().DownloadFile("http://mc.capgemini.de/challenge/in.txt", @"D:\in.txt");
        // Read of lines of downloaded file
        var a = File.ReadAllLines(@"D:\in.txt");
        // Line index in input file
        int l = 0;
        while (l < a.Length)
        {
            // Parse number of rows to take
            int n = Int32.Parse(a[l]);

            // Take the n rows
            var b = a.Skip(l + 1).Take(n).ToArray();
            var f = new List<string[]> { b };
            var d = 0;
            string g = null;
            while (d < 10)
            {
                // Last state consists only of o's? ->
                var s = f.Last();
                if (s.All(e => e.All(c => c == 'o')))
                {
                    g = "empty";
                    break;
                }
                // In h we will build up the new state
                var h = new string[n];
                // Loop through all rows of initial state
                for (int r = 0; r < n; r++)
                {
                    // This is our new row we will build up for the current state
                    var k = "";
                    // Count number of orthogonal adjacent x's
                    // And catch potential OutOfRangeExceptions
                    for (int c = 0; c < b[r].Length; c++)
                    {
                        int x = 0;
                        try { if (s[r][c - 1] == 'x') x++; }
                        catch { }
                        try { if (s[r][c + 1] == 'x') x++; }
                        catch { }
                        try { if (s[r - 1][c] == 'x') x++; }
                        catch { }
                        try { if (s[r + 1][c] == 'x') x++; }
                        catch { }
                        // Is number of adjacent x's odd? -> character will be 'x'
                        // otherwise -> 'o'
                        k += ((x % 2) == 1) ? 'x' : 'o';
                    }
                    // Add the new row to the current state
                    h[r] = k;
                }
                // Increase round count
                d++;
                // Add the new state to our state collection
                f.Add(h);
                // Now check, whether it is a repetition by comparing the last state (h) with all other states
                bool w = false;
                for (int i = 0; i < f.Count - 1; i++)
                {
                    var m = f[i];
                    if (!h.Where((t, y) => t != m[y]).Any())
                        w = true;
                }
                if (w)
                {
                    g = "repetition";
                    break;
                }
            }
            // Check whether we reached maximum AND the last round wasn't a repetition
            if (d == 10 && g == null)
                g = "giveup";
            // Now we append the final output row to our text file
            File.AppendAllLines(@"D:\out.txt",
                new[]
                    {
                        string.Format("Round {0}: {1}, {2} percent maximum-fill",
                        d,
                        g,
                        // Here we select all rates of x's per state
                        // and then grab the maximum of those rates
                        f.Select(z =>
                            {
                                int t=0;
                                int x=0;
                                foreach (char c in z.SelectMany(s => s))
                                {
                                    t++;
                                    if(c=='x')
                                        x++;
                                }
                                return (int) Math.Floor((double) x / t *100);
                            }).Concat(new[] {0}).Max())
                    });
            // finally we shift our index to the next (expected) number n in the input file
            l = l + n + 1;
        }
    }
}

Short, shorter, Ben's Solution. You've created such a micro of a solution thinking in C# terms...

J - 275 char
Oh, all these I/O specifications! Such a shamefully large score for J, in the end. Takes input on STDIN with a trailing newline, and assumes there aren't any carriage returns (\r) in the input. Here's the result of applying it to the sample input file in the question.
stdout;,&LF&.>}:(".@{~&0(('Round ',":@(#->/@t),': ',(empty`repetition`giveup{::~2<.#.@t=.11&=@#,0={:),', ',' percent maximum-fill',~0":>./)@(100*1&=%&(+/"1)_&~:)@,.@(a=:(a@,`[@.(e.~+.10<#@[)(_*_&=)+[:~:/((,-)(,:|.)0 1)|.!.0=&1){:)@,:@('ox'&i.^_:)@{.;$: ::]@}.)}.)];._2[1!:1]3

Ungolfed: (I may add a more thorough and J-newbie-friendly explanation later.)
input   =: ];._2 [ 1!:1]3
convert =: 'ox'&i. ^ _:               NB. 'x'=>1  'o'=>0  else=>infinity
spread  =: ((,-)(,:|.)0 1) |.!.0 =&1  NB. x spreading outwards
cover   =: (_*_&=) + [: ~:/ spread    NB. collecting x`s and removing tiles not on board
iterate =: (iterate@, ` [ @. (e.~ +. 10<#@[) cover) {:
percent =: 100 * 1&= %&(+/"1) _&~:    NB. percentage of x at each step
max     =: 0 ": >./
stat    =: 11&=@# , 0={:              NB. information about the simulation
ending  =: empty`repetition`giveup {::~ 2 <. #.@stat   NB. how simulation ended
round   =: ": @ (# - >/@stat)         NB. round number
format  =: 'Round ', round, ': ', ending, ', ', ' percent maximum-fill',~ max
evolvex =: format @ percent@,. @ iterate@,: @ convert
joinln  =: ,&LF &.>
nlines  =: ". @ {~&0
remain  =: }.
stdout ; joinln }: (nlines (evolvex@{. ; $: ::]@}.) remain) input

The $: part makes the main body recurse over the input (a terribly inconvenient form for J to parse), applying the @ daisy-chain over each section. nlines finds the number of lines for the next board.
The action on each board (evolvex) is neat: iterate (called a in the golf) constructs a list of each iteration of the simulation until we hit either something seen before or too many steps. Then percent@,. calculates the percentage of filled square in each result, and format runs some statistics (stat, called t in the golf) to figure out how the simulation ended, which percentage was the greatest, and so on, before formatting all of that into a string.
Finally, }: takes care of some garbage before ; joinln joins all of the individual board outputs into one newline-separated string.

Hi algorithmshark, could you please provide instructions on how to start your script from the command line with a .txt file as input parameter? Thanks!

@DevanLoper That reminds me, I forgot to make it output to stdout; added that correction. It should work the standard way now: jconsole golf.ijs < input.txt.

Thanks for the info, but it still does not print out any output for me, even with your code changed.

@DevanLoper The problem appears to be my use of v as a name, which for whatever reason is not allowed in scripts. (I had been running the snippet in the REPL.) Changing it to a appears to work.

@algoshark It could be me, but I can still not get it to print me anything out.


text:
Gravity Controls
Your task is to find the total destination of objects that are falling to a planet, you will get inputs like this:
7
...#...
.......
#..O..#
.......
...#...
.......
.......

where O is the planet and # are the objects, note that the planet will attract objects from the for basic directions(NEWS). You should output:
    #
   #O#
    #

i.e the objects after reaching their destination.
The first number given as an input is the length of the grid(nxn), in the above example it is 7.
The object should always move in the shortest direction(note that the allowed directions are only horizontal and vertical; the object can't move diagonally)
If an object is equidistant from two directions it should go in a clock wise direction:
    ..#
    ...
    O..

Will reach this side:
    ...
    ...
    O#.

If an object collides with the planet, it will stop. If it collides with another object they become one object,
 4
 .#..
 #...
 ....
 .O..

would become:
  ....
  ....
  .#..
  .O..

One final example:
6
..#...
.#....
......
.#O...
....#.
......

Output:
......
......
..#...
.#O#..
......
......

Note: You should output the final shape, so all outputs are accepted as long as they show the final shape of the planet.
for example for this input:
...#
....
.O..
....

Should output:
O#

or
....
....
.O#.
....

Both of these are accepted.
This is code-golf  so the shortest answer will win
Note 2:
As you may have noticed a . represents vaccum so the shortest path is the shortest number of dots.
For example:
.#.
...
.O.

Is not accepted to be
O#

since the shortest path is vertical.
Note3:
The object should always move to be in the same line with the planet in one of the four directions(choosing the shortest)
     |<#
     |
     |
-----O------
     |

Restrictions:
2<=n<=100

What are the possible input sizes?

Please clarify "shortest direction."

@KenA I think it could be rephrased like: objects travel diagonally towards the planet until they are in line with the planet (after which they'll move straight towards the planet); if an object ends up touching the the planet diagonally, move one final step in counter-clockwise direction. This should lead to the same result as the OP's specification. But clarification by the OP would be nice.

I noticed your example above has some trailing whitespace at the end of some lines. Is it safe to assume the same may be true of the input the program is expected to handle?

@skib no. It might be a typo but the inputs do not have trailing whitespace.

@Mhmd In your fourth example the result has an object on the left, right and top. In order to get the one at the right it moved up one row, which would be incorrect since that is counter clockwise, shouldnt it be at the bottom?

@TeunPronk no because it only has to move up by 1 unit, but would have to move to the left by 2 units. So the right side is closer to the object than the bottom.

@m.buettner Yes but he has to move up 1 unit and then 1 unit to the left, which is still 2 steps

@TeunPronk hm, interesting. by this interpretation, every object that is not in line with the planet is equidistant from two final positions. I figured the OP meant that the object first moves to be in line with the planet along the shorter axis. But he should probably clarify that.

Perl, 156 153 148
$n=$_+1;
s/.+\n//;
$o=index$_,O;
$x=$o%$n-$-[0]%$n,
pos=$o+(($==($o-$-[0])/$n)&&$x/$=>-1&&$x/$=<=1?$=>0?-$n:$n:0<=>$x),
s/\G./x/ while s/#/./;
y/x/#/

Newlines for readability. Run with -0777p (5 added to count), input through STDIN.
More readable:
$n=$_+1;
s/.+\n//;
$o=index$_,O;
while(s/#/./){
    $x=$o%$n-$-[0]%$n;
    $==($o-$-[0])/$n;
    pos=$o+(
        $=
        &&$x/$=>-1
        &&$x/$=<=1
            ?$=>0
                ?-$n
                :$n
            :0<=>$x

    );
    s/\G./x/
}
y/x/#/

Wow oO =) more explanation would be nice for those who aren't intimately familiar with Perl's re engine and special variables.

@skibrianski, thanks. Though I did nothing special and it was easier for me to answer after notes were added to the OP, you are right: we should document our code.

What's maybe not obvious at first glance is using $= 'magick' variable (which can be only integer - saves us 5 characters 'int()'), and using \G anchor in search pattern. Here we set its position by assigning to pos function (whose default argument is $_).

Mathematica, 206 bytes
f=(m=Characters@StringSplit@#;o=#-Join@@m~(p=Position)~"O"&/@m~p~"#";h=If[MemberQ[#3/@o,{m_,n_}/;m#<0&&m#<=n#2<-m#],"#",e]&;{e=".",h[1,1,#&],e,n="\n",h[1,-1,r=Reverse],"O",h[-1,1,r],n,e,h[-1,-1,#&],e}<>"")&

Somewhat more readable:
f[input_] := (
  map = Characters @ StringSplit @ input;
  planet = Flatten[Position[map, "O"]];
  objects = Map[# - planet &, Position[map, "#"]];
  helper[pattern_] := If[
    Length[Position[objects, pattern]] > 0,
    "#",
    "."
  ];
  StringJoin[{
    ".", h[{m_, n_} /; m < 0 && m <= n < -m], ".", "\n",
    h[{m_, n_} /; n < 0 && n < m <= -n], "O", h[{m_, n_} /; n > 0 && -n <= m < n], "\n",
    ".", h[{m_, n_} /; m > 0 && -m < n <= m], "."
  }]
);

As you can see, I only take a single input which is the string containing the input map. This is because I wouldn't use the size integer anyway. If you insist on the input format, I can change the input string to the second argument for one more character.
As for the algorithm, I'm just collecting all the {Δx, Δy} pairs of the objects and look for one pair in each quadrant with the conditions passed to h. I suspect this is also the part that could be golfed down further.

I didn't know you were a Mathematica enthusiast as well!

@AndrewCheong I suppose that comes naturally when you're a software developer studying physics. ;)

perl, 270 chars
3 steps: 1) find the planet and satellites in the input, 2) determine quadrant for each satellite, 3) output
sub _{"#"}$D=<>;$\=$/;for$L(1..$D){for$M(1..$D){$/=\1;$_=<>;$p=$M,$q=$L if/O/;push@s,[$M,$L] if/#/}$/=$\;<>}for(@s){$x=$_->[0]-$p,$y=$_->[1]-$q;($x<0&&$x<$y&&$y<=-$x?$l:$x>0&&-$x<=$y&&$y<$x?$r:$y<0&&$y<=$x&&$x<-$y?$u:$d)=_}$_=$l?" #":_;$u&&print;print $l."O$r";$d&&print

Less golfed:
sub _{"#"}
$D=<>;
$\=$/;
for$L(1..$D){
  $/=\1;
  for$M(1..$D){
    $_=<>;
    $p=$M,$q=$L if/O/;
    push@s,[$M,$L] if/#/;
  }
  $/=$\;
  <>
}

for(@s){
  $x=$_->[0]-$p,$y=$_->[1]-$q;

  ($x<0&&$x<$y&&$y<=-$x ? $l :
   $x>0&&-$x<=$y&&$y<$x ? $r :
   $y<0&&$y<=$x&&$x<-$y ? $u : $d)=_;
}

$_=$l?" #":_;
$u && print;
print$l."O$r";
$d && print;