Hungry Image Snake - Hole #3 Hole #1

Joe the snake is hungry.

He eats pictures, one pixel at a time.

He really likes bright pixels.

The Challenge

Program Joe to eat the most bright pixels he can find, given that he can only move up, down, left or right.

Specifications


Joe must start at the upper left pixel of the image.
Joe can only move horizontally or vertically by 1 each move
Joe has only enough time to move 1/3 of the amount of pixels in the picture (1/3 as many moves as pixels). If the number of pixels is not a multiple of 3, round down to the nearest integer.
Joe may cross his path, though that counts as 0 brightness
Brightness is based on the sum of r,g and b, so rgb(0,0,0) has a brightness of 0 while rgb(255,255,255) has maximum brightness.


Input

You may input the image however you like.

Output


an image showing the end result of your picture (with black being eaten pixels). 
The amount of brightness eaten (please specify what range in your answer)


Scoring

Your program will be graded on:


The average brightness of pixels Joe eats
/ The average brightness of the pixels in the picture*


*you may hardcode this in your program

Your total score will be the average of the scores for the following images:

Test images:





http://upload.wikimedia.org/wikipedia/en/thumb/f/f4/The_Scream.jpg/800px-The_Scream.jpg
C++, Score: 1.42042 1.46766

This is essentially a slightly more sophisticated version of the two existing solutions:
Of the four possible moves, it selects the one that maximizes brightness.
However, instead of only looking at the brightness of the target pixel, it looks at the weighted sum of pixel-brightness in the neighborhood of the target pixel, where pixels closer to the target have a greater weight.

EDIT: Using nonlinear brightness in neighborhood calculation improves the score slightly.

Compile with g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Requires cairo.

Run with joe &lt;image-file&gt; [&lt;radius&gt;].
&lt;image-file&gt; is the input PNG image.
&lt;radius&gt; (optional argument) is the radius of the summed-over neighborhood, in pixels (smaller is faster, larger is (roughly) better.)
Outputs the score and an image named out.&lt;image-file&gt;.

#include &lt;cairo/cairo.h&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;algorithm&gt;
#include &lt;string&gt;

using namespace std;

int main(int argc, const char* argv[]) {
    auto* img = cairo_image_surface_create_from_png(argv[1]);
    int width = cairo_image_surface_get_width(img),
        height = cairo_image_surface_get_height(img),
        stride = cairo_image_surface_get_stride(img);
    unsigned char* data = cairo_image_surface_get_data(img);

    double* brightness = new double[width * height];
    double total_brightness = 0;
    for (int y = 0; y &lt; height; ++y) {
        for (int x = 0; x &lt; width; ++x) {
            const unsigned char* p = data + stride * y + 4 * x;
            total_brightness += brightness[y * width + x] = p[0] + p[1] + p[2];
        }
    }

    const int r = argc &gt; 2 ? stoi(argv[2]) : 64, R = 2 * r + 1;
    double* weight = new double[R * R];
    for (int y = -r; y &lt;= r; ++y) {
        for (int x = -r; x &lt;= r; ++x)
            weight[R * (y + r) + (x + r)] = 1.0 / (x*x + y*y + 1);
    }

    auto neighborhood = [&amp;] (int x, int y) {
        double b = 0;
        int x1 = max(x - r, 0), x2 = min(x + r, width - 1);
        int y1 = max(y - r, 0), y2 = min(y + r, height - 1);
        for (int v = y1; v &lt;= y2; ++v) {
            const double *B = brightness + width * v + x1;
            const double *W = weight + R * (v - (y - r)) + (x1 - (x - r));
            for (int u = x1; u &lt;= x2; ++u, ++B, ++W)
                b += (*W) * (*B) * (*B);
        }
        return b;
    };

    int n = (2 * width * height + 3) / 6;
    int x = 0, y = 0;
    double path_brightness = 0;
    int O[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int i = 0; i &lt; n; ++i) {
        if (i % 1000 == 0) cerr &lt;&lt; (200 * i + n) / (2 * n) &lt;&lt; "%\r";

        path_brightness += brightness[width * y + x]; brightness[width * y + x] = 0;
        unsigned char* p = data + stride * y + 4 * x;
        p[0] = p[1] = 16 * i % 255; p[2] = 0;

        auto O_end = partition(begin(O), end(O), [&amp;] (const int* o) {
            return x + o[0] &gt;= 0 &amp;&amp; x + o[0] &lt; width &amp;&amp;
                   y + o[1] &gt;= 0 &amp;&amp; y + o[1] &lt; height;
        });
        const int* o_max; double o_max_neighborhood = -1;
        for (auto o = O; o != O_end; ++o) {
            double o_neighborhood = neighborhood(x + (*o)[0], y + (*o)[1]);
            if (o_neighborhood &gt; o_max_neighborhood)
                o_max = *o, o_max_neighborhood = o_neighborhood;
        }
        x += o_max[0]; y += o_max[1];
    }

    cout &lt;&lt; (path_brightness * width * height) / (n * total_brightness) &lt;&lt; endl;

    cairo_surface_write_to_png(img, (string("out.") + argv[1]).c_str());

    delete []brightness;
    delete []weight;
    cairo_surface_destroy(img);
}


Results

Bridge    1.39945
Balls     1.77714
Scream    1.38349
Fractal   1.31727
Vortex    1.66493
Tornado   1.26366
-----------------
Average   1.46766









More eye-candy