Serpiente Hambrienta de Imagen - Hoyo # 3

25

Hoyo # 1

Joe la serpiente tiene hambre.

Come fotos, un píxel a la vez.

Realmente le gustan los píxeles brillantes.

El reto

Programe a Joe para que coma los píxeles más brillantes que pueda encontrar, dado que solo puede moverse hacia arriba, abajo, izquierda o derecha.

Presupuesto

  • Joe debe comenzar en el píxel superior izquierdo de la imagen.
  • Joe solo puede moverse horizontal o verticalmente en 1 movimiento
  • Joe solo tiene tiempo suficiente para mover 1/3 de la cantidad de píxeles en la imagen (1/3 tantos movimientos como píxeles). Si el número de píxeles no es múltiplo de 3, redondea hacia abajo al entero más cercano.
  • Joe puede cruzarse en su camino, aunque eso cuenta como 0 brillo
  • El brillo se basa en la suma de r, gyb, por lo que rgb (0,0,0) tiene un brillo de 0 mientras que rgb (255,255,255) tiene el brillo máximo.

Entrada

Puede ingresar la imagen como desee.

Salida

  • una imagen que muestra el resultado final de su imagen (con píxeles negros comidos).
  • La cantidad de brillo consumido (especifique qué rango en su respuesta)

Tanteo

Su programa será calificado en:

  • El brillo promedio de los píxeles que Joe come / El brillo promedio de los píxeles en la imagen *

* puede codificar esto en su programa

Su puntaje total será el promedio de los puntajes de las siguientes imágenes:

Imágenes de prueba:

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

http://upload.wikimedia.org/wikipedia/en/thumb/f/f4/The_Scream.jpg/800px-The_Scream.jpg

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

Estiramiento maniaco
fuente
3
Diversión de rebajas hecho - Usted puede convertir las imágenes en vínculos a sus originales: [![image description](SE URL for downsized image)](URL for original image).
Hobbies de Calvin
1
Podría ser una idea pedirle a la gente que incluya un ejemplo de imagen "comida" en sus respuestas.
Nathaniel

Respuestas:

16

C ++, Puntuación: 1.42042 1.46766

Esta es esencialmente una versión ligeramente más sofisticada de las dos soluciones existentes: de los cuatro movimientos posibles, selecciona la que maximiza el brillo. Sin embargo, en lugar de solo mirar el brillo del píxel objetivo, mira la suma ponderada del brillo del píxel en la vecindad del píxel objetivo, donde los píxeles más cercanos al objetivo tienen un mayor peso.

EDITAR: el uso de brillo no lineal en el cálculo de vecindad mejora ligeramente la puntuación.

Compilar con g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Requiere cairo.

Corre con joe <image-file> [<radius>]. <image-file>es la imagen PNG de entrada. <radius>(argumento opcional) es el radio del vecindario sumado, en píxeles (más pequeño es más rápido, más grande es (más o menos) mejor). Emite la puntuación y una imagen llamada out.<image-file>.

#include <cairo/cairo.h>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

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 < height; ++y) {
        for (int x = 0; x < 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 > 2 ? stoi(argv[2]) : 64, R = 2 * r + 1;
    double* weight = new double[R * R];
    for (int y = -r; y <= r; ++y) {
        for (int x = -r; x <= r; ++x)
            weight[R * (y + r) + (x + r)] = 1.0 / (x*x + y*y + 1);
    }

    auto neighborhood = [&] (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 <= 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 <= 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 < n; ++i) {
        if (i % 1000 == 0) cerr << (200 * i + n) / (2 * n) << "%\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), [&] (const int* o) {
            return x + o[0] >= 0 && x + o[0] < width &&
                   y + o[1] >= 0 && y + o[1] < 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 > o_max_neighborhood)
                o_max = *o, o_max_neighborhood = o_neighborhood;
        }
        x += o_max[0]; y += o_max[1];
    }

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

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

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

Resultados

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

Puente Bolas Gritar Fractal Vórtice Tornado

Más ojos dulces

Animación de vórtice Animación de tornado

