Dada uma lista de pontos, encontre o caminho mais curto que visite todos os pontos e retorne ao ponto de partida.

O Problema do Vendedor Viajante é bem conhecido no campo da ciência da computação, pois há muitas maneiras de calcular / aproximar esse problema. Foi resolvido para grupos muito grandes de pontos, mas alguns dos maiores levam muitos anos de CPU para serem concluídos.

Não se queime pela batata.

Hot Potato é um jogo em que mais de 2 jogadores passam uma "batata" em círculo enquanto a música toca. O objetivo é passá-lo para o próximo jogador rapidamente. Se você estiver segurando a batata quando a música parar, estará fora.

O objetivo do vendedor de batata quente é:

Dado um conjunto de 100 pontos únicos , retorne esses pontos em uma ordem melhor ( distância total menor, conforme definido mais abaixo ). Isso "passará" o problema para o próximo jogador. Eles precisam aprimorá-lo e passá-lo para o próximo, etc. Se um jogador não puder melhorá-lo, eles estarão fora e o jogo continuará até que um jogador seja deixado.

Para evitar que isso seja uma competição de "força bruta-por-um-caminho", existem as seguintes estipulações:

• Você não pode demorar mais de um minuto para passar a batata. Se você não encontrou e aprovou uma solução mais curta quando termina um minuto, está fora.

• Você não pode alterar a posição de mais de 25 pontos. Para ser exato, os >= 75pontos devem estar na mesma posição em que você os recebeu. Não importa quais você decide mudar, apenas a quantidade que você muda.

Quando resta apenas um jogador, ele é o vencedor do jogo e recebe um ponto. Um torneio consiste em 5*njogos, onde né o número de jogadores. A cada jogo, o jogador inicial será girado e a ordem restante do jogador será embaralhada . O jogador com mais pontos no final é o vencedor do torneio. Se o torneio terminar empatado em primeiro lugar, um novo torneio será disputado apenas com esses competidores. Isso continuará até que não haja empate.

O jogador inicial de cada jogo receberá um conjunto de pontos selecionados pseudo-aleatoriamente em nenhuma ordem específica.

Os pontos são definidos como um par de x,ycoordenadas inteiras em uma grade cartesiana. A distância é medida usando Manhattan distância , |x1-x2| + |y1-y2|. Todas as coordenadas estarão no [0..199]intervalo.

Entrada

A entrada é fornecida com um argumento de cadeia única. Ele consistirá em 201 inteiros separados por vírgula, representando o número de jogadores atuais ( m) e 100 pontos:

m,x0,y0,x1,y1,x2,y2,...,x99,y99

A ordem desses pontos é o caminho atual. A distância total é obtida adicionando a distância de cada ponto ao próximo ( dist(0,1) + dist(1,2) + ... + dist(99,0)). Não se esqueça de voltar ao início ao calcular a distância total!

Note que mé não o número de jogadores que iniciaram o jogo, é o número que ainda está dentro

Saída

A saída é dada da mesma maneira que a entrada, menos m; uma única sequência contendo números inteiros separados por vírgula, representando os pontos em sua nova ordem.

x0,y0,x1,y1,x2,y2,...,x99,y99

O programa de controle aguardará a saída por apenas um minuto. Quando a saída é recebida, ele verifica se:

• a saída é bem formada
• a saída consiste em apenas e todos os 100 pontos presentes na entrada
• >=75 pontos estão em suas posições originais
• o comprimento do caminho é menor que o caminho anterior

Se alguma dessas verificações falhar (ou não houver saída), você estará fora e o jogo prosseguirá para o próximo jogador.

Programa de Controle

Você pode encontrar o programa de controle neste link . O programa de controle em si é determinístico e é lançado com uma semente fictícia de1 . A semente usada durante a pontuação será diferente, portanto, não se preocupe em tentar analisar a lista de pontos / ordem dos turnos que ela cospe.

