# Question
Title: 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

1. 6.86688 – **Kuroi Neko**
2. 8.73108 – **user2357112 - 2nd submission**
3. 9.86627 – **nneonneo**
4. 10.66109 – **user2357112 - 1st submission**
5. 12.49643 – **Ray**
6. 40.0759 – **pseudonym117** (probabilistic)

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

# Answer
# 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";
?>

```
> 5 votes

# Answer
# 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
> 10 votes

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

```
> 6 votes

# Answer
# 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

```
> 3 votes

# Answer
## 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

```
> 1 votes

# Answer
**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

```
> 1 votes

---
Tags: code-challenge, graph-theory, path-finding
---


title: Hello World in 1024 characters

text:
# Question
Title: Hello World in 1024 characters
In exactly 1024 characters, no more, no less:

* Must print `Hello World`.
* Must not use unnecessary whitespace.
* Must not use comments.

Judging should favor creativity and/or humor over simple obfuscation when voting up answers.

---

The earliest I will select an answer is the 11th (Sunday) of November (2012). I'm seeing some awesome entries so far, can't wait to see what else people come up with.

# Answer
> 50 votes
## C# (and without “Hello World” anywhere)

Code-golfed, so that obviously no unnecessary whitespace is used:

```
using System;using System.IO.Compression;using System.Runtime.Serialization;using System.Runtime.Serialization.Json;using System.Linq;using System.Net;using System.Text.RegularExpressions;class C{static void Main(){var g=WebRequest.Create("https://api.stackexchange.com/2.1/questions/8859?site=codegolf&filter=withbody");var r=(HttpWebResponse)g.GetResponse();if(r.StatusCode==HttpStatusCode.OK){var s=r.GetResponseStream();foreach(var a in r.ContentEncoding.ToLowerInvariant().Split(',').Reverse())switch(a){case"gzip":s=new GZipStream(s,CompressionMode.Decompress);break;case"deflate":s=new DeflateStream(s,CompressionMode.Decompress);break;default:throw new InvalidOperationException();}var d=new DataContractJsonSerializer(typeof(R));var q=(R)d.ReadObject(s);var e=new Regex("<code>([^<]*)</code>");var m=e.Match(q.I[0].B);Console.WriteLine(m.Groups[1].Value);}}}[DataContract]public class R{[DataMember(Name="items")]public I[]I{get;set;}}[DataContract]public class I{[DataMember(Name="body")]public string B{get;set;}}

```

Formatted for readability:

```
using System;
using System.IO.Compression;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Json;
using System.Linq;
using System.Net;
using System.Text.RegularExpressions;

class C
{
    static void Main()
    {
        var g = WebRequest.Create("https://api.stackexchange.com/2.1/questions/8859?site=codegolf&filter=withbody");
        var r = (HttpWebResponse)g.GetResponse();
        if (r.StatusCode == HttpStatusCode.OK)
        {
            var s=r.GetResponseStream();
            foreach (var a in r.ContentEncoding.ToLowerInvariant().Split(',').Reverse())
            switch(a)
            {
                case "gzip":
                    s = new GZipStream(s,CompressionMode.Decompress);
                    break;
                case "deflate":
                    s = new DeflateStream(s,CompressionMode.Decompress);
                    break;
                default:
                    throw new InvalidOperationException();
            }
            var d = new DataContractJsonSerializer(typeof(R));
            var q = (R)d.ReadObject(s);
            var e = new Regex("<code>([^<]*)</code>");
            var m = e.Match(q.I[0].B);
            Console.WriteLine(m.Groups[1].Value);
        }
    }
}

[DataContract]
public class R
{
    [DataMember(Name="items")]
    public I[] I { get; set; }
}

[DataContract]
public class I
{
    [DataMember(Name="body")]
    public string B { get; set; }
}

```

The program retrieves this question from Code Golf using Stack Exchange API, finds the first piece of text formatted as code (which, in case of this question, is the “Hello World” text), and prints it out.

# Answer
> 41 votes
# brainfuck

```
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++>+++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++[+++++<]>[.[-]>]

