Bitwa o kolory


33

GRATULACJE dla @kuroineko za najlepsze wejście i wygranie 200 nagród od @TheBestOne (doskonałe sportowe!).

Napisz program, który pokoloruje jak najwięcej obrazu, zanim zrobią to programy przeciwne.

Zasady w skrócie

  • Twój program otrzyma obraz, kolor i liczbę całkowitą N.
  • Do każdej kolejki są wysyłane aktualizacje pikseli przez inne programy i pytane o twoje N aktualizacji.
  • Możesz zaktualizować dowolny biały piksel znajdujący się obok piksela twojego koloru.
  • Program, który dodał najwięcej pikseli, wygrywa.

Szczegółowe zasady

Twój program otrzyma nazwę pliku obrazu PNG, kolor domowy i liczbę N. Liczba N to maksymalna liczba pikseli, jaką Twój program może pokolorować za każdym razem.

Przykład: MyProg arena.png (255,0,0) 30

Obrazem wejściowym będzie prostokąt o bokach o długości od 20 do 1000 pikseli. Będzie się składał z czarnych, białych i kolorowych pikseli. Twój program może wybrać sekwencję białych pikseli do pokolorowania jako własne, pod warunkiem, że każdy nowy piksel musi mieć co najmniej jeden z czterech sąsiadujących pikseli tego samego koloru. Obraz będzie początkowo miał co najmniej jeden piksel twojego koloru. Może także mieć piksele kolorów, do których żaden program nie jest przypisany. Kanał alfa nie jest używany.

Twoim celem jest blokowanie przeciwników i zapisywanie kolorów w jak największej liczbie pikseli.

Za każdym razem twój program akceptuje 1 lub więcej linii komunikatów na STDIN i zapisuje linię składającą się ze współrzędnych pikseli na STDOUT. Pamiętaj, aby przypisywać STDOUT jako niebuforowane lub opróżniać bufor STDOUT co turę.

Kolejność graczy nazywanych w każdej turze zostanie losowo przydzielona. Oznacza to, że przeciwnik (lub twój program) może mieć 2 tury z rzędu.

Twój program otrzyma colour (N,N,N) chose X,Y X,Y ... X,Ywiadomości informacyjne opisujące piksele wypełnione przez programy odtwarzacza. Jeśli gracz nie wykona żadnych ruchów lub nie wykona prawidłowych ruchów, nie zostanie wysłana wiadomość o ruchach tego gracza. Twój program otrzyma również wiadomość o twoich zaakceptowanych ruchach (jeśli podałeś przynajmniej jeden prawidłowy ruch). Piksel 0,0 znajduje się w lewym górnym rogu obrazu.

Po otrzymaniu pick pixelsTwój program wyświetli X,Y X,Y ... X,Ydo N pikseli (dozwolony jest pusty ciąg składający się tylko z „\ n”). Piksele muszą być w kolejności kreślenia. Jeśli piksel jest nieprawidłowy, zostanie zignorowany i nie będzie w raporcie dla graczy. Twój program ma 2 sekundy na zainicjowanie po uruchomieniu, ale tylko 0,1 sekundy na odpowiedź z każdą kolejką, w przeciwnym razie przegapi tę kolejkę. Aktualizacja piksela wysłana po 0,1 sekundy zarejestruje błąd. Po 5 usterkach program zostanie zawieszony i nie będą wysyłane aktualizacje ani pick pixelsżądania.

Gdy program oceniający otrzyma pusty lub nieprawidłowy wybór pikseli z każdego niezawieszonego programu odtwarzacza, obraz zostanie uznany za kompletny, a do programów zostanie wysłany komunikat „wyjdź”. Programy muszą zakończyć się po otrzymaniu „exit”.

Punktacja

Sędzia zdobędzie punkty po skompletowaniu obrazu. Twój wynik będzie liczbą zaktualizowanych pikseli podzieloną przez średnią liczbę przechwyconych pikseli w tej rundzie, wyrażoną w procentach.