A classe principal é Tourney. Se isso acontecer, será realizado um torneio completo, com os participantes como argumentos. Ele cuspiu o vencedor de cada jogo e uma contagem no final. Um torneio de amostra com dois SwapBots é semelhante a:

Starting tournament with seed 1

(0) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 3
(0) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 4
(1) SwapBot wins a game! Current score: 5
(1) SwapBot wins a game! Current score: 6
(1) SwapBot wins a game! Current score: 7
(1) SwapBot wins a game! Current score: 8

Final Results:

Wins        Contestant
2       (0) SwapBot
8       (1) SwapBot

Se você quiser testar apenas um jogo de cada vez, poderá executar a Gameaula. Isso executará um jogo com os jogadores na ordem dada como argumento. Por padrão, ele também imprimirá uma reprodução por reprodução, mostrando o player atual e o comprimento do caminho.

Também estão incluídos alguns jogadores de teste: SwapBot, BlockPermuter, e TwoSwapBot. Os dois primeiros não serão incluídos nas execuções de pontuação; portanto, fique à vontade para usá-los e abusar deles durante o teste. TwoSwapBot vai incluído no julgamento, e ele não é desleixado, então traga seu A-game.

Miscelânea

• Você não pode salvar informações de estado e cada turno é uma execução separada do seu programa. A única informação que você receberá a cada turno é o conjunto de pontos.

• Você não pode usar recursos externos. Isso inclui chamadas de rede e acesso a arquivos.

• Você não pode usar as funções da biblioteca projetadas para resolver / ajudar com o problema do TSP ou suas variantes.

• Você não pode manipular ou interferir com outros jogadores de forma alguma.

• Você não pode manipular ou interferir no programa de controle ou em quaisquer classes ou arquivos incluídos de forma alguma.

• Multi-threading é permitido.

• Um envio por usuário. Se você enviar mais de uma entrada, inserirei apenas a primeira. Se você deseja alterar seu envio, edite / exclua o original.

• O torneio será executado no Ubuntu 13.04, em um computador com um CPU i7-3770K e 16GB de RAM. Não será executado em uma VM. Qualquer coisa que eu considere maliciosa desqualificará imediatamente a entrada atual e futura que você enviar.

• Todas as entradas devem ser executáveis ​​na linha de comando com free ( como na cerveja ). Se eu tiver problemas para compilar / executar sua entrada, solicitarei ajuda nos comentários. Se você não responder ou se eu não conseguir colocá-lo em execução, ele será desqualificado.

Resultados (22 de maio de 2014)

Novos resultados estão chegando! O UntangleBot venceu bastante a concorrência. O TwoSwapBot conseguiu sete vitórias e o SANNbot também obteve uma vitória. Aqui está um placar e um link para a saída bruta :

Wins        Contestant
22      (2) ./UntangleBot
7       (0) TwoSwapBot
1       (5) SANNbot.R
0       (1) BozoBot
0       (3) Threader
0       (4) DivideAndConquer

Como está agora , o UntangleBot ganhou a marca de seleção. Não deixe que isso o desanime de participar, pois eu vou disputar o torneio à medida que mais competidores aparecerem e mudar a resposta aceita de acordo.

UntangleBot (anteriormente NiceBot)

Um bot C ++ 11 que usa duas estratégias.
Inicialmente, ele tentará "desembaraçar" o caminho, se possível, detectando interseções entre caminhos com menos de 25 pontos (uma vez que desembaraçar implica modificar todos os pontos intermediários).
Se a primeira estratégia falhar, alterna aleatoriamente pontos para encontrar distâncias melhores até que um caminho melhor seja encontrado.

Esse bot vence o TwoSwapBot de forma consistente com uma proporção aproximada de cinco vitórias por uma perda nos meus torneios de teste.

// g++ -std=c++11 -O3 -o UntangleBot UntangleBot.cpp
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <sstream>

const int NPOINTS = 100;

