How to recover from DDOS'ed internet

Question

The internet has failed. DDoS attacks are now rampant and widespread. It is up to you to take control and repair the internet.

Each bot will control 20 nodes in this network. Every node is either active or safe, has an owner, and has a strength, which starts at 2. Every active node is connected to all other active nodes.

Each turn, you will receive a list of all active nodes with their strength. For each of the active nodes that you own, you either:

1. Designate an active node you want to transfer your entire strength to, or
2. Save and increase its strength

Then the following happens in order:

1. A Node choosing to save its strength will increase its strength by 1.
2. All nodes choosing to transfer their strength will simultaneously transfer their entire strength to the new node.
3. If a node was transferred strength from an enemy node, an attack will ensue. If an enemy owner collectively transfers more strength than the original owner (and all other attackers), then that enemy becomes the new owner. The strength of that node then becomes the strength of the attacker. If there is a tie for strength, then the owner will be chosen randomly.
4. All nodes left without any strength will be considered safe, and gives 1 point to the owner.

After 100 games of 100 turns, the owner with the most safe nodes across all games wins. EDIT: I changed it from 2000 to 100 turns, as it ended up that the last 1900 turns were useless

IO

You will be passed the list of active nodes (via command line args) like the following:

F20 F4 E7 E2 E20 F2

F designates that the node is a friendly node, and E designates that the node is an enemy.

For each of your friendly nodes, you should return an action (via STDOUT) like the following:

0,0 1,3 5,0

The above would mean that you want to increase your strength of the first node, use your second node to attack the fourth node, and your last node will transfer its strength the first node (and if nobody attacks it, it will become a safe node).

After returning, your program should quit.

Scoreboard

accumulator got 3240 points

classy got 2370 points

dumbot got 2262 points

random_bot got 1603 points

smarter_random_bot got 1319 points

steady_bot got 1097 points

The controller can be found here: https://github.com/nathanmerrill/NetAttack

Answer 1

Accumulator, Python

Let's get this party started! My submission should work both on Python 2 and 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()

The idea is really simple. I start enumerating my nodes in ascending order of strength, keeping a running sum of the strengths. When the sum exceeds the strength of the weakest enemy node (+1 for a possible increase), I attack that node and remove it from the pool, reset the sum, and continue. At the end, if the strongest nodes can't find anyone to attack, they'll collect more strength.

EDIT: Accumulator is now a bit smarter. Instead of always attacking the weakest enemy node, it accumulates the strength until it could do so, and then attacks the strongest free node it can with that strength. Also, if there are still enemies left at the end, any unassigned nodes will attack the weakest remaining enemy, just in case it decides to transfer its strength away.

Answer 2

Classy, 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()

The bot splits its own nodes into 3 categories based on strength and each node acts according to its category.

• Each strong node attacks a random enemy node which it can beat.
• Each middle node supports it's weak node pair.
• Each weak node supports itself.

Result against Accumulator and the two sample bots:

smarter_random_bot got 1301 points
random_bot got 1841 points
Accumulator got 2178 points
Classy got 2580 points

Answer 3

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

The bot will attack without any thinking or strategy. The main goal is to ensure a lot of safe node right at the beginning. Be aware that this bot make an infinite loop with accumulator.

Answer 4

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

• Assumes enemies won't reinforce large nodes: Largest friendly node attacks strongest enemy it can beat under this assumption.
• Assumes that weakest target will be attacked: Second largest friendly node moves to weakest friendly node each round.
• Wants lots of free strength: Other nodes wait.