SELAMAT DATANG ke @kuroineko untuk entri terbaik dan menangkan 200 hadiah dari @TheBestOne (sportivitas luar biasa!).

Tulis program untuk mewarnai gambar sebanyak mungkin sebelum program oposisi melakukannya.

Aturan secara singkat

• Program Anda akan diberi gambar, warna Anda, dan bilangan bulat N.
• Setiap belokan Anda dikirim pembaruan piksel oleh program lain, dan diminta untuk pembaruan N Anda.
• Anda dapat memperbarui piksel putih apa pun yang berada di sebelah piksel warna Anda.
• Program yang telah menambahkan piksel terbanyak akan menang.

Aturan secara rinci

Program Anda akan diberi nama file gambar PNG, warna beranda, dan angka N. Angka N adalah jumlah piksel maksimum yang dapat diwarnai program Anda setiap giliran.

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

Gambar input akan menjadi persegi panjang dengan sisi antara 20 dan 1000 piksel. Ini akan terdiri dari piksel hitam, putih, dan warna. Program Anda dapat memilih urutan piksel putih untuk diwarnai sebagai milik Anda, dengan ketentuan bahwa setiap piksel baru harus memiliki setidaknya satu dari empat piksel tetangganya dengan warna Anda sendiri. Gambar awalnya akan memiliki setidaknya satu piksel warna Anda. Mungkin juga memiliki piksel warna yang tidak ada program ditugaskan untuk. Saluran alfa tidak digunakan.

Tujuan Anda adalah untuk memblokir lawan Anda dan menulis warna Anda menjadi piksel sebanyak yang Anda bisa.

Setiap belokan program Anda akan menerima 1 atau lebih baris pesan pada STDIN, dan menulis baris yang terdiri dari koordinat piksel pada STDOUT. Ingatlah untuk menetapkan STDOUT sebagai tidak terbaca atau siram buffer STDOUT setiap belokan.

Urutan pemain yang dipanggil setiap belokan akan ditentukan secara acak. Ini berarti bahwa lawan (atau program Anda) mungkin memiliki 2 putaran berturut-turut.

Program Anda akan dikirimi colour (N,N,N) chose X,Y X,Y ... X,Ypesan informasi yang menggambarkan piksel yang diisi oleh program pemain. Jika seorang pemain tidak membuat gerakan, atau tidak ada gerakan yang valid, Anda tidak akan dikirimi pesan tentang gerakan pemain itu. Program Anda juga akan dikirimi pesan tentang gerakan Anda sendiri yang diterima (jika Anda telah menentukan setidaknya satu gerakan yang valid). Pixel 0,0 berada di sudut kiri atas gambar.

Saat menerima pick pixels, program Anda akan menghasilkan X,Y X,Y ... X,Yhingga N piksel (string kosong yang hanya terdiri dari '\ n' diperbolehkan). Piksel harus dalam urutan plot. Jika sebuah piksel tidak valid, itu akan diabaikan dan tidak ada dalam laporan kepada pemain. Program Anda memiliki 2 detik untuk diinisialisasi setelah memulai, tetapi hanya 0,1 detik untuk menjawab dengan jawaban setiap belokan atau ia akan melewatkan belokan itu. Pembaruan piksel yang dikirim setelah 0,1 detik akan mencatat kesalahan. Setelah 5 kesalahan, program Anda ditangguhkan dan tidak akan dikirim pembaruan atau pick pixelspermintaan.

Ketika program juri menerima pilihan piksel kosong atau tidak valid dari setiap program pemain yang tidak ditangguhkan, gambar akan dianggap selesai dan program akan dikirim pesan "keluar". Program harus berakhir setelah menerima "keluar".

Mencetak gol

Juri akan mencetak poin setelah gambar selesai. Skor Anda akan menjadi jumlah piksel Anda yang diperbarui dibagi dengan tangkapan piksel rata-rata pada putaran itu, dinyatakan sebagai persentase.

