text:
To Vectory! – The Vector Racing Grand Prix

User CarpetPython posted a new take on this problem which puts a much bigger focus on heuristic solutions, due to an increased search space. I personally think that challenge is much nicer than mine, so consider giving that one a try!

Vector racing is an addictive game that can be played with a pen and a sheet of square-ruled paper. You draw an arbitrary racetrack on the paper, define a start and end and then you steer your point-sized car in a turn-based manner. Get to the end as fast as you can, but be careful not to end up in a wall!
The Track

The map is a two dimensional grid, where each cell has integer coordinates.
You move on the grid cells.
Each grid cell is either part of the track or it's a wall.
Exactly one track cell is the starting coordinate.
At least one track cell is designated as the goal. Landing on any of these completes the race. Multiple goal cells are not necessarily connected.

Steering the Car
Your car starts at a given coordinate and with velocity vector (0, 0). In each turn, you may adjust each component of the velocity by ±1 or leave it as is. Then, the resulting velocity vector is added to your car's position.
A picture may help! The red circle was your position last turn. The blue circle is your current position. Your velocity is the vector from the red to the blue circle. In this turn, depending on how you adjust your velocity, you may move to any of the green circles.

If you land in a wall, you lose immediately.
Your task
You guessed it: write a program which, given a racetrack as input, steers the car to one of the goal cells in as few turns as possible. Your solution should be able to deal reasonably well with arbitrary tracks and not be specifically optimised towards the test cases provided.
Input
When your program is invoked, read from stdin:
target
n m
[ASCII representation of an n x m racetrack]
time

target is the maximum number of turns you may take to complete the track, and time is your total time budget for the track, in seconds (not necessarily integer). See below for details about timing.
For the newline-delimited track, the following characters are used:

# – wall
S – the start
* – a goal
. – all other track cells (i.e. road)

All cells outside the n x m grid provided are implied to be walls.
The coordinate origin is in the top left corner.
Here is a simple example:
8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###

Using 0-based indexing, the starting coordinate would be (0,4).
After every move you will receive further input:
x y
u v
time

Where x, y, u, v are all 0-based integers. (x,y) is your current position and (u,v) is your current velocity. Note that x+u and/or y+v could be out of bounds.
time is whatever is left of your time budget, in seconds. Feel free to ignore this. This is only for participants who really want to take their implementation to the time limit.
When the game is over (because you've landed in a wall, moved out of bounds, exceeded target turns, ran out of time or reached the goal), you'll receive an empty line.
Output
For each turn, write to stdout:
Δu Δv

where Δu and Δv each are one of -1, 0, 1. This will be added to (u,v) to determine your new position. Just to clarify, the directions are as follows
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)

An optimal solution for the above example would be
1 0
1 -1
1 0

Note that the controller does not attach itself to stderr, so you're free to use it for any sort of debug output you may need while developing your bot. Please remove/comment out any such output in your submitted code, though.
Your bot may take half a second to respond in each single turn. For turns that take longer, you will have a time budget (per track) of target/2 seconds. Every time a turn takes longer than half a second, the additional time will be subtracted from your time budget. When your time budget hits zero the current race will be aborted.
New: For practical reasons, I have to set a memory limit (since memory seems to be more limiting than time for reasonable track sizes). Therefore, I will have to abort any test run where the racer uses more than 1GB of memory as measured by Process Explorer as Private Bytes.
Scoring
There is a benchmark of 20 tracks. For each track:

If you complete the track, your score is the number of moves you need to reach a goal cell divided by target.
If you run out of time/memory or don't reach the goal before target turns have elapsed or you land in a wall/out of bounds at any time, your score is 2.
If your program is not deterministic, your score is the average over 10 runs on that track (please state this in your answer).

Your overall score is the sum of the individual track scores. Lowest score wins!
Furthermore, every participant may (and is strongly encouraged to) provide an additional benchmark track, which will be added to the official list. Previous answers will be re-evaluated including this new track. This is to make sure that no solution is tailored too closely to the existing test cases and to account for interesting edge cases I might have missed (but which you may spot).
Tie breaking
Now that there is already an optimal solution, this will probably be the main factor for participants' scores.
If there is a tie (due to several answers solving all tracks optimally or otherwise), I will add additional (larger) test cases to break the tie. To avoid any human bias when creating those tie-breakers, these will be generated in a fixed manner:

