FELICITACIONES a @kuroineko por la mejor entrada y ganar la recompensa de 200 de @TheBestOne (¡excelente deportividad!).

Escriba un programa para colorear la mayor cantidad de imagen posible antes de que lo hagan los programas de oposición.

Reglas breves

• Su programa recibirá una imagen, su color y un número entero N.
• Cada turno, otros programas le envían actualizaciones de píxeles y le solicitan sus N actualizaciones.
• Puede actualizar cualquier píxel blanco que esté al lado de un píxel de su color.
• El programa que ha agregado más píxeles gana.

Reglas en detalle

Su programa recibirá un nombre de archivo de imagen PNG, color de inicio y un número N. El número N es el número máximo de píxeles que su programa puede colorear cada turno.

Ejemplo: MyProg arena.png (255,0,0) 30

La imagen de entrada será un rectángulo con lados entre 20 y 1000 píxeles de largo. Consistirá en píxeles negros, blancos y de color. Su programa puede elegir una secuencia de píxeles blancos para colorear como suya, con la condición de que cada nuevo píxel debe tener al menos uno de sus cuatro píxeles vecinos de su propio color. La imagen tendrá inicialmente al menos un píxel de su color. También puede tener píxeles de colores a los que no se asigna ningún programa. El canal alfa no se utiliza.

Tu objetivo es bloquear a tus oponentes y escribir tu color en tantos píxeles como puedas.

Cada turno, su programa aceptará 1 o más líneas de mensaje en STDIN y escribirá una línea que consiste en coordenadas de píxeles en STDOUT. Recuerde asignar STDOUT como sin búfer o vaciar el búfer STDOUT cada turno.

El orden de los jugadores llamados a cada turno se asignará al azar. Esto significa que un oponente (o su programa) puede tener 2 turnos seguidos.

Su programa recibirá colour (N,N,N) chose X,Y X,Y ... X,Ymensajes de información que describen los píxeles completados por los programas del jugador. Si un jugador no hace movimientos o no tiene movimientos válidos, no se le enviará un mensaje sobre los movimientos de ese jugador. Su programa también recibirá un mensaje sobre sus propios movimientos aceptados (si ha especificado al menos un movimiento válido). El píxel 0,0 está en la esquina superior izquierda de la imagen.

Al recibir pick pixels, su programa generará X,Y X,Y ... X,Yhasta N píxeles (se permite una cadena vacía que consta de solo '\ n'). Los píxeles deben estar en orden de trazado. Si un píxel no es válido, se ignorará y no aparecerá en el informe para los jugadores. Su programa tiene 2 segundos para inicializar después de comenzar, pero solo 0.1 segundos para responder con una respuesta cada turno o perderá ese turno. Una actualización de píxeles enviada después de 0.1 segundos registrará una falla. Después de 5 fallas, su programa se suspende y no se enviarán actualizaciones o pick pixelssolicitudes.

Cuando el programa de jueces recibe una opción de píxeles vacía o inválida de cada programa de jugador no suspendido, la imagen se considerará completa y los programas recibirán el mensaje "salir". Los programas deben finalizar después de recibir "salir".

Tanteo

El juez obtendrá puntos después de que se complete la imagen. Su puntaje será su número de píxeles actualizados dividido por la captura de píxeles promedio en esa ronda, expresada como un porcentaje.

El número de píxeles agregados a la imagen por su reproductor es A. El número total de píxeles agregados por todos los jugadores P es T. avg = T/P score = 100*A/avg

Puntuaciones contables

Se da un oponente de referencia "The Blob". Para cada respuesta, titula tu bot con un nombre, idioma y tu puntaje (promedio de arena 1 a 4) contra el oponente de referencia. Una imagen o animación de una de tus batallas también sería buena. El ganador es el programa con la puntuación más alta contra el bot de referencia.

Si The Blob resulta demasiado fácil de vencer, puedo agregar una segunda ronda con un oponente de referencia más fuerte.

También te gustaría experimentar con 4 o más programas de jugador. También puedes probar tu bot contra otros bots publicados como respuestas.

El juez

El programa de juez requiere la Biblioteca de imágenes de Python (PIL) común y debe ser fácil de instalar desde el administrador de paquetes de su sistema operativo en Linux. Tengo un informe de que PIL no funciona con Python de 64 bits en Windows 7, así que compruebe si PIL funcionará para usted antes de comenzar este desafío (actualizado 2015-01-29).

#!/usr/bin/env python
# Judge Program for Image Battle challenge on PPCG.
# Runs on Python 2.7 on Ubuntu Linux. May need edits for other platforms.
# V1.0 First release.
# V1.1 Added Java support
# V1.2 Added Java inner class support
# usage: judge cfg.py
import sys, re, random, os, shutil, subprocess, datetime, time, signal
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)  # Java fix
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        if name.endswith('.class'): # Java inner class fix
            rootname = re.sub(r'\.class$', '', name)
            for fn in os.listdir('.'):
                if fn.startswith(rootname) and fn.endswith('.class'):
                    shutil.copy(fn, self.env)
        else:
            shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, `PIXELBATCH`]
        self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
            stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write(msg + '\n')
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline()
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0: print 'Turn %s done %s pixels' % (turn, total)
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print 'Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score)
image.save(BATTLE+'.png')

Configuración de ejemplo: cfg.py

BATTLE = 'Green Blob vs Red Blob'
MAXTURNS = 20000
PIXELBATCH = 10
INITTIME = 2.0
TIMELIMIT = 0.1
FAULTLIMIT = 5

imagename = 'arena1.png'

colourspec = (0,255,0), (255,0,0)

botspec = [
    ('blob.py', 'python'),
    ('blob.py', 'python'),
    ]

The Blob - el oponente de referencia

# Blob v1.0 - A reference opponent for the Image Battle challenge on PPCG.
import sys, os
from PIL import Image

image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, colour):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            return True
    return False

def near(loc):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255)]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        skin.discard(p)
        if colour == mycolour:
            for np in near(p):
                skin.add(np)

board = [(x,y) for x in range(W) for y in range(H)]
skin = set(p for p in board if canchoose(p, mycolour))

while 1:
    msg = sys.stdin.readline()
    if msg.startswith('colour'):
        updateimage(image, msg.strip())
    if msg.startswith('pick'):
        plen = min(pixbatch, len(skin))
        moves = [skin.pop() for i in range(plen)]
        movetext = ' '.join('%u,%u'%p for p in moves)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit'):
        break

image.save('blob.png')

Arena 1

Arena 2

Arena 3

Arena 4

Un ejemplo de batalla - Blob vs Blob

Esta batalla tuvo un resultado predecible:

Bot blob.py with colour (255, 0, 0) scored 89.2883333333
Bot blob.py with colour (0, 255, 0) scored 89.365

ColorFighter - C ++ - come un par de golondrinas para el desayuno