struct Point {
    int x, y;

    Point():x(0),y(0) {}    
    Point(int x, int y):x(x),y(y) {}

    int distance_to(const Point & pt) const {
        return std::abs(x - pt.x) + std::abs(y - pt.y);
    }
};

std::ostream & operator<<(std::ostream & out, const Point & point) {
    return out << point.x << ',' << point.y;
}

int total_distance(const Point points[NPOINTS]) {
    int distance = 0;
    for (int i = 0; i < NPOINTS; ++i) {
        distance += points[i].distance_to(points[(i+1)%NPOINTS]);
    }
    return distance;
}

bool intersects(const Point & p1, const Point & p2, const Point & p3, const Point & p4) {
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p2.x - p1.x;
    s1_y = p2.y - p1.y;
    s2_x = p4.x - p3.x;
    s2_y = p4.y - p3.y;

    double s, t;
    s = (-s1_y * (p1.x - p3.x) + s1_x * (p1.y - p3.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p1.y - p3.y) - s2_y * (p1.x - p3.x)) / (-s2_x * s1_y + s1_x * s2_y);

    return s >= 0 && s <= 1 && t >= 0 && t <= 1;
}

int main(int argc, char ** argv) {
    Point points[NPOINTS];

    using Clock = std::chrono::system_clock;
    const Clock::time_point start_time = Clock::now();

    // initialize points
    if (argc < 2) {
        std::cerr << "Point list is missing" << std::endl;
        return 1;
    }
    std::stringstream in(argv[1]);
    int players;
    char v;
    in >> players >> v;
    for (int i = 0; i < NPOINTS; ++i) {
        in >> points[i].x >> v >> points[i].y >> v;
    }

    int original_distance = total_distance(points);

    // detect intersection between any 4 points
    for (int i = 0; i < NPOINTS; ++i) {
        for (int j = i+1; j < NPOINTS; ++j) {
            Point & p1 = points[i];
            Point & p2 = points[(i+1)%NPOINTS];
            Point & p3 = points[j];
            Point & p4 = points[(j+1)%NPOINTS];

            // points must all be distinct
            if (p1.distance_to(p3) == 0 || p1.distance_to(p4) == 0 || p2.distance_to(p3) == 0 || p2.distance_to(p4) == 0) {
                continue;
            }

            // do they intersect ?
            if (!intersects(p1, p2, p3, p4)) {
                continue;
            }

            // can modify less than 25 points ?
            if (std::abs(j-i) > 25) {
                continue;
            }

            // swap points
            for (int m = 0; m < std::abs(j-i)/2; ++m) {
                if (i+1+m != j-m) {
                    std::swap(points[i+1+m], points[j-m]);
                    //std::cerr << "untangle " << i+1+m << " <=> " << j-m << '\n';
                }
            }

            int new_distance = total_distance(points);
            if (new_distance < original_distance) {
                std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                std::cout << points[NPOINTS-1];
                return 0;
            }
            else {
                // swap points back
                for (int m = 0; m < std::abs(j-i)/2; m++) {
                    if (i+1+m != j-m) {
                        std::swap(points[i+1+m], points[j-m]);
                    }
                }
            }
        }
    }

    // more traditional approach if the first fails
    std::mt19937 rng(std::chrono::duration_cast<std::chrono::seconds>(start_time.time_since_epoch()).count());
    std::uniform_int_distribution<> distr(0, NPOINTS-1);
    while (true) {
        // try all possible swaps from a random permutation
        int p1 = distr(rng);
        int p2 = distr(rng);
        std::swap(points[p1], points[p2]);

        for (int i = 0; i < NPOINTS; ++i) {
            for (int j = i+1; j < NPOINTS; ++j) {
                std::swap(points[i], points[j]);
                if (total_distance(points) < original_distance) {
                    std::copy(std::begin(points), std::end(points)-1, std::ostream_iterator<Point>(std::cout, ","));
                    std::cout << points[NPOINTS-1];
                    return 0;
                }
                else {
                    std::swap(points[i], points[j]);
                }
            }
        }

        // they didn't yield a shorter path, swap the points back and try again
        std::swap(points[p1], points[p2]);
    }
    return 0;
}

