ПОЗДРАВЛЯЕМ @kuroineko за лучшую запись и выигрыш в размере 200 от @TheBestOne (отличное спортивное мастерство!).

Напишите программу, чтобы раскрасить как можно большую часть изображения до того, как это сделают оппозиционные программы.

Правила вкратце

• Ваша программа получит изображение, ваш цвет и целое число N.
• Каждый ход вам посылают обновления пикселей другими программами и запрашивают ваши N обновлений.
• Вы можете обновить любой белый пиксель, который находится рядом с пикселем вашего цвета.
• Программа, которая добавила наибольшее количество пикселей, выигрывает.

Правила в деталях

Ваша программа получит имя файла PNG-изображения, домашний цвет и число N. Число N - это максимальное количество пикселей, которые ваша программа может раскрашивать каждый ход.

Пример: MyProg arena.png (255,0,0) 30

Входное изображение будет прямоугольником со сторонами от 20 до 1000 пикселей. Он будет состоять из черного, белого и цветного пикселей. Ваша программа может выбрать последовательность белых пикселей для окрашивания как свою собственную, при условии, что каждый новый пиксель должен иметь хотя бы один из четырех соседних пикселей вашего собственного цвета. Изображение изначально будет иметь как минимум один пиксель вашего цвета. Также могут быть пиксели цветов, которым не назначена ни одна программа. Альфа-канал не используется.

Ваша цель состоит в том, чтобы блокировать своих оппонентов и записать свой цвет в максимально возможное количество пикселей.

Каждый ход ваша программа будет принимать 1 или более строк сообщений в STDIN и записывать строку, состоящую из координат пикселей в STDOUT. Не забудьте назначить STDOUT небуферизованным или очищать буфер STDOUT каждый ход.

Порядок игроков, вызываемых каждый ход, будет назначен случайным образом. Это означает, что у противника (или вашей программы) может быть 2 хода подряд.

Ваша программа будет отправлять colour (N,N,N) chose X,Y X,Y ... X,Yинформационные сообщения, описывающие пиксели, заполненные программами плеера. Если игрок не делает ходов или не имеет действительных ходов, вам не будет отправлено сообщение о ходах этого игрока. Вашей программе также будет отправлено сообщение о ваших собственных принятых ходах (если вы указали хотя бы один действительный ход). Пиксель 0,0 находится в верхнем левом углу изображения.

При получении pick pixelsваша программа будет выводить X,Y X,Y ... X,Yдо N пикселей (допускается пустая строка, состоящая только из '\ n'). Пиксели должны быть в порядке построения. Если пиксель недействителен, он будет проигнорирован и не будет в отчете игрокам. Ваша программа имеет 2 секунды для инициализации после запуска, но только 0,1 секунды, чтобы отвечать ответом каждый ход, иначе она пропустит этот ход. Обновление пикселей, отправленное через 0,1 секунды, запишет ошибку. После 5 ошибок ваша программа будет приостановлена ​​и не будет отправляться обновления или pick pixelsзапросы.

Когда программа-судья получает выбор пустого или недействительного пикселя от каждой неподдерживаемой программы проигрывателя, изображение будет считаться завершенным, и программам будет отправлено сообщение «Выход». Программы должны завершаться после получения «выхода».

счет

Судья наберет очки после того, как изображение будет завершено. Ваша оценка будет вашим количеством обновленных пикселей, деленным на среднее количество пикселей, полученных за этот раунд, выраженное в процентах.

Количество пикселей, добавленных к изображению вашим плеером, равно A. Общее количество пикселей, добавленных всеми игроками P, равно T. avg = T/P score = 100*A/avg

Отправка баллов

Ссылка оппонента "Blob" дается. Для каждого ответа назовите своего бота именем, языком и вашим счетом (в среднем от 1 до 4) по отношению к оппоненту. Картинка или анимация одного из ваших сражений тоже подойдут. Победителем становится программа с наибольшим счетом по отношению к контрольному боту.

Если «Блоб» окажется слишком легко победить, я могу добавить второй раунд с более сильным оппонентом.

Вы также можете поэкспериментировать с 4 или более программами игрока. Вы также можете проверить своего бота против других ботов, опубликованных в качестве ответов.

Судья