Ana
fuente
Acabo de probar su programa en algunas de mis propias imágenes de muestra, y una tiene mucho negro solo alrededor del punto de inicio, y allí su programa se bloquea debido a que el lambda del vecindario devuelve NaN.
PlasmaHH
@PlasmaHH ¿Te importa compartir la imagen ofensiva?
Ell
Lo estaba alimentando con imágenes de vacaciones ... 400x400 negro puro también hace el "truco".
PlasmaHH
@PlasmaHH Bueno, una imagen puramente negra tiene una puntuación indefinida, es cero sobre cero, lo que sería un NaN. Sin embargo, no debería afectar el cálculo del vecindario ni bloquear el programa (aunque esto puede depender del entorno de punto flotante).
Ell
Eche un vistazo al puntero o_max if (o_neighborhood > o_max_neighborhood) o_max = *o, o_max_neighborhood = o_neighborhood;solo este código lo establece. sin embargo, debido a nan involucrados, la comparación siempre es falsa, por lo tanto, o_max nunca se establece y se utiliza sin inicializar.
PlasmaHH
7

Python 3, puntaje = 1.57

Primero, nuestra serpiente recorre la imagen creando líneas verticales con la misma distancia entre sí.

una

Podemos extender esta serpiente tomando dos puntos uno al lado del otro en una línea vertical y creando un bucle cuyos puntos finales son ellos.

|      |
|  =>  +----+
|      +----+
|      |

Organizamos los puntos en pares y para cada par almacenamos el tamaño y el valor de brillo promedio del bucle que da el mayor brillo promedio.

En cada paso que elegimos, el par con el valor más alto extiende su bucle para lograr el brillo promedio máximo en la extensión y calculamos el nuevo tamaño de bucle óptimo y el valor de brillo óptimo para el par.

Almacenamos los tripletes (value, size, point_pair) en una estructura de montón ordenada por valor para que podamos eliminar el elemento más grande (en O (1)) y agregar el nuevo modificado (en O (log n)) de manera eficiente.

Nos detenemos cuando alcanzamos el límite de recuento de píxeles y esa serpiente será la serpiente final.

La distancia entre las líneas verticales tiene muy poco efecto en los resultados, por lo que se eligió una constante de 40 píxeles.

Resultados

swirl    1.33084397946
chaos    1.76585674741
fractal  1.49085737611
bridge   1.42603926741
balls    1.92235115238
scream   1.48603818637
----------------------
average  1.57033111819

una una una una una una

Nota: la imagen original de "The Scream" no estaba disponible, así que utilicé otra imagen de "The Scream" con una resolución similar.

Gif que muestra el proceso de extensión de la serpiente en la imagen "remolino":

una

El código toma uno o más nombres de archivo (separados por espacios) de stdin y escribe las imágenes de serpiente resultantes en archivos png e imprime las puntuaciones en stdout.

from PIL import Image
import numpy as np
import heapq as hq

def upd_sp(p,st):
    vs,c=0,0
    mv,mp=-1,0
    for i in range(st,gap):
        if p[1]+i<h:
            vs+=v[p[0],p[1]+i]+v[p[0]+1,p[1]+i]
            c+=2
            if vs/c>mv:
                mv=vs/c
                mp=i
    return (-mv,mp)

mrl=[]
bf=input().split()