Liczba pikseli dodanych do obrazu przez odtwarzacz wynosi A. Całkowita liczba pikseli dodanych przez wszystkie odtwarzacze P to T. avg = T/P score = 100*A/avg

Publikowanie wyników

Podany jest referencyjny przeciwnik „Kropla”. Dla każdej odpowiedzi nazwij swojego bota nazwą, językiem i wynikiem (średnio areny od 1 do 4) w stosunku do przeciwnika referencyjnego. Przydałby się również obraz lub animacja jednej z twoich bitew. Zwycięzcą jest program z najwyższym wynikiem w stosunku do referencyjnego bota.

Jeśli Blob okaże się zbyt łatwy do pokonania, mogę dodać drugą rundę z silniejszym przeciwnikiem referencyjnym.

Możesz także chcieć eksperymentować z 4 lub więcej programami dla graczy. Możesz także przetestować swojego bota na innych botach opublikowanych jako odpowiedzi.

Sędzia

Program sędziego wymaga wspólnej biblioteki Python Imaging Library (PIL) i powinien być łatwy do zainstalowania z poziomu menedżera pakietów systemu operacyjnego Linux. Mam raport, że PIL nie działa z 64-bitowym Pythonem w systemie Windows 7, więc przed rozpoczęciem tego wyzwania sprawdź, czy PIL będzie działał (zaktualizowano 29.01.2015).

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

Przykład konfiguracji - 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 - referencyjny przeciwnik

# 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

arena1.png

Arena 2

arena2.png

Arena 3

arena3.png

Arena 4

arena4.png

Przykładowa bitwa - Blob kontra Blob

Ta bitwa miała przewidywalny wynik:

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

Przykładowa bitwa


Jesteś pewien, że to nie powinien być [król wzgórza]?
Justin

Myślałem o tym. Boty nie walczą ze sobą bezpośrednio. Walczą z referencyjnym botem. Czy to wyklucza KOTH?
Logic Knight

Tak, ponieważ to nie jest KOTH, pytałem, czy jesteś pewien, że chcesz walczyć z botem referencyjnym, a nie ze sobą.
Justin

1
@TheBestOne, Dodano obsługę Java. Jednak niesprawdzone z programem Java. Daj mi znać, jeśli to nie zadziała.
Logic Knight

1
10 pikseli jest ułożonych w kolejności, więc późniejsze piksele mogą polegać na poprzednich rozmieszczeniach pikseli. Mogą się nawzajem budować, jak sugerujesz.
Logic Knight

Odpowiedzi:


17

ColorFighter - C ++ - zjada kilka połykaczy na śniadanie

EDYTOWAĆ

  • wyczyścił kod
  • dodano prostą, ale skuteczną optymalizację
  • dodano kilka animacji GIF

Boże, nienawidzę węży (udawaj, że to pająki, Indy)

Właściwie uwielbiam Python. Chciałbym być mniej leniwym chłopcem i zacząłem się go właściwie uczyć, to wszystko.

Biorąc to wszystko pod uwagę, musiałem zmagać się z 64-bitową wersją tego węża, aby uruchomić Sędziego. Zmuszenie PIL do pracy z 64-bitową wersją Pythona pod Win7 wymaga więcej cierpliwości, niż byłem gotów poświęcić temu wyzwaniu, więc ostatecznie (boleśnie) przerzuciłem się na wersję Win32.

Ponadto, sędzia ma tendencję do poważnych awarii, gdy bot jest zbyt wolny, aby zareagować.
Nie znając języka Python, nie naprawiłem tego, ale ma to związek z przeczytaniem pustej odpowiedzi po upływie limitu czasu na stdin.

Niewielkim ulepszeniem byłoby umieszczenie wyjścia stderr w pliku dla każdego bota. Ułatwi to śledzenie debugowania pośmiertnego.

Oprócz tych drobnych problemów uznałem, że Sędzia jest bardzo prosty i przyjemny w użyciu.
Uznanie za kolejne pomysłowe i zabawne wyzwanie.