I will increase the side length n by 10 compared to the last track generated this way. (I may skip sizes if they don't break the tie.)
The basis is this vector-graphic
This will be rasterised at the desired resolution using this Mathematica snippet.
The start is in the top left corner. In particular, it will be the left-most cell of the top-most row of that end of the track.
The goal is in the bottom right corner. In particular, it will be the right-most cell of the bottom-most row of that end of the track.
The target will 4*n.

The final track of the initial benchmark was already generated like this, with n = 50.
The Controller
The program that tests the submissions is written in Ruby and can be found on GitHub along with the benchmark file I'll be using. There is also an example bot called randomracer.rb in there, which simply picks random moves. You can use its basic structure as a starting point for your bot to see how the communication works.
You can run your own bot against a track file of your choice as follows:
ruby controller.rb track_file_name command to run your racer

e.g.
ruby controller.rb benchmark.txt ruby randomracer.rb

The repository also contains two classes Point2D and Track. If your submission is written in Ruby, feel free to reuse those for your convenience.
Command-line switches
You can add command-line switches -v, -s, -t before the benchmark's file name. If you want to use multiple switches, you can also do, for instance, -vs. This is what they do:
-v (verbose): Use this to produce a little more debug output from the controller.
-s (silent): If you prefer to keep track of your position and velocity yourself and don't care about the time budget, you can switch off those three lines of output each turn (sent to your submission) with this flag.
-t (tracks): Lets you select individual tracks to be tested. E.g. -t "1,2,5..8,15" would test tracks 1, 2, 5, 6, 7, 8 and 15 only. Thanks a lot to Ventero for this feature and the options parser.
Your submission
In summary, please include the following in your answer:

Your score.
If you're using randomness, please state this, so I can average your score over multiple runs.
The code for your submission.
The location of a free compiler or interpreter for your language of choice that runs on a Windows 8 machine.
Compilation instructions if necessary.
A Windows command-line string to run your submission.
Whether your submission requires the -s flag or not.
(optionally) A new, solvable track which will be added to the benchmark. I will determine a reasonable target for your track manually. When the track is added to the benchmark, I'll edit it out of your answer. I reserve the right to ask you for a different track (just in case you add an disproportionally large track, include obscene ASCII art in the track, etc.). When I add the test case to the benchmark set, I'll replace the track in your answer with a link to the track in the benchmark file to reduce the clutter in this post.

As you can see, I'll be testing all submissions on a Windows 8 machine. If there is absolutely no way to get your submission running on Windows, I can also try on a Ubuntu VM. This will be considerably slower though, so if you want to max out the time limit, make sure your program runs on Windows.
May the best driver emerge vectorious!
But I wanna play!
If you want to try out the game yourself to get a better feel for it, there is this implementation. The rules used there are slightly more sophisticated, but it is similar enough to be useful, I think.
Leaderboard
Last updated: 01/09/2014, 21:29 UTC
Tracks in benchmark: 25
Tie-breaker sizes: 290, 440

6.86688 – Kuroi Neko
8.73108 – user2357112 - 2nd submission
9.86627 – nneonneo
10.66109 – user2357112 - 1st submission
12.49643 – Ray
40.0759 – pseudonym117 (probabilistic)

Detailed test results. (The scores for probabilistic submissions have been determined separately.)

C++11 - 6.66109
Yet another breadth first search implementation, only optimized.
It must be run with the -s option.
Its input is not sanitized at all, so wrong tracks might turn it into a pumpkin.
I tested it with Microsoft Visual C++ 2013, release build with the default /O2 flag (optimize for speed).
DOES build OK with g++ and the Microsoft IDE.
My barebone memory allocator is a piece of crap, so don't expect it to work with other STL implementations of unordered_set!
#include <cstdint>
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#include <unordered_set>

#define MAP_START 'S'
#define MAP_WALL  '#'
#define MAP_GOAL  '*'

#define NODE_CHUNK_SIZE   100 // increasing this will not improve performances
#define VISIT_CHUNK_SIZE 1024 // increasing this will slightly reduce mem consumption at the (slight) cost of speed

#define HASH_POS_BITS 8 // number of bits for one coordinate
#define HASH_SPD_BITS (sizeof(size_t)*8/2-HASH_POS_BITS)

typedef int32_t tCoord; // 32 bits required to overcome the 100.000 cells (insanely) long challenge

// basic vector arithmetics
struct tPoint {
    tCoord x, y;
    tPoint(tCoord x = 0, tCoord y = 0) : x(x), y(y) {}
    tPoint operator+ (const tPoint & p) { return tPoint(x + p.x, y + p.y); }
    tPoint operator- (const tPoint & p) { return tPoint(x - p.x, y - p.y); }
    bool operator== (const tPoint & p) const { return p.x == x && p.y == y;  }
};

// a barebone block allocator. Improves speed by about 30%
template <class T, size_t SIZE> class tAllocator
{
    T * chunk;
    size_t i_alloc;
    size_t m_alloc;
public:
    typedef T                 value_type;
    typedef value_type*       pointer;
    typedef const value_type* const_pointer;
    typedef std::size_t       size_type;
    typedef value_type&       reference;
    typedef const value_type& const_reference;
    tAllocator()                                              { m_alloc = i_alloc = SIZE; }
    template <class U> tAllocator(const tAllocator<U, SIZE>&) { m_alloc = i_alloc = SIZE; }
    template <class U> struct rebind { typedef tAllocator<U, SIZE> other; };
    pointer allocate(size_type n, const_pointer = 0)
    {
        if (n > m_alloc) { i_alloc = m_alloc = n; }      // grow max size if request exceeds capacity
        if ((i_alloc + n) > m_alloc) i_alloc = m_alloc;  // dump current chunk if not enough room available
        if (i_alloc == m_alloc) { chunk = new T[m_alloc]; i_alloc = 0; } // allocate new chunk when needed
        T * mem = &chunk[i_alloc];
        i_alloc += n;
        return mem;
    }
    void deallocate(pointer, size_type) { /* memory is NOT released until process exits */ }
    void construct(pointer p, const value_type& x) { new(p)value_type(x); }
    void destroy(pointer p) { p->~value_type(); }
};

// a node in our search graph
class tNode {
    static tAllocator<tNode, NODE_CHUNK_SIZE> mem; // about 10% speed gain over a basic allocation
    tNode * parent;
public:
    tPoint pos;
    tPoint speed;
    static tNode * alloc (tPoint pos, tPoint speed, tNode * parent) { return new (mem.allocate(1)) tNode(pos, speed, parent); }
    tNode (tPoint pos = tPoint(), tPoint speed = tPoint(), tNode * parent = nullptr) : parent(parent), pos(pos), speed(speed) {}
    bool operator== (const tNode& n) const { return n.pos == pos && n.speed == speed; }
    void output(void)
    {
        std::string output;
        tPoint v = this->speed;
        for (tNode * n = this->parent ; n != nullptr ; n = n->parent)
        {
            tPoint a = v - n->speed;
            v = n->speed;
            std::ostringstream ss;  // a bit of shitty c++ text I/O to print elements in reverse order
            ss << a.x << ' ' << a.y << '\n';
            output = ss.str() + output;
        }
        std::cout << output;
    }
};
tAllocator<tNode, NODE_CHUNK_SIZE> tNode::mem;

// node queueing and storing
static int num_nodes = 0;
class tNodeJanitor {
    // set of already visited nodes. Block allocator improves speed by about 20%
    struct Hasher { size_t operator() (tNode * const n) const
    {
        int64_t hash = // efficient hashing is the key of performances
            ((int64_t)n->pos.x   << (0 * HASH_POS_BITS))
          ^ ((int64_t)n->pos.y   << (1 * HASH_POS_BITS))
          ^ ((int64_t)n->speed.x << (2 * HASH_POS_BITS + 0 * HASH_SPD_BITS))
          ^ ((int64_t)n->speed.y << (2 * HASH_POS_BITS + 1 * HASH_SPD_BITS));
        return (size_t)((hash >> 32) ^ hash);
        //return (size_t)(hash);
    }
    };
    struct Equalizer { bool operator() (tNode * const n1, tNode * const n2) const
        { return *n1 == *n2; }};
    std::unordered_set<tNode *, Hasher, Equalizer, tAllocator<tNode *, VISIT_CHUNK_SIZE>> visited;
    std::queue<tNode *> queue; // currently explored nodes queue
public:
    bool empty(void) { return queue.empty();  }
    tNode * dequeue() { tNode * n = queue.front(); queue.pop(); return n; }
    tNode * enqueue_if_new (tPoint pos, tPoint speed = tPoint(0,0), tNode * parent = nullptr)
    {
        tNode signature (pos, speed);
        tNode * n = nullptr;
        if (visited.find (&signature) == visited.end()) // the classy way to check if an element is in a set
        {
            n = tNode::alloc(pos, speed, parent);
            queue.push(n);
            visited.insert (n);
num_nodes++;
        }
        return n;
    }
};

// map representation
class tMap {
    std::vector<char> cell;
    tPoint dim; // dimensions
public:
    void set_size(tCoord x, tCoord y) { dim = tPoint(x, y); cell.resize(x*y); }
    void set(tCoord x, tCoord y, char c) { cell[y*dim.x + x] = c; }
    char get(tPoint pos)
    {
        if (pos.x < 0 || pos.x >= dim.x || pos.y < 0 || pos.y >= dim.y) return MAP_WALL;
        return cell[pos.y*dim.x + pos.x];
    }
    void dump(void)
    {
        for (int y = 0; y != dim.y; y++)
        {
            for (int x = 0; x != dim.x; x++) fprintf(stderr, "%c", cell[y*dim.x + x]);
            fprintf(stderr, "\n");
        }
    }
};

// race manager
class tRace {
    tPoint start;
    tNodeJanitor border;
    static tPoint acceleration[9];
public:
    tMap map;
    tRace ()
    {
        int target;
        tCoord sx, sy;
        std::cin >> target >> sx >> sy;
        std::cin.ignore();
        map.set_size (sx, sy);
        std::string row;
        for (int y = 0; y != sy; y++)
        {
            std::getline(std::cin, row);
            for (int x = 0; x != sx; x++)
            {
                char c = row[x];
                if (c == MAP_START) start = tPoint(x, y);
                map.set(x, y, c);
            }
        }
    }

    // all the C++ crap above makes for a nice and compact solver
    tNode * solve(void)
    {
        tNode * initial = border.enqueue_if_new (start);
        while (!border.empty())
        {
            tNode * node = border.dequeue();
            tPoint p = node->pos;
            tPoint v = node->speed;
            for (tPoint a : acceleration)
            {
                tPoint nv = v + a;
                tPoint np = p + nv;
                char c = map.get(np);
                if (c == MAP_WALL) continue;
                if (c == MAP_GOAL) return new tNode (np, nv, node);
                border.enqueue_if_new (np, nv, node);
            }
        }
        return initial; // no solution found, will output nothing
    }
};
tPoint tRace::acceleration[] = {
    tPoint(-1,-1), tPoint(-1, 0), tPoint(-1, 1),
    tPoint( 0,-1), tPoint( 0, 0), tPoint( 0, 1),
    tPoint( 1,-1), tPoint( 1, 0), tPoint( 1, 1)};

#include <ctime>
int main(void)
{
    tRace race;
    clock_t start = clock();
    tNode * solution = race.solve();
    std::cerr << "time: " << (clock()-start)/(CLOCKS_PER_SEC/1000) << "ms nodes: " << num_nodes << std::endl;
    solution->output();
    return 0;
}

Results
 No.       Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1       37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2       38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3       33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4       10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5        9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6       15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7       17 x 8        16   0.31250   Racer reached goal at ( 14, 0) in 5 turns.
  8       19 x 13       18   0.27778   Racer reached goal at ( 0, 11) in 5 turns.
  9       60 x 10      107   0.14953   Racer reached goal at ( 0, 6) in 16 turns.
 10       31 x 31      106   0.23585   Racer reached goal at ( 27, 0) in 25 turns.
 11       31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12       50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13      100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14       79 x 63      242   0.24380   Racer reached goal at ( 3, 42) in 59 turns.
 15       26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16       17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17       50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18       10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19       55 x 55       45   0.17778   Racer reached goal at ( 50, 26) in 8 turns.
 20      101 x 100     100   0.14000   Racer reached goal at ( 99, 99) in 14 turns.
 21   100000 x 1         1   1.00000   Racer reached goal at ( 0, 0) in 1 turns.
 22       50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
 23      290 x 290    1160   0.16466   Racer reached goal at ( 269, 265) in 191 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:                 6.66109

Performances
That crappy C++ language has a knack to make you jump through hoops just to move a matchstick. However, you can whip it into producing relatively fast and memory-efficient code.
Hashing
Here the key is to provide a good hash table for the nodes. That is by far the dominant factor for execution speed.
Two implementations of unordered_set (GNU and Microsoft) yielded a 30% execution speed difference (in favor of GNU, yay!).
The difference is not really surprising, what with the truckloads of code hidden behind unordered_set.
Out of curiosity, I did some stats on the final state of the hash table.
Both algorithms end up with nearly the same bucket/elements ratio, but repartition varies:
for the 290x290 tie breaker, GNU gets an average of 1.5 elements per non empty bucket, while Microsoft is at 5.8 (!).
Looks like my hashing function is not very well randomized by Microsoft... I wonder if the  guys in Redmond did really benchmark their STL, or maybe my use case just favors the GNU implementation...
Sure, my hashing function is nowhere near optimal. I could have used the usual integer mixing based on multiple shift/muls but a hash-efficient function takes time to compute.
It appears the number of hash table queries is very high compared with the number of insertions. For instance, in the 290x290 tie breaker, you have about 3.6 million insertions for 22.7 million queries.
In this context, a suboptimal but fast hashing yields better performances.
Memory allocation
Providing an efficient memory allocator comes second. It improved performances by about 30%. Whether it is worth the added crap code is debatable :).
The current version uses between 40 and 55 bytes per node.
The functional data require 24 bytes for a node (4 coordinates and 2 pointers).
Due to the insane 100.000 lines test case, coordinates have to be stored in 4 bytes words, otherwise you could gain 8 bytes by using shorts (with a max coordinate value of 32767).
The remaining bytes are mostly consumed by the unordered set's hash table. It means the data handling actually consumes a bit more than the "useful" payload.
And the winner is...
On my PC under Win7, the tie breaker (case 23, 290x290) is solved by the worst version (i.e. Microsoft compiled) in about 2.2 seconds, with a memory consumption of about 185 Mb.
For comparison, the current leader (python code by user2357112) takes a bit more than 30 seconds and consumes about 780 Mb.
Controller issues
I'm not quite sure I might be able to code in Ruby to save my life.
However, I spotted and hacked two problems out of the controller code:
1) map reading in track.rb
With ruby 1.9.3 installed, the track reader would croak about shift.to_i not being available for string.lines.
After a long bit of wading through the online Ruby documentation I gave up on strings and used an intermediate array instead, like so (right at the begining of the file):
def initialize(string)
    @track = Array.new;
    string.lines.each do |line|
        @track.push (line.chomp)
    end

2) killing ghosts in controller.rb
As other posters have already noted, the controller sometimes tries to kill processes that have already exited. To avoid these disgracious error outputs, I simply handled the exception away, like so (around line 134):
if silent
    begin # ;!;
        Process.kill('KILL', racer.pid)
    rescue Exception => e
    end

Test case
To defeat the brute force approach of the BFS solvers, the worst track is the opposite of the 100.000 cells map: a completely free area with the goal as far from the start as possible.
In this example, a 100x400 map with the goal in the upper left corner and the start in the lower right.
This map has a solution in 28 turns, but a BFS solver will explore millions of states to find it (mine counted 10.022.658 states visited, took about 12 seconds and peaked at 600 Mb !).
With less than half the surface of the 290x290 tie breaker, it requires about 3 times more node visits. On the other hand, a heuristic / A* based solver should defeat it easily.
30
100 400
*...................................................................................................
....................................................................................................
                          < 400 lines in all >
....................................................................................................
....................................................................................................
...................................................................................................S

Bonus: an equivalent (but somewhat less efficient) PHP version
This is what I started with, before the inherent language slowness convinced me to use C++.
PHP internal hash tables don't seem as efficient as Python's, at least in this particular case :).
<?php

class Trace {
    static $file;
    public static $state_member;
    public static $state_target;
    static function msg ($msg)
    {
        fputs (self::$file, "$msg\n");
    }

    static function dump ($var, $msg=null)
    {
        ob_start();
        if ($msg) echo "$msg ";
        var_dump($var);
        $dump=ob_get_contents();
        ob_end_clean();
        fputs (self::$file, "$dump\n");
    }

    function init ($fname)
    {
        self::$file = fopen ($fname, "w");
    }
}
Trace::init ("racer.txt");

class Point {
    public $x;
    public $y;

    function __construct ($x=0, $y=0)
    {
        $this->x = (float)$x;
        $this->y = (float)$y;
    }

    function __toString ()
    {
        return "[$this->x $this->y]";
    }