for bfe in bf:
    mr,mg=0,0    
    for gap in range(40,90,1500):

        im=Image.open(bfe)
        im_d=np.asarray(im).astype(int)

        v=im_d[:,:,0]+im_d[:,:,1]+im_d[:,:,2]

        w,h=v.shape

        fp=[]
        sp=[]
        x,y=0,0
        d=1

        go=True
        while go:
            if 0<=x+2*d<w:
                fp+=[(x,y)]
                fp+=[(x+d,y)]
                sp+=[(x-(d<0),y)]
                x+=2*d
                continue
            if y+gap<h:
                for k in range(gap):
                    fp+=[(x,y+k)]
                y+=gap
                d=-d
                continue
            go=False

        sh=[]
        px=im.load()

        pl=[]

        for p in fp:
            pl+=[v[p[0],p[1]]]
            px[p[1],p[0]]=(0,127,0)   

        for p in sp:
            mv,mp=upd_sp(p,1)
            if mv<=0:
                hq.heappush(sh,(mv,1,mp+1,p))

        empty=False
        pleft=h*w//3
        pleft-=len(fp)
        while pleft>gap*2 and not empty:

            if len(sh)>0:
                es,eb,ee,p=hq.heappop(sh)
            else:
                empty=True
            pleft-=(ee-eb)*2

            mv,mp=upd_sp(p,ee)
            if mv<=0:
                hq.heappush(sh,(mv,ee,mp+1,p))    

            for o in range(eb,ee):
                pl+=[v[p[0],p[1]+o]]
                pl+=[v[p[0]+1,p[1]+o]]
                px[p[1]+o,p[0]]=(0,127,0)   
                px[p[1]+o,p[0]+1]=(0,127,0)

        pl+=[0]*pleft

        sb=sum(pl)/len(pl)
        ob=np.sum(v)/(h*w)

        im.save(bfe[:-4]+'snaked.png')

        if sb/ob>mr:
            mr=sb/ob
            mg=gap

    print(bfe,mr)
    mrl+=[mr]

print(sum(mrl)/len(mrl))
randomra
fuente
5

Python 2 (puntaje: 0.0797116)

Solo un algoritmo codicioso muy simple e ingenuo para hacer rodar la pelota.

#!/usr/bin/python

from PIL import Image

OFFSETS = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def test_img(filename):
    img = Image.open(filename)

    joe, eaten = (0, 0), []
    img_w, img_h = img.size
    all_pixels = [
        sum(img.getpixel((x, y)))
        for x in xrange(img_w)
        for y in xrange(img_h)
    ]
    total_brightness = float(sum(all_pixels)) / len(all_pixels)

    for _ in xrange(0, (img_w*img_h)/3):
        max_offset, max_brightness = (0, 0), 0
        for o in OFFSETS:
            try:
                brightness = sum(img.getpixel((joe[0] + o[0], joe[1] + o[1])))
            except IndexError:
                brightness = -1
            if brightness >= max_brightness:
                max_offset = o
                max_brightness = brightness

        joe = (joe[0] + max_offset[0], joe[1] + max_offset[1])
        eaten.append(max_brightness)
        img.putpixel(joe, (0, 0, 0))

    eaten_brightness = float(sum(eaten)) / len(eaten)
    print('%d of %d (score %f)' % (eaten_brightness, total_brightness, eaten_brightness / total_brightness))
    img.show()

test_img('img0.jpg')
test_img('img1.png')
test_img('img2.jpg')
test_img('img3.jpg')
test_img('img4.jpg')

Salida:

llama@llama:~/Code/python/ppcg40069hungrysnake$ ./hungrysnake.py 
15 of 260 (score 0.060699)
9 of 132 (score 0.074200)
16 of 300 (score 0.055557)
4 of 369 (score 0.010836)
79 of 400 (score 0.197266)
Pomo de la puerta
fuente
1
Creo que tu puntuación está apagada. Es el promedio del brillo de Joe comido sobre el brillo promedio de toda la imagen ... Un Joe al azar debería obtener una puntuación de aproximadamente 1.
Stretch Maniac
@StretchManiac Hmm, no veo nada malo. sum of brightnesses of eaten pixels / amount of eaten pixelses la fórmula correcta, correcta? Quizás sea un algoritmo realmente terrible;)
Pomo de la puerta
@Doorknob esThe average brightness of pixels Joe eats / The average brightness of the pixels in the picture*
hmatt1
Para el naranja y el negro (no azul), obtuve un brillo promedio de 68.0846 ... que no parece coincidir con ninguno de los suyos. ¿Quizás sum (getPixel (...)) no te devuelve lo que quieres? (Soy un poco un novato en python). Por cierto, hay 6 imágenes, pero solo tiene 5 salidas. ¿Podría también etiquetar las imágenes de alguna manera?
Stretch Maniac
@StretchManiac ¿Cómo estás calculando tu brillo? El mío solo suma los valores R, G y B. Lo siento, me perdí el remolino que viene penúltimo (el que mencionaste en tu comentario, creo). Agregaré eso en la mañana (tengo que dormir ahora).
Pomo de la puerta
5

