Como recuperar da Internet DDOS

17

A internet falhou. Os ataques DDoS agora são galopantes e generalizados. Cabe a você assumir o controle e reparar a Internet.

Cada bot controlará 20 nós nesta rede. Cada nó é ativo ou seguro , possui um proprietário e uma força, que começa em 2. Todo nó ativo é conectado a todos os outros nós ativos.

A cada turno, você receberá uma lista de todos os nós ativos com suas forças. Para cada um dos nós ativos que você possui, você:

  1. Designe um nó ativo que você deseja transferir todo o seu força ou
  2. Economize e aumente sua força

Então, o seguinte acontece em ordem :

  1. Um nó que optar por salvar sua força aumentará sua força em 1.
  2. Todos os nós que optarem por transferir sua força transferirão simultaneamente toda a sua força para o novo nó.
  3. Se um nó foi transferido força de um nó inimigo, um ataque ocorrerá. Se um dono inimigo transferir coletivamente mais força do que o proprietário original (e todos os outros atacantes), esse inimigo se tornará o novo proprietário. A força desse nó se torna a força do atacante. Se houver um empate por força, o proprietário será escolhido aleatoriamente.
  4. Todos os nós deixados sem força serão considerados seguros e atribuem 1 ponto ao proprietário.

Após 100 jogos de 100 turnos, o proprietário com os nós mais seguros em todos os jogos vence. EDIT: Eu mudei de 2000 para 100 voltas, pois as últimas 1900 foram inúteis

IO

Você receberá a lista de nós ativos (via args da linha de comando), como a seguir:

F20 F4 E7 E2 E20 F2

F designa que o nó é um nó amigável e E designa que o nó é um inimigo.

Para cada um dos seus nós amigáveis, você deve retornar uma ação (via STDOUT) da seguinte maneira:

0,0 1,3 5,0

O exposto acima significa que você deseja aumentar sua força do primeiro nó, usar seu segundo nó para atacar o quarto nó e seu último nó transferirá sua força no primeiro nó (e se ninguém o atacar, ele se tornará um nó seguro )

Depois de retornar, seu programa deve sair.

Placar

acumulador tem 3240 pontos

elegante conseguiu 2370 pontos

dumbot obteve 2262 pontos

random_bot obteve 1603 pontos

smarter_random_bot obteve 1319 pontos

stead_bot obteve 1097 pontos

O controlador pode ser encontrado aqui: https://github.com/nathanmerrill/NetAttack

Nathan Merrill
fonte
O controlador contradiz a especificação: "Se um proprietário inimigo transferir coletivamente mais força do que o proprietário original ...". Atualmente é igual ou mais .
randomra
@randomra: na especificação que diz: Se houver um empate para a força, em seguida, o proprietário será escolhido aleatoriamente
Nathan Merrill
@NathanMerrill Presumi que os atacantes empatassem.
Aleatório #
O último nó restante está parado aguardando até o final do jogo, certo? Não há como ele fugir?
aebabis
O @acbabis está correto, mas na verdade testo isso e encerro o jogo prematuramente nesse ponto.
Nathan Merrill

Respostas:

5

Acumulador, Python

Vamos começar esta festa! Minha submissão deve funcionar tanto no Python 2 quanto no Python 3.

import sys

inputs = [(i, x[0], int(x[1:])) for (i, x) in enumerate(sys.argv[1].split())]

own_nodes = sorted([(s,i) for (i,o,s) in inputs if o == 'F'])
targets = sorted([(s,i) for (i,o,s) in inputs if o == 'E'])

if targets:
    t_copy = targets[:]
    out = ""
    total_str = 0
    attackers = []
    for (s,i) in own_nodes:
        attackers += [i]
        if t_copy:
            total_str += s
            if t_copy[0][0] < total_str - 1:
                j = max([j for j in range(len(t_copy)) if t_copy[j][0] < total_str - 1])
                out += " ".join([str(k) + "," + str(t_copy[j][1]) for k in attackers]) + " "
                attackers = []
                total_str = 0
                t_copy = t_copy[:j] + t_copy[j+1:]
    if attackers:
        if t_copy:
            out += " ".join([str(k) + "," + str(t_copy[0][1]) for k in attackers])
        else:
            out += " ".join([str(k) + "," + str(attackers[0]) for k in attackers])
else:
    out = " ".join([str(i) + "," + str(own_nodes[0][1]) for (s,i) in own_nodes])

print(out.rstrip())
sys.stdout.flush()

A ideia é realmente simples. Começo a enumerar meus nós em ordem crescente de força, mantendo uma soma contínua das forças. Quando a soma excede a força do nó inimigo mais fraco (+1 para um possível aumento), ataquei esse nó e o removi da piscina, redefinii a soma e continue. No final, se os nós mais fortes não encontrarem alguém para atacar, eles ganharão mais força.

Edição: Acumulador é agora um pouco mais inteligente. Em vez de sempre atacar o nó inimigo mais fraco, ele acumula força até poder fazê-lo e, em seguida, ataca o nó livre mais forte que puder com essa força. Além disso, se ainda houver inimigos no final, qualquer nó não atribuído atacará o inimigo restante mais fraco, apenas no caso de ele decidir transferir sua força.