    function add ($v)
    {
        return new Point ($this->x + $v->x, $this->y + $v->y);
    }

    function vector_to ($goal)
    {
        return new Point ($goal->x - $this->x, $goal->y - $this->y);
    }
}

class Node {
    public $posx  , $posy  ;
    public $speedx, $speedy;
    private $parent;

    public function __construct ($posx, $posy, $speedx, $speedy, $parent)
    {
        $this->posx = $posx;
        $this->posy = $posy;
        $this->speedx = $speedx;
        $this->speedy = $speedy;
        $this->parent = $parent;
    }

    public function path ()
    {
        $res = array();
        $v = new Point ($this->speedx, $this->speedy);
        for ($node = $this->parent ; $node != null ; $node = $node->parent)
        {
            $nv = new Point ($node->speedx, $node->speedy);
            $a = $nv->vector_to ($v);
            $v = new Point ($node->speedx, $node->speedy);
            array_unshift ($res, $a);
        }
        return $res;
    }
}

class Map {

    private static $target;       // maximal number of turns
    private static $time;         // time available to solve
    private static $sx, $sy;      // map dimensions
    private static $cell;         // cells of the map
    private static $start;        // starting point
    private static $acceleration; // possible acceleration values

    public static function init ()
    {
        // read map definition
        self::$target = trim(fgets(STDIN));
        list (self::$sx, self::$sy) = explode (" ", trim(fgets(STDIN)));
        self::$cell = array();
        for ($y = 0 ; $y != self::$sy ; $y++) self::$cell[] = str_split (trim(fgets(STDIN)));
        self::$time = trim(fgets(STDIN));

        // get starting point
        foreach (self::$cell as $y=>$row)
        {
            $x = array_search ("S", $row);
            if ($x !== false)
            {
                self::$start = new Point ($x, $y);
Trace::msg ("start ".self::$start);
                break;
            }
        }

        // compute possible acceleration values
        self::$acceleration = array();
        for ($x = -1 ; $x <= 1 ; $x++)
        for ($y = -1 ; $y <= 1 ; $y++)
        {
            self::$acceleration[] = new Point ($x, $y);
        }
    }

    public static function solve ()
    {
        $now = microtime(true);
        $res = array();
        $border = array (new Node (self::$start->x, self::$start->y, 0, 0, null));
        $present = array (self::$start->x." ".self::$start->y." 0 0" => 1);
        while (count ($border))
        {
if ((microtime(true) - $now) > 1)
{
Trace::msg (count($present)." nodes, ".round(memory_get_usage(true)/1024)."K");
$now = microtime(true);
}
            $node = array_shift ($border);
//Trace::msg ("node $node->pos $node->speed");
            $px = $node->posx;
            $py = $node->posy;
            $vx = $node->speedx;
            $vy = $node->speedy;
            foreach (self::$acceleration as $a)
            {
                $nvx = $vx + $a->x;
                $nvy = $vy + $a->y;
                $npx = $px + $nvx;
                $npy = $py + $nvy;
                if ($npx < 0 || $npx >= self::$sx || $npy < 0 || $npy >= self::$sy || self::$cell[$npy][$npx] == "#")
                {
//Trace::msg ("invalid position $px,$py $vx,$vy -> $npx,$npy");
                    continue;
                }
                if (self::$cell[$npy][$npx] == "*")
                {
Trace::msg ("winning position $px,$py $vx,$vy -> $npx,$npy");
                    $end = new Node ($npx, $npy, $nvx, $nvy, $node);
                    $res = $end->path ();
                    break 2;
                }
//Trace::msg ("checking $np $nv");
                $signature = "$npx $npy $nvx $nvy";
                if (isset ($present[$signature])) continue;
//Trace::msg ("*** adding $np $nv");
                $border[] = new Node ($npx, $npy, $nvx, $nvy, $node);
                $present[$signature] = 1;
            }
        }
        return $res;
    }
}

ini_set("memory_limit","1000M");
Map::init ();
$res = Map::solve();
//Trace::dump ($res);
foreach ($res as $a) echo "$a->x $a->y\n";
?>

erf... My barebone allocator is just a bit too barebone. I'll add the necessary crap to make it work with g++, then. Sorry about that.

OK, that's fixed. The g++ version even actually works about 30% faster. It now outputs some stats on stderr. Feel free to comment it out (from the last lines of the source). Sorry again for the blunder.

Alright, it works now and I reproduced your score. It's damn fast! :) I'll add your test case to the benchmark, but I'll change the target to 400, as that's in line with how I determined all the other targets (except the tie breaker). I'll update the main post once I've reran all the other submissions.

Updated the results. There was no need for a tie breaker, because all other submissions exceed the memory limit on your test track. Congrats on that! :)

Thanks. Actually this challenge gave me an occasion to dig into these STL hash tables. Though I hate C++ guts, I can't help but getting killed by my curiosity. Meow! :).

Nice submission. I wonder if I'd have to switch languages to beat it, or if algorithmic optimizations and microoptimizations would do it.

@MartinBüttner: I've added a second racer to my submission, this time using bidirectional search. It seems to just barely squeeze by under the memory limit for the new track, though I don't expect it to win the tiebreakers.

@user2357112 Thanks for letting me know, I'll rerun tests tonight.

@user2357112 The BFS approach is a brute. Clearly a smarter algorithm should defeat it. I was thinking of enforcing stricter memory limits (maybe 100Mb or so), so that you won't need huge maps to tell smarter algorithms apart from the current winning brutes :)

@kuroineko I don't think I want to change the limits again more than 2 months after the challenge was posted. I guess I'll just have to live with running huge test sets now.

Well bad news then, I just finished another refinement of my BFS that beats the 100x400 map in 1.5s and consumes just over 200 Mb :). I can post it to another answer if you like. I would rather not overwrite the other answer to keep the discussions about hash tables, since the new version does without any.

@user2357112 (and kuroi) I've updated the results. user2357112's new submission hits the memory limit at a tie-breaker of size 440. interestingly, nneonneo's submission doesn't have a problem with that, and hence overtakes your old submission again. kuroi's still has lots of room in any case. kuroi, post another version if you want, but currently there's no need since you're very clearly leading anyway. of course, if you do I'll have no choice but run more tests later this week.

lol I would not want to overburden you. I'd rather explore a few possibilities before publishing a new source. I'm thinking of adding some kind of preprocessing to reduce the BFS search space. Btw my current version hits the 1Gb limit for a 100x1050 map similar to the one I posted.

C++, 5.4 (deterministic, optimal)
Dynamic programming solution. Provably optimal. Very fast: solves all 20 testcases in 0.2s. Should be especially fast on 64-bit machines. Assumes the board is less than 32,000 places in each direction (which should hopefully be true).
This racer is a little unusual. It computes the optimal path at the starting line, and afterwards executes the computed path instantly. It ignores the time control and assumes it can finish the optimization step on time (which should be true for any reasonably modern hardware). On excessively large maps, there's a small chance that the racer may segfault. If you can convince it to segfault, you get a brownie point, and I'll fix it to use an explicit loop.
Compile with g++ -O3. May require C++11 (for <unordered_map>). To run, just run the compiled executable (no flags or options are supported; all input is taken on stdin).
#include <unordered_map>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

#include <cstdint>

#define MOVES_INF (1<<30)

union state {
    struct {
        short px, py, vx, vy;
    };
    uint64_t val;
};

struct result {
    int nmoves;
    short dvx, dvy;
};

typedef std::unordered_map<uint64_t, result> cache_t;
int target, n, m;
std::vector<std::string> track;
cache_t cache;

static int solve(uint64_t val) {
    cache_t::iterator it = cache.find(val);
    if(it != cache.end())
        return it->second.nmoves;

    // prevent recursion
    result res;
    res.nmoves = MOVES_INF;
    cache[val] = res;

    state cur;
    cur.val = val;
    for(int dvx = -1; dvx <= 1; dvx++) for(int dvy = -1; dvy <= 1; dvy++) {
        state next;
        next.vx = cur.vx + dvx;
        next.vy = cur.vy + dvy;
        next.px = cur.px + next.vx;
        next.py = cur.py + next.vy;
        if(next.px < 0 || next.px >= n || next.py < 0 || next.py >= m)
            continue;
        char c = track[next.py][next.px];
        if(c == '*') {
            res.nmoves = 1;
            res.dvx = dvx;
            res.dvy = dvy;
            break;
        } else if(c == '#') {
            continue;
        } else {
            int score = solve(next.val) + 1;
            if(score < res.nmoves) {
                res.nmoves = score;
                res.dvx = dvx;
                res.dvy = dvy;
            }
        }
    }

    cache[val] = res;
    return res.nmoves;
}

bool solve_one() {
    std::string line;
    float time;

    std::cin >> target;
    // std::cin >> time; // uncomment to use "time" control
    std::cin >> n >> m;
    if(!std::cin)
        return false;
    std::cin.ignore(); // skip newline at end of "n m" line

    track.clear();
    track.reserve(m);

    for(int i=0; i<m; i++) {
        std::getline(std::cin, line);
        track.push_back(line);
    }

    cache.clear();

    state cur;
    cur.vx = cur.vy = 0;
    for(int y=0; y<m; y++) for(int x=0; x<n; x++) {
        if(track[y][x] == 'S') {
            cur.px = x;
            cur.py = y;
            break;
        }
    }

    solve(cur.val);

    int sol_len = 0;
    while(track[cur.py][cur.px] != '*') {
        cache_t::iterator it = cache.find(cur.val);
        if(it == cache.end() || it->second.nmoves >= MOVES_INF) {
            std::cerr << "Failed to solve at p=" << cur.px << "," << cur.py << " v=" << cur.vx << "," << cur.vy << std::endl;
            return true;
        }

        int dvx = it->second.dvx;
        int dvy = it->second.dvy;
        cur.vx += dvx;
        cur.vy += dvy;
        cur.px += cur.vx;
        cur.py += cur.vy;
        std::cout << dvx << " " << dvy << std::endl;
        sol_len++;
    }

    //std::cerr << "Score: " << ((float)sol_len) / target << std::endl;

    return true;
}

int main() {
    /* benchmarking: */
    //while(solve_one())
    //    ;

    /* regular running */
    solve_one();
    std::string line;
    while(std::cin) std::getline(std::cin, line);

    return 0;
}

Results
 No.    Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1    37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2    38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3    33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4    10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5     9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6    15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7    17 x 8        16   0.31250   Racer reached goal at ( 15, 0) in 5 turns.
  8    19 x 13       18   0.27778   Racer reached goal at ( 1, 11) in 5 turns.
  9    60 x 10      107   0.14953   Racer reached goal at ( 2, 6) in 16 turns.
 10    31 x 31      106   0.25472   Racer reached goal at ( 28, 0) in 27 turns.
 11    31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12    50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13   100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14    79 x 63      242   0.26860   Racer reached goal at ( 3, 42) in 65 turns.
 15    26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16    17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17    50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18    10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19    55 x 55       45   0.17778   Racer reached goal at ( 52, 26) in 8 turns.
 20    50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:              5.40009