EDITAR

• limpiado el código
• agregó una optimización simple pero efectiva
• agregó algunas animaciones GIF

Dios, odio las serpientes (solo finge que son arañas, Indy)

En realidad me encanta Python. Desearía ser menos flojo y comenzar a aprenderlo correctamente, eso es todo.

Dicho todo esto, tuve que luchar con la versión de 64 bits de esta serpiente para que el juez funcionara. Hacer que PIL funcione con la versión de 64 bits de Python en Win7 requiere más paciencia de la que estaba listo para dedicar a este desafío, así que al final cambié (dolorosamente) a la versión Win32.

Además, el juez tiende a fallar gravemente cuando un bot es demasiado lento para responder.
Al no ser un experto en Python, no lo solucioné, pero tiene que ver con leer una respuesta vacía después de un tiempo de espera en stdin.

Una mejora menor sería colocar la salida stderr en un archivo para cada bot. Eso facilitaría el rastreo para la depuración post mortem.

Excepto por estos problemas menores, el juez me pareció muy simple y agradable de usar.
Felicitaciones por otro desafío inventivo y divertido.

El código

#define _CRT_SECURE_NO_WARNINGS // prevents Microsoft from croaking about the safety of scanf. Since every rabid Russian hacker and his dog are welcome to try and overflow my buffers, I could not care less.
#include "lodepng.h"
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>
#include <cassert>   // paranoid android
#include <cstdint>   // fixed size types
#include <algorithm> // min max

using namespace std;

// ============================================================================
// The less painful way I found to teach C++ how to handle png images
// ============================================================================
typedef unsigned tRGB;
#define RGB(r,g,b) (((r) << 16) | ((g) << 8) | (b))
class tRawImage {
public:
    unsigned w, h;

    tRawImage(unsigned w=0, unsigned h=0) : w(w), h(h), data(w*h * 4, 0) {}
    void read(const char* filename) { unsigned res = lodepng::decode(data, w, h, filename); assert(!res);  }
    void write(const char * filename)
    {
        std::vector<unsigned char> png;
        unsigned res = lodepng::encode(png, data, w, h, LCT_RGBA); assert(!res);
        lodepng::save_file(png, filename);
    }
    tRGB get_pixel(int x, int y) const
    {
        size_t base = raw_index(x,y);
        return RGB(data[base], data[base + 1], data[base + 2]);
    }
    void set_pixel(int x, int y, tRGB color)
    {
        size_t base = raw_index(x, y);
        data[base+0] = (color >> 16) & 0xFF;
        data[base+1] = (color >>  8) & 0xFF;
        data[base+2] = (color >> 0) & 0xFF;
        data[base+3] = 0xFF; // alpha
    }
private:
    vector<unsigned char> data;
    void bound_check(unsigned x, unsigned y) const { assert(x < w && y < h); }
    size_t raw_index(unsigned x, unsigned y) const { bound_check(x, y); return 4 * (y * w + x); }
};

// ============================================================================
// coordinates
// ============================================================================
typedef int16_t tCoord;

struct tPoint {
    tCoord x, y;
    tPoint operator+  (const tPoint & p) const { return { x + p.x, y + p.y }; }
};

typedef deque<tPoint> tPointList;

// ============================================================================
// command line and input parsing
// (in a nice airtight bag to contain the stench of C++ string handling)
// ============================================================================
enum tCommand {
    c_quit,
    c_update,
    c_play,
};

class tParser {
public:
    tRGB color;
    tPointList points;

    tRGB read_color(const char * s)
    {
        int r, g, b;
        sscanf(s, "(%d,%d,%d)", &r, &g, &b);
        return RGB(r, g, b);
    }

    tCommand command(void)
    {
        string line;
        getline(cin, line);

        string cmd = get_token(line);
        points.clear();

        if (cmd == "exit") return c_quit;
        if (cmd == "pick") return c_play;

        // even more convoluted and ugly than the LEFT$s and RIGHT$s of Apple ][ basic...
        if (cmd != "colour")
        {
            cerr << "unknown command '" << cmd << "'\n";
            exit(0);
        }
        assert(cmd == "colour");
        color = read_color(get_token(line).c_str());
        get_token(line); // skip "chose"
        while (line != "")
        {
            string coords = get_token(line);
            int x = atoi(get_token(coords, ',').c_str());
            int y = atoi(coords.c_str());
            points.push_back({ x, y });
        }
        return c_update;
    }

private:
    // even more verbose and inefficient than setting up an ADA rendezvous...
    string get_token(string& s, char delimiter = ' ')
    {
        size_t pos = 0;
        string token;
        if ((pos = s.find(delimiter)) != string::npos)
        {
            token = s.substr(0, pos);
            s.erase(0, pos + 1);
            return token;
        }
        token = s; s.clear(); return token;
    }
};

// ============================================================================
// pathing
// ============================================================================
class tPather {

public:
    tPather(tRawImage image, tRGB own_color)
        : arena(image)
        , w(image.w)
        , h(image.h)
        , own_color(own_color)
        , enemy_threat(false)
    {
        // extract colored pixels and own color areas
        tPointList own_pixels;
        color_plane[neutral].resize(w*h, false);
        color_plane[enemies].resize(w*h, false);
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            tRGB color = image.get_pixel(x, y);
            if (color == col_white) continue;
            plane_set(neutral, x, y);
            if (color == own_color) own_pixels.push_back({ x, y }); // fill the frontier with all points of our color
        }