Для программы судьи требуется общая библиотека изображений Python (PIL), и ее легко установить из диспетчера пакетов ОС в Linux. У меня есть отчет о том, что PIL не работает с 64-битным Python в Windows 7, поэтому, пожалуйста, проверьте, будет ли PIL работать для вас, прежде чем начинать эту задачу (обновлено 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')

Пример конфигурации - 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'),
    ]

Blob - ссылочный оппонент

# 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')

Арена 1

Арена 2

Арена 3

Арена 4

Пример битвы - Blob против Blob

Эта битва имела предсказуемый результат:

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

ColorFighter - C ++ - ест пару глотателей на завтрак

РЕДАКТИРОВАТЬ

• убрал код
• добавлена ​​простая, но эффективная оптимизация
• добавлены некоторые GIF-анимации

Боже, я ненавижу змей (просто притворяйся, что они пауки, Инди)

На самом деле я люблю Python. Хотелось бы, чтобы я был менее ленивым мальчиком и начал учить его правильно, вот и все.

После всего этого, мне пришлось бороться с 64-битной версией этой змеи, чтобы заставить судью работать. Чтобы PIL работал с 64-битной версией Python под Win7, требуется больше терпения, чем я готов был посвятить этому испытанию, поэтому в итоге я (болезненно) переключился на версию Win32.

Кроме того, судья имеет тенденцию сильно падать, когда бот слишком медленно реагирует.
Будучи не разбирающимся в Python, я не исправил это, но это связано с чтением пустого ответа после тайм-аута на stdin.

Незначительным улучшением было бы поместить вывод stderr в файл для каждого бота. Это облегчило бы отслеживание для посмертной отладки.

За исключением этих мелких проблем, я нашел Судью очень простым и приятным в использовании.
Престижность для еще одного изобретательного и веселого испытания.

Код

#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();
}

Сборка исполняемого файла

Я использовал LODEpng.cpp и LODEpng.h для чтения изображений PNG.
О самом простом способе, которым я научил этот отсталый язык C ++, как читать картинку, не создавая полдюжины библиотек.
Просто скомпилируйте и свяжите LODEpng.cpp вместе с главной и Бобом, вашим дядей.

Я скомпилировал с MSVC2013, но так как я использовал только несколько базовых контейнеров STL (deque и векторы), он может работать с gcc (если вам повезет).
Если это не так, я мог бы попробовать сборку MinGW, но, честно говоря, я устал от проблем с переносимостью C ++.

В свое время я много занимался переносом C / C ++ (на экзотических компиляторах для различных 8–32-битных процессоров, а также на SunOS, Windows от 3.11 до Vista и Linux от младенчества до Ubuntu Cooing Zebra или чего-то еще, так что я думаю, У меня есть довольно хорошее представление о том, что означает переносимость), но в то время не требовалось запоминать (или обнаруживать) бесчисленные расхождения между интерпретациями GNU и Microsoft загадочных и раздутых спецификаций монстра STL.

Результаты против Swallower

Как это работает

По сути, это простой путь заливки.

Граница цвета игрока (то есть пикселей, которые имеют по крайней мере одного белого соседа) используется в качестве начального числа для выполнения классического алгоритма затопления расстояний.

Когда точка достигает окрестности вражеского цвета, вычисляется обратный путь, чтобы создать ряд пикселей, движущихся в направлении ближайшего вражеского пятна.

Процесс повторяется до тех пор, пока не будет набрано достаточное количество точек для ответа желаемой длины.

Это повторение непристойно дорого, особенно когда сражаешься рядом с врагом.
Каждый раз, когда последовательность пикселей, ведущая от границы к вражескому пикселю, была найдена (и нам нужно больше точек, чтобы завершить ответ), заливка затопляется заново с начала, с новым путем, добавленным к границе. Это означает, что вы могли бы сделать 5 заливок или больше, чтобы получить ответ в 10 пикселей.

Если вражеские пиксели больше недоступны, выбираются произвольные соседи пограничных пикселей.
Алгоритм сводится к довольно неэффективному заполнению флудом, но это происходит только после того, как будет решен исход игры (то есть больше нет нейтральной территории для борьбы).
Я оптимизировал его так, чтобы судья не тратил целую вечность, заполняя карту после того, как соревнование было рассмотрено. В своем текущем состоянии время исполнения пренебрежимо мало по сравнению с самим судьей.

Поскольку вражеские цвета не известны в начале, исходное изображение арены сохраняется в хранилище, чтобы скопировать начальные области врага, когда он делает свой первый ход.
Если код воспроизводится первым, он просто заполняет несколько произвольных пикселей.