Jumlah piksel yang ditambahkan ke gambar oleh pemain Anda adalah A. Jumlah piksel yang ditambahkan oleh semua pemain P adalah T. avg = T/P score = 100*A/avg

Posting skor

Referensi lawan "Gumpalan" diberikan. Untuk setiap jawaban, beri judul bot Anda dengan nama, bahasa, dan skor Anda (rata-rata arena 1 hingga 4) melawan lawan referensi. Gambar atau animasi dari salah satu pertempuran Anda juga bagus. Pemenangnya adalah program dengan skor tertinggi melawan bot referensi.

Jika The Blob terbukti terlalu mudah dikalahkan, saya dapat menambahkan ronde kedua dengan lawan referensi yang lebih kuat.

Anda mungkin juga ingin bereksperimen dengan 4 program pemain atau lebih. Anda juga dapat menguji bot Anda terhadap bot lain yang diposting sebagai jawaban.

Hakim

Program juri memerlukan Python Imaging Library (PIL) yang umum dan harus mudah diinstal dari manajer paket OS Anda di Linux. Saya punya laporan bahwa PIL tidak bekerja dengan 64 bit Python di Windows 7, jadi silakan periksa apakah PIL akan bekerja untuk Anda sebelum memulai tantangan ini (diperbarui 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')

Contoh Config - 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 - lawan referensi

# 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

Contoh Pertempuran - Blob vs Blob

Pertempuran ini memiliki hasil yang dapat diprediksi:

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

ColorFighter - C ++ - makan beberapa swallower untuk sarapan

EDIT

• membersihkan kode
• menambahkan pengoptimalan yang sederhana namun efektif
• menambahkan beberapa animasi GIF

Ya Tuhan, aku benci ular (pura-pura itu laba-laba, Indy)

Sebenarnya saya suka Python. Seandainya saja saya bukan anak yang malas dan mulai mempelajarinya dengan baik, itu saja.

Semua ini dikatakan, saya harus berjuang dengan versi 64 bit dari ular ini untuk membuat Hakim bekerja. Membuat PIL bekerja dengan versi 64 bit Python di bawah Win7 membutuhkan lebih banyak kesabaran daripada yang saya siapkan untuk tantangan ini, jadi pada akhirnya saya beralih (dengan menyakitkan) ke versi Win32.

Juga, Hakim cenderung crash parah ketika bot terlalu lambat untuk merespon.
Menjadi bukan Python savvy, saya tidak memperbaikinya, tetapi itu ada hubungannya dengan membaca jawaban kosong setelah batas waktu pada stdin.

Perbaikan kecil akan menempatkan output stderr ke file untuk setiap bot. Itu akan memudahkan pelacakan untuk debugging post-mortem.

Kecuali untuk masalah-masalah kecil ini, saya menemukan bahwa Hakim itu sangat sederhana dan menyenangkan untuk digunakan.
Pujian untuk tantangan inventif dan menyenangkan lainnya.

Kode

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

Membangun executable

Saya menggunakan LODEpng.cpp dan LODEpng.h untuk membaca gambar png.
Tentang cara termudah yang saya temukan untuk mengajarkan bahasa C ++ terbelakang ini cara membaca gambar tanpa harus membangun setengah lusin perpustakaan.
Kompilasi saja & tautkan LODEpng.cpp bersama dengan main dan Bob adalah pamanmu.

Saya dikompilasi dengan MSVC2013, tetapi karena saya hanya menggunakan beberapa kontainer dasar STL (deque dan vektor), mungkin berhasil dengan gcc (jika Anda beruntung).
Jika tidak, saya mungkin mencoba membangun MinGW, tapi terus terang saya bosan dengan masalah portabilitas C ++.

Saya melakukan cukup banyak C / C ++ portabel di hari-hari saya (pada kompiler eksotis untuk berbagai 8 hingga 32 bit prosesor serta SunOS, Windows dari 3,11 hingga Vista dan Linux dari masa kanak-kanak ke Ubuntu cooing zebra atau apa pun, jadi saya pikir Saya memiliki ide yang cukup bagus tentang apa artinya portabilitas), tetapi pada saat itu tidak perlu untuk menghafal (atau menemukan) perbedaan yang tak terhitung banyaknya antara interpretasi GNU dan Microsoft tentang spesifikasi samar dan bengkak dari monster STL.

Hasil melawan Swallower

Bagaimana itu bekerja

Pada intinya, ini adalah jalur penimbunan brute force yang sederhana.

Batas warna pemain (yaitu piksel yang memiliki setidaknya satu tetangga putih) digunakan sebagai seed untuk melakukan algoritma flooding jarak klasik.

Ketika suatu titik mencapai lingkaran warna musuh, jalur mundur dihitung untuk menghasilkan serangkaian piksel bergerak menuju tempat musuh terdekat.

Proses ini diulangi sampai cukup banyak poin telah dikumpulkan untuk tanggapan dengan panjang yang diinginkan.

Pengulangan ini sangat mahal, terutama ketika bertarung di dekat musuh.
Setiap kali serangkaian piksel yang mengarah dari perbatasan ke piksel musuh telah ditemukan (dan kami membutuhkan lebih banyak poin untuk menyelesaikan jawabannya), isi banjir akan dikerjakan ulang dari awal, dengan jalur baru ditambahkan ke perbatasan. Ini berarti Anda harus melakukan 5 pengisian banjir atau lebih untuk mendapatkan jawaban 10 piksel.

Jika tidak ada lagi piksel musuh yang dapat dijangkau, tetangga arbitrer dari piksel perbatasan dipilih.
Algoritma beralih ke pengisian banjir yang agak tidak efisien, tetapi ini hanya terjadi setelah hasil permainan telah diputuskan (yaitu tidak ada wilayah yang lebih netral untuk diperjuangkan).
Saya memang mengoptimalkannya sehingga Hakim tidak menghabiskan waktu lama untuk mengisi peta begitu kompetisi telah ditangani. Dalam kondisi saat ini, waktu eksekusi dapat diabaikan dibandingkan dengan Hakim itu sendiri.

Karena warna musuh tidak diketahui saat start, gambar arena awal disimpan di toko untuk menyalin area awal musuh ketika itu membuat langkah pertama.
Jika kode diputar terlebih dahulu, itu hanya akan mengisi beberapa piksel sembarang.

Hal ini membuat algoritma mampu melawan sejumlah musuh yang sewenang-wenang, dan bahkan mungkin musuh baru tiba pada titik waktu yang acak, atau warna muncul tanpa area awal (meskipun ini sama sekali tidak ada penggunaan praktis).

Penanganan musuh berdasarkan warna-per-warna juga akan memungkinkan dua instance bot bekerja sama (menggunakan koordinat piksel untuk melewati tanda pengakuan rahasia).
Kedengarannya menyenangkan, saya mungkin akan mencobanya :).