SANNbot

(um bot de recozimento simulado em R )

Deve ser chamado com Rscript SANNbot.R.

input <- strsplit(commandArgs(TRUE),split=",")[[1]]
n <- as.integer(input[1])                            # Number of players
init_s <- s <- matrix(as.integer(input[-1]),ncol=2,byrow=TRUE) # Sequence of points
totdist <- function(s){                              # Distance function
    d <- 0
    for(i in 1:99){d <- d + (abs(s[i,1]-s[i+1,1])+abs(s[i,2]-s[i+1,2]))}
    d
    }
gr <- function(s){                                   # Permutation function
    changepoints <- sample(1:100,size=2, replace=FALSE)
    tmp <- s[changepoints[1],]
    s[changepoints[1],] <- s[changepoints[2],]
    s[changepoints[2],] <- tmp
    s
    }
d <- init_d <- totdist(s)                            # Initial distance
k <- 1                                               # Number of iterations
v <- 0
t <- n*(init_d/12000)                                 # Temperature
repeat{
    si <- gr(s)                                      # New sequence
    di <- totdist(si)                                # New distance
    dd <- di - d                                     # Difference of distances
    if(dd <= 0 | runif(1) < exp(-dd/t)){             # Allow small uphill changes
        d <- di
        s <- si
        v <- v+2
        }
    k <- k+1
    if(k > 10000){break}
    if(d > init_d & v>20){s <- init_s; d <- init_d; v <- 0}
    if(v>23){break}
}
cat(paste(apply(s,1,paste,collapse=","),collapse=","))

A idéia é relativamente simples: cada turno é um "passo de resfriamento" de um recozimento simulado com o número de jogadores ainda no jogo como "temperatura" (modificado pela distância atual acima de 12000, ou seja, aproximadamente a distância inicial). A única diferença com um recozimento simulado adequado é que eu verifiquei que não permuto mais de 25 elementos e se usei 20 movimentos, mas a sequência resultante vale mais que a inicial, e então recomeça.

BozoBot

Utiliza a lógica complexa por trás do Bozosort para encontrar um caminho melhor. Se parece com isso.

• Troque pontos aleatórios
• Se melhorássemos
  • Retornar a resposta
• De outra forma
  • Tente novamente

O BozoBot agora foi aprimorado com o Multithreading ! Agora quatro lacaios fazem malabarismos sem rumo, até encontrar uma melhoria. O primeiro a encontrar uma solução recebe um cookie!

Aparentemente, falhei no multithreading.

import java.util.Random;
public class BozoBot {
    public static String[] input;
    public static void main(String[] args) {
        input = args;
        for(int i = 0; i < 4; i++) new Minion().run();
    }
}

class Minion implements Runnable {
    public static boolean completed = false;
    public static synchronized void output(int[] x, int[] y) {
        if(!completed) {
            completed = true;
            String result = x[0]+","+y[0];
            for (int i = 1; i < 100; i++)
                result+=","+x[i]+","+y[i];
            System.out.print(result);
            // receiveCookie(); // Commented out to save money
        }
    }
    public void run() {
        String[] args = BozoBot.input[0].split(",");
        int[] x = new int[100];
        int[] y = new int[100];
        for (int i = 1; i < 201; i+=2) {
            x[(i-1)/2] = Integer.parseInt(args[i]);
            y[i/2] = Integer.parseInt(args[i+1]);
        }
        int startDistance = 0;
        for (int i = 1; i < 100; i++)
            startDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
        int r1, r2, r3, r4, tX, tY, newDistance;
        Random gen = new java.util.Random();
        while (true) {
            r1 = gen.nextInt(100);
            r2 = gen.nextInt(100);
            r3 = gen.nextInt(100);
            r4 = gen.nextInt(100);
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
            newDistance = 0;
            for (int i=1; i < 100; i++)
                newDistance += Math.abs(x[i-1]-x[i]) + Math.abs(y[i-1]-y[i]);
            if(newDistance < startDistance)
                break;
            tX = x[r1];
            x[r1] = x[r2];
            x[r2] = tX;
            tY = y[r1];
            y[r1] = y[r2];
            y[r2] = tY;
            tX = x[r3];
            x[r3] = x[r4];
            x[r4] = tX;
            tY = y[r3];
            y[r3] = y[r4];
            y[r4] = tY;
        }
        output(x,y);
    }
}