Это делает алгоритм способным бороться с произвольным числом противников и даже, возможно, с новыми противниками, прибывающими в произвольный момент времени, или с цветами, появляющимися без начальной области (хотя это абсолютно не имеет практического применения).

Обработка врага на основе цвета за цвет также позволила бы двум экземплярам взаимодействовать с ботом (используя пиксельные координаты для передачи секретного знака распознавания).
Звучит весело, я, наверное, попробую :).

Интенсивный вычислительный путь выполняется, как только появляются новые данные (после уведомления о перемещении), и некоторые оптимизации (обновление границы) выполняются сразу после получения ответа (чтобы сделать как можно больше вычислений во время поворотов других ботов) ).

Здесь снова могут быть способы сделать более тонкие вещи, если бы было более одного противника (например, прервать вычисление, если новые данные стали доступны), но, во всяком случае, я не вижу, где необходима многозадачность, пока алгоритм способен работать на полную нагрузку.

Проблемы с производительностью

Все это не может работать без быстрого доступа к данным (и большей вычислительной мощности, чем у всей программы Appolo, т. Е. Вашего обычного ПК, когда вы используете больше, чем публикуете несколько твитов).

Скорость сильно зависит от компилятора. Обычно GNU опережает Microsoft на 30% (это магическое число, которое я заметил при трех других проблемах с кодом, связанным с маршрутизацией), но этот пробег может меняться, конечно.

Код в его текущем состоянии с трудом справляется с трудностями на арене 4. Перфметр Windows сообщает о 4–7% -ной загрузке ЦП, поэтому он должен быть в состоянии справиться с картой 1000x1000 в пределах времени отклика 100 мс.

В основе каждого алгоритма маршрутизации лежит FIFO (возможно, проритизированный, но не в этом случае), который, в свою очередь, требует быстрого выделения элементов.

Так как ОП обязательно установил ограничение на размер арены, я немного посчитал и увидел, что фиксированные структуры данных размером до максимума (т. Е. 1.000.000 пикселей) не будут потреблять более пары десятков мегабайт, которые ваш средний компьютер ест на завтрак.
Действительно, под Win7 и скомпилированный с MSVC 2013, код потребляет около 14 МБ на арене 4, в то время как два потока Swallower используют более 20 МБ.

Я начал с контейнеров STL для упрощения создания прототипов, но STL сделал код еще менее читаемым, поскольку у меня не было желания создавать класс для инкапсуляции каждого бита данных, чтобы скрыть запутывание (связано ли это с моими собственными возможностями справиться с STL оставлено на усмотрение читателя).
Несмотря на это, результат был настолько ужасно медленным, что сначала я думал, что по ошибке строю отладочную версию.

Я считаю, что это отчасти связано с невероятно плохой реализацией Microsoft STL (где, например, векторы и наборы битов выполняют связанные проверки или другие криптические операции над оператором [], в прямом нарушении спецификации), а также частично из-за конструкции STL сам.

Я мог бы справиться с жестокими проблемами синтаксиса и переносимости (то есть Microsoft против GNU), если бы производительность была там, но это, конечно, не так.

Например, dequeизначально медленный, потому что он тасует много бухгалтерских данных в ожидании случая, чтобы сделать его супер-умное изменение размера, о котором мне наплевать.
Конечно, я мог бы реализовать собственный распределитель и другие биты пользовательских шаблонов, но один только собственный распределитель стоит несколько сотен строк кода и лучшую часть дня, чтобы проверить, что с дюжиной интерфейсов, которые он должен реализовать, в то время как Эквивалентная структура, созданная вручную, состоит из нуля строк кода (хотя и более опасно, но алгоритм не сработал бы, если бы я не знал - или, думаю, знал - что я делал в любом случае).

Таким образом, в конце концов я сохранил контейнеры STL в некритических частях кода и создал свой собственный брутальный распределитель и FIFO с двумя массивами 1970 года и тремя шортами без знака.

Глотать глотатель

Как подтвердил его автор, неустойчивые паттерны «ласточки» вызваны задержкой между уведомлениями о перемещениях противника и обновлениями из потока пути.
Системный перфметр четко показывает траекторию потока, потребляющую 100% ЦП все время, и неровные узоры имеют тенденцию появляться, когда фокус сражения смещается в новую область. Это также вполне очевидно с анимацией.

Простая, но эффективная оптимизация