Kod

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

Budowanie pliku wykonywalnego

Użyłem LODEpng.cpp i LODEpng.h do odczytu obrazów png.
O najprostszym sposobie, w jaki udało mi się nauczyć tego opóźnionego języka C ++, jak czytać obrazki bez konieczności budowania kilku bibliotek.
Wystarczy skompilować i połączyć LODEpng.cpp wraz z głównym, a Bob jest wujem.

Kompilowałem z MSVC2013, ale ponieważ użyłem tylko kilku podstawowych kontenerów STL (deque i wektory), może działać z gcc (jeśli masz szczęście).
Jeśli nie, to może spróbować kompilacji MinGW, ale szczerze mówiąc jestem zmęczony kwestii przenośności C ++.

Zrobiłem całkiem sporo przenośnego C / C ++ w moich czasach (na egzotycznych kompilatorach dla różnych procesorów od 8 do 32 bitów, a także SunOS, Windows od 3.11 do Vista i Linux od niemowlęctwa po zebrę grającą Ubuntu itp., Więc myślę Mam całkiem niezłe pojęcie o tym, co oznacza przenośność), ale w tamtym czasie nie wymagało to zapamiętywania (ani odkrywania) niezliczonych rozbieżności między interpretacjami GNU i Microsoft dotyczących tajemniczych i rozdętych specyfikacji potwora STL.

Wyniki przeciwko Swallower

arena1 arena2 arena3 arena4

Jak to działa

Zasadniczo jest to prosta ścieżka wypełniania brute-force.

Granica koloru gracza (tj. Piksele, które mają co najmniej jednego białego sąsiada) służy jako ziarno do wykonania klasycznego algorytmu zalewania odległości.

Kiedy punkt osiąga stopień koloru wroga, obliczana jest ścieżka wsteczna w celu wytworzenia ciągu pikseli zbliżającego się do najbliższego punktu wroga.

Proces ten powtarza się, aż zgromadzi się wystarczającą liczbę punktów do uzyskania żądanej długości.

Powtarzanie jest nieprzyzwoicie drogie, szczególnie podczas walki w pobliżu wroga.
Za każdym razem, gdy zostanie znaleziony ciąg pikseli prowadzących od granicy do piksela wroga (i potrzebujemy więcej punktów, aby ukończyć odpowiedź), wypełnienie powodziowe jest powtarzane od początku, a nowa ścieżka jest dodawana do granicy. Oznacza to, że możesz uzyskać 5 lub więcej wypełnień, aby uzyskać odpowiedź 10 pikseli.

Jeśli nie ma już więcej pikseli wroga, wybierani są dowolni sąsiedzi pikseli nadgranicznych.
Algorytm przekształca się w raczej nieefektywne wypełnienie powodziowe, ale dzieje się tak dopiero po ustaleniu wyniku gry (tj. Nie ma już neutralnego terytorium do walki).
Zoptymalizowałem go, aby sędzia nie spędzał wieków na wypełnianiu mapy po rozstrzygnięciu zawodów. W obecnym stanie czas wykonania jest pomijalny w porównaniu z samym sędzią.

Ponieważ kolory wroga nie są znane na początku, początkowy obraz areny jest przechowywany w celu skopiowania obszarów początkowych wroga, gdy wykonuje on pierwszy ruch.
Jeśli kod zostanie odtworzony jako pierwszy, wypełni tylko kilka dowolnych pikseli.

To sprawia, że ​​algorytm jest w stanie walczyć z dowolną liczbą przeciwników, a nawet potencjalnie nowymi przeciwnikami przybywającymi w przypadkowym momencie lub kolorami pojawiającymi się bez obszaru początkowego (choć nie ma to praktycznie żadnego praktycznego zastosowania).