TwoSwapBot

Uma atualização para SwapBot, esse cara verifica todos os swaps. Primeiro, ele verifica se alguma troca única reduzirá o caminho. Se isso acontecer, ele retornará imediatamente. Caso contrário, ele verifica cada uma para ver se outra troca a reduzirá. Caso contrário, ele simplesmente morre.

Enquanto o caminho ainda é semi-aleatório, ele normalmente retorna em cerca de 100ms. Se ele tiver que verificar cada 2-swap (aproximadamente 25M), leva cerca de 20 segundos.

No momento da apresentação, isso venceu todos os outros concorrentes nas rodadas de teste.

public class TwoSwapBot {

    static int numPoints = 100;

    String run(String input){
        String[] tokens = input.split(",");
        if(tokens.length < numPoints*2)
            return "bad input? nope. no way. bye.";

        Point[] points = new Point[numPoints];  
        for(int i=0;i<numPoints;i++)
            points[i] = new Point(Integer.valueOf(tokens[i*2+1]), Integer.valueOf(tokens[i*2+2]));
        int startDist = totalDistance(points);

        Point[][] swapped = new Point[(numPoints*(numPoints+1))/2][];       
        int idx = 0;
        for(int i=0;i<numPoints;i++){
            for(int j=i+1;j<numPoints;j++){
                Point[] test = copyPoints(points);
                swapPoints(test,i,j);
                int testDist = totalDistance(test);
                if( testDist < startDist)
                    return getPathString(test);
                else
                    swapped[idx++] = test;
            }
        }

        for(int i=0;i<idx;i++){
            for(int k=0;k<numPoints;k++){
                for(int l=k+1;l<numPoints;l++){
                    swapPoints(swapped[i],k,l);
                    if(totalDistance(swapped[i]) < startDist)
                        return getPathString(swapped[i]);
                    swapPoints(swapped[i],k,l);
                }
            }
        }
        return "well damn";
    }

    void swapPoints(Point[] in, int a, int b){
        Point tmp = in[a];
        in[a] = in[b];
        in[b] = tmp;
    }

    String getPathString(Point[] in){
        String path = "";
        for(int i=0;i<numPoints;i++)
            path += in[i].x + "," + in[i].y + ",";
        return path.substring(0,path.length()-1);
    }

    Point[] copyPoints(Point[] in){
        Point[] out = new Point[in.length];
        for(int i=0;i<out.length;i++)
            out[i] = new Point(in[i].x, in[i].y);
        return out;
    }

    static int totalDistance(Point[] in){
        int dist = 0;
        for(int i=0;i<numPoints-1;i++)
            dist += in[i].distance(in[i+1]);
        return dist + in[numPoints-1].distance(in[0]);
    }

    public static void main(String[] args) {
        if(args.length < 1)
            return;
        System.out.print(new TwoSwapBot().run(args[0]));
    }

    class Point{
        final int x; final int y;
        Point(int x, int y){this.x = x; this.y = y;}
        int distance(Point other){return Math.abs(x-other.x) + Math.abs(y-other.y);}
    }
}

Threader

Este bot