```

This is 1024 characters, excluding the whitespace I added to make a nice 64\*16 block.

The strategy is as follows:

* Fill the first few bytes with characters "Hello World", except each byte is 5 too small. This is done in all but the last 16 characters. The first byte is left blank in order to not have the pointer go out of bounds later.
* Bring the pointer back to the start, adding 5 to each byte using `[+++++<]`
* Go through the characters, print them and zero the byte using `>[.[-]>]`

# Answer
> 39 votes
# JavaScript (1024 bytes...)

No unnecessary whitespace? What about unnecessary semicolons that JavaScript doesn't need at all? Let's add those semicolons to make people like Crockford happy.

```
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;console.log('Hello World');;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

```

Yes, I'm aware that this is abuse of rules.

# Answer
> 37 votes
## Shell :)

```
echo '
.@@@@......@@@@.@@@@@@@@@@@.@@.........@@...........@@@@@@@@..
..@@@......@@@..@@.......@@..@..........@..........@........@@.
..@@@......@@@..@............@..........@.........@..........@@
..@@@@@@@@@@@@..@@@@@@.......@..........@.........@..........@@
..@@@@@@@@@@@@..@@@@@@.......@..........@.........@..........@@
..@@@......@@@..@............@..........@.........@..........@@
..@@@......@@@..@@.......@@..@@@@@@@@@@.@@@@@@@@@..@.......@@@.
.@@@@......@@@@.@@@@@@@@@@@..@@@@@@@@@@.@@@@@@@@@...@@@@@@@@..
@@............@@@..@@@@@.....@@@@@@@.....@@........@@@@@@@@@@.
.@@..........@@...@.....@.....@.....@@...@@.........@@.......@.
..@@........@@...@.......@....@.....@@...@@.........@@........@
...@@..@@..@@...@.........@...@@@@@@.....@@.........@@........@
....@@@.@@.@....@........@@...@@@@.@@....@@.........@@........@
....@@...@@@....@.......@@....@.....@@...@@.........@@.......@
...@@......@@....@.....@@.....@......@@..@@@....@@..@@@@...@@.
..@@.......@@@....@@@@@@....@@.......@..@@@@@@@@...@@@@@@@@@'

```

# Answer
> 37 votes
# Mathematica 1024 chars

```
Graph[Partition[
 Riffle[Characters[
 StringTake[ElementData[][[2]], 3] <>
  StringTake[WordData["high", "Antonyms"][[2, 2, 1]], 2] <>
  FromCharacterCode[Power[2, 5]] <>
  StringTake[GraphData[][[Prime@705]], 2] <>
  StringTake[AstronomicalData["Planet"][[1]], {3}] <> "ld"],
Rest@Characters[
  StringTake[ElementData[][[2]], 3] <>
   StringTake[WordData["high", "Antonyms"][[2, 2, 1]], 2] <>
   FromCharacterCode[Power[2, 5]] <>
   StringTake[GraphData[][[Prime[705]]], 2] <>
   StringTake[AstronomicalData["Planet"][[1]], {3}] <> "ld"]],
   2] /. {a_, b_} :> DirectedEdge[a, b],

EdgeLabelStyle -> Power[2, 4],
EdgeLabels -> (Partition[
   Riffle[l =
     Characters[
      StringTake[ElementData[][[2]], 3] <>
       StringTake[WordData["high", "Antonyms"][[2, 2, 1]],
        1 + 1] <> FromCharacterCode[Sqrt[Sqrt[1048576]]] <>
       StringTake[GraphData[][[Prime[705]]], 2] <>
       StringTake[AstronomicalData["Planet"][[1]], {3}] <> "ld"],
    Rest@l], 2] /. {a_, b_} :> DirectedEdge[a, b]) +
Power[{1, 8, 27, 64, 125, 216, 343, 512, 729, 1000},
 1/3] /. {Plus[a_, b_] :> Rule[b, a]},
VertexLabelStyle -> Directive[RGBColor[0, 0, 1], Large],
VertexLabels -> "Name", ImagePadding -> Power[5, 2],
ImageSize -> 2^2*5^2*7]

```

**De-bowled** (partially)

For those who don't have access to Mathematica's curated data:

```
 ElementData[][[2]]
 WordData["high", "Antonyms"][[2, 2, 1]]
 GraphData[][[Prime[705]]]
 AstronomicalData["Planet"][[1]]