Посмотрев на грандиозные воздушные бои между Ласточкой и моим бойцом, я вспомнил старую поговорку из игры в Го: защищайся крупным планом, но атакуй издалека.

В этом есть мудрость. Если вы слишком стараетесь придерживаться своего противника, вы будете тратить драгоценные ходы, пытаясь заблокировать каждый возможный путь. Напротив, если вы останетесь на расстоянии всего одного пикселя, вы, скорее всего, избежите заполнения небольших пробелов, которые могут принести очень мало, и будете использовать свои действия для противодействия более важным угрозам.

Чтобы реализовать эту идею, я просто расширил ходы врага (отметив 4 соседа каждого хода как вражеский пиксель).
Это останавливает алгоритм прохождения пути на расстоянии одного пикселя от границы врага, позволяя моему бойцу обходить противника, не оказываясь втянутым в слишком много воздушных боев.

Вы можете увидеть улучшение
(хотя все прогоны не так успешны, вы можете заметить более плавные контуры):

Глубина-первая Blob против Blob

Язык = Python (3.2)

Оценка = 111,475388276 153,34210035

Обновление: теперь используя пользовательский Setкласс, чтобы получить pop()метод для создания своего рода сетки, которая радикально улучшает область, покрытую в начале, отрезая большие части изображения от врага. Примечание: для этого я использую сетку 12 x 12, которая из случайной выборки размеров сетки, по-видимому, дала наилучшие результаты для arena3 (той, которая получила худший результат перед обновлением), однако весьма вероятно, что более оптимальная Размер сетки существует для данного выбора арен.

Я пошел на простую модификацию эталонного бота, чтобы он выбирал возможные точки, ограниченные как можно меньшим количеством точек собственного цвета. Улучшение может заключаться в том, чтобы оно также способствовало выбору возможных точек, ограниченных как можно большим количеством цветов врага.

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')

Оригинальный судья был немного изменен для работы с Python 3.2 (и для добавления грубой логирующей функциональности к ботам + периодически сохраняйте изображение арены для создания анимации):

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')

Результаты арены следуют. Бот dfblob получил красный цвет для всех арен.

Арена 1:

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

Арена 2:

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

Арена 3:

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

Арена 4:

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

Swallower

Язык = Java

Оценка = +162,3289512601408075 +169,4020975612382575

Ищет врагов и окружает. Возможно, вам придется продлить срок. Может быть улучшен совсем немного. Иногда печатает недопустимые пиксели.

Обновление: Окружает намного быстрее. Использует другой поток для обновления приоритетов. Всегда возвращается в течение 0,1 секунды. Оценка должна быть невозможной без увеличения 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;
    }

}

Как это работает:

Этот бот поддерживает приоритетную очередь пикселей, которые он может добавить. Приоритет вражеского пикселя равен 0. Приоритет пустого пикселя на 1 больше, чем самый низкий приоритет вокруг него. Все остальные пиксели имеют приоритет Integer.MAX_VALUE. Тема обновления постоянно обновляет приоритеты пикселей. Каждый ход наименьшие N пикселей выталкиваются из очереди приоритетов.

Грин Блоб против Красного Глотателя

Оценка Blob = 1.680553372583887225

Счет ласточкина = 169.4020975612382575

Арена 1:

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

Арена 2:

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

Арена 3:

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

Арена 4:

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

Зеленый глотатель против Красной капли

Оценка Blob = 1.6852943642218457375

Счет ласточкина = 169.3923095387498625

Арена 1:

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

Арена 2:

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

Арена 3:

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

Арена 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 против Green Depth Первая капля

Счет ласточкина = 157.0749775233111925

Глубина Оценка первого BLOB-объекта = 18.192783547939744

Арена 1:

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

Арена 2:

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

Арена 3:

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

Арена 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 против Red Depth Первая капля

Счет ласточкина = 154.3368355651281075

Глубина Оценка первого BLOB-объекта = 18,84463249420435425

Арена 1:

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

Арена 2:

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

Арена 3:

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

Арена 4:

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

Зеленая капля против красной глубины Первая капля против синей ласточки:

Оценка Blob = 6,347962032393275525

Глубина Оценка первого BLOB-объекта = 27,34842554331698275

Оценка ласточкина = 227.720728953415375

Арена 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

Арена 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

Арена 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

Арена 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

Вот судья Сэма Йонну с несколькими изменениями, чтобы вы указали файлы и команду отдельно:

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')