        // compute initial frontier
        for (tPoint pixel : own_pixels)
        for (tPoint n : neighbour)
        {
            tPoint pos = pixel + n;
            if (!in_picture(pos)) continue;
            if (image.get_pixel(pos.x, pos.y) == col_white)
            {
                frontier.push_back(pixel);
                break;
            }
        }
    }

    tPointList search(size_t pixels_required)
    {
        // flood fill the arena, starting from our current frontier
        tPointList result;
        tPlane closed;
        static tCandidate pool[max_size*max_size]; // fastest possible garbage collection
        size_t alloc;
        static tCandidate* border[max_size*max_size]; // a FIFO that beats a deque anytime
        size_t head, tail;
        static vector<tDistance>distance(w*h); // distance map to be flooded
        size_t filling_pixels = 0; // end of game  optimization

    get_more_results:

        // ready the distance map for filling
        distance.assign(w*h, distance_max);

        // seed our flood fill with the frontier
        alloc = head = tail = 0;
        for (tPoint pos : frontier)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate (pos);
        }

        // set already explored points
        closed = color_plane[neutral]; // that's one huge copy

        // add current result
        for (tPoint pos : result)
        {
            border[tail++] = new (&pool[alloc++]) tCandidate(pos);
            closed[raw_index(pos)] = true;
        }

        // let's floooooood!!!!
        while (tail > head && pixels_required > filling_pixels)
        {
            tCandidate& candidate = *border[head++];
            tDistance  dist = candidate.distance;
            distance[raw_index(candidate.pos)] = dist++;
            for (tPoint n : neighbour)
            {
                tPoint pos = candidate.pos + n;
                if (!in_picture (pos)) continue;
                size_t index = raw_index(pos);
                if (closed[index]) continue;
                if (color_plane[enemies][index])
                {
                    if (dist == (distance_initial + 1)) continue; // already near an enemy pixel

                    // reached the nearest enemy pixel
                    static tPoint trail[max_size * max_size / 2]; // dimensioned as a 1 pixel wide spiral across the whole map
                    size_t trail_size = 0;

                    // walk back toward the frontier
                    tPoint walker = candidate.pos;
                    tDistance cur_d = dist;
                    while (cur_d > distance_initial)
                    {
                        trail[trail_size++] = walker;
                        tPoint next_n;
                        for (tPoint n : neighbour)
                        {
                            tPoint next = walker + n;
                            if (!in_picture(next)) continue;
                            tDistance prev_d = distance[raw_index(next)];
                            if (prev_d < cur_d)
                            {
                                cur_d = prev_d;
                                next_n = n;
                            }
                        }
                        walker = walker + next_n;
                    }

                    // collect our precious new pixels
                    if (trail_size > 0)
                    {
                        while (trail_size > 0)
                        {
                            if (pixels_required-- == 0) return result;       // ;!; <-- BRUTAL EXIT
                            tPoint pos = trail[--trail_size];
                            result.push_back (pos);
                        }
                        goto get_more_results; // I could have done a loop, but I did not bother to. Booooh!!!
                    }
                    continue;
                }

                // on to the next neighbour
                closed[index] = true;
                border[tail++] = new (&pool[alloc++]) tCandidate(pos, dist);
                if (!enemy_threat) filling_pixels++;
            }
        }

        // if all enemies have been surrounded, top up result with the first points of our flood fill
        if (enemy_threat) enemy_threat = pixels_required == 0;
        tPathIndex i = frontier.size() + result.size();
        while (pixels_required--) result.push_back(pool[i++].pos);
        return result;
    }

    // tidy up our map and frontier while other bots are thinking
    void validate(tPointList moves)
    {
        // report new points
        for (tPoint pos : moves)
        {
            frontier.push_back(pos);
            color_plane[neutral][raw_index(pos)] = true;
        }

        // remove surrounded points from frontier
        for (auto it = frontier.begin(); it != frontier.end();) 
        {
            bool in_frontier = false;
            for (tPoint n : neighbour)
            {
                tPoint pos = *it + n;
                if (!in_picture(pos)) continue;
                if (!(color_plane[neutral][raw_index(pos)] || color_plane[enemies][raw_index(pos)]))
                {
                    in_frontier = true;
                    break;
                }
            }
            if (!in_frontier) it = frontier.erase(it); else ++it; // the magic way of deleting an element without wrecking your iterator
        }       
    }

    // handle enemy move notifications
    void update(tRGB color, tPointList points)
    {
        assert(color != own_color);

        // plot enemy moves
        enemy_threat = true;
        for (tPoint p : points) plane_set(enemies, p);

        // important optimization here :
        /*
         * Stop 1 pixel away from the enemy to avoid wasting moves in dogfights.
         * Better let the enemy gain a few more pixels inside the surrounded region
         * and use our precious moves to get closer to the next threat.
         */
        for (tPoint p : points) for (tPoint n : neighbour) plane_set(enemies, p+n);

        // if a new enemy is detected, gather its initial pixels
        for (tRGB enemy : known_enemies) if (color == enemy) return;
        known_enemies.push_back(color);
        tPointList start_areas = scan_color(color);
        for (tPoint p : start_areas) plane_set(enemies, p);
    }

private:
    typedef uint16_t tPathIndex;

    typedef uint16_t tDistance;
    static const tDistance distance_max     = 0xFFFF;
    static const tDistance distance_initial = 0;

    struct tCandidate {
        tPoint pos;
        tDistance distance;
        tCandidate(){} // must avoid doing anything in this constructor, or pathing will slow to a crawl
        tCandidate(tPoint pos, tDistance distance = distance_initial) : pos(pos), distance(distance) {}
    };

    // neighbourhood of a pixel
    static const tPoint neighbour[4];

    // dimensions
    tCoord w, h; 
    static const size_t max_size = 1000;

    // colors lookup
    const tRGB col_white = RGB(0xFF, 0xFF, 0xFF);
    const tRGB col_black = RGB(0x00, 0x00, 0x00);
    tRGB own_color;
    const tRawImage arena;
    tPointList scan_color(tRGB color)
    {
        tPointList res;
        for (size_t x = 0; x != w; x++)
        for (size_t y = 0; y != h; y++)
        {
            if (arena.get_pixel(x, y) == color) res.push_back({ x, y });
        }
        return res;
    }

    // color planes
    typedef vector<bool> tPlane;
    tPlane color_plane[2];
    const size_t neutral = 0;
    const size_t enemies = 1;
    bool plane_get(size_t player, tPoint p) { return plane_get(player, p.x, p.y); }
    bool plane_get(size_t player, size_t x, size_t y) { return in_picture(x, y) ? color_plane[player][raw_index(x, y)] : false; }
    void plane_set(size_t player, tPoint p) { plane_set(player, p.x, p.y); }
    void plane_set(size_t player, size_t x, size_t y) { if (in_picture(x, y)) color_plane[player][raw_index(x, y)] = true; }
    bool in_picture(tPoint p) { return in_picture(p.x, p.y); }
    bool in_picture(int x, int y) { return x >= 0 && x < w && y >= 0 && y < h; }
    size_t raw_index(tPoint p) { return raw_index(p.x, p.y); }
    size_t raw_index(size_t x, size_t y) { return y*w + x; }

    // frontier
    tPointList frontier;

    // register enemies when they show up
    vector<tRGB>known_enemies;

    // end of game optimization
    bool enemy_threat;
};

// small neighbourhood
const tPoint tPather::neighbour[4] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

// ============================================================================
// main class
// ============================================================================
class tGame {
public:
    tGame(tRawImage image, tRGB color, size_t num_pixels)
        : own_color(color)
        , response_len(num_pixels)
        , pather(image, color)
    {}