```

> "Helium"
>
> "low"
>
> "WongGraph"
>
> "Mercury"

"Hel" (from "Helium") + "lo" (from "low") + " " (`FromCharacterCode[32]`) + "Wo" (from "WongGraph") + "r" (from "Mercury") + "ld"

yields the string "Hello World".

The string is split into characters, each of which becomes a vertex in the following graph:

```
Graph[{"H" \[DirectedEdge] "e", "e" \[DirectedEdge] "l",
 "l" \[DirectedEdge] "l", "l" \[DirectedEdge] "o",
 "o" \[DirectedEdge] " ", " " \[DirectedEdge] "W",
 "W" \[DirectedEdge] "o", "o" \[DirectedEdge] "r",
 "r" \[DirectedEdge] "l", "l" \[DirectedEdge] "d"},

EdgeLabelStyle -> 16,
EdgeLabels -> {"H" \[DirectedEdge] "e" -> 1, "e" \[DirectedEdge] "l" -> 2, "l" \ [DirectedEdge] "l" -> 3,
"l" \[DirectedEdge] "o" -> 4, "o" \[DirectedEdge] " " -> 5,
" " \[DirectedEdge] "W" -> 6, "W" \[DirectedEdge] "o" -> 7,
"o" \[DirectedEdge] "r" -> 8, "r" \[DirectedEdge] "l" -> 9,
"l" \[DirectedEdge] "d" -> 10},
VertexLabelStyle -> Directive[Blue, Large], VertexLabels -> "Name", ImagePadding -> 25]

```

# Answer
> 22 votes
## C, 1024 characters

Here's an adaptation of my answer to another "Hello, world" question:

I'm not sure what's "unnecessary whitespace". I used spaces, indentation and line breaks to make code nicely formatted, but strictly speaking most of it is unnecessary. I did count the whitespace in the 1024 chars.

*EDIT*: Changed to `return!` in the first line. Nicer this way, I think.

```
#include <stdio.h>
int main(int argc, char **argv, char **envp) {
        return!
        putchar(-~-~-~-~-~-~-~-~-~-~!
        putchar(~-~-~-~-~-~-~-~-
        putchar(~-~-~-~-~-~-
        putchar(-~-~-~
        putchar(-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
        putchar(-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
                ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
        putchar(-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
                ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
                -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
                ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
                -~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
                ~-~
        putchar(-~-~-~
        putchar(
        putchar(-~-~-~-~-~-~-~
        putchar(-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
        putchar(-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
                ~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~
                -~-~-~0))))))))))));
}

```

## Another one - Python this time

1024 characters, 944 of them are whitespace, all necessary.

```
print 11*'%c'%tuple(len(x)+8for x in'                                                                /                                                                                /                                                                                /                                                                                /                                                                                /                        /                                                                               /                                                                                /                                                                                /                                                                                /                                                                                '.split('/'))

```

# Answer
> 11 votes
### GolfScript

I had to modify the max length of scripts on http://golfscript.apphb.com/ for this :)

```
1)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))1)))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))))))))1))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))1))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))' '1))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))1)))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))1))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))))))))))1))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))1))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))){)}8*]''+

```

Run the program online here.

# Answer
> 7 votes
## Haskell

```
main=putStrLn hello_world
 where hello_world=show H++ello_world
        where ello_world=show E++llo_world
               where llo_world=show L++lo_world
                      where lo_world=show L++o_world
                             where o_world=show O++_world
                                    where _world=show ++world
                                           where world=show W++orld
                                                  where orld=show O++rld
                                                         where rld=show R++ld
                                                                where ld=show L++d
                                                                       where d=show D
data Letter=H|E|L|O||W|R|D
instance Show Letter where
 show H=["Hello, World!"!!0]
 show E=["Hello, World!"!!1]
 show L=["Hello, World!"!!2]
 show O=["Hello, World!"!!4]
 show =["Hello, World!"!!6]
 show W=["Hello, World!"!!7]
 show R=["Hello, World!"!!9]
 show D=["Hello, World!"!!11]
main::IO()