1. Divide os 100 pontos em 4 10 peças de 25 10 pontos
2. Inicia um thread para cada peça
3. No encadeamento, embaralhe aleatoriamente a matriz, mantendo o ponto inicial e final fixos
4. Se a distância da nova matriz for menor, mantenha-a
5. Após 59s, o thread principal coleta os resultados e os imprime

A idéia é encontrar a melhor melhoria no caminho, para que os outros bots falhem com sua lógica.

import java.util.Arrays;
import java.util.Collections;

public class Threader {
    public static final int THREAD_COUNT = 10;
    public static final int DOT_COUNT = 100;
    private final Dot[] startDots = new Dot[THREAD_COUNT];
    private final Dot[] endDots = new Dot[THREAD_COUNT];
    private final Dot[][] middleDots = new Dot[THREAD_COUNT][DOT_COUNT/THREAD_COUNT-2];
    private final Worker worker[] = new Worker[THREAD_COUNT];
    private final static long TIME = 59000; 

    public static void main(String[] args) {
        Threader threader = new Threader();
        //remove unnecessary player count to make calculation easier
        threader.letWorkersWork(args[0].replaceFirst("^[0-9]{1,3},", "").split(","));
    }

    public void letWorkersWork(String[] args) {
        readArgs(args);
        startWorkers();
        waitForWorkers();
        printOutput();
    }

    private void readArgs(String[] args) {
        final int magigNumber = DOT_COUNT*2/THREAD_COUNT;
        for (int i = 0; i < args.length; i += 2) {
            Dot dot = new Dot(Integer.parseInt(args[i]), Integer.parseInt(args[i + 1]));
            if (i % magigNumber == 0) {
                startDots[i / magigNumber] = dot;
            } else if (i % magigNumber == magigNumber - 2) {
                endDots[i / magigNumber] = dot;
            } else {
                middleDots[i / magigNumber][(i % magigNumber) / 2 - 1] = dot;
            }
        }
    }

    private void startWorkers() {
        for (int i = 0; i < THREAD_COUNT; i++) {
            worker[i] = new Worker(startDots[i], endDots[i], middleDots[i]);
            Thread thread = new Thread(worker[i]);
            thread.setDaemon(true);
            thread.start();
        }
    }

    private void waitForWorkers() {
        try {
            Thread.sleep(TIME);
        } catch (InterruptedException e) {
        }
    }

    private void printOutput() {
        //get results
        Worker.stopWriting = true;
        int workerOfTheYear = 0;
        int bestDiff = 0;
        for (int i = 0; i < THREAD_COUNT; i++) {
            if (worker[i].diff() > bestDiff) {
                bestDiff = worker[i].diff();
                workerOfTheYear = i;
            }
        }
        //build output
        StringBuilder result = new StringBuilder(1000);
        for (int i = 0; i < THREAD_COUNT; i++) {
            result.append(startDots[i]);
            Dot middle[] = middleDots[i];
            if (i == workerOfTheYear) {
                middle = worker[i].bestMiddle;
            }
            for (int j = 0; j < middle.length; j++) {
                result.append(middle[j]);
            }
            result.append(endDots[i]);
        }
        result.replace(0, 1, ""); //replace first comma
        System.out.print(result);
    }

}

class Worker implements Runnable {

    public Dot start;
    public Dot end;
    private Dot[] middle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public Dot[] bestMiddle = new Dot[Threader.DOT_COUNT/Threader.THREAD_COUNT-2];
    public static boolean stopWriting = false;
    private int bestDist = Integer.MAX_VALUE;
    private final int startDist;

    public Worker(Dot start, Dot end, Dot[] middle) {
        this.start = start;
        this.end = end;
        System.arraycopy(middle, 0, this.middle, 0, middle.length);
        System.arraycopy(middle, 0, this.bestMiddle, 0, middle.length);
        startDist = Dot.totalDist(start, middle, end);
    }