Obsługa wroga w oparciu o kolor za kolorem pozwoliłaby również na współpracę dwóch instancji bota (użycie współrzędnych pikseli w celu przekazania tajnego znaku rozpoznawczego).
Brzmi fajnie, prawdopodobnie spróbuję :).

Ścieżka wymagająca dużej ilości obliczeń jest wykonywana, gdy tylko nowe dane są dostępne (po powiadomieniu o przeniesieniu), a niektóre optymalizacje (aktualizacja granicy) są wykonywane tuż po udzieleniu odpowiedzi (aby wykonać jak najwięcej obliczeń podczas innych tur botów ).

Tutaj znowu mogą istnieć sposoby robienia bardziej subtelnych rzeczy, jeśli byłby więcej niż 1 przeciwnik (np. Przerwanie obliczeń, jeśli nowe dane staną się dostępne), ale w każdym razie nie widzę, gdzie potrzebna jest wielozadaniowość, dopóki algorytm jest zdolny do pracy przy pełnym obciążeniu.

Problemy z wydajnością

Wszystko to nie może działać bez szybkiego dostępu do danych (i większej mocy obliczeniowej niż cały program Appolo, tj. Przeciętnego komputera PC, gdy wykonuje się więcej niż opublikowanie kilku tweetów).

Szybkość zależy w dużej mierze od kompilatora. Zwykle GNU bije Microsoft o 30% margines (to magiczna liczba, którą zauważyłem w 3 innych wyzwaniach związanych z kodowaniem ścieżek), ale ten przebieg może się oczywiście różnić.

Kod w obecnym stanie z trudem powstrzymuje pot na arenie 4. Perfektor Windows zgłasza około 4 do 7% użycia procesora, więc powinien być w stanie poradzić sobie z mapą 1000x1000 w limicie czasu odpowiedzi 100ms.

W centrum każdego algorytmu ścieżkowania znajduje się FIFO (być może prowizoryczny, choć nie w tym przypadku), co z kolei wymaga szybkiej alokacji elementów.

Ponieważ OP obowiązkowo ustanowiło limit wielkości areny, zrobiłem matematykę i zobaczyłem, że ustalone struktury danych zwymiarowane na maksimum (tj. 1.000.000 pikseli) nie będą zużywać więcej niż kilkadziesiąt megabajtów, które przeciętny komputer je na śniadanie.
Rzeczywiście pod Win7 i skompilowany z MSVC 2013, kod zużywa około 14 Mb na arenie 4, podczas gdy dwa wątki Swallower zużywają ponad 20 Mb.

Zacząłem od kontenerów STL dla łatwiejszego prototypowania, ale STL sprawił, że kod był jeszcze mniej czytelny, ponieważ nie miałem ochoty tworzyć klasy, która zawierałaby wszystkie dane w celu ukrycia zaciemnienia (czy to z powodu mojej własnej niezdolności do poradzenie sobie z STL pozostawiono do uznania czytelnika).
Niezależnie od tego wynik był tak okropnie powolny, że początkowo myślałem, że przez pomyłkę buduję wersję debugującą.

Sądzę, że jest to częściowo spowodowane niewiarygodnie słabą implementacją STL Microsoftu (gdzie na przykład wektory i zestawy bitów wykonują kontrole graniczne lub inne operacje szyfrujące na operatorze [], co stanowi bezpośrednie naruszenie specyfikacji), a częściowo ze względu na konstrukcję STL samo.

Mógłbym poradzić sobie z okropnymi problemami ze składnią i przenośnością (tj. Microsoft vs GNU), gdyby występy były, ale z pewnością tak nie jest.

Na przykład dequejest z natury powolny, ponieważ tasuje wiele danych z ksiąg rachunkowych, czekając na okazję, aby zrobić super inteligentną zmianę rozmiaru, o którą nie obchodzi mnie to mniej.
Jasne, że mogłem zaimplementować niestandardowy alokator i inne niestandardowe bity szablonu, ale sam niestandardowy alokator kosztuje kilkaset wierszy kodu i lepszą część dnia na przetestowanie, co z dziesiątkami interfejsów, które musi zaimplementować, podczas gdy ręcznie robiona równoważna struktura ma około zero linii kodu (choć jest bardziej niebezpieczna, ale algorytm nie zadziałałby, gdybym nie wiedział - lub nie sądziłbym, że wiedziałem - co robię).