```

1024 characters, including the (*necessary*, Haskell is indentation-sensitive!) whitespace. (Though you could remove the line breaks entirely, but who wants an unreadable one-liner? Even now, it's hard enough to guess what this program does, what with the lack of comments...)

# Answer
> 5 votes
# Python 2 - 1024

```
print''.join(chr(32if c[0]>"z"else """
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy
eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam
voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita
kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem
ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod
tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At
vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd
gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum
dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor
invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero
eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no
sea takimata sanctus est Lorem ipsum dolor sit amet. Duis autem vel enum...
""".count(c[0]+c[1])+99)for c in zip(' yddd~ doda','t iio~doliu')).title()

```

Writing this program was quite a tedious process, the length of the algorithm (first and last line) impacts the length of the dummy text (to meet the required total number of 1024 characters), which in turn impacts the count of certain substrings... And even worse: Some counts might just not occur with any substring, so I need to adjust the general bias 99, which impacts all other letters. But happily, a helper script is always quickly implemented. :)

# Answer
> 4 votes
Javascript, cut and paste into console (chrome browser of course) on this page to see the page disappear!

```
function pad_with_zeroes(number, length){
var my_string = '' + number;
while (my_string.length < length){
my_string = '0' + my_string;
}
return my_string;
}
var code_tags = document.getElementsByTagName('code');
var hello_world = code_tags[0].innerHTML;
var body_tags = document.getElementsByTagName('body');
var body = 'NULL';
body = body_tags[0];
var html_input = "<div id='div_that_holds_hello_world' style='font-size:50px; color:#987324; width: 900px; height: 900px; text-align: center;'><span id='hello_world_span'>" +hello_world+ "</span></div>";
body.innerHTML = html_input;
var span = document.getElementById('hello_world_span');
var div = document.getElementById('div_that_holds_hello_world');
var j_c = 1;
var i_c = 0;
var setIn = setInterval(function(){
i_c++;
if(i_c%2 == 0){
span.style.display = 'none';
}else{
span.style.display = 'block';
}
if(i_c%50 != 0){
div.style.fontSize = j_c + 'px';
if(i_c < 1000000){
div.style.color = '#'+ pad_with_zeroes(i_c, 6);
}else{
i_c = 0;
}
j_c++;
}else{
j_c = 0;
}
}, 500);

```

# Answer
> 2 votes
## Javascript

Lipsum Test with a regex:

```
"Hello World|Ta what. Soft lad mardy bum that's champion. Tha knows chuffin' nora tha knows tha knows mardy bum shurrup. Where's tha bin. Any rooad ne'ermind. Is that thine cack-handed ah'll gi' thee a thick ear. Ah'll gi' thee a thick ear. Gerritetten tintintin ah'll learn thi shurrup chuffin' nora. Sup wi' 'im. Nah then soft southern pansy tintintin breadcake t'foot o' our stairs how much. Shu' thi gob be reet th'art nesh thee ah'll gi' thee a thick ear that's champion. Shu' thi gob t'foot o' our stairs tha daft apeth where's tha bin ah'll gi' thi summat to rooer abaht. Wacken thi sen up eeh eeh. Shu' thi gob tha what that's champion soft southern pansy ah'll learn thi a pint 'o mild. Appens as maybe gi' o'er nobbut a lad nobbut a lad.Big girl's blouse a pint 'o mild. Big girl's blouse ah'll learn thi. A pint 'o mild. How much ah'll gi' thi summat to rooer abaht michael palin nay lad. Gerritetten a pint 'o mild be reet nay lad. Nay lad how much ee by gum. 1234567I love feet so much.".match(/Hello World/)[0]

```

The regex: `.match(/Hello World/)[0]`

# Answer
> 2 votes
# Python

Kinda cheap:

```
print"""Hello World"""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""+""

```

---
Tags: popularity-contest, hello-world, code-shuffleboard
---


title: BrainFlow Interpreter!

text:
# Question
Title: BrainFlow Interpreter!
# BrainFlow

## What is BrainFlow?

BrainFlow is an extension of BrainF\**k (BFk) with 3 additional commands for added functionality and confusion.

## What commands?

In addition to the normal BFk commands, we also have:

> **^** *Jumps to the cell # depending on the value in the cell. Ex: If we are at cell # 0 with a value of 4, ^ will jump us to cell # 4.*

> **=** *Sets the value at the cell to the index of the cell. Ex: If we are at cell # 4 with a value of 0, = will set our value to 4.*

> **&** *Will set the value at the current cell equal to the value at the cell based on the value in our current cell. (This one's hard to word, so here's an example!) Ex: We are at cell # 33 and our current value at this cell is 7, & will set our current value at cell # 33 to whatever value is in cell # 7.*

## Optional Challenges

Accomplishing any of the following will apply the specified bonus to your byte count.

`Interpreter written in BrainFlow` *(Can be interpreted by the sample and contains at least one meaningful* **^ =** *or* **&***):* **Score / 3**

`Interpreter written in BrainF**k:` **Score / 2**

`Doesn't contain any English letters (in either upper or lower case):` **Score - 20**