    @Override
    public void run() {
        while (true) {
            shuffleArray(middle);
            int newDist = Dot.totalDist(start, middle, end);
            if (!stopWriting && newDist < bestDist) {
                System.arraycopy(middle, 0, bestMiddle, 0, middle.length);
                bestDist = newDist;
            }
        }
    }

    public int diff() {
        return startDist - bestDist;
    }

    private void shuffleArray(Dot[] ar) {
        Collections.shuffle(Arrays.asList(ar));
    }

}

class Dot {

    public final int x;
    public final int y;

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

    public int distTo(Dot other) {
        return Math.abs(x - other.x) + Math.abs(y - other.y);
    }

    public static int totalDist(Dot start, Dot[] dots, Dot end) {
        int distance = end.distTo(start);
        distance += start.distTo(dots[0]);
        distance += end.distTo(dots[dots.length - 1]);
        for (int i = 1; i < dots.length; i++) {
            distance += dots[i].distTo(dots[i - 1]);
        }
        return distance;
    }

    @Override
    public String toString() {
        return "," + x + "," + y;
    }
}

Dividir e conquistar + Bot ganancioso

NOTA:Game Examinei o seu código, o qual inclui o seguinte em Game.parsePath:

for(int i=0;i<numPoints;i++){
        test[i] = new Point(Integer.valueOf(tokens[i*2]), Integer.valueOf(tokens[i*2+1]));
        if(test[i].equals(currentPath[i]))
            same++;

No entanto, como não há catch(NumberFormatException)bloqueio, o seu programa provavelmente trava quando um programa reproduz uma string (como demonstrado no final do mainmétodo do meu programa ). Aconselho que você corrija isso, porque os programas podem gerar exceções, rastrear pilhas ou similares. Caso contrário, comente essa linha no meu programa antes de executá-la.

Voltar ao tópico

Esta implementação (em Java) divide a lista de pontos em pedaços de 25, espaçados aleatoriamente na lista. Em seguida, ele cria threads para encurtar o caminho entre os pontos em cada bloco (daí, "Divide and Conquer"). O thread principal monitora os outros e apresenta a solução mais curta dentro do prazo. Se um encadeamento morre com ou sem solução, ele inicia outro encadeamento novamente em um pedaço diferente.

Cada thread usa o algoritmo "ganancioso", que inicia em um ponto aleatório, vai para o ponto mais próximo e se repete até que todos os pontos sejam cobertos (por isso, "ganancioso").

Notas

• Isso será executado durante todo o minuto 1 (eu dei três segundos para inicialização / desligamento do programa e inicialização da JVM - você nunca sabe o que as rotinas de inicialização da JVM serão apanhadas na próxima ...)
• Mesmo que tenha encontrado soluções, ele continuará pesquisando e, após 1 minuto, apresenta a melhor solução encontrada.
• Não tenho certeza se essa implementação é realmente boa. Eu me diverti codificando isso :)
• Como muitas coisas são aleatórias, isso pode não dar a mesma saída para a mesma entrada.

Basta compilar e usar java DivideAndConquer.classpara executar.

public class DivideAndConquer extends Thread {
    static LinkedList<Point> original;
    static Solution best;
    static LinkedList<DivideAndConquer> bots;
    static final Object _lock=new Object();