Więc ostatecznie trzymałem kontenery STL w niekrytycznych częściach kodu i zbudowałem własnego brutalnego alokatora i FIFO z dwoma tablicami z około 1970 roku i trzema niepodpisanymi skrótami.

Połknięcie połykacza

Jak potwierdził jego autor, nieregularne wzorce Jaskółki są spowodowane opóźnieniem między powiadomieniami o ruchach wroga i aktualizacjami z wątku.
Systemowy miernik wydajności wyraźnie pokazuje, że nici zużywające 100% procesora przez cały czas, a postrzępione wzory pojawiają się zwykle, gdy walka przenosi się na nowy obszar. Jest to również dość widoczne w przypadku animacji.

Prosta, ale skuteczna optymalizacja

Po obejrzeniu epickich pojedynków między Swallower a moim wojownikiem przypomniałem sobie stare powiedzenie z gry Go: broń z bliska, ale atakuj z daleka.

Jest w tym mądrość. Jeśli spróbujesz zbyt mocno trzymać się przeciwnika, zmarnujesz cenne ruchy, próbując zablokować każdą możliwą ścieżkę. Wręcz przeciwnie, jeśli pozostaniesz tylko o jeden piksel, prawdopodobnie unikniesz wypełniania małych luk, które zyskałyby bardzo niewiele, i użyjesz swoich ruchów, aby przeciwdziałać ważniejszym zagrożeniom.

Aby zrealizować ten pomysł, po prostu rozszerzyłem ruchy wroga (zaznaczając 4 sąsiadów każdego ruchu jako piksel wroga).
To zatrzymuje algorytm ścieżkowania jeden piksel od granicy wroga, pozwalając mojemu wojownikowi ominąć przeciwnika, nie dając się złapać w zbyt wiele pojedynków.

Możesz zobaczyć poprawę
(chociaż wszystkie przebiegi nie są tak udane, możesz zauważyć znacznie gładsze kontury):

przed po


1
Łał. Myślałem, że nic nie pokona Swallowera. Doskonałe rozwiązanie z doskonałym opisem. Pamiętam K&R C z dawnych dobrych czasów, ale potem C przeszedł na ciemną stronę. Myślę, że spodoba ci się Python .
Logic Knight

To była prawdziwa przyjemność podjąć wyzwanie, więc ... no cóż ... wyzwanie i zabawa. To pozwoliło mi przetestować ten mały klejnot w pełnej skali LODEpng, a wyniki są tak obiecujące, że mogę ponownie odwiedzić png racera, testując jeszcze raz moją relację miłości / nienawiści z tym niesławnym post-przyrostowym C.

1
Połykacz jest czasami trochę nieregularny, aby dotrzymać limitu czasu. Po to częściowo służy wielowątkowość. Dobra robota!! Myślę, że
podwoję

1
Poduszka ma pliki do pobrania dla 64-bitów. Można go używać tak jak PIL.
TheNumberOne

@TheBestOne Tak myślałem. Mój brutalny malarz wykorzystuje chwile, w których twój połykacz gryzie nieaktualne dane :). Jeśli chodzi o PIL, pobrałem wszystkie wersje Amd64 PIL i Pillow dostępne w sieci WWW, ale nie działałyby one z moim głównym 63,5-bitowym Pythonem, który prawdopodobnie był bootlegiem i / lub nieaktualną wersją. W każdym razie port Win32 działa równie dobrze, a jeśli pewnego dnia będę potrzebować czegoś szybciej, będę musiał przejść na PyPy.

21

Najpierw kropelka kontra kropelka

Język = Python (3.2)

Wynik = 111,475388276 153,34210035