New Testcase

Well, something like this was pretty much expected. There just isn't enough state in the puzzle to render dynamic programming infeasible. If I enter, I'm going to need to submit a map that requires more sophisticated search strategies to solve.

How does your racer perform on your test case?

0.14 (14 moves)

Is that time taken or moves/target? If it's moves/target, how does it perform in terms of time?

Moves/target. For my test case the solver takes about .3 seconds.

Keep in mind that the solver is basically quadratic w.r.t. the number of board cells. So it should be possible to make a really evil test case.

Plan A is a map with a giant, empty playground to waste solver states, and a long, winding path that needs to be traversed at low speed to make sure the solver doesn't find the goal before it blows all its memory wandering around the playground. The time budget is generous enough that I'm not sure whether memory or time will be the limiting factor.

Do be careful that the solver can't quantum-tunnel from the playground to the path. (This necessitates putting a very large gap between the playground and the lath).

The plan for that was to space the curves so that if you jump into the path, you're guaranteed to careen into a wall within the next move or two. Other map concepts include a really long corridor with walls spaced so you have to take the whole thing at a speed of 2, hopefully blowing both the hardcoded map width limit and the available stack space for recursion.

Well, not bad. I guess I should have written an optimal solver myself to determine a more reasonable time limit. I guess all competitive solutions will have to be optimal and will need to get to a larger tie-breaker than this one. As far as I know the search space goes like n³ where n is the side-length of the track. Since the tie-breakers target scales only linearly, I think the performance of this algorithm should blow up fast enough. Still it's a bit unfortunate that suboptimal algorithms will barely be able to compete any more. Congrats on that!

I can reproduce your scores for all tracks except your own in which case your program doesn't submit a single move, so it scores 2 there.

@m.buettner: Odd. It worked fine for me. Score: 0.14  20   101 x 100     100   0.14000   Racer reached goal at ( 99, 99) in 14 turns.

@nneonneo I suppose it segfaults earlier on my machine?

@m.buettner: Did you check the input format? The time budget line is missing.

@user2357112 the time budget line is not present in the benchmark file (it's computed from the target line)

@m.buettner Looks like with some compilers/optimization levels (e.g. g++-4.8 -O3, but not -O2), the stack can overflow due to the recursion. Try increasing ulimit -s before running the test.

@Ventero thanks, that did it. I'm running it on Windows, so there's no ulimit -s for me, but I can set the stack size during compilation. When I increase it to 100M (10M wasn't enough), it works.

I think I've found a bug in the cycle prevention code. It assumes that for each state the search reaches from a state S, an optimal path cannot be to return to S. It might seem that if an optimal path does return to S, then the state cannot be on an optimal path (since we could just remove the loop it's on and get a shorter path), and so we don't care whether we get a too-high result for that state. However, if an optimal path passes through states A and B in that order, but the search first finds A while B is still on the stack, then A's results are poisoned by the loop prevention.

Unfortunately, I had to add another rule. Memory seems to be more limiting than time in this challenge, so I had to set a hard to limit on memory consumption. Any run in which your racer uses more than 1GB of memory will be aborted to the same effect as exceed the time limit. For the current set of tracks, your score has not been affected by this change. Please let me know if you apply any optimisations, so I can rerun the tests.

Python 2, deterministic, optimal
Here's my racer. I haven't tested it on the benchmark (still waffling about what version and installer of Ruby to install), but it should solve everything optimally and under the time limit. The command to run it is python whateveryoucallthefile.py. Needs the -s controller flag.
# Breadth-first search.
# Future directions: bidirectional search and/or A*.

import operator
import time

acceleration_options = [(dvx, dvy) for dvx in [-1, 0, 1] for dvy in [-1, 0, 1]]

class ImpossibleRaceError(Exception): pass

def read_input(line_source=raw_input):
    # We don't use the target.
    target = int(line_source())

    width, height = map(int, line_source().split())
    input_grid = [line_source() for _ in xrange(height)]

    start = None
    for i in xrange(height):
        for j in xrange(width):
            if input_grid[i][j] == 'S':
                start = i, j
                break
        if start is not None:
            break

    walls = [[cell == '#' for cell in row] for row in input_grid]
    goals = [[cell == '*' for cell in row] for row in input_grid]

    return start, walls, goals

def default_bfs_stop_threshold(walls, goals):
    num_not_wall = sum(sum(map(operator.not_, row)) for row in walls)
    num_goals = sum(sum(row) for row in goals)
    return num_goals * num_not_wall

def bfs(start, walls, goals, stop_threshold=None):
    if stop_threshold is None:
        stop_threshold = default_bfs_stop_threshold(walls, goals)

    # State representation is (x, y, vx, vy)
    x, y = start
    initial_state = (x, y, 0, 0)
    frontier = {initial_state}
    # Visited set is tracked by a map from each state to the last move taken
    # before reaching that state.
    visited = {initial_state: None}

    while len(frontier) < stop_threshold:
        if not frontier:
            raise ImpossibleRaceError

        new_frontier = set()
        for x, y, vx, vy in frontier:
            for dvx, dvy in acceleration_options:
                new_vx, new_vy = vx+dvx, vy+dvy
                new_x, new_y = x+new_vx, y+new_vy
                new_state = (new_x, new_y, new_vx, new_vy)

                if not (0 <= new_x < len(walls) and 0 <= new_y < len(walls[0])):
                    continue
                if walls[new_x][new_y]:
                    continue
                if new_state in visited:
                    continue

                new_frontier.add(new_state)
                visited[new_state] = dvx, dvy

                if goals[new_x][new_y]:
                    return construct_path_from_bfs(new_state, visited)
        frontier = new_frontier

def construct_path_from_bfs(goal_state, best_moves):
    reversed_path = []
    current_state = goal_state
    while best_moves[current_state] is not None:
        move = best_moves[current_state]
        reversed_path.append(move)

        x, y, vx, vy = current_state
        dvx, dvy = move
        old_x, old_y = x-vx, y-vy # not old_vx or old_vy
        old_vx, old_vy = vx-dvx, vy-dvy
        current_state = (old_x, old_y, old_vx, old_vy)
    return reversed_path[::-1]

def main():
    t = time.time()

    start, walls, goals = read_input()
    path = bfs(start, walls, goals, float('inf'))
    for dvx, dvy in path:
        # I wrote the whole program with x pointing down and y pointing right.
        # Whoops. Gotta flip things for the output.
        print dvy, dvx

if __name__ == '__main__':
    main()

After inspecting nneonneo's racer (but not actually testing it, since I also don't have a C++ compiler), I have found that it seems to perform a nearly-exhaustive search of the state space, no matter how close the goal or how short a path has already been found. I have also found that the time rules mean building a map with a long, complex solution requires a long, boring time limit. Thus, my map submission is pretty simple:
New Testcase
(GitHub cannot display the long line. The track is *S.......[and so on].....)

Additional submission: Python 2, bidirectional search
This is an approach I wrote up about two months ago, when trying to optimize my breadth-first submission. For the test cases that existed at the time, it didn't offer an improvement, so I didn't submit it, but for kuroi's new map, it seems to just barely squeeze by under the memory cap. I'm still expecting kuroi's solver to beat this, but I'm interested in how it holds up.
# Bidirectional search.
# Future directions: A*.

import operator
import time

acceleration_options = [(dvx, dvy) for dvx in [-1, 0, 1] for dvy in [-1, 0, 1]]

class ImpossibleRaceError(Exception): pass

def read_input(line_source=raw_input):
    # We don't use the target.
    target = int(line_source())

    width, height = map(int, line_source().split())
    input_grid = [line_source() for _ in xrange(height)]

    start = None
    for i in xrange(height):
        for j in xrange(width):
            if input_grid[i][j] == 'S':
                start = i, j
                break
        if start is not None:
            break

    walls = [[cell == '#' for cell in row] for row in input_grid]
    goals = [[cell == '*' for cell in row] for row in input_grid]

    return start, walls, goals

def bfs_to_bidi_threshold(walls, goals):
    num_not_wall = sum(sum(map(operator.not_, row)) for row in walls)
    num_goals = sum(sum(row) for row in goals)
    return num_goals * (num_not_wall - num_goals)

class GridBasedGoalContainer(object):
    '''Supports testing whether a state is a goal state with `in`.

    Does not perform bounds checking.'''
    def __init__(self, goal_grid):
        self.goal_grid = goal_grid
    def __contains__(self, state):
        x, y, vx, vy = state
        return self.goal_grid[x][y]

def forward_step(state, acceleration):
    x, y, vx, vy = state
    dvx, dvy = acceleration

    new_vx, new_vy = vx+dvx, vy+dvy
    new_x, new_y = x+new_vx, y+new_vy

    return (new_x, new_y, new_vx, new_vy)

def backward_step(state, acceleration):
    x, y, vx, vy = state
    dvx, dvy = acceleration

    old_x, old_y = x-vx, y-vy
    old_vx, old_vy = vx-dvx, vy-dvy

    return (old_x, old_y, old_vx, old_vy)

def bfs(start, walls, goals):
    x, y = start
    initial_state = (x, y, 0, 0)
    initial_frontier = {initial_state}
    visited = {initial_state: None}

    goal_state, frontier, visited = general_bfs(
        frontier=initial_frontier,
        visited=visited,
        walls=walls,
        goalcontainer=GridBasedGoalContainer(goals),
        stop_threshold=float('inf'),
        step_function=forward_step
    )

    return construct_path_from_bfs(goal_state, visited)

def general_bfs(
        frontier,
        visited,
        walls,
        goalcontainer,
        stop_threshold,
        step_function):

    while len(frontier) <= stop_threshold:
        if not frontier:
            raise ImpossibleRaceError

        new_frontier = set()
        for state in frontier:
            for accel in acceleration_options:
                new_state = new_x, new_y, new_vx, new_vy = \
                        step_function(state, accel)

                if not (0 <= new_x < len(walls) and 0 <= new_y < len(walls[0])):
                    continue
                if walls[new_x][new_y]:
                    continue
                if new_state in visited:
                    continue

                new_frontier.add(new_state)
                visited[new_state] = accel

                if new_state in goalcontainer:
                    return new_state, frontier, visited
        frontier = new_frontier
    return None, frontier, visited