    void main_loop(void)
    {
        // grab an initial answer in case we're playing first
        tPointList moves = pather.search(response_len);
        for (;;)
        {
            ostringstream answer;
            size_t        num_points;
            tPointList    played;

            switch (parser.command())
            {
            case c_quit: 
                return;

            case c_play:
                // play as many pixels as possible
                if (moves.size() < response_len) moves = pather.search(response_len);
                num_points = min(moves.size(), response_len);
                for (size_t i = 0; i != num_points; i++)
                {
                    answer << moves[0].x << ',' << moves[0].y;
                    if (i != num_points - 1) answer << ' '; // STL had more important things to do these last 30 years than implement an implode/explode feature, but you can write your own custom version with exception safety and in-place construction. It's a bit of work, but thanks to C++ inherent genericity you will be able to extend it to giraffes and hippos with a very manageable amount of code refactoring. It's not anyone's language, your C++, eh. Just try to implode hippos in Python. Hah!
                    played.push_back(moves[0]);
                    moves.pop_front();
                }
                cout << answer.str() << '\n';

                // now that we managed to print a list of points to stdout, we just need to cleanup the mess
                pather.validate(played);
                break;

            case c_update:
                if (parser.color == own_color) continue; // hopefully we kept track of these already
                pather.update(parser.color, parser.points);
                moves = pather.search(response_len); // get cracking
                break;
            }
        }
    }

private:
    tParser parser;
    tRGB    own_color;
    size_t  response_len;
    tPather pather;
};

void main(int argc, char * argv[])
{
    // process command line
    tRawImage raw_image; raw_image.read (argv[1]);
    tRGB my_color = tParser().read_color(argv[2]);
    int num_pixels               = atoi (argv[3]);

    // init and run
    tGame game (raw_image, my_color, num_pixels);
    game.main_loop();
}

Construyendo el ejecutable

Solía LODEpng.cpp y LODEpng.h para leer imágenes PNG.
Sobre la forma más fácil que encontré para enseñarle a este lenguaje C ++ retrasado cómo leer una imagen sin tener que construir media docena de bibliotecas.
Simplemente compile y vincule LODEpng.cpp junto con el principal y Bob es su tío.

Compilé con MSVC2013, pero como solo utilicé unos pocos contenedores básicos STL (deque y vectores), podría funcionar con gcc (si tienes suerte).
Si no es así, podría intentar una compilación MinGW, pero, francamente, me estoy cansando de los problemas de portabilidad de C ++.

Hice bastante C / C ++ portátil en mis días (en compiladores exóticos para varios procesadores de 8 a 32 bits, así como SunOS, Windows desde 3.11 hasta Vista y Linux desde su infancia hasta Ubuntu Cooing Zebra o lo que sea, así que creo Tengo una idea bastante clara de lo que significa la portabilidad), pero en ese momento no requería memorizar (o descubrir) las innumerables discrepancias entre las interpretaciones de GNU y Microsoft de las especificaciones crípticas e hinchadas del monstruo STL.

Resultados contra Swallower

Cómo funciona

En el fondo, esta es una simple ruta de relleno de fuerza bruta.

La frontera del color del jugador (es decir, los píxeles que tienen al menos un vecino blanco) se utiliza como semilla para realizar el clásico algoritmo de inundación a distancia.

Cuando un punto alcanza la vinculación de un color enemigo, se calcula un camino hacia atrás para producir una cadena de píxeles que se mueven hacia el punto enemigo más cercano.

El proceso se repite hasta que se hayan reunido suficientes puntos para una respuesta de la longitud deseada.

Esta repetición es obscenamente costosa, especialmente cuando se lucha cerca del enemigo.
Cada vez que se encuentra una cadena de píxeles que va de la frontera a un píxel enemigo (y necesitamos más puntos para completar la respuesta), el relleno de inundación se vuelve a hacer desde el principio, con el nuevo camino agregado a la frontera. Significa que podría tener que hacer 5 rellenos de inundación o más para obtener una respuesta de 10 píxeles.

Si no se puede acceder a más píxeles enemigos, se seleccionan vecinos arbitrarios de los píxeles fronterizos.
El algoritmo se convierte en un relleno de inundación bastante ineficiente, pero esto solo sucede después de que se ha decidido el resultado del juego (es decir, no hay más territorio neutral por el que luchar).
Lo optimicé para que el Juez no pase años llenando el mapa una vez que se haya tratado la competencia. En su estado actual, el tiempo de ejecución es despreciable en comparación con el propio juez.

Dado que los colores enemigos no se conocen al principio, la imagen inicial de la arena se mantiene almacenada para copiar las áreas iniciales del enemigo cuando realiza su primer movimiento.
Si el código se reproduce primero, simplemente inundará unos pocos píxeles arbitrarios.

Esto hace que el algoritmo sea capaz de luchar contra un número arbitrario de adversarios, e incluso posiblemente nuevos adversarios que lleguen a un punto aleatorio en el tiempo, o que aparezcan colores sin un área de inicio (aunque esto no tiene ningún uso práctico).

El manejo del enemigo en una base de color por color también permitiría que dos instancias del bot cooperen (usando coordenadas de píxeles para pasar un signo de reconocimiento secreto).
Suena divertido, probablemente lo intentaré :).

La ruta de cálculo pesado se realiza tan pronto como hay nuevos datos disponibles (después de una notificación de movimiento), y algunas optimizaciones (la actualización de la frontera) se realizan justo después de que se haya dado una respuesta (para hacer la mayor cantidad de cómputo posible durante los turnos de otros bots) )

Una vez más, podría haber formas de hacer cosas más sutiles si hubiera más de 1 adversario (como abortar un cálculo si hay nuevos datos disponibles), pero de todos modos no veo dónde se necesita la multitarea, siempre que el algoritmo sea capaz de trabajar a plena carga.

Problemas de desempeño

Todo esto no puede funcionar sin un acceso rápido a los datos (y más potencia de cómputo que todo el programa Appolo, es decir, su PC promedio cuando solía hacer más que publicar algunos tweets).

La velocidad depende en gran medida del compilador. Por lo general, GNU supera a Microsoft por un margen del 30% (ese es el número mágico que noté en otros 3 desafíos de código relacionados con la ruta), pero este kilometraje puede variar, por supuesto.

El código en su estado actual apenas comienza a sudar en la arena 4. El perfímetro de Windows informa entre un 4 y un 7% de uso de CPU, por lo que debería ser capaz de hacer frente a un mapa de 1000x1000 dentro del límite de tiempo de respuesta de 100 ms.

En el corazón de casi todos los algoritmos de ruta se encuentra un FIFO (posiblemente proritizado, aunque no en ese caso), que a su vez requiere una rápida asignación de elementos.

Dado que el OP obligó obligatoriamente un límite al tamaño de la arena, hice algunos cálculos y vi que las estructuras de datos fijas dimensionadas al máximo (es decir, 1,000,000 de píxeles) no consumirían más de un par de docenas de megabytes, que su PC promedio come para el desayuno.
De hecho, bajo Win7 y compilado con MSVC 2013, el código consume alrededor de 14Mb en arena 4, mientras que los dos hilos de Swallower están usando más de 20Mb.