Aktualizacja: Teraz używamy niestandardowej Setklasy, aby uzyskać pop()metodę generowania pewnego rodzaju wzoru siatki, który drastycznie poprawia obszar pokryty na początku, odcinając duże części obrazu od wroga. Uwaga: używam siatki 12 x 12 do tego, która z losowej próbki rozmiarów siatki wydawała się dawać najlepsze wyniki dla areny3 (tej, która uzyskała najgorszy wynik przed aktualizacją), jednak jest bardzo prawdopodobne, że bardziej optymalna rozmiar siatki istnieje dla danego wyboru aren.

Poszedłem do prostej modyfikacji bota referencyjnego, aby sprzyjał on wybieraniu możliwych do wykonania punktów, które są otoczone jak najmniejszą liczbą punktów o tym samym kolorze. Ulepszenie może polegać na tym, że sprzyja również wybieraniu wykonalnych punktów, które są otoczone jak największą liczbą punktów w kolorze wroga.

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

Oryginalny sędzia został nieznacznie zmodyfikowany do pracy z Pythonem 3.2 (i do dodania prymitywnej funkcji logowania do botów + okresowego zapisywania obrazu areny w celu wykonania animacji):

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

Wyniki areny są następujące. Bot dfblob otrzymał czerwony kolor dla wszystkich aren.

Arena 1:

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

1

Arena 2:

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

2)

Arena 3:

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

3)

Arena 4:

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

4


Twój algorytm jest taki sam, jak ten, który zaimplementowałem w silniejszym bracie Bloba, Boxerze. Chciałem użyć Boxera, jeśli Blob nie był wystarczającym wyzwaniem. Bardzo ładne animacje.
Logic Knight

Aby użyć PIL w pythonie 3, czy używasz poduszki ?
trichoplax

@githubphagocyte Tak
SamYonnou

Jakiego oprogramowania użyłeś do stworzenia tych GIF-ów?
TheNumberOne

1
@TheBestOne Użyłem ImageMagick konkretnie polecenia, convert -delay 5 -loop 0 result*.png animated.gifchociaż niektóre gify musiały zostać później ręcznie odcięte, aby można je tutaj przesłać
SamYonnou

18

Jaskółka

Język = Java

Wynik = 162,3289512601408075 169,4020975612382575

Szuka wrogów i otacza. Być może będziesz musiał wydłużyć termin. Można by trochę poprawić. Czasami drukuje nieprawidłowe piksele.

Aktualizacja: Otacza się znacznie szybciej. Używa innego wątku do aktualizacji priorytetów. Zawsze wraca w ciągu 1 sekundy. Wynik powinien być niemożliwy do pokonania bez zwiększenia 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;
    }

}

Jak to działa:

Ten bot utrzymuje priorytetową kolejkę pikseli, którą może dodać. Priorytet wrogiego piksela wynosi 0. Priorytet pustego piksela jest o 1 większy niż najniższy priorytet wokół niego. Wszystkie pozostałe piksele mają priorytet Integer.MAX_VALUE. Wątek aktualizujący stale aktualizuje priorytety pikseli. Za każdym razem najniższe N ​​pikseli jest usuwane z kolejki priorytetowej.

Green Blob vs Red Swallower

Wynik obiektu Blob = 1,680553372583887225

Wynik jaskółki = 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

wprowadź opis zdjęcia tutaj

Arena 2:

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

wprowadź opis zdjęcia tutaj

Arena 3:

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

wprowadź opis zdjęcia tutaj

Arena 4:

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

wprowadź opis zdjęcia tutaj

Zielona jaskółka kontra czerwona kropelka

Wynik obiektu Blob = 1,6852943642218457375

Wynik jaskółki = 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

wprowadź opis zdjęcia tutaj

Arena 2:

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

wprowadź opis zdjęcia tutaj

Arena 3:

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

wprowadź opis zdjęcia tutaj

Arena 4:

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

wprowadź opis zdjęcia tutaj