def max_velocity_component(n):
    # It takes a distance of at least 0.5*v*(v+1) to achieve a velocity of
    # v in the x or y direction. That means the map has to be at least
    # 1 + 0.5*v*(v+1) rows or columns long to accomodate such a velocity.
    # Solving for v, we get a velocity cap as follows.
    return int((2*n-1.75)**0.5 - 0.5)

def solver(
        start,
        walls,
        goals,
        mode='bidi'):

    x, y = start
    initial_state = (x, y, 0, 0)
    initial_frontier = {initial_state}
    visited = {initial_state: None}
    if mode == 'bidi':
        stop_threshold = bfs_to_bidi_threshold(walls, goals)
    elif mode == 'bfs':
        stop_threshold = float('inf')
    else:
        raise ValueError('Unsupported search mode: {}'.format(mode))

    goal_state, frontier, visited = general_bfs(
        frontier=initial_frontier,
        visited=visited,
        walls=walls,
        goalcontainer=GridBasedGoalContainer(goals),
        stop_threshold=stop_threshold,
        step_function=forward_step
    )

    if goal_state is not None:
        return construct_path_from_bfs(goal_state, visited)

    # Switching to bidirectional search.

    not_walls_or_goals = []
    goal_list = []
    for x in xrange(len(walls)):
        for y in xrange(len(walls[0])):
            if not walls[x][y] and not goals[x][y]:
                not_walls_or_goals.append((x, y))
            if goals[x][y]:
                goal_list.append((x, y))
    max_vx = max_velocity_component(len(walls))
    max_vy = max_velocity_component(len(walls[0]))
    reverse_visited = {(goal_x, goal_y, goal_x-prev_x, goal_y-prev_y): None
                        for goal_x, goal_y in goal_list
                        for prev_x, prev_y in not_walls_or_goals
                        if abs(goal_x-prev_x) <= max_vx
                        and abs(goal_y - prev_y) <= max_vy}
    reverse_frontier = set(reverse_visited)
    while goal_state is None:
        goal_state, reverse_frontier, reverse_visited = general_bfs(
            frontier=reverse_frontier,
            visited=reverse_visited,
            walls=walls,
            goalcontainer=frontier,
            stop_threshold=len(frontier),
            step_function=backward_step
        )
        if goal_state is not None:
            break
        goal_state, frontier, visited = general_bfs(
            frontier=frontier,
            visited=visited,
            walls=walls,
            goalcontainer=reverse_frontier,
            stop_threshold=len(reverse_frontier),
            step_function=forward_step
        )
    forward_path = construct_path_from_bfs(goal_state, visited)
    backward_path = construct_path_from_bfs(goal_state,
                                            reverse_visited,
                                            step_function=forward_step)
    return forward_path + backward_path[::-1]

def construct_path_from_bfs(goal_state,
                            best_moves,
                            step_function=backward_step):
    reversed_path = []
    current_state = goal_state
    while best_moves[current_state] is not None:
        move = best_moves[current_state]
        reversed_path.append(move)
        current_state = step_function(current_state, move)
    return reversed_path[::-1]

def main():
    start, walls, goals = read_input()
    t = time.time()
    path = solver(start, walls, goals)
    for dvx, dvy in path:
        # I wrote the whole program with x pointing down and y pointing right.
        # Whoops. Gotta flip things for the output.
        print dvy, dvx

if __name__ == '__main__':
    main()

This sometimes fail on case 12 and 13. Dont know why since the error messages are somewhat ... unfriendly

@Ray I do get error messages, too, but I always get the result for those anyway. I think it might rather be something in my controller, because it looks like the controller tries to kill the racer process although it's already finished.

@m.buettner I found the reason, add -s then it will be OK.

@Ray Oh yeah, I'm doing that. I still get an error on tracks 13 and 14 when the controller is trying to kill the process although the result is already there. I guess I should look into that, but doesn't affect the scoring so I didn't bother yet.

Unfortunately, I had to add another rule. Memory seems to be more limiting than time in this challenge, so I had to set a hard to limit on memory consumption. Any run in which your racer uses more than 1GB of memory will be aborted to the same effect as exceed the time limit. For the current set of tracks, your score has not been affected by this change. (I think you'll reach that limit on tie-breakers around n = 400.) Please let me know if you apply any optimisations, so I can rerun the tests.

Looks like bidirectional search isn't any help on the tiebreaker maps. Rather than an exponential explosion of states, the search space is structured more like a long corridor. The forward and backward searches both rapidly hit the width of the corridor, after which they just sort of flood forward with little outward expansion. Future work might try A*, beam search, other search algorithms, or optimizations that let the search drop parts of the visited set that will never be looked at again.

Python 3: 6.49643 (Optimal, BFS)
For the old 20 case benchmark file, it got a score of 5.35643. The solution by @nneonneo is not optimal since it got 5.4. Some bugs maybe.
This solution use BFS to search the Graph, each search state is in the form of (x, y, dx, dy). Then I use a map to map from states to distances. In the worst case, it's time and space complexity is O(n^2 m^2). This will rarely happen since the speed won't be too high or the racer will crash. Actually, it cost 3 seconds on my machine to complete all the 22 testcases.
from collections import namedtuple, deque
import itertools

Field = namedtuple('Map', 'n m grids')

class Grid:
    WALL = '#'
    EMPTY = '.'
    START = 'S'
    END = '*'

def read_nums():
    return list(map(int, input().split()))

def read_field():
    m, n = read_nums()
    return Field(n, m, [input() for i in range(n)])

def find_start_pos(field):
    return next((i, j)
        for i in range(field.n) for j in range(field.m)
        if field.grids[i][j] == Grid.START)

def can_go(field, i, j):
    return 0 <= i < field.n and 0 <= j < field.m and field.grids[i][j] != Grid.WALL

def trace_path(start, end, prev):
    if end == start:
        return
    end, step = prev[end]
    yield from trace_path(start, end, prev)
    yield step

def solve(max_turns, field, time):
    i0, j0 = find_start_pos(field)
    p0 = i0, j0, 0, 0
    prev = {}
    que = deque([p0])
    directions = list(itertools.product((-1, 0, 1), (-1, 0, 1)))

    while que:
        p = i, j, vi, vj = que.popleft()
        for dvi, dvj in directions:
            vi1, vj1 = vi + dvi, vj + dvj
            i1, j1 = i + vi1, j + vj1
            if not can_go(field, i1, j1):
                continue
            p1 = i1, j1, vi1, vj1
            if p1 in prev:
                continue
            que.append(p1)
            prev[p1] = p, (dvi, dvj)
            if field.grids[i1][j1] == Grid.END:
                return trace_path(p0, p1, prev)
    return []

def main():
    for dvy, dvx in solve(int(input()), read_field(), float(input())):
        print(dvx, dvy)

main()

＃ Results
± % time ruby controller.rb benchmark.txt python ../mybfs.py                                                                                !9349
["benchmark.txt", "python", "../mybfs.py"]

Running 'python ../mybfs.py' against benchmark.txt

 No.       Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1       37 x 1        36   0.22222   Racer reached goal at ( 36, 0) in 8 turns.
  2       38 x 1        37   0.24324   Racer reached goal at ( 37, 0) in 9 turns.
  3       33 x 1        32   0.25000   Racer reached goal at ( 32, 0) in 8 turns.
  4       10 x 10       10   0.40000   Racer reached goal at ( 7, 7) in 4 turns.
  5        9 x 6         8   0.37500   Racer reached goal at ( 6, 0) in 3 turns.
  6       15 x 7        16   0.37500   Racer reached goal at ( 12, 4) in 6 turns.
  7       17 x 8        16   0.31250   Racer reached goal at ( 14, 0) in 5 turns.
  8       19 x 13       18   0.27778   Racer reached goal at ( 0, 11) in 5 turns.
  9       60 x 10      107   0.14953   Racer reached goal at ( 0, 6) in 16 turns.
 10       31 x 31      106   0.23585   Racer reached goal at ( 27, 0) in 25 turns.
 11       31 x 31      106   0.24528   Racer reached goal at ( 15, 15) in 26 turns.
 12       50 x 20       50   0.24000   Racer reached goal at ( 49, 10) in 12 turns.
 13      100 x 100    2600   0.01385   Racer reached goal at ( 50, 0) in 36 turns.
 14       79 x 63      242   0.24380   Racer reached goal at ( 3, 42) in 59 turns.
 15       26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16       17 x 1        19   0.52632   Racer reached goal at ( 16, 0) in 10 turns.
 17       50 x 1        55   0.34545   Racer reached goal at ( 23, 0) in 19 turns.
 18       10 x 7        23   0.34783   Racer reached goal at ( 1, 3) in 8 turns.
 19       55 x 55       45   0.17778   Racer reached goal at ( 50, 26) in 8 turns.
 20      101 x 100     100   0.14000   Racer reached goal at ( 99, 99) in 14 turns.
 21   100000 x 1         1   1.00000   Racer reached goal at ( 0, 0) in 1 turns.
 22       50 x 50      200   0.05500   Racer reached goal at ( 47, 46) in 11 turns.
-------------------------------------------------------------------------------------
TOTAL SCORE:                 6.49643

ruby controller.rb benchmark.txt python ../mybfs.py  3.06s user 0.06s system 99% cpu 3.146 total

Yes, according to user2357112's comment there's a bug in nneonneo's cycle prevention. As far as I know, the speed is limited by O(√n) which would make your implementation O(n³) on square grids (same as the others, I suppose). I will add a tie breaker to score your submission versus user2357112's later today.

Btw, are you planning to add another test case?

@m.buettner No, I dont have a good enough comprehension for this game. So my testcase wont be a interesting one.

Unfortunately, I had to add another rule. Memory seems to be more limiting than time in this challenge, so I had to set a hard to limit on memory consumption. Any run in which your racer uses more than 1GB of memory will be aborted to the same effect as exceed the time limit. With this rule, your submission is the first to exceed that limit on a tie-breaker of size n=270, which is why you're now behind the other two "optimal" submissions. That being said, your submission is also the slowest of the three, so would have been third anyway, just with a larger tie-breaker.

Please let me know if you apply any optimisations, so I can rerun the tests.

I retested with the changes you made 6 hours ago. The tie-breaker is now at n = 290 instead, but the results are pretty much the same.

@m.buettner  I read the python2 solution and that inspired me. Seems like cheating. Feel free to rate this below that one.  However, if you make n much more larger, I will optimize it using heuristic search, which will make it work in randomly large map but not optimal.

I'd love to see heuristic solutions! I think they could actually beat the optimal ones if the tie-breakers get sufficiently large. However, adhering to my own rules I won't add any larger tie-breakers unless there actually is a tie as that would seem unfair towards the optimal solutions. So if you can manage to find a heuristic that happens to produce the optimal result for some maps (in particular the ones currently in the benchmark) you might be able to keep up longer with the tie-breakers than the optimal ones.

That being said, I will add tie-breakers for places other than the 1st (e.g. if the 3rd and 4th best submissions tie). So if there are multiple heuristic approaches, these might be able to build up a set of larger tie-breakers, which cause the optimal solutions to fail, which in turn would allow the heuristic ones to overtake them. ;)