    public static void main(String[] args){
        if(args.length != 1) {
            System.err.println("Bad input!");
            System.exit(-1);
        }
        // make sure we don't sleep too long... get the start time
        long startTime = System.currentTimeMillis();
        // parse input
        String[] input=args[0].split(",");
        int numPlayers=Integer.parseInt(input[0]);
        original=new LinkedList<Point>();
        for(int i=1;i<input.length;i+=2){
            original.add(new Point(Integer.parseInt(input[i]), Integer.parseInt(input[i+1])));
        }
        // start threads
        bots=new LinkedList<DivideAndConquer>();
        for(int i=0;i<6;i++)
            bots.add(new DivideAndConquer(i));
        // sleep
        try {
            Thread.sleep(57000 - (System.currentTimeMillis() - startTime));
        } catch(Exception e){} // should never happen, so ignore
        // time to collect the results!
        Solution best=getBestSolution();
        if(best!=null){
            best.apply(original);
            String printStr="";
            for(int i=0;i<original.size();i++){
                Point printPoint=original.get(i);
                printStr+=printPoint.x+","+printPoint.y+",";
            }
            printStr=printStr.substring(0, printStr.length()-1);
            System.out.print(printStr);
        } else {
            System.out.println("Hey, I wonder if the tournament program crashes on NumberFormatExceptions... Anyway, we failed");
        }
    }

    // check the distance
    public static int calculateDistance(List<Point> points){
        int distance = 0;
        for(int i=0;i<points.size();i++){
            int next=i+1;
            if(next>=points.size())next=0;
            distance+=points.get(i).distance(points.get(next));
        }
        return distance;
    }

    public static void solutionFound(Solution s){
        // thanks to Java for having thread safety features built in
        synchronized(_lock){
            // thanks to Java again for short-circuit evaluation
            // saves lazy programmers lines of code all the time
            if(best==null || best.distDifference < s.distDifference){
                best=s;
            }
        }
    }

    public static Solution getBestSolution(){
        // make sure we don't accidentally return
        // the best Solution before it's even
        // done constructing
        synchronized(_lock){
            return best;
        }
    }

    List<Point> myPoints;
    int start;
    int length;
    int id;

    public DivideAndConquer(int id){
        super("DivideAndConquer-Processor-"+(id));
        this.id=id;
        myPoints=new LinkedList<Point>();
        start=(int) (Math.random()*75);
        length=25;
        for(int i=start;i<start+length;i++){
            myPoints.add(original.get(i));
        }
        start();
    }

    public void run(){
        // copy yet again so we can delete from it
        List<Point> copied=new LinkedList<Point>(myPoints);
        int originalDistance=calculateDistance(copied);
        // this is our solution list
        List<Point> solution=new LinkedList<Point>();
        int randomIdx=new Random().nextInt(copied.size());
        Point prev=copied.get(randomIdx);
        copied.remove(randomIdx);
        solution.add(prev);
        while(copied.size()>0){
           int idx=-1;
           int len = -1;
           for(int i=0;i<copied.size();i++){
               Point currentPoint=copied.get(i);
               int dist=prev.distance(currentPoint);
               if(len==-1 || dist<len){
                   len=dist;
                   idx=i;
               }
           }
           prev=copied.get(idx);
           copied.remove(idx);
           solution.add(prev);
        }
        // aaaand check our distance
        int finalDistance=calculateDistance(solution);
        if(finalDistance<originalDistance){
            // yes! solution
            Solution aSolution=new Solution(start, length, solution, originalDistance-finalDistance);
            solutionFound(aSolution);
        }
        // start over regardless
        bots.set(id, new DivideAndConquer(id));
    }

    // represents a solution
    static class Solution {
        int start;
        int length;
        int distDifference;
        List<Point> region;
        public Solution(int start, int length, List<Point> region, int distDifference){
            this.region=new LinkedList<Point>(region);
            this.start=start;
            this.length=length;
            this.distDifference=distDifference;
        }
        public void apply(List<Point> points){
            for(int i=0;i<length;i++){
                points.set(i+start, region.get(i));
            }
        }
    }

    // copied your Point class, sorry but it's useful...
    // just added public to each method for aesthetics
    static class Point{
        int x;
        int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        Point(Point other){
            this.x = other.x;
            this.y = other.y;
        }
        public boolean equals(Point other){
            if(this.x==other.x && this.y==other.y)
                return true;
            return false;
        }

        public int distance(Point other){
            return Math.abs(x-other.x) + Math.abs(y-other.y);
        }
    }
}