Zgarb
fonte
4

Com classe, Python3

import random, sys
f,e,p=[],[],[]
for si,s in enumerate(sys.argv[1].split()):
    if s[0]=='F': f+=[(int(s[1:]),si)]
    else: e+=[(int(s[1:]),si)]
f=sorted(f,key=lambda t:t[0]);r=4
f1,f2,f3=f[:len(f)//r],f[len(f)//r:len(f)//r*2],f[len(f)//r*2:]
for fa in f3:
    ea=[t for t in e if t[0]<fa[0]]
    p+=[(fa[1],random.choice(ea)[1])] if ea else [(fa[1],fa[1])]
for fd,fs in zip(f1,reversed(f2)):
    p+=[(fs[1],fd[1])]
    p+=[(fd[1],fd[1])]
if len(e)==0: p=[(fe[1],0) for fe in f]
for t in p: print(t[0],',',t[1],' ',sep='',end='')
sys.stdout.flush()

O bot divide seus próprios nós em 3 categorias com base na força e cada nó age de acordo com sua categoria.

  • Cada nó forte ataca um nó inimigo aleatório que ele pode vencer.
  • Cada nó do meio suporta seu par de nós fraco.
  • Cada nó fraco se suporta.

Resultado contra o acumulador e os dois robôs de amostra:

smarter_random_bot got 1301 points
random_bot got 1841 points
Accumulator got 2178 points
Classy got 2580 points
randomra
fonte
2

Dumbot, Nodejs

var input = process.argv.splice(2);
var regexp = new RegExp(" ", "gm");
input = String(input).split(regexp);
var nodes = [];
var targets = [];
for(var i = 0; i < input.length; i++){
    if(input[i].charAt(0) == "F")
        nodes.push(i);
    else
        targets.push(i);
}
var result = "";
var length = nodes.length;
for(var i = 0; i < length; i++){
    if(targets.length>0)
        result += nodes.shift() + "," + targets.shift() + " ";
    else
        result += nodes.shift() + ",0 ";
}
console.log(result);

O bot atacará sem nenhum pensamento ou estratégia. O objetivo principal é garantir muitos nós seguros logo no início. Esteja ciente de que este bot faz um loop infinito com o acumulador.

Bater
fonte
2

SteadyBot, Node.js

(new Promise(function(resolve, reject) {
    var input = process.argv[2];
    if(input) {
        resolve(input);
    } else {
        process.stdin.once('data', function(data){
            resolve(data.toString());
        });
    }
})).then(function(input) {
    return input.trim().split(' ');
}).then(function(nodes) {
    var friends = [], enemies = [];
    nodes.forEach(function(value, index) {
        var data = { index: index, strength: parseInt(value.substring(1)) };
        if(value[0] === 'F') {
            friends.push(data);
        } else {
            enemies.push(data);
        }
    });

    function weaknessCompare(a, b) {
        return (a.strength > b.strength) ? -1 : ((a.strength < b.strength) ? 1 : 0);
    }

    friends.sort(weaknessCompare);
    enemies.sort(weaknessCompare);

    if(enemies.length === 0) {
        friends.forEach(function(friend) {
            friend.target = 0;
        });
    } else {
        if(friends.length > 0) {
            var strongest = friends[0];
            for(var i = 0; i < enemies.length; i++) {
                var enemy = enemies[i];
                if(enemy.strength + 1 < strongest.strength) {
                    strongest.target = enemy.index;
                    break;
                }
            };
        }
        if(friends.length > 1) {
            friends[1].target = friends[friends.length - 1].index;
        }
    }

    console.log(friends.map(function(friend) {
        return friend.index + ',' +
                (typeof friend.target === 'number' ? friend.target : friend.index);
    }).join(' '));
});
  • Assume que os inimigos não reforçam nós grandes: o maior nó amigo ataca o inimigo mais forte que ele pode vencer sob essa suposição.
  • Assume que o alvo mais fraco será atacado: O segundo maior nó amigável passa para o nó amigável mais fraco a cada rodada.
  • Quer muita força livre: outros nós esperam.
aebabis
fonte
Não sei por que, mas esse bot não está retornando corretamente (ele imprime uma string vazia). O outro bot do nodejs funciona, então eu recomendo dar uma olhada nele. Também devo mencionar que acabei de instalar o nodejs e, embora eu conheça javascript, posso estar perdendo algo específico para o nodejs.
Nathan Merrill
Obrigado pelo aviso. Quando eu faço node SteadyBot.js F20 F4 E7 E2 E20 F2, funciona para mim. Você poderia, por favor, me dizer a entrada pela qual está falhando?
aebabis
@NathanMerrill Reescrevi para também trabalhar com stdin. Espero que conserte isso. cat F20 F4 E7 E2 E20 F2 | node SteadyBot.js
aebabis
@acbabis A entrada é dada como um grande argumento.
Random #
@acbabis randomra está correto. Você receberá um grande argumento, a lista (a menos que você receba a chamada, assim como C ++, nesse caso, receberá 2).
Nathan Merrill