RandomRacer, ~40.0 (averaged over 10 runs)
It's not that this bot never finishes a track, but definitely much less often than once in 10 attempts. (I get a non-worst-case score every 20 to 30 simulations or so.)
This is mostly to act as a baseline case and to demonstrate a possible (Ruby) implementation for a racer:
# Parse initial input
target = gets.to_i
size = gets.split.map(&:to_i)
track = []
size[1].times do
    track.push gets
end
time_budget = gets.to_f

# Find start position
start_y = track.find_index { |row| row['S'] }
start_x = track[start_y].index 'S'

position = [start_x, start_y]
velocity = [0, 0]

while true
    x = rand(3) - 1
    y = rand(3) - 1
    puts [x,y].join ' '
    $stdout.flush

    first_line = gets
    break if !first_line || first_line.chomp.empty?

    position = first_line.split.map(&:to_i)
    velocity = gets.split.map(&:to_i)
    time_budget = gets.to_f
end

Run it with
ruby controller.rb benchmark.txt ruby randomracer.rb

Random Racer 2.0, ~31
Well this isn't going to beat the posted optimal solver, but it is a slight improvement on a random racer. Main difference is that this racer only will consider randomly going where there isn't a wall, unless it runs out of valid places to move, and if it can move to a goal that turn, it will. It also will not move in order to stay in the same spot, unless there is no other move available (unlikely, but possible).
Implemented in Java, compiled with java8, but Java 6 should be fine. No command line parameters. There's a pretty good clusterfuck of hierarchy, so I think I'm doing java right.
import java.util.Scanner;
import java.util.Random;
import java.util.ArrayList;
import java.io.ByteArrayOutputStream;
import java.io.PrintStream;

public class VectorRacing   {
    private static Scanner in = new Scanner(System.in);
    private static Random rand = new Random();
    private static Track track;
    private static Racer racer;
    private static int target;
    private static double time;
    public static void main(String[] args)  {
        init();
        main_loop();
    }
    private static void main_loop() {
        Scanner linescan;
        String line;
        int count = 0,
            x, y, u, v;

        while(!racer.lost() && !racer.won() && count < target)  {
            Direction d = racer.think();
            racer.move(d);
            count++;
            System.out.println(d);

            line = in.nextLine();
            if(line.equals("")) {
                break;
            }
            linescan = new Scanner(line);
            x = linescan.nextInt();
            y = linescan.nextInt();
            linescan = new Scanner(in.nextLine());
            u = linescan.nextInt();
            v = linescan.nextInt();
            time = Double.parseDouble(in.nextLine());

            assert x == racer.location.x;
            assert y == racer.location.y;
            assert u == racer.direction.x;
            assert v == racer.direction.y;
        }
    }
    private static void init()  {
        target = Integer.parseInt(in.nextLine());
        int width = in.nextInt();
        int height = Integer.parseInt(in.nextLine().trim());
        String[] ascii = new String[height];
        for(int i = 0; i < height; i++) {
            ascii[i] = in.nextLine();
        }
        time = Double.parseDouble(in.nextLine());
        track = new Track(width, height, ascii);
        for(int y = 0; y < ascii.length; y++)   {
            int x = ascii[y].indexOf("S");
            if( x != -1)    {
                racer = new RandomRacer(track, new Location(x, y));
                break;
            }
        }
    }

    public static class RandomRacer extends Racer   {
        public RandomRacer(Track t, Location l) {
            super(t, l);
        }
        public Direction think()    {
            ArrayList<Pair<Location, Direction> > possible = this.getLocationsCanMoveTo();
            if(possible.size() == 0)    {
                return Direction.NONE;
            }
            Pair<Location, Direction> ret = null;
            do  {
                ret = possible.get(rand.nextInt(possible.size()));
            }   while(possible.size() != 1 && ret.a.equals(this.location));
            return ret.b;
        }
    }

    // Base things
    public enum Direction   {
        NORTH("0 -1"), SOUTH("0 1"), EAST("1 0"), WEST("-1 0"), NONE("0 0"),
        NORTH_EAST("1 -1"), NORTH_WEST("-1 -1"), SOUTH_EAST("1 1"), SOUTH_WEST("-1 1");

        private final String d;
        private Direction(String d) {this.d = d;}
        public String toString()    {return d;}
    }
    public enum Cell    {
        WALL('#'), GOAL('*'), ROAD('.'), OUT_OF_BOUNDS('?');

        private final char c;
        private Cell(char c)    {this.c = c;}
        public String toString()    {return "" + c;}
    }

    public static class Track   {
        private Cell[][] track;
        private int target;
        private double time;
        public Track(int width, int height, String[] ascii) {
            this.track = new Cell[width][height];
            for(int y = 0; y < height; y++) {
                for(int x = 0; x < width; x++)  {
                    switch(ascii[y].charAt(x))  {
                        case '#':   this.track[x][y] = Cell.WALL; break;
                        case '*':   this.track[x][y] = Cell.GOAL; break;
                        case '.':
                        case 'S':   this.track[x][y] = Cell.ROAD; break;
                        default:    System.exit(-1);
                    }
                }
            }
        }
        public Cell atLocation(Location loc)    {
            if(loc.x < 0 || loc.x >= track.length || loc.y < 0 || loc.y >= track[0].length) return Cell.OUT_OF_BOUNDS;
            return track[loc.x][loc.y];
        }

        public String toString()    {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            PrintStream ps = new PrintStream(bos);
            for(int y = 0; y < track[0].length; y++)    {
                for(int x = 0; x < track.length; x++)   {
                    ps.append(track[x][y].toString());
                }
                ps.append('\n');
            }
            String ret = bos.toString();
            ps.close();
            return ret;
        }
    }

    public static abstract class Racer  {
        protected Velocity tdir;
        protected Location tloc;
        protected Track track;
        public Velocity direction;
        public Location location;

        public Racer(Track track, Location start)   {
            this.track = track;
            direction = new Velocity(0, 0);
            location = start;
        }
        public boolean canMove() throws GoHereDammitException {return canMove(Direction.NONE);}
        public boolean canMove(Direction d) throws GoHereDammitException    {
            tdir = new Velocity(direction);
            tloc = new Location(location);
            tdir.add(d);
            tloc.move(tdir);
            Cell at = track.atLocation(tloc);
            if(at == Cell.GOAL) {
                throw new GoHereDammitException();
            }
            return at == Cell.ROAD;
        }
        public ArrayList<Pair<Location, Direction> > getLocationsCanMoveTo()    {
            ArrayList<Pair<Location, Direction> > ret = new ArrayList<Pair<Location, Direction> >(9);
            for(Direction d: Direction.values())    {
                try {
                    if(this.canMove(d)) {
                        ret.add(new Pair<Location, Direction>(tloc, d));
                    }
                }   catch(GoHereDammitException e)  {
                    ret.clear();
                    ret.add(new Pair<Location, Direction>(tloc, d));
                    return ret;
                }
            }
            return ret;
        }
        public void move()  {move(Direction.NONE);}
        public void move(Direction d)   {
            direction.add(d);
            location.move(direction);
        }
        public boolean won()    {
            return track.atLocation(location) == Cell.GOAL;
        }
        public boolean lost()   {
            return track.atLocation(location) == Cell.WALL || track.atLocation(location) == Cell.OUT_OF_BOUNDS;
        }
        public String toString()    {
            return location + ", " + direction;
        }
        public abstract Direction think();

        public class GoHereDammitException extends Exception    {
            public GoHereDammitException()  {}
        }
    }

    public static class Location extends Point  {
        public Location(int x, int y)   {
            super(x, y);
        }
        public Location(Location l) {
            super(l);
        }
        public void move(Velocity d)    {
            this.x += d.x;
            this.y += d.y;
        }
    }

    public static class Velocity extends Point  {
        public Velocity(int x, int y)   {
            super(x, y);
        }
        public Velocity(Velocity v) {
            super(v);
        }
        public void add(Direction d)    {
            if(d == Direction.NONE) return;
            if(d == Direction.NORTH || d == Direction.NORTH_EAST || d == Direction.NORTH_WEST)  this.y--;
            if(d == Direction.SOUTH || d == Direction.SOUTH_EAST || d == Direction.SOUTH_WEST)  this.y++;
            if(d == Direction.EAST || d == Direction.NORTH_EAST || d == Direction.SOUTH_EAST)   this.x++;
            if(d == Direction.WEST || d == Direction.NORTH_WEST || d == Direction.SOUTH_WEST)   this.x--;
        }
    }

    public static class Point   {
        protected int x, y;
        protected Point(int x, int y)   {
            this.x = x;
            this.y = y;
        }
        protected Point(Point c)    {
            this.x = c.x;
            this.y = c.y;
        }
        public int getX()   {return x;}
        public int getY()   {return y;}
        public String toString()    {return "(" + x + ", " + y + ")";}
        public boolean equals(Point p)  {
            return this.x == p.x && this.y == p.y;
        }
    }

    public static class Pair<T, U>  {
        public T a;
        public U b;
        public Pair(T t, U u)   {
            a=t;b=u;
        }
    }
}