Java (puntuación: 0,6949)

Un algoritmo simple que come el píxel más brillante de los cuatro píxeles que rodean el píxel actual. En el caso de un empate, el píxel comido es aleatorio, lo que lleva a puntajes diferentes e imágenes resultantes en cada ejecución. Como tal, los puntajes a continuación son los promedios de más de 50 ejecuciones en cada imagen.

Para ejecutarlo, edite los tres argumentos (existentes como constantes de clase) en la fuente, o páselos a través de la línea de comandos en el formulario java HungryImageSnake <source> <iterations> <printScores>donde <source>está el archivo fuente de la imagen para comer, <iterations>es el número de veces que se come la imagen (tomando el puntaje promedio y guardar el mejor puntaje en todas las iteraciones), y <printScores>es verdadero para imprimir el puntaje de cada iteración o falso para no hacerlo.

import javax.imageio.ImageIO;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

public class HungryImageSnake {

    private static final String SOURCE = "tornado.jpg";
    private static final int ITERATIONS = 50;
    private static final boolean PRINT_SCORES = true;

    public static void main(String[] args) {
        try {
            String source = args.length > 0 ? args[0] : SOURCE;
            int iterations = args.length > 1 ? Integer.parseInt(args[1]) : ITERATIONS;
            boolean printScores = args.length > 2 ? Boolean.parseBoolean(args[2]) : PRINT_SCORES;

            System.out.printf("Reading '%s'...%n", source);
            System.out.printf("Performing %d meals...%n", iterations);
            BufferedImage image = ImageIO.read(new File(source));
            double totalScore = 0;
            double bestScore = 0;
            BufferedImage bestImage = null;
            for (int i = 0; i < iterations; i++) {
                HungryImageSnake snake = new HungryImageSnake(image);
                while (snake.isHungry()) {
                    snake.eat();
                }
                double score = snake.getScore();
                if (printScores) {
                    System.out.printf("    %d: score of %.4f%n", i + 1, score);
                }
                totalScore += score;
                if (bestImage == null || score > bestScore) {
                    bestScore = score;
                    bestImage = snake.getImage();
                }
            }
            System.out.printf("Average score: %.4f%n", totalScore / iterations);
            String formattedScore = String.format("%.4f", bestScore);
            String output = source.replaceFirst("^(.*?)(\\.[^.]+)?$", "$1-b" + formattedScore + "$2");
            ImageIO.write(bestImage, source.substring(source.lastIndexOf('.') + 1), new File(output));
            System.out.printf("Wrote best image (score: %s) to '%s'.%n", bestScore, output);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private int x;
    private int y;
    private int movesLeft;
    private int maximumMoves;
    private double eatenAverageBrightness;
    private double originalAverageBrightness;
    private BufferedImage image;

    public HungryImageSnake(BufferedImage image) {
        this.image = copyImage(image);
        int size = image.getWidth() * image.getHeight();
        this.maximumMoves = size / 3;
        this.movesLeft = this.maximumMoves;
        int totalBrightness = 0;
        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                totalBrightness += getBrightnessAt(x, y);
            }
        }
        this.originalAverageBrightness = totalBrightness / (double) size;
    }

    public BufferedImage getImage() {
        return image;
    }

    public double getEatenAverageBrightness() {
        return eatenAverageBrightness;
    }

    public double getOriginalAverageBrightness() {
        return originalAverageBrightness;
    }

    public double getScore() {
        return eatenAverageBrightness / originalAverageBrightness;
    }

    public boolean isHungry() {
        return movesLeft > 0;
    }