Penelusuran berat komputasi dilakukan segera setelah data baru tersedia (setelah pemberitahuan perpindahan), dan beberapa optimisasi (pembaruan perbatasan) dilakukan tepat setelah respons diberikan (untuk melakukan perhitungan sebanyak mungkin selama putaran bot lainnya) ).

Di sini lagi, mungkin ada cara untuk melakukan hal-hal yang lebih halus jika ada lebih dari 1 musuh (seperti membatalkan perhitungan jika data baru tersedia), tetapi bagaimanapun saya gagal untuk melihat di mana multitasking diperlukan, asalkan algoritma itu dapat bekerja dengan beban penuh.

Masalah kinerja

Semua ini tidak dapat bekerja tanpa akses data cepat (dan lebih banyak daya komputasi dari seluruh program Appolo, yaitu PC rata-rata Anda saat digunakan untuk melakukan lebih dari memposting beberapa tweet).

Kecepatannya sangat bergantung pada kompiler. Biasanya GNU mengalahkan Microsoft dengan selisih 30% (itu angka ajaib yang saya perhatikan pada 3 tantangan kode terkait lintasan lainnya), tetapi jarak tempuh ini tentu saja bervariasi.

Kode dalam kondisi saat ini nyaris tidak berkeringat di arena 4. Windows perfmeter melaporkan penggunaan CPU sekitar 4 hingga 7%, sehingga harus mampu mengatasi peta 1000x1000 dalam batas waktu respons 100 ms.