Czerwona kropla przeciwko pierwszej kropli zielonej głębi

Wynik połykacza = 157,0749775233111925

Wynik pierwszej kropli głębokości = 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

wprowadź opis zdjęcia tutaj

Arena 2:

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

wprowadź opis zdjęcia tutaj

Arena 3:

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

wprowadź opis zdjęcia tutaj

Arena 4:

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

wprowadź opis zdjęcia tutaj

Zielona kropla kontra pierwsza kropla o czerwonej głębi

Wynik połykacza = 154,3368355651281075

Wynik pierwszej kropli głębokości = 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

wprowadź opis zdjęcia tutaj

Arena 2:

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

wprowadź opis zdjęcia tutaj

Arena 3:

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

wprowadź opis zdjęcia tutaj

Arena 4:

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

wprowadź opis zdjęcia tutaj

Green Blob vs Red Depth First Blob vs Blue Swallower:

Wynik Blob = 6,347962032393275525

Wynik pierwszej kropli głębokości = 27,344842554331698275

Wynik jaskółki = 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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

Oto sędzia Sama Yonnou z kilkoma zmianami, aby osobno określić pliki i polecenie:

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

Przykład cfg:

BATTLE = 'Green DepthFirstBlob vs Red Swallower @ arena1'
MAXTURNS = 20000
PIXELBATCH = 10
INITTIME = 2.0
TIMELIMIT = .1
FAULTLIMIT = 5

imagename = 'arena1.png'

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

botspec = [
    (['DepthFirstBlob.py'], ['python', 'DepthFirstBlob.py']),
    (['Swallower.class','Swallower$Pixel.class'], ['java', 'Swallower']),
    ]

Uwaga: Każdy, kto zdoła przełknąć Jaskółkę, otrzyma nagrodę w wysokości 100 reputacji. Jeśli to się powiedzie, opublikuj poniższe komentarze.


2
@githubphagocyte Zgodnie z życzeniem.
TheNumberOne

1
Dobra robota ze zmianami sędziego. Oddzielne kopiowanie plików i poleceń to dobry pomysł, a rejestrowanie błędów było bardzo potrzebne.
Logic Knight

1
Jeśli miałeś na myśli MAXTURNS, możesz to zmienić. To nie jest częścią zasad. To po prostu powstrzymuje sędziego przed bieganiem na zawsze (ale myślę, że warunki zakończenia i tak temu zapobiegają).
Logic Knight

1
@githubphagocyte Naprawiono
TheNumberOne

1
Po obejrzeniu twoich animowanych bitew zacząłem zastanawiać się, jak wyglądałaby bitwa Swallower vs. Swallower. Czy jeden szybko złapałby się w pułapkę, czy byłaby to ciągła walka o dominację kosmosu?
Logic Knight

6

Losowo, język = java, wynik = 0,43012126100275

Ten program losowo umieszcza piksele na ekranie. Niektóre (jeśli nie wszystkie) piksele będą nieprawidłowe. Na marginesie, utworzenie szybszego programu powinno być trudne.

import javax.imageio.ImageIO;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;

public class Random {

    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    static int n;

    static int height;

    static int width;

    public static void main(String[] args) throws Exception{
        BufferedImage image = ImageIO.read(new File(args[0]));
        height = image.getHeight();
        width = image.getWidth();
        n = Integer.parseInt(args[2]);
        while (true){
            String input = in.readLine();
            if (input.equals("exit")){
                return;
            }
            if (!input.equals("pick pixels")){
                continue;
            }
            for (int i = 0; i < n; i++){
                System.out.print((int) (Math.random() * width) + ",");
                System.out.print((int) (Math.random() * height) + " ");
            }
            System.out.println();
        }
    }
}

Arena 1:

1

Arena 2:

2)

Arena 3:

3)

Arena 4:

4


7
Widzę, że nie wpadłeś w pułapkę przedwczesnej optymalizacji .
Logic Knight
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.