    public void eat() {
        if (!isHungry()) {
            return;
        }
        int[][] options = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        shuffleArray(options); // prevent snake from getting stuck in corners
        int[] bestOption = null;
        int bestBrightness = 0;
        for (int[] option : options) {
            int optionX = this.x + option[0];
            int optionY = this.y + option[1];
            if (exists(optionX, optionY)) {
                int brightness = getBrightnessAt(optionX, optionY);
                if (bestOption == null || brightness > bestBrightness) {
                    bestOption = new int[]{ optionX, optionY };
                    bestBrightness = brightness;
                }
            }
        }

        image.setRGB(bestOption[0], bestOption[1], 0);
        this.movesLeft--;
        this.x = bestOption[0];
        this.y = bestOption[1];
        this.eatenAverageBrightness += bestBrightness / (double) maximumMoves;
    }

    private boolean exists(int x, int y) {
        return x >= 0 && x < image.getWidth() && y >= 0 && y < image.getHeight();
    }

    private int getBrightnessAt(int x, int y) {
        int rgb = image.getRGB(x, y);
        int r = (rgb >> 16) & 0xFF;
        int g = (rgb >> 8) & 0xFF;
        int b = rgb & 0xFF;
        return r + g + b;
    }

    private static <T> void shuffleArray(T[] array) {
        Random random = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            T temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    private static BufferedImage copyImage(BufferedImage source){
        BufferedImage b = new BufferedImage(source.getWidth(), source.getHeight(), source.getType());
        Graphics g = b.getGraphics();
        g.drawImage(source, 0, 0, null);
        g.dispose();
        return b;
    }
}

Puntajes promedio, por imagen, más de cincuenta iteraciones:

Bridge - 0.7739
Spheres - 0.5580
Scream - 0.8197
Fractal - 0.3850
Vortex - 0.9158
Tornado - 0.7172

Los mejores puntajes, por imagen, en las mismas cincuenta iteraciones:

Bridge - 0.8996
Spheres - 0.8741
Scream - 0.9183
Fractal - 0.5720
Vortex - 1.1520
Tornado - 0.9281

Las imágenes de las carreras con la puntuación más alta:

Puente - 0.8996 Esferas - 0.8741 Grito - 0.9183 Fractal - 0.5720 Vórtice - 1.1520 Tornado - 0.9281

Como es evidente a partir de las imágenes, mucho menos de un tercio de los píxeles se comen realmente, ya que la serpiente ocasionalmente se queda atrapada entre los píxeles que ya ha comido, en los que permanece atrapada dentro del área muerta hasta que la aleatoriedad de sus movimientos la lleva a Una porción comestible de la imagen.

Además, como resultado de los píxeles que vuelven a comer las serpientes, las puntuaciones están sesgadas hacia abajo, ya que el brillo cero de los píxeles muertos se vuelve a tener en cuenta en el promedio. Esperaría ver puntuaciones mucho más altas si el algoritmo de puntuación se modificara para dividir solo por el número de movimientos que llevaron a comer nuevos píxeles, en lugar de todos los movimientos (incluidos aquellos en los que la serpiente come un píxel ahora muerto que ha comido antes )

Por supuesto, un mejor enfoque sería crear algún tipo de brillo heurístico para cada píxel y encontrar la ruta de los width * height / 3píxeles con el brillo promedio más alto, pero dudo que este enfoque sea óptimo en tiempo de ejecución, especialmente en imágenes más grandes, ya que el número de posibles permutaciones sería muy grande. Puedo tomar una oportunidad en alguna forma de este enfoque más tarde y publicarlo en una respuesta separada si es así.

FThompson
fuente
Si a alguien le molesta cuán grande es mi respuesta (debido a las imágenes que contiene), avíseme y eliminaré las imágenes a favor de los enlaces u otra alternativa menos espaciosa. O, si alguien quisiera los originales en resolución completa de cualquier imagen "comida", hágamelo saber también en un comentario.
FThompson
4

Python 2, Puntuación: 1.205

Creé una solución rápida de Python hace algún tiempo, pero olvidé publicarla. Aquí está. Encuentra los bloques más ricos en la imagen, luego viaja a cada bloque, comiendo todos los mejores bloques a los que llega.

Resultados

bridge.jpg: 591.97866/515.41501 =                               1.14855 
BallsRender.png: 493.24711/387.80635 =                          1.27189 
Mandel_zoom_04_seehorse_tail.jpg: 792.23990/624.60579 =         1.26838 
Red_Vortex_Apophysis_Fractal_Flame.jpg: 368.26121/323.08463 =   1.13983 
The_Scream.jpg: 687.18565/555.05221 =                           1.23806
swirl.jpg: 762.89469/655.73767 =                                1.16341

AVERAGE                                                         1.205

Imagen de ejemplo

Imagen procesada del puente

Python 2.7 Code

from pygame.locals import *
import pygame, sys, random

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
pic = pygame.image.load(fn)
pic.convert()
W,H = pic.get_size()
enough = W*H/3
screen.blit(pic, (0,0))

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

def look(p):
    x,y = p
    if 0 <= x < W and 0 <= y < H:
        return sum(pic.get_at(p))
    else:
        return -1

# index picture
locs = [(x,y) for x in range(W) for y in range(H)]
grid = dict( (p,sum(pic.get_at(p))) for p in locs )
rank = sorted( grid.values() )
median = rank[ len(rank)/2 ]
dark = dict( (k,v) for k,v in grid if v < median )
good = dict( (k,v) for k,v in grid if v > median )
pictotal = sum(rank)
picavg = 1.0 * pictotal/(W*H)
print('Indexed')

# compute zone values:
block = 16
xblocks, yblocks = (W-1)/block, (H-1)/block
zones = dict( ((zx,zy),0) for zx in range(xblocks) for zy in range(yblocks) )
for x,y in locs:
    div = (x/block, y/block)
    if div in zones:
        colsum = sum( pic.get_at((x,y)) )
        zones[div] += colsum

# choose best zones:
zonelist = sorted( (v,k) for k,v in zones.items() )
cut = int(xblocks * yblocks * 0.33)
bestzones = dict( (k,v) for v,k in zonelist[-cut:] )

# make segment paths:
segdrop = [(0,1)] * (block-1)
segpass = [(1,0)] * block
segloop = [(0,-1)] * (block-1) + [(1,0)] + [(0,1)] * (block-1)
segeat = ( segloop+[(1,0)] ) * (block/2)
segshort = [(1,0)] * 2 + ( segloop+[(1,0)] ) * (block/2 - 1)

def segtopath(path, seg, xdir):
    for dx,dy in seg:
        x,y = path[-1]
        newloc = (x+dx*xdir, y+dy)
        path.append(newloc)

# design good path:
xdir = 1
path = [(0,0)]
segtopath(path, segdrop, xdir)
shortzone = True
while True:
    x,y = path[-1]
    zone = (x/block, y/block)
    if zone in bestzones:
        if shortzone:
            seg = segshort
        else:
            seg = segeat
    else:
        seg = segpass
    segtopath(path, seg, xdir)
    shortzone = False
    # check end of x block run:
    x,y = path[-1]
    zone = (x/block, y/block)
    if not ( 0 <= x < xblocks*block ):
        del path[-1]
        segtopath(path, segdrop, xdir)
        shortzone = True
        xdir = xdir * -1
    if len(path) > enough:
        break
print('Path Found')

# show path on picture:
loc = path.pop(0)
eaten = 1
joetotal = grid[loc]
i = 0
while eaten <= enough:
    loc = path[i]
    i += 1
    pic.set_at(loc, (0,0,0))
    joetotal += grid[loc]
    eaten += 1
    if i % 1000 == 0:
        screen.blit(pic, (0,0))
        pygame.display.flip()
        for event in pygame.event.get():
            if event.type == QUIT: sys.exit(0)

# save picture and wait:
screen.blit(pic, (0,0))
pygame.display.flip()
pygame.image.save(pic, 'output/'+fn)
joeavg = 1.0 * joetotal/eaten
print '%s: %7.5f/%7.5f = %7.5f' % (fn, joeavg, picavg, joeavg/picavg)
while True:
    for event in pygame.event.get():
        if event.type == QUIT: sys.exit(0)
Caballero Lógico
fuente