Inti dari setiap algoritma lintasan terletak pada FIFO (mungkin diprioritaskan, meskipun tidak dalam kasus itu), yang pada gilirannya membutuhkan alokasi elemen cepat.

Karena OP wajib menetapkan batas ukuran arena, saya melakukan beberapa matematika dan melihat bahwa struktur data tetap berdimensi maks (yaitu 1.000.000 piksel) tidak akan mengkonsumsi lebih dari beberapa lusin megabita, yang rata-rata PC Anda makan untuk sarapan.
Memang di bawah Win7 dan dikompilasi dengan MSVC 2013, kode ini mengkonsumsi sekitar 14MB di arena 4, sementara dua utas Swallower menggunakan lebih dari 20MB.

Saya mulai dengan wadah STL untuk prototipe yang lebih mudah, tetapi STL membuat kodenya bahkan lebih mudah dibaca, karena saya tidak punya keinginan untuk membuat kelas untuk merangkum setiap bit data untuk menyembunyikan kebingungan menjauh (apakah itu karena ketidakmampuan saya sendiri untuk mengatasi STL diserahkan kepada apresiasi pembaca).
Bagaimanapun, hasilnya sangat lambat sehingga pada awalnya saya pikir saya membangun versi debug secara tidak sengaja.

Saya rasa ini sebagian karena implementasi STL Microsoft yang sangat buruk (di mana, misalnya, vektor dan bitet melakukan pemeriksaan terikat atau operasi crypic lainnya pada operator [], yang melanggar spesifikasi secara langsung), dan sebagian karena desain STL diri.

Saya bisa mengatasi masalah sintaksis dan portabilitas (yaitu Microsoft vs GNU) yang buruk jika pertunjukannya ada di sana, tetapi ini tentu saja bukan masalahnya.

Sebagai contoh, dequesecara inheren lambat, karena mengacak banyak data pembukuan sekitar menunggu kesempatan untuk melakukan perubahan ukuran super pintar, tentang yang saya tidak peduli.
Tentu saya bisa menerapkan pengalokasi kustom dan whatver bit template kustom lainnya, tetapi pengalokasi kustom sendiri biaya beberapa ratus baris kode dan bagian yang lebih baik dari hari untuk menguji, apa dengan selusin antarmuka yang harus diimplementasikan, sementara struktur setara buatan tangan adalah tentang nol baris kode (walaupun lebih berbahaya, tetapi algoritme tidak akan bekerja jika saya tidak tahu - atau berpikir saya tahu - apa yang saya lakukan tetap).

Jadi akhirnya saya menyimpan kontainer STL di bagian kode yang tidak kritis, dan membangun pengalokasi brutal saya sendiri dan FIFO dengan dua array sekitar tahun 1970 dan tiga celana pendek yang tidak ditandatangani.

Menelan burung walet

Seperti yang dikonfirmasikan oleh penulisnya, pola Swallower yang tidak menentu disebabkan oleh jeda antara pemberitahuan pergerakan musuh dan pembaruan dari utas lintasan.
Perfmeter sistem menunjukkan dengan jelas bahwa jalur path mengkonsumsi 100% CPU sepanjang waktu, dan pola bergerigi cenderung muncul ketika fokus pertarungan bergeser ke area baru. Ini juga cukup jelas dengan animasinya.

Optimalisasi sederhana namun efektif

Setelah melihat pertarungan epik antara Swallower dan petarung saya, saya teringat pepatah lama dari permainan Go: bertahan dari dekat, tetapi serang dari jauh.

