Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Skynet Revolution - Episode 1

Original Problem

The Goal

Your virus has caused a backdoor to open on the Skynet network enabling you to send new instructions in real time.

You decide to take action by stopping Skynet from communicating on its own internal network.

Skynet's network is divided into several smaller networks, in each sub-network is a Skynet agent tasked with transferring information by moving from node to node along links and accessing gateways leading to other sub-networks.

Your mission is to reprogram the virus so it will sever links in such a way that the Skynet Agent is unable to access another sub-network thus preventing information concerning the presence of our virus to reach Skynet's central hub.

Rules

For each test you are given:
  • A map of the network.
  • The position of the exit gateways.
  • The starting position of the Skynet agent.
>>> Nodes can only be connected to up to a single gateway. <<<

Each game turn:
  • First off, you sever one of the given links in the network.
  • Then the Skynet agent moves from one Node to another accessible Node.
Skynet agent
Gateway
Victory Conditions
The Skynet agent cannot reach an exit gateway
Lose Conditions
The Skynet agent has reached a gateway

 Example

4 4 1
0 1
0 2
1 3
2 3
3
Initialization input
Text representation of the network used in this example. There are 4 nodes, 4 links and 1 gateway. The next 4 lines describe the links. The last integer is the index of the exit node.
Turn 1
The Skynet agent starts at node 0 (SI = 0). Our virus cut the link between the nodes 1 and 3.
Turn 2
The Skynet agent moves to node 2 (SI = 2). Our virus cut the link between the nodes 2 and 3.
Turn 3
The Skynet agent has been cut off from the exit, you have won !

Note

The tests provided are similar to the validation tests used to compute the final score but remain different.

Game Input

The program must first read the initialization data from standard input. Then, within an infinite loop, read the data from the standard input related to the current state of the Skynet agent and provide to the standard output the next instruction.
Initialization input

Line 1: 3 integers N L E
N, the total number of nodes in the level, including the gateways.
L, the number of links in the level.
E, the number of exit gateways in the level.

Next L lines: 2 integers per line (N1N2), indicating a link between the nodes indexed N1 and N2 in the network.

Next E lines: 1 integer EI representing the index of a gateway node.

Input for one game turn
Line 1: 1 integer SI, which is the index of the node on which the Skynet agent is positioned this turn.
Output for one game turn
A single line comprised of two integers C1 and C2 separated by a space. C1 and C2 are the indices of the nodes you wish to sever the link between.
Constraints
2 ≤ N ≤ 500
1 ≤ L ≤ 1000
1 ≤ E ≤ 20
0 ≤ N1N2 < N
0 ≤ SI < N
0 ≤ C1C2 < N
Response time per turn ≤ 150ms

Solution

This problem is pretty simple, when it is only about cutting the way to a gateway. The game can be won just by cutting a random connection and only prevent the agent going to a gateway. However, another restriction is to have 50 or moves remaining. This brought me to elobarate several strategies. Here the ideas:

1. One improvement to the naiv random implementation is to try to encircle the agent by cutting the agents neighbours and intervene a gateway entering at the last resort

2. Another idea is to find the shortest path from the agent to the nearest gateway and cut either the last segment in front of the agent or the gate. For the shortest path, a lot of different algorithms can be used, like dijkstra's algorithm or a simple breadth first search.

3. A mere naiv idea is to cut all links from gateways to their direct neighbours as long as the agent isn't too close to a gateway. This could be improved by cutting a neighbour of the neighbours, closest to a gateway.

All these strategies have in common that they don't build a trap for the agent. When we observe the moving pattern, the agent always runs in circles. To improve the performance and not shut down so many links, we need to cut on the ring somewhere so that the agent runs in a trap. The basic idea builds on the previous strategies, but adds more heuristics.

4. We first check if the agent is close to a gateway and cut this link if necessary. Another heuristic is that we cut the link when the agent has two options to jump. We then cut the way with more neighbours behind. And the last step is building a trap. For the big games we have one move at the beginning, which is wasted with all other strategies, but for our optimal solution, we try to find a place to place it. When we look at the map, (almost) all nodes on rings have 3 neighbours, the gateway and the other two neighbours to the left and right. We focus on these 3 neighbour nodes, which are close to a gateway and search for their closest neighbour. It can happen that such a neighbour isn't present anymore. In this case we cut a random neighbour close to the agent. When it comes to the implementation, we read in the information into a simple graph strcuture:

var [N, L, E] = readline().split(' ').map(Number);

var graph = new Array(N);
var gates = new Array(E);

for (var i = 0; i < L; i++) {
  var [N1, N2] = readline().split(' ').map(Number);

  if (graph[N1] === undefined) graph[N1] = [];
  if (graph[N2] === undefined) graph[N2] = [];

  graph[N1].push(N2);
  graph[N2].push(N1);
}
for (var i = 0; i < E; i++) {
  gates[i] = +readline();
}

And for the rest, we follow the previously described algorithm:

while (true) {
  var SI = +readline();
  var r1, r2 = SI;

  // Check if agent neighbours are close to a gate
  var neighbours = graph[SI];
  var gate = neighbours.find(n => gates.indexOf(n) !== -1);

  if (gate !== undefined) {
    r1 = gate;
  } else if (neighbours.length === 2) {

    // If the agent has two options, cut the one with more neighbours
    if (graph[neighbours[0]].length < graph[neighbours[1]].length) {
      r1 = neighbours[1];
    } else {
      r1 = neighbours[0];
    }
  } else {

    // Create a list of gate neighbours having 3 neighbours themselves
    var gateNeighbours = [];
    for (var g = 0; g < gates.length; g++) {
      var gn = graph[gates[g]];

      for (var n = 0; n < gn.length; n++) {
        if (graph[gn[n]].length === 3) {
          gateNeighbours.push(gn[n]);
        }
      }
    }

    // Take the first gate neighbour for the moment, could be improved
    r1 = gateNeighbours[0];

    // Cut on the ring to another neighbour
    r2 = graph[r1].find(n => gateNeighbours.indexOf(n) !== -1);

    if (r2 === undefined) {
      r1 = neighbours[0];
      r2 = SI;
    }
  }

  graph[r1] = graph[r1].filter(x => x !== r2);
  graph[r2] = graph[r2].filter(x => x !== r1);

  print(r1 + ' ' + r2);
}

Go to overview

All images are copyright to Codingame