Comencé con contenedores STL para crear prototipos más fácilmente, pero STL hizo que el código fuera aún menos legible, ya que no deseaba crear una clase para encapsular todos y cada uno de los datos para ocultar la ofuscación (ya sea debido a mis propias incapacidades para hacer frente a la STL se deja a la apreciación del lector).
De todos modos, el resultado fue tan atrozmente lento que al principio pensé que estaba creando una versión de depuración por error.

Creo que esto se debe en parte a la increíblemente pobre implementación de Microsoft del STL (donde, por ejemplo, los vectores y los conjuntos de bits realizan comprobaciones encuadernadas u otras operaciones crípticas en el operador [], en violación directa de la especificación), y en parte al diseño del STL sí mismo.

Podría hacer frente a los atroces problemas de sintaxis y portabilidad (es decir, Microsoft vs GNU) si las actuaciones estuvieran allí, pero ciertamente este no es el caso.

Por ejemplo, dequees inherentemente lento, ya que baraja muchos datos de contabilidad esperando que la ocasión haga su cambio de tamaño súper inteligente, por lo que no podría importarme menos.
Claro que podría haber implementado un asignador personalizado y cualquier otro bit de plantilla personalizada, pero un asignador personalizado solo cuesta unos cientos de líneas de código y la mejor parte del día para probar, con la docena de interfaces que tiene que implementar, mientras que un La estructura equivalente hecha a mano tiene aproximadamente cero líneas de código (aunque es más peligroso, pero el algoritmo no habría funcionado si no supiera, o creo que sabía, lo que estaba haciendo de todos modos).

Así que eventualmente mantuve los contenedores STL en partes no críticas del código, y construí mi propio asignador brutal y FIFO con dos arreglos de alrededor de 1970 y tres cortos sin firmar.

Tragar la golondrina

Como confirmó su autor, los patrones erráticos de Swallower son causados ​​por el retraso entre las notificaciones de movimientos enemigos y las actualizaciones del hilo de ruta.
El perfímetro del sistema muestra claramente el hilo de ruta que consume 100% de CPU todo el tiempo, y los patrones irregulares tienden a aparecer cuando el foco de la lucha se desplaza a una nueva área. Esto también es bastante evidente con las animaciones.

Una optimización simple pero efectiva

Después de mirar las épicas peleas de perros entre Swallower y mi luchador, recordé un viejo dicho del juego de Go: defender de cerca, pero atacar desde lejos.

Hay sabiduría en eso. Si intentas apegarte demasiado a tu adversario, desperdiciarás movimientos preciosos tratando de bloquear cada posible camino. Por el contrario, si te mantienes a solo un píxel de distancia, es probable que evites llenar pequeños huecos que ganarían muy poco y usar tus movimientos para contrarrestar las amenazas más importantes.

Para implementar esta idea, simplemente extendí los movimientos de un enemigo (marcando los 4 vecinos de cada movimiento como un píxel enemigo).
Esto detiene el algoritmo de ruta a un píxel de la frontera del enemigo, lo que permite a mi luchador sortear a un adversario sin quedar atrapado en demasiadas peleas de perros.

Puede ver la mejora
(aunque todas las ejecuciones no son tan exitosas, puede notar los contornos mucho más suaves):

Profundidad: primer blob contra blob

Lenguaje = Python (3.2)

Puntuación = 111.475388276 153.34210035

Actualización: ahora usando una Setclase personalizada para obtener el pop()método para producir una especie de patrón de cuadrícula que mejora drásticamente el área cubierta al principio cortando grandes partes de la imagen del enemigo. Nota: Estoy usando una cuadrícula de 12 x 12 para esto, que en una muestra aleatoria de tamaños de cuadrícula pareció dar los mejores resultados para arena3 (el que obtuvo la peor puntuación antes de la actualización), sin embargo, es muy probable que una mejor El tamaño de la cuadrícula existe para la selección dada de arenas.

Hice una modificación simple al bot de referencia para que sea más fácil elegir puntos factibles que estén bordeados por la menor cantidad posible de puntos de color propio. Una mejora podría ser hacer que también favorezca la elección de puntos factibles que estén rodeados por tantos puntos de color enemigo como sea posible.

dfblob.py:

import sys, os
from PIL import Image