Ada kebijaksanaan dalam hal itu. Jika Anda mencoba terlalu banyak bertahan pada musuh Anda, Anda akan menyia-nyiakan gerakan berharga mencoba memblokir setiap jalur yang mungkin. Sebaliknya, jika Anda tinggal satu piksel jauhnya, Anda kemungkinan akan menghindari mengisi celah kecil yang akan mendapatkan sangat sedikit, dan menggunakan gerakan Anda untuk menghadapi ancaman yang lebih penting.

Untuk mengimplementasikan ide ini, saya cukup memperluas gerakan musuh (menandai 4 tetangga dari setiap gerakan sebagai piksel musuh).
Ini menghentikan algoritme lintasan satu piksel dari perbatasan musuh, memungkinkan pejuang saya untuk mengatasi musuh tanpa terjebak dalam terlalu banyak pertempuran udara.

Anda dapat melihat peningkatannya
(meskipun semua proses tidak berhasil, Anda dapat melihat garis besar yang jauh lebih lancar):

Kedalaman-Pertama Gumpalan vs Gumpalan

Bahasa = Python (3.2)

Nilai = 111,475388276 153.34210035

Pembaruan: Sekarang menggunakan Setkelas khusus untuk mendapatkan pop()metode untuk menghasilkan semacam pola kisi yang secara drastis meningkatkan area yang dicakup pada awal memotong sebagian besar gambar dari musuh. Catatan: Saya menggunakan kisi 12 x 12 untuk sampel acak ukuran kisi mana yang tampaknya memberikan hasil terbaik untuk arena3 (yang mendapat skor terburuk sebelum pembaruan), namun sangat mungkin lebih optimal ukuran kisi ada untuk pemilihan arena yang diberikan.

Saya pergi untuk modifikasi sederhana ke bot referensi untuk membuatnya memilih titik-titik yang layak yang dibatasi oleh poin berwarna sendiri sesedikit mungkin. Suatu perbaikan mungkin untuk membuatnya juga mendukung memilih poin yang layak yang dibatasi oleh sebanyak mungkin poin berwarna musuh.

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

Juri asli telah sedikit dimodifikasi untuk bekerja dengan Python 3.2 (dan untuk menambahkan fungsi logging mentah ke bot + simpan gambar arena secara berkala untuk membuat animasi):

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

Hasil arena mengikuti. Bot dfblob diberi warna merah untuk semua arena.

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

Swallower

Bahasa = Jawa

Skor = 162.3289512601408075 169.4020975612382575

Mencari musuh dan mengelilingi. Anda mungkin harus memberikan batas waktu yang lebih lama. Dapat ditingkatkan sedikit. Terkadang mencetak piksel yang tidak valid.

Pembaruan: Mengalami lebih cepat. Gunakan utas lain untuk memperbarui prioritas. Selalu kembali dalam 0,1 detik. Skor seharusnya mustahil dikalahkan tanpa meningkatkan 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;
    }

}

Bagaimana itu bekerja:

Bot ini mempertahankan antrian prioritas piksel yang dapat ditambahkan. Prioritas piksel musuh adalah 0. Prioritas piksel kosong adalah 1 lebih besar dari prioritas terendah di sekitarnya. Semua piksel lainnya memiliki prioritas Integer.MAX_VALUE. Utas updater secara konstan memperbarui prioritas piksel. Setiap belokan, piksel N terendah dikeluarkan dari antrian prioritas.

Green Blob vs Red Swallower

Skor Blob = 1.680553372583887225

Skor 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

Green Swallower vs. Red Blob

Skor Blob = 1.6852943642218457375

Skor 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 First Blob

Skor Swallower = 157.0749775233111925

Skor Kedalaman Gumpalan Pertama = 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 First Blob

Skor Swallower = 154.3368355651281075

Skor Kedalaman Gumpalan Pertama = 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:

Skor Blob = 6.347962032393275525

Skor Kedalaman First Blob = 27.34842554331698275

Skor 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

Ini adalah hakim Sam Yonnou dengan beberapa perubahan sehingga Anda menentukan file dan perintah secara terpisah:

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