`Doesn't contain any of the BrainFlow / BFk commands in the interpreter itself:` **Score - 50**

# Example

An example Java interpreter:

```
import java.util.Scanner;

public class Interpreter {

    private String exp;

    private int[] values = new int[256];
    private int index = 0;

    private Scanner in;

    public Interpreter(String exp, Scanner in){
        this.exp = exp;
        this.in = in;
    }

    public void run(){
        //Reset index and values
        for(int i = 0; i < values.length; i++){
            values[i] = 0;
        }
        this.index = 0;

        System.out.println("Starting...");
        this.process(this.exp, false);
        System.out.println("\nDone.");
    }

    private void process(String str, boolean loop){
        boolean running = loop;
        do{
            for(int i = 0; i < str.length(); i++){
                switch(str.charAt(i)){
                case '>':increaseIndex();break;
                case '<':decreaseIndex();break;
                case '+':increaseValue();break;
                case '-':decreaseValue();break;
                case '[':
                    String s = str.substring(i);
                    int j = this.getClosingIndex(s);
                    if(this.values[this.index] == 0){
                        i +=j;
                        break;
                    }
                    process(s.substring(1, j), true);
                    i += j;
                    break;
                case '.':
                    int v = this.values[this.index];
                    System.out.print((char)v);
                    break;
                case ',':this.values[this.index] =  this.in.next().charAt(0);break;
                case '^':this.index = this.values[this.index];break;// Jumps to the index specified in the current cell.
                case '=':this.values[index] = this.index;break;// Sets the value at cell #x to x
                case '&':this.values[index] = this.values[this.values[index]];break;// If cell contains X, makes value of current cell equal to value in cell X
                default:
                    //Ignore others
                    break;
                }
            }
            if(this.values[this.index] == 0){
                running = false;
            }
        }while(running);
    }

    private void increaseIndex(){
        if(++this.index >= this.values.length){
            this.index = 0;
        }
    }

    private void decreaseIndex(){
        if(--this.index < 0){
            this.index = this.values.length - 1;
        }
    }

    private void increaseValue(){
        int newVal = this.values[this.index] + 1;
        if(newVal >= this.values.length){
            newVal = 0;
        }
        this.values[this.index] =  newVal;
    }

    private void decreaseValue(){
        int newVal = this.values[this.index] - 1;
        if(newVal < 0){
            newVal = this.values.length - 1;
        }
        this.values[this.index] =  newVal;
    }

    private int getClosingIndex(String str){
        int openings = 0;
        int closings = 0;
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            if(c == '['){
                openings++;
            }else if(c == ']'){
                closings++;
            }
            if(openings == closings){
                return i;
            }
        }
        return -1;
    }
}

```

Not even close to golfed but should provide a good starting point.

Lowest final score wins, where score is number of bytes in your program after the applicable Challenge reductions have been taken into account.

# Testing

The following BrainFlow program should print the specified output after reading a '+' char from stdin:

```
<<,++++[>++++[>++++<-]<-] Set cell #0 to a value dependent on input
>>>+[[-]&>=]+& Set every other cell to that value
[ Start loop
+^ Add one to current value and jump to that cell index
. Print the value at that cell
& Copy value from specified cell
] End loop

```

Output:

```
ðñðòñðòðôóòñóñôóðòõóñõðôôóòñööõôöðóöðõðùõñô÷ùõóñöóùñô÷øôøõôòöõóðòöóñ÷ðõôûôòú÷úø÷öùøöùñøðùúðûðþöûñùýøðòñ

```

# Answer
# **Perl - 233 230 210 182 180 176 174 171 bytes
**