The Results (Best case I've seen)
Running 'java VectorRacing' against ruby-runner/benchmark.txt

 No.    Size     Target   Score     Details
-------------------------------------------------------------------------------------
  1    37 x 1        36   0.38889   Racer reached goal at ( 36, 0) in 14 turns.
  2    38 x 1        37   0.54054   Racer reached goal at ( 37, 0) in 20 turns.
  3    33 x 1        32   0.62500   Racer reached goal at ( 32, 0) in 20 turns.
  4    10 x 10       10   0.40000   Racer reached goal at ( 9, 8) in 4 turns.
  5     9 x 6         8   0.75000   Racer reached goal at ( 6, 2) in 6 turns.
  6    15 x 7        16   2.00000   Racer did not reach the goal within 16 turns.
  7    17 x 8        16   2.00000   Racer hit a wall at position ( 8, 2).
  8    19 x 13       18   0.44444   Racer reached goal at ( 16, 2) in 8 turns.
  9    60 x 10      107   0.65421   Racer reached goal at ( 0, 6) in 70 turns.
 10    31 x 31      106   2.00000   Racer hit a wall at position ( 25, 9).
 11    31 x 31      106   2.00000   Racer hit a wall at position ( 8, 1).
 12    50 x 20       50   2.00000   Racer hit a wall at position ( 27, 14).
 13   100 x 100    2600   2.00000   Racer went out of bounds at position ( 105, 99).
 14    79 x 63      242   2.00000   Racer went out of bounds at position (-2, 26).
 15    26 x 1        25   0.32000   Racer reached goal at ( 25, 0) in 8 turns.
 16    17 x 1        19   2.00000   Racer went out of bounds at position (-2, 0).
 17    50 x 1        55   2.00000   Racer went out of bounds at position ( 53, 0).
 18    10 x 7        23   2.00000   Racer went out of bounds at position ( 10, 2).
 19    55 x 55       45   0.33333   Racer reached goal at ( 4, 49) in 15 turns.
 20    50 x 50      200   2.00000   Racer hit a wall at position ( 14, 7).
-------------------------------------------------------------------------------------
TOTAL SCORE:             26.45641

Yes, I got it running, although I had to run it from the directory where the .class file is for some reason (instead of the directory where the controller is). Ping me (with a comment) if you decide to add a testcase, so I can add it to the benchmark. Your score was about 33 over 10 runs (see leaderboard), but this might well change with every new test track that is added to the benchmark.

Ah got it to run from the other directory, too. For those not familiar with Java on the command line: java -cp path/to/class/file VectorRacing

Ah, yeah I made a ton of classes (13, to be exact). I was always running your script from my classes directory, so I didn't actually test that. I may make a test case, but I think I'll try to make a racer that isn't random first.

Sure. If you do, please add it as a separate answer. (And feel free to add one test case with each of them.)

Unfortunately, I had to add another rule. Memory seems to be more limiting than time in this challenge, so I had to set a hard to limit on memory consumption. Any run in which your racer uses more than 1GB of memory will be aborted to the same effect as exceed the time limit. For the current set of tracks, your score has not been affected by this change (and likely won't ever be).

Congratulations! Your submission is the only one that fulfilled the bounty criterion. :D (scaling in less than O(n²))

woo! thanks! random decisions are just like a heuristic. just a really bad one.


text:
Simulate rotating a board
Introduction
You're playing a matching game, in which coins are inserted at the top and fall to the bottom (onto the top coin) due to gravity.
So this
O <- inserting this coin

OO O
OOOOO

will become this
O
OO O
OOOOO

Now imagine someone rotates the board clockwise. The following will happen:
1. The board is rotated
OOO
OO
O
OO
O

2. Coins fall down due to gravity
O
O
OO
OO
OOO

Your task
Your task is to simulate the rotation of the board by writing a program or a function. For the sake of simplicity we're only dealing with one kind of coin (it's not a too exciting matching game, is it…). You can assume that gravity is applied only after the rotation is complete. The board is rotated clockwise.
Input
The input is going to be a string, which contains 3 types of characters:

O (capital o) OR 0 (zero) - a coin (you decide which one your solution supports)
(space) - an empty field
\n (new line) - end of row

The input represents the state of the board. You can assume, the input is well formed and contains a valid state of the board (no coins are floating).
The input can be a function parameter, or can be read from the standard input or from a file.
Output
The output is the new state of the board after rotation. The output contains the same 3 types of characters as the input. The output can be returned from your function or can be written to the standard output or to a file.
Sample
Input1:
O
OO O
OOOOO

Output1:
O
O
OO
OO
OOO

Input2:
O O
O O

Output2:
OO
OO

You can use any language and the standard library of the chosen language. Shortest program in bytes wins.

Are the shorter lines padded with trailing spaces?

If you need so then yes.

What are the requirements for the board size? Can I choose a reasonable maximum size, or does the application/function need to work for all possible sizes?

You can assume that the maximum size of the board is 50x50

Does any part of the task involve matching?

@user2357112 no

If gravity is applied after rotation, how does Input2 become Output2? I would have thought it would drop the top coins down but not horizontally?

I think the correct output2 should be two piles of two coins separated by one empty column.

@Matt Note, that there are no empty rows in Input2, nor in Output2 (SE displays margin between the rows).

@justhalf You can assume, the input is well formed and contains a valid state of the board (no coins are floating) It's actually impossible to get a blank column sandwiched between non-blank columns

Yes, I thought there was an empty row in the input.

@David Frank, you are right, makes sense now! The empty column along with what looked like the empty row was confusing (to me!).

GolfScript, 14 12 characters
' '-n%zip$n*

Input must be given on STDIN, the character for coins can be any non-whitespace characters. Try here. Thanks to Peter for pointing out a two character reduction.

Oh, what I wouldn't give for a transpose in Ruby that can handle arrays with different lengths ...

@Ventero Most of the times I use this hacky version: ([nil]*a.map(&:size).max).zip(*a). Not good for golfing though.

You can save 2 chars: since the longest lines always end up at the bottom, you can replace -1% with $.

@PeterTaylor You're right - we can save to chars. Thank you.

The CJam translation has 9 characters, but it's way too similar so I hesitate to post it :p

@aditsu, you designed CJam, didn't you? Why didn't you include a one-character alias for ' '?

@PeterTaylor Well, I did include a one-character alias for " ".

Ruby 2.0, 59 characters
puts$<.map(&:chars).reverse.transpose.sort[1,50].map &:join

Input via stdin, assumes lines all have the same length. This is probably much longer than necessary. But at least it's readable ...

I think you can use $<.map instead.

@Howard That's one thing I always forget. Thanks!

what is [1,50] doing there?

@Charles It skips the first row, which contains all the newlines from the input. David mentioned in a comment that 50x50 is the maximum possible size, so instead of selecting all but the first row (1..-1), I just select 50 rows starting with the second one (1,50).

@Ventero got it.  cool. thanks!

Javascript (E6) 103
First try, just matrix operations. Each row in input string need to be padded.
Quite wordy.
R=t=>(x=t.split('\n').reverse().map(x=>[...x].sort()),x.map((c,i)=>x.map(r=>r[i]).join('')).join('\n'))

Pseudo code

string -> array of rows
up/down reverse array
each row -> char array
sort each row (coins 'fall' to right)
transpose
each char array in a row -> a string
join array -> single string

Oh wow, sorting is smart (+1)! Mind if I steal it?

I've never seen the syntax [...x] before. What is it called?

@ComFreak it's called spread [https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_operator]

@edc65 You broke your own link with brackets. Here is the correct link

J - 49 31 24 bytes
I think there might be unnecessary rotations in there, but otherwise it works fine. It's a function that takes the input as specified, coins being O. No trailing whitespace is required in the input.
New version, inspired by edc65's Javascript answer:
f=:[:|."1@|:[:/:~"1,;._2

Explanation:
f=:[:|."1@|:[:/:~"1,;._2
                   ,;._2 Split the string at every fret, which is the last character in the string (newline).
              /:~"1      Sort every row separately.
     |."1@|:             Rotate the array clockwise.

Old version:
f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)

Explanation:
f=:[:|:((#~=&' '),=&'O'#])"1@|:@(|."1@|:)@(,;._2)
                                          (,;._2) Split the string at every fret, which is the last character in the string (newline).
                                (|."1@|:)@        Rotate the array clockwise.
                             |:@                  Reverse the axes (columns become rows and vice-versa).
       ((#~=&' '),=&'O'#])"1                      Function that applies the "gravity"
                          "1                       Apply to every row separately:
                  =&'O'#]                           Get the O's in the row.
       (#~=&' ')                                    Get the spaces in the row.
                ,                                   Join them, spaces come first.
  [:|:                                            Reverse axes again.

Examples (note that multiline strings start with 0 : 0 and end withh a bracket):
   f 0 : 0
O
OO O
OOOOO
) NB. output starts now
O
O
OO
OO
OOO
   f 0 : 0
O O
O O
) NB. Output starts now.

OO
OO

If you can, sort before rotate

@edc65 You're a smart man.

Python 2 (69) (79)
for c in sorted(zip(*raw_input().split("\\n"))):print''.join(c[::-1])

Takes input padded with spaces so all lines have equal length. The split creates an arrat of each line. The zip effectively transposes the array. Then, the sorted sorts tuples in lexicographic order, causing all coins to fall to the bottom. Finally, we print each line, turning it back into a string, though we must reverse it first. Doing print'O'*c.count('O') is equivalent and uses the same number of characters.
Example run:
>> O    \nOO O \nOOOOO
O
O
OO
OO
OOO

Haskell — 86
Just learning, so I'm sure this can be improved.
import Data.List
c=putStr.unlines.filter(/="").sort.map(filter(/=' ')).transpose.lines

Sample Input:
let a = "O    \nOO O \nOOOOO"
let b = " O O \n O O "
c a
c b

Sample Output:
O
O
OO
OO
OOO

OO
OO

C, 167 119 bytes
This shorter version is (unfortunately?) much clearer than the original too.
m;j;b[99];r;main(){while(j=getchar()+1)j-11?m+=j-33&&++b[r]>m:++r;for(j=r;m+1;putchar(j--?m<b[j]?79:32:(j=r,m--,10)));}

Racket: 130
(let l((a'()))(let((b(sort(string->list(read-line))char<?)))(if
(null? b)(apply map(λ x(map display x)(newline))a)(l(cons b a)))))

It requires you pad with spaces so the lines are equal lemgth.

C# - 209 174 bytes
Right, I have to try this Code golf at some point I reckon. Created a function (r) that rotates the board and prints it. I guess I'm cheating a little when I am printing my char array, but if you cannot figure out why you shouldn't be mad :)
Thanks to ProgramFOX for the tips :)
void r(string s){int x=s.IndexOf('\n'),j,i=-1,k,z=x+1;var y=new char[x*x+x];for(;++i<x;y[z*(i+1)-1]='\n')for(k=j=x;j>0;)if(s[i*z+--j]=='0')y[k--*z-i-2]='0';Console.Write(y);}

Cheat

 new char[x*x+x] fills the array with '\0' and not ' '

Removing the newlines and removing the space between char[] and y will reduce your character count to 192 characters. Also, it is not really necessary to provide the keyword static when posting an answer here. Removing it will reduce your character count to 185 characters.

I was also able to remove 'ref ' which was forgotten there since an earlier try.

source: Stack Exchange

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

sort: votes


text:
A Most Excellent Code Golf Adventure
You dudes, the Most Excellent Adventure is a home brew roleplaying game system based on the Bill & Ted Films, plays gnarly air guitar riff.
In this game system, when you draw from your dice pool (you have between 1 and 12 ten-sided dice, with faces labelled 0-9) you need to connect the results as a phone number on your phone pad:

Here one person has rolled 4, 2, 8, 3, 8, and 2, dialling 3-2-2-4-8-8. The other 7, 4, 6, 3, 9, and 4, only dialling 4-4-7 or 3-6-9. And the longest number wins.
Bill and Ted want to play this game on their telephone kiosk, but haven't the first clue about programming. As Station isn't around, they want you to program it. The kiosk had access to all programming languages and OSs past and future (causality forbids you using any future technology... No imaginary python 7 !)
Your input is two numbers between 1 and 12, representing the number of dice player 1 and player 2 have respectively. The output is the result for each player, and the length of the largest number they could dial.
Input: 8 10
Output:
Player 1 rolled 1 2 3 4 5 6 7 8 with longest dialable number of 8.
Player 2 rolled 8 8 8 2 3 1 4 0 3 3 with longest dialable number of 10.

Numbers can be reordered and pressing the same key twice counts as two digits (which is why the above sequence 8 8 8 2 3 1 4 10 3 3 makes a six digit number not a 4 digit number)
Also, as you're programming this in a telephone kiosk you can only access 0-9, a-z, the * and a # keys in your code. Letters are accessed by repeated typing, much like on a mobile phone. Every other key must be input in the kiosk as its ASCII code in hex like so: #0a the upshot is when scoring your submission, these keys "cost" three times as many.[Unclear / Incorrect?]
For instance to type ~ you press the hash key once, the 7 and then 3 three times to cycle through the digits 3de. This gives the code #7e which corresponds to ~. When you upload you code here you can just type the ~, and count it as five characters.
The keypad looks a little like this:
For instance If your code had print() that would cost 15 for the print (7p 7pqr 4ghi 6mn 8t) plus 6 for the () (#28 #29).
This is code golf as Bill and Ted will get bored otherwise. Let the coding commence plays gnarly air guitar riff.

@m.buettner You're not allowed the star or hash character.

Never mind, I somehow stopped readong that sentence at "can't dial them".

You roll a 12-sided dice to obtain a number from 0-9? Is this right?

I think your tags are not going to work for this challenges. First, the restriction is really arbitrary and doesn't make codes any more interesting. And second it is not a good fit for [tag:popularity-contest]. What should I judge by? Popularity of the language/poster? And your idea with added features make this challenge too broad.

@nneonneo if I'm not mistaken you roll 12 six sided dice.

@Anzeo which makes it even more interesting how he can throw these numbers.

How do you throw a 0? I can take an educated guess, but it should be in the rules explicitly...

@all I will redo the rules in a minute please bear with me.

After the years of learning how to write good questions, I've come back in time to rewrite this one so that its more gnarly, and most excellent.

@Howard I've made some quite drastic edits, how does it look now?

The restriction to only using 0123456789ab*# rules out even the esoteric languages most commonly used on this site. You'll be lucky to get one answer, let alone two. PS What d10s are you using which have 10 rather than 0?

-1. The challenge of computing the exact probability is tricky by itself, and your character restriction rules out pretty much any useful code, let alone one that does what you want.

Isn't the maximum length equivalent to min(#dice, 10)?

@PeterTaylor, I thought the restriction would be fun, I'll see how many answers we get. The dice are these http://www.thediceshoponline.com/images/productimages/1168_1_big.jpg

If by maximum length you mean for that particular roll, how do you define the probability? Is that the probability of a roll that allows a path at least that long?

@jandvorak not if you roll all of one number

Your definition of "unreadable" is too subjective for code golf and it allows too much room for tactical voting.

@jandvorak yes your assumption is correct. If it is to hard I can lift the restriction.

Please use the sandbox next time

@Jan yeah, I thought the question was ready...

Just  to clarify: is dialing 3-2-2-4-8-8 equivalent to 3-2-4-8? If so, is 3-2-3-2-4-8?

@Jan that should be clear from the example but I've spelled it out. Is the extra cost of characters clear enough?

Does your revision #4 mean that ,-./\]^_|}~ and both cases of lmno (and most of Unicode) are still inaccessible? The hex codes of their ASCII codes contain CDEF.

@jandvorak why would that make them inaccessible? You can access 0-9 as well as a-b and * and #.  That is 0123456789abcdefghijklmnopqrstuvwxyz*#

How would you encode ~? The obvious solution would be #7f, but f doesn't exist. You can reencode f to produce #7#66, but the code length doesn't work out. Not to mention your encoding is lossy since an escape sequence escapes to itself.

@jandvorak the is an f in my list above

Uh... You can't input letters yet they cost one point each? How so? So, alphanumerics, asterisks and hashes cost one each, and the rest costs three each? How does that match up with your storyline?

@jandvorak I explain in my post : Also as your programming this in a telephone kiosk you can only access 0-9, a-b, the * and a # keys in your code, every other key must be input in the kiosk as its ASCII code in hex like so #0a the upshot is these keys "cost" three times as many.

When you say (repeatedly) a-b, do you mean a-z? There's a difference of 24 characters.

So... Does p cost one, or three points? If one, your comments are incorrect. If three, your example in the body is. Also, if three, how much does ~ cost? Its escape sequence is #7e, which you can't type on the phone keypad. Your list in the comment doesn't make any sense to me.

As a side note - what keypad is it that you have in mind? Most of them doesn't have the a, b keys. Not even the one on your diagram does. The ones that do that I know of also have c and d.

Sorry all I made a massive mistake with "a-b" vs "a-z"

@jandvorak better?

I think it's clear now. It's still primarily a rather difficult mathematical challenge with unusual code scoring mechanics.

@jandvorak thanks glad it's clear

The roll "8 8 8 2 3 1 4 0 3 3" can be reordered "3 3 3 2 1 4 8 8 8 0" to make a 10 digit number on the keypad, if I'm not mistaken.

@algorithmshark well spotted

What is left to collapse?

Did you try this question in the sandbox first?

@nneonneo no. But I've learnt my lesson.

Here's a Perl program that converts a program to a sequence of digits, as well as outputting the total score. Although this code isn't reversible because it's not self-synchronizing (You can't tell whether "222222222" is "abc" or "bbb" or "aa2a" or any of a bunch of choices) I decided that since # is an escape to introduce hex sequences, "#" itself has to be coded as #23. If that's in error, you can change my %map = qw(* *); to my %map = qw(* * # #); to allow "#"s to pass through unscathed. Code: http://pastebin.com/raw.php?i=NcwRxP9w

VBScript - 1668 telephone keypresses (was 1708)
My entry is golfed a bit more - I realized (doh!) that the variable names should be characters that require less telephone keypresses (a,d,g,j,etc).
This program produces the output exactly as shown and takes the input as command line parameters.  If line endings are 1 byte there is no advantage to using : to put it all on one line (#0a vs #3a).  Run it with cscript script.vbs 8 10 replacing 8 and 10 with whatever values you want - it tries every combination in order to get the maximum string so it is SLOW.
I just have one question: if you needed a two numbers beside each other that were both on the same key isn't it a bit ambiguous.  Wouldn't the text a=e (22#333333) be the same keypresses as a>d (22#333333)?  How do you differentiate where the character boundaries are?  I didn't specifically check for every possible occurance of where things on the same key are beside themselves and I don't know what I would have done if I did notice it...
sub b(d,m)
p=true
a=len(m)
for g=1to a-1
p=p and instr(split("7890*1245*123456*2356*124578*123456789*235689*45780*4567890*56890","*")(mid(m,g,1)),mid(m,g+1,1))>0
next
if p and t<a then t=a
if d=""then exit sub
a=len(d)
for g=1to a
w=""
if g>1then w=left(d,g-1)
p=""
if g<a then p=mid(d,g+1)
b w+p,m+mid(d,g,1)
next
end sub
randomize
set m=wscript.arguments
for e=1to 2
d=""
j="Player "+cstr(e)+" rolled"
for t=1to mid(10000+m.item(0)*100+m.item(1),e*2,2)
w=cstr(int(rnd()*10))
j=j+" "+w
d=d+w
next
j=j+" with longest dialable number of"
t=0
b d,""
wscript.echo j+" "+cstr(t)
next

Ok, I am finally ready to score my entry - that of course means no more changes to it because of how long it takes to transform it to a score.  The transformed phone input is:
77777888222#20222#2833#2222266#29#02277#333887777888333#02222#3335555333666#2866#29#02233336666777
7#2044#3331886666#2022#2331#02277#33377#202266633#20444466677777887777#2877777775555444488#28#2278
90*1245*123456*2356*124578*123456789*235689*45780*4567890*56890#22#22222#22*#22#29#2866444433#2866
#2222244#222221#29#29#2222266444433#2866#2222244#22221#222221#29#29#33330#02266633399988#022444433
33#2077#202266633#2088#3222222#2088444333666#2088#33322#02244443333#2033#333#22#2288444333666#2033
3999444488#2077777888222#02222#3335555333666#2833#29#022333366667777#2044#3331886666#2022#02299#33
3#22#22#02244443333#2044#3333188444333666#2099#3335555333333388#2833#2222244#2331#29#02277#333#22#
22#02244443333#2044#3222222#2088444333666#2077#33366444433#2833#2222244#22221#29#022222#2099#22227
7#2222266#222266444433#2833#2222244#222221#29#02266633399988#02233366633#2077777888222#02277772266
633666666444499999333#0227777733388#2066#33399777772222777744447788#233322777744888663336668877777
#022333366667777#20333#3331886666#202#02233#333#22#22#02255#333#22#5055552299993337777#20#22#22222
22277777887777#28333#29#2222#22#20777766665555555533333#22#022333366667777#2088#3331886666#2066444
433#2810000#222266#233344448833366#280#29*100#222266#233344448833366#281#29#22222333*2#222222#29#0
2299#333222277777887777#28444466688#28777766633#28#29*10#29#29#02255#33355#2222#22#20#22#222299#02
233#33333#222299#02266633399988#02255#33355#2222#22#2099444488444#2055556666666443337777788#203344
44225555222225555333#20666888662223337777#2066663333#22#02288#3330#022222#2033#22222#22#22#0229977
7772222777744447788#233333322224446666#2055#2222#22#20#22#2222222277777887777#2888#29#022666333999
88

You don't need to count newlines as 2 bytes. It does not matter whether you are on Windows or not, here you can always count them as 1 byte.

I have just had an idea how to make it much shorter - I'll have a new version soon (and I will put the linefeeds back if they count as the same length as a colon)

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


text:
Sum up a number in words
Here's a simple one.
In the shortest code possible, given an arbitrary number such as 567421, print it out in words:
five
six
seven
four
two
one

You may assume the input is an integer that is already provided in a one-letter variable such as n.

I see, sorry about that, didn't find those when i was searching.

Though both possible duplicates ask something slightly different.

In particular the only change you need to make to answers of the duplicate mentioned by undergroundmonorail is to call the code you already have for each digit of the input.

Python
for i in `n`:print' ottffssennwhoiieiieoruvxvgn  ere ehe  e   nt'[int(i)::9]

"Inspired" by https://codegolf.stackexchange.com/a/32156/18638