class RoomyIntPairHashSet:
    def __init__(self, firstMax, secondMax):
        self.m1 = firstMax
        self.m2 = secondMax
        self.set = [set() for i in range((firstMax - 1) * (secondMax - 1) + 1)]
        self.len = 0

    def add(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.add(tup)
        self.len += len(subset)

    def discard(self, tup):
        subset = self.set[self.gettuphash(tup)]
        self.len -= len(subset)
        subset.discard(tup)
        self.len += len(subset)

    def pop(self):
        for s in self.set:
            if len(s) > 0:
                self.len -= 1
                return s.pop()
        return self.set[0].pop()

    def gettuphash(self, tup):
        return (tup[0] % self.m1) * (tup[1] % self.m2)

    def __len__(self):
        return self.len

gridhashwidth = 12
gridhashheight = 12
image = Image.open(sys.argv[1])
pix = image.load()
W,H = image.size
mycolour = eval(sys.argv[2])
pixbatch = int(sys.argv[3])

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def canchoose(loc, virtualneighbors, colour, num_neighbors):
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        actual_num_neighbors = 0
        for p in plist:
            if 0<=p[0]<W and 0<=p[1]<H and pix[p]==colour or p in virtualneighbors:
                actual_num_neighbors += 1
        return num_neighbors == actual_num_neighbors
    return False

def near(loc, exclude):
    plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
    pboard = [p for p in plist if 0<=p[0]<W and 0<=p[1]<H]
    return [p for p in pboard if pix[p] == (255,255,255) and p not in exclude]

def updateimage(image, msg):
    ctext, colourtext, chose, points = msg.split(None, 3)
    colour = eval(colourtext)
    plist = [tuple(int(v) for v in pr.split(',')) for pr in points.split()]
    for p in plist:
        pix[p] = colour
        for i in range(len(skins)):
            skins[i].discard(p)
        if colour == mycolour:
            for np in near(p, []):
                for j in range(len(skins)):
                    skins[j].discard(np)
                    if canchoose(np, [], mycolour, j + 1):
                        skins[j].add(np)


board = [(x,y) for x in range(W) for y in range(H)]
skins = []
for i in range(1, 1 + len(ORTH)):
    skin = RoomyIntPairHashSet(gridhashwidth, gridhashheight)
    skins.append(skin)
    for p in board:
        if canchoose(p, [], mycolour, i):
            skin.add(p)

while 1:
    msg = sys.stdin.readline()
    print("got message "+ msg, file=sys.stderr)
    if msg.startswith('colour'):
        print("updating image", file=sys.stderr)
        updateimage(image, msg.strip())
        print("updated image", file=sys.stderr)
    if msg.startswith('pick'):
        moves = []
        print("picking moves", file=sys.stderr)
        virtualskins = [RoomyIntPairHashSet(gridhashwidth, gridhashheight) for i in range(len(skins))]
        for i in range(pixbatch):
            for j in range(len(skins)):
                if len(virtualskins[j]) > 0 or len(skins[j]) > 0:
                    move = None
                    if len(virtualskins[j]) > 0:
                        move = virtualskins[j].pop()
                    else:
                        move = skins[j].pop()
                    moves.append(move)
                    print("picking move (%u,%u) " % move, file=sys.stderr)
                    for p in near(move, moves):
                        for k in range(len(skins)):
                            virtualskins[k].discard(p)
                            if canchoose(p, moves, mycolour, k + 1):
                                virtualskins[k].add(p)
                    break
        movetext = ' '.join('%u,%u'%p for p in moves)
        print("picked %u moves" % (len(moves)), file=sys.stderr)
        sys.stdout.write(movetext + '\n')
        sys.stdout.flush()
    if msg.startswith('exit') or len(msg) < 1:
        break

image.save('dfblob.png')

El juez original se ha modificado ligeramente para trabajar con Python 3.2 (y para agregar una funcionalidad de registro en bruto a los bots + guardar la imagen de la arena periódicamente para hacer animación):

import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, name, interpreter=None, colour=None):
        self.prog = name
        self.botlist.append(self)
        callarg = re.sub(r'\.class$', '', name)
        self.call = [interpreter, callarg] if interpreter else [callarg]
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        shutil.copy(self.prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = self.call + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (prog, interp) in enumerate(botspec):
    Bot(prog, interp, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
os.mkdir('results')

time.sleep(INITTIME)
total = 0
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save("results/"+BATTLE+str(turn//100).zfill(3)+'.png')
for msgbot in Bot.botlist:
    msgbot.exit()

counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
image.save(BATTLE+'.png')

Los resultados de la arena siguen. El bot dfblob recibió el color rojo para todas las arenas.

Arena 1:

Bot dfblob.py with colour (255, 0, 0) scored 163.75666666666666
Bot blob.py with colour (0, 255, 0) scored 14.896666666666667

Arena 2:

Bot blob.py with colour (0, 255, 0) scored 17.65563547726219
Bot dfblob.py with colour (255, 0, 0) scored 149.57006774236964

Arena 3:

Bot blob.py with colour (0, 255, 0) scored 21.09758208782965
Bot dfblob.py with colour (255, 0, 0) scored 142.9732433108277

Arena 4:

Bot blob.py with colour (0, 255, 0) scored 34.443810082244205
Bot dfblob.py with colour (255, 0, 0) scored 157.0684236785121

Golondrina

Lenguaje = Java

Puntuación = 162.3289512601408075 169.4020975612382575

Busca enemigos y los rodea. Puede que tenga que darle un límite de tiempo más largo. Podría mejorarse bastante. A veces imprime píxeles no válidos.

Actualización: rodea mucho más rápido. Utiliza otro hilo para actualizar las prioridades. Siempre regresa dentro de .1 segundos. La puntuación debería ser imposible de superar sin aumentar MAX_TURNS.

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

public class Swallower {

    static final byte MY_TYPE = 1;
    static final byte BLANK_TYPE = 0;
    static final byte NEUTRAL_TYPE = 2;
    static final byte ENEMY_TYPE = 3;
    private static final int WHITE = Color.WHITE.getRGB();
    private static final int MAX_TIME = 50;
    private final int color;
    private final int N;
    private final int width;
    private final int height;
    private final BufferedReader in;
    Lock borderLock;
    private final PriorityBlockingQueue<Pixel> border;
    private final Set<Pixel> borderSet;
    private final Thread updater;

    Lock imageLock;
    volatile byte[][] image;
    Lock priorityLock;
    volatile int[][] priority;
    volatile boolean updating;
    volatile private boolean exit;

    class Pixel implements Comparable<Pixel> {

        int x;
        int y;

        public Pixel(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pixel o) {
            return priority() - o.priority();
        }

        private int priority() {
            priorityLock.lock();
            int p = priority[x][y];
            priorityLock.unlock();
            return p;
        }

        public byte type() {
            imageLock.lock();
            byte i = image[x][y];
            imageLock.unlock();
            return i;
        }

        public boolean isBorder() {
            if (type() != BLANK_TYPE){
                return false;
            }
            for (Pixel p : pixelsAround()){
                if (p.type() == MY_TYPE){
                    return true;
                }
            }
            return false;
        }

        public void setType(byte newType) {
            imageLock.lock();
            image[x][y] = newType;
            imageLock.unlock();
        }

        public void setPriority(int newPriority) {
            borderLock.lock();
            boolean contains = borderSet.remove(this);
            if (contains){
                border.remove(this);
            }
            priorityLock.lock();
            priority[x][y] = newPriority;
            priorityLock.unlock();
            if (contains){
                border.add(this);
                borderSet.add(this);
            }
            borderLock.unlock();
        }

        public List<Pixel> pixelsAround() {
            List<Pixel> pixels = new ArrayList<>(4);
            if (x > 0){
                pixels.add(new Pixel(x - 1, y));
            }
            if (x < width - 1){
                pixels.add(new Pixel(x + 1, y));
            }
            if (y > 0){
                pixels.add(new Pixel(x, y - 1));
            }
            if (y < height - 1){
                pixels.add(new Pixel(x, y + 1));
            }
            return pixels;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pixel pixel = (Pixel) o;

            return x == pixel.x && y == pixel.y;

        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedImage image = ImageIO.read(new File(args[0]));
        int color = parseColorString(args[1]);
        int N = Integer.parseInt(args[2]);
        new Swallower(image, color, N).start();
    }

    private void start() throws IOException {
        updater.start();
        try {
            while (true) {
                String input = in.readLine();
                if (input.equals("exit")) {
                    exit = true;
                    if (!updating) {
                        updater.interrupt();
                    }
                    return;
                } else if (input.startsWith("colour")) {
                    updateImage(input);
                } else if (input.equals("pick pixels")) {
                    if (updating) {
                        try {
                            synchronized (Thread.currentThread()){
                                Thread.currentThread().wait(MAX_TIME);
                            }
                        } catch (InterruptedException ignored) {
                        }
                    }
                    for (int i = 0; i < N && !border.isEmpty(); i++) {
                        borderLock.lock();
                        Pixel p = border.poll();
                        borderSet.remove(p);
                        borderLock.unlock();
                        if (!p.isBorder()){
                            i--;
                            continue;
                        }
                        updateImage(MY_TYPE, p);
                        System.out.print(p.x + "," + p.y + " ");
                    }
                    System.out.println();
                }
            }
        } catch (Throwable e){
            exit = true;
            if (!updating){
                updater.interrupt();
            }
            throw e;
        }
    }

    private void updateImage(byte type, Pixel... pixels) {
        for (Pixel pixel : pixels){
            pixel.setType(type);
            if (type == MY_TYPE){
                pixel.setPriority(Integer.MAX_VALUE);
            } else {
                pixel.setPriority(0);
            }
        }
        for (Pixel pixel : pixels){
            for (Pixel p : pixel.pixelsAround()){
                if (p.type() == BLANK_TYPE){
                    addPixelToUpdate(p);
                }
                if (type == MY_TYPE && p.isBorder()){
                    borderLock.lock();
                    if (borderSet.add(p)){
                        border.add(p);
                    }
                    borderLock.unlock();
                }
            }
        }
    }

    private synchronized void addPixelToUpdate(Pixel p) {
        if (pixelsToUpdateSet.add(p)) {
            pixelsToUpdate.add(p);
            if (!updating){
                updater.interrupt();
            }
        }
    }

    Queue<Pixel> pixelsToUpdate;
    Set<Pixel> pixelsToUpdateSet;

    private void update(){
        while (true){
            if (exit){
                return;
            }
            if (pixelsToUpdate.isEmpty()){
                try {
                    updating = false;
                    while (!exit) {
                        synchronized (Thread.currentThread()) {
                            Thread.currentThread().wait();
                        }
                    }
                } catch (InterruptedException ignored){}
                continue;
            }
            updating = true;
            Pixel pixel = pixelsToUpdate.poll();
            if (pixel.type() != BLANK_TYPE){
                continue;
            }
            pixelsToUpdateSet.remove(pixel);
            updatePixel(pixel);
        }
    }

    private void updatePixel(Pixel pixel) {
        int originalPriority = pixel.priority();
        int minPriority = Integer.MAX_VALUE;
        List<Pixel> pixelsAround = pixel.pixelsAround();
        for (Pixel p : pixelsAround){
            int priority = p.priority();
            if (priority < minPriority){
                minPriority = priority;
            }
        }
        if (minPriority >= originalPriority){
            pixel.setPriority(Integer.MAX_VALUE);
            pixelsToUpdate.addAll(pixelsAround.stream().filter(p -> p.type() == 0 && p.priority() != Integer.MAX_VALUE).filter(pixelsToUpdateSet::add).collect(Collectors.toList()));
        } else {
            pixel.setPriority(minPriority + 1);
            for (Pixel p : pixelsAround){
                if (p.type() == 0 && p.priority() > minPriority + 2){
                    if (pixelsToUpdateSet.add(p)){
                        pixelsToUpdate.add(p);
                    }
                }
            }
        }

    }

    private void updateImage(String input) {
        String[] inputs = input.split("\\s");
        int color = parseColorString(inputs[1]);
        byte type;
        if (color == this.color){
            return;
        } else {
            type = ENEMY_TYPE;
        }
        Pixel[] pixels = new Pixel[inputs.length - 3];
        for (int i = 0; i < inputs.length - 3; i++){
            String[] coords = inputs[i + 3].split(",");
            pixels[i] = new Pixel(Integer.parseInt(coords[0]), Integer.parseInt(coords[1]));
        }
        updateImage(type, pixels);
    }

    private static int parseColorString(String input) {
        String[] colorString = input.split("[\\(\\),]");
        return new Color(Integer.parseInt(colorString[1]), Integer.parseInt(colorString[2]), Integer.parseInt(colorString[3])).getRGB();
    }

    private Swallower(BufferedImage image, int color, int N){
        this.color = color;
        this.N = N;
        this.width = image.getWidth();
        this.height = image.getHeight();
        this.image = new byte[width][height];
        this.priority = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                int pixelColor = image.getRGB(x,y);
                priority[x][y] = Integer.MAX_VALUE;
                if (pixelColor == WHITE){
                    this.image[x][y] = BLANK_TYPE;
                } else if (pixelColor == this.color){
                    this.image[x][y] = MY_TYPE;
                } else {
                    this.image[x][y] = NEUTRAL_TYPE;
                }
            }
        }
        border = new PriorityBlockingQueue<>();
        borderSet = Collections.synchronizedSet(new HashSet<>());
        borderLock = new ReentrantLock();
        priorityLock = new ReentrantLock();
        imageLock = new ReentrantLock();
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                Pixel pixel = new Pixel(x,y);
                if (pixel.type() == BLANK_TYPE){
                    if (pixel.isBorder()){
                        if (borderSet.add(pixel)){
                            border.add(pixel);
                        }
                    }
                }
            }
        }
        in = new BufferedReader(new InputStreamReader(System.in));
        updating = false;
        updater = new Thread(this::update);
        pixelsToUpdate = new ConcurrentLinkedQueue<>();
        pixelsToUpdateSet = Collections.synchronizedSet(new HashSet<>());
        exit = false;
    }

}

Cómo funciona:

Este bot mantiene una cola prioritaria de píxeles que puede agregar. La prioridad de un píxel enemigo es 0. La prioridad de un píxel en blanco es 1 mayor que la prioridad más baja a su alrededor. Todos los demás píxeles tienen una prioridad de Integer.MAX_VALUE. El subproceso actualizador actualiza constantemente las prioridades de los píxeles. Cada vuelta, los N píxeles más bajos se sacan de la cola de prioridad.

Green Blob vs Red Swallower

Puntuación de Blob = 1.680553372583887225

Puntuación de Swallower = 169.4020975612382575

Arena 1:

Bot Blob.py with colour (0, 255, 0) scored 1.2183333333333333
Bot Swallower.class with colour (255, 0, 0) scored 177.435

Arena 2:

Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517
Bot Blob.py with colour (0, 255, 0) scored 0.5159187091564356

Arena 3:

Bot Blob.py with colour (0, 255, 0) scored 0.727104853136361
Bot Swallower.class with colour (255, 0, 0) scored 163.343720545521

Arena 4:

Bot Swallower.class with colour (255, 0, 0) scored 187.25137716604686
Bot Blob.py with colour (0, 255, 0) scored 4.260856594709419

Golondrina Verde vs. Mancha Roja

Puntuación de Blob = 1.6852943642218457375

Puntuación de Swallower = 169.3923095387498625

Arena 1:

Bot Blob.py with colour (255, 0, 0) scored 1.3166666666666667
Bot Swallower.class with colour (0, 255, 0) scored 177.33666666666667

Arena 2:

Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517
Bot Blob.py with colour (255, 0, 0) scored 0.49573058575466195

Arena 3:

Bot Swallower.class with colour (0, 255, 0) scored 163.14367053301788
Bot Blob.py with colour (255, 0, 0) scored 0.9271548656394868

Arena 4:

Bot Swallower.class with colour (0, 255, 0) scored 187.51060842192973
Bot Blob.py with colour (255, 0, 0) scored 4.0016253388265675

Red Swallower vs Green Depth Primera gota

Puntuación de Swallower = 157.0749775233111925

Profundidad Puntuación del primer blob = 18.192783547939744

Arena 1:

Bot Swallower.class with colour (255, 0, 0) scored 173.52166666666668
Bot dfblob.py with colour (0, 255, 0) scored 5.131666666666667

Arena 2:

Bot dfblob.py with colour (0, 255, 0) scored 17.25635925887156
Bot Swallower.class with colour (255, 0, 0) scored 149.57829253338517

Arena 3:

Bot Swallower.class with colour (255, 0, 0) scored 153.59801488833747
Bot dfblob.py with colour (0, 255, 0) scored 10.472810510319889

Arena 4:

Bot dfblob.py with colour (0, 255, 0) scored 39.91029775590086
Bot Swallower.class with colour (255, 0, 0) scored 151.60193600485545

Green Swallower vs Red Depth Primera gota

Puntuación de Swallower = 154.3368355651281075

Profundidad Puntuación del primer blob = 18.84463249420435425

Arena 1:

Bot Swallower.class with colour (0, 255, 0) scored 165.295
Bot dfblob.py with colour (255, 0, 0) scored 13.358333333333333

Arena 2:

Bot dfblob.py with colour (255, 0, 0) scored 8.91118721119768
Bot Swallower.class with colour (0, 255, 0) scored 149.57829253338517

Arena 3:

Bot Swallower.class with colour (0, 255, 0) scored 157.01136822667206
Bot dfblob.py with colour (255, 0, 0) scored 7.059457171985304

Arena 4:

Bot dfblob.py with colour (255, 0, 0) scored 46.0495522603011
Bot Swallower.class with colour (0, 255, 0) scored 145.4626815004552

Green Blob vs Red Depth First Blob vs Blue Swallower:

Puntuación de Blob = 6.347962032393275525

Profundidad Puntuación del primer blob = 27.34842554331698275

Puntuación de Swallower = 227.720728953415375

Arena 1:

Bot Swallower.class with colour (0, 0, 255) scored 242.54
Bot Blob.py with colour (0, 255, 0) scored 1.21
Bot dfblob.py with colour (255, 0, 0) scored 24.3525

Arena 2:

Bot dfblob.py with colour (255, 0, 0) scored 17.828356088588478
Bot Blob.py with colour (0, 255, 0) scored 0.9252889892479551
Bot Swallower.class with colour (0, 0, 255) scored 224.36743880007776

Arena 3:

Bot dfblob.py with colour (255, 0, 0) scored 7.105141670032893
Bot Swallower.class with colour (0, 0, 255) scored 226.52057245080502
Bot Blob.py with colour (0, 255, 0) scored 12.621905476369092

Arena 4:

Bot dfblob.py with colour (255, 0, 0) scored 60.10770441464656
Bot Blob.py with colour (0, 255, 0) scored 10.634653663956055
Bot Swallower.class with colour (0, 0, 255) scored 217.45490456277872

Aquí está el juez de Sam Yonnou con algunos cambios para que especifique los archivos y el comando por separado:

import sys, re, random, os, shutil, subprocess, datetime, time, signal, io
from PIL import Image

ORTH = ((-1,0), (1,0), (0,-1), (0,1))
def place(loc, colour):
    # if valid, place colour at loc and return True, else False
    if pix[loc] == (255,255,255):
        plist = [(loc[0]+dx, loc[1]+dy) for dx,dy in ORTH]
        if any(pix[p]==colour for p in plist if 0<=p[0]<W and 0<=p[1]<H):
            pix[loc] = colour
            return True
    return False

def updateimage(image, msg, bot):
    if not re.match(r'(\s*\d+,\d+)*\s*', msg):
        return []
    plist = [tuple(int(v) for v in pr.split(',')) for pr in msg.split()]
    plist = plist[:PIXELBATCH]
    return [p for p in plist if place(p, bot.colour)]

class Bot:
    botlist = []
    def __init__(self, progs, command=None, colour=None):
        self.prog = progs[0]
        self.botlist.append(self)
        self.colour = colour
        self.colstr = str(colour).replace(' ', '')
        self.faults = 0
        self.env = 'env%u' % self.botlist.index(self)
        try: os.mkdir(self.env)
        except: pass
        for prog in progs:
            shutil.copy(prog, self.env)
        shutil.copy(imagename, self.env)
        os.chdir(self.env)
        args = command + [imagename, self.colstr, str(PIXELBATCH)]
        errorfile = 'err.log'
        with io.open(errorfile, 'wb') as errorlog:
            self.proc = subprocess.Popen(args, stdin=subprocess.PIPE, 
                stdout=subprocess.PIPE, stderr=errorlog)
        os.chdir('..')
    def send(self, msg):
        if self.faults < FAULTLIMIT:
            self.proc.stdin.write((msg+'\n').encode('utf-8'))
            self.proc.stdin.flush()
    def read(self, timelimit):
        if self.faults < FAULTLIMIT:
            start = time.time()
            inline = self.proc.stdout.readline().decode('utf-8')
            if time.time() - start > timelimit:
                self.faults += 1
                inline = ''
            return inline.strip()
    def exit(self):
        self.send('exit')

from cfg import *
for i, (progs, command) in enumerate(botspec):
    Bot(progs, command, colourspec[i])

image = Image.open(imagename)
pix = image.load()
W,H = image.size
resultdirectory = 'results of ' + BATTLE
os.mkdir(resultdirectory)

time.sleep(INITTIME)
total = 0
image.save(resultdirectory+'/'+'result000.png')
for turn in range(1, MAXTURNS+1):
    random.shuffle(Bot.botlist)
    nullbots = 0
    for bot in Bot.botlist:
        bot.send('pick pixels')
        inmsg = bot.read(TIMELIMIT)
        newpixels = updateimage(image, inmsg, bot)
        total += len(newpixels)
        if newpixels:
            pixtext = ' '.join('%u,%u'%p for p in newpixels)
            msg = 'colour %s chose %s' % (bot.colstr, pixtext)
            for msgbot in Bot.botlist:
                msgbot.send(msg)
        else:
            nullbots += 1
    if nullbots == len(Bot.botlist):
        break
    if turn % 100 == 0:
        print('Turn %s done %s pixels' % (turn, total))
        image.save(resultdirectory+'/result'+str(turn//100).zfill(3)+'.png')
image.save(resultdirectory+'/result999.png')
for msgbot in Bot.botlist:
    msgbot.exit()

resultfile = io.open(resultdirectory+'/result.txt','w')
counts = dict((c,f) for f,c in image.getcolors(W*H))
avg = 1.0 * sum(counts.values()) / len(Bot.botlist)
for bot in Bot.botlist:
    score = 100 * counts[bot.colour] / avg
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score))
    print('Bot %s with colour %s scored %s' % (bot.prog, bot.colour, score), file=resultfile)
image.save(BATTLE+'.png')