`$/=$,;%d=qw(> $p++ < $p-- + $v[$p]++ - $v[$p]-- , $v[$p]=ord+getc . print+chr+$v[$p] [ while+$v[$p]{ ] } ^ $p=$v[$p] = $v[$p]=$p & $v[$p]=$v[$v[$p]]);eval$d{$_}for<>=~/./g`
Simply took an existing BrainFuck interpreter of mine, golfed it, and added the BrainFlow functions.
Update: Completely restructured the program to lose 28 bytes.
> 7 votes

# Answer
Let's get this party started.

## C - 408 384 393 390 380 357 352 bytes (still chipping away)

Compile with `gcc` on a POSIX compliant system. The first argument is the name of a file containing the Brainflow code to be interpreted. Newlines added to improve readability.

```
i,p,b[9999],*k=b;unsigned char g[9999],a[30000],*d=a;main(c,v)char**v;
{read(open(v[1],0),g,9999);while(c=g[i++]){c-62||d++;c-60||d--;c-43||
(*d)++;c-45||(*d)--;c-46||putchar(*d);c==44?*d=getchar():0;c==94?d=a+*d:0;
c==61?*d=d-a:0;c==38?*d=a[*d]:0;c==93?i=*(--k):0;if(c==91)if(*d)*k++=i-1;else
while(c=g[i++]){c==91?p++:0;if(c==93)if(p)p--;else break;}}}

```

And the ungolfed version if you're interested. Let me know if you see any bugs.

```
int i, depth, buffer[9999], *stack = buffer;
unsigned char c, program[9999], array[30000], *data = array;

main(int argc, char **argv)
{
    read(open(argv[1], 0), program, 9999);

    while(c = program[i++]){
        if (c=='>') data++;
        if (c=='<') data--;
        if (c=='+') (*data)++;
        if (c=='-') (*data)--;
        if (c=='.') putchar(*data);
        if (c==',') *data=getchar();
        if (c=='^') data=array+*data;
        if (c=='=') *data=data-array;
        if (c=='&') *data=array[*data];
        if (c==']') i=*(--stack);
        if (c=='[')
            if (*data) *stack++=i-1;
            else while (c=program[i++]) {
                    if (c=='[') depth++;
                    if (c==']') if (depth) depth--; else break;
            }
    }
}

```

Updates:

* Thanks for the initial feedback which allowed me to knock an extra 24 bytes off.
* Sign bug fixed. Added another 9 bytes.
* Saved another 3 bytes per es1024's suggestions.
* Saved another 10 bytes per more suggestions from es1024.
* Just remembered that global variables are initialized to 0. Switched from fread and fopen to read and open. Saved 23 bytes.
* Don't need to set null terminator on program because buffer is already initialized to zero. Saved 5 bytes.
> 6 votes

# Answer
## AppleScript 972 670

Mostly golfed although there's no way it will ever win. I don't know why I didn't think about just constructing a script like the perl one did (though it still won't win haha). This could probably be golfed more by readjusting how the index values a bit better, AppleScript is frustratingly (for this type of stuff) a 1 index language.

Just pass the BrainFlow code in to e(). Note that AppleScript's ASCII commands use MacOSRoman encoding, so while the output will appear different, it is correct looking at its binary representation. You'll need to take that into account when passing in any upper ASCII characters though on "," commands.

```
on e(x)
set d to {"", "set b'sitem(i+1)to(b'sitem(i+1)+1)mod 256", "set b'sitem(i+1)to(b'sitem(i+1)+255)mod 256", "set i to(i+1)mod 256", "set i to(i+255)mod 256", "repeat while b'sitem(i+1)≠0", "end", "set o to o&(ASCII character b'sitem(i+1))", "display dialog \"\"default answer\"\"
set b'sitem(i+1)to ASCII number result'stext returned'stext1", "set i to b'sitem(i+1)", "set b'sitem(i+1)to i", "set b'sitem(i+1)to b'sitem(b'sitem(i+1)+1)"}
set s to "set i to 0
set b to{}
repeat 256
set b'send to 0
end
set o to  \"\"
"
repeat with c in x'stext
set s to s&d'sitem((offset of c in "+-><[].,^=&")+1)&"
"
end
set s to s&"return o"
return run script s
end

```

(because what f\***s with your brain more than writing a brainfuck/flow interpreter in another language that f\***s with your head way too much?
> 6 votes

---
Tags: code-golf, interpreter
---