CodinGame - Skynet: the Virus - Solution

skynet_the_virus.js

/**
*@author Dennis Kaffer
*/

function Node(data) {
    var _data = data;
    var _neighbors = [];
    
    return {
        add_neighb: function(n){
            _neighbors.push(n);
        },
        remove_neighb: function(n){
            _neighbors.splice(_neighbors.indexOf(n), 1);
        },
        get_data: function(){
            return _data;
        },
        neighb: function(){
            for(var i = 0; i < _neighbors.length; i++){
                _neighbors[i] = new Node();
            }          
            return _neighbors;
        },
        get_neighb: function(){
            return _neighbors;
        }
    }
}

function Graph(root, end, nodes){
    this._path = []; 
    this._n = null;
    this.root = root;
    this.end = end;
    this.nodes = nodes;
    this.explored = []
    this.preceded = new Array(nodes.length);

    this.q = [];
    this.q.push(this.root);
    
    this.all_functions();
}

Graph.prototype.all_functions = function(){
      this.explore_path();
      this.initialize_preceded();
      this.BFS();
      this.create_path();
};

Graph.prototype.add_first = function(n){
    this._path.unshift(n);
};

Graph.prototype.get_node = function(index){
    return this._path[index]; 
};

Graph.prototype.length = function(){
    return this._path.length;
}

Graph.prototype.explore_path = function(){//populate the explored path of checked nodes 
    for(var i = 0; i < nodes.length; i++){
        this.explored[i] = false;
    }
    this.explored[this.root.get_data()] = true;
};

Graph.prototype.initialize_preceded = function(){  
    for (var j = 0; j < nodes.length; j++){
         this.preceded[j] = 0;
    }
};

Graph.prototype.BFS = function(){
    while((this.q.length !== 0) && (this._n = this.q.splice(0, 1)[0]) != this.end){ 
        for(var x in this._n.get_neighb()){ 
            var n_data = this._n.get_neighb()[x].get_data();
            if(!this.explored[n_data]){
                this.explored[n_data] = true;
                this.preceded[n_data] = this._n.get_data();
                this.q.push(this._n.get_neighb()[x]);
            }
        }
    }
};

Graph.prototype.create_path = function(){//add nodes on the path
    if(this._n == this.end){
        while(this._n != this.root){
            this.add_first(this._n);
            this._n = this.nodes[this.preceded[this._n.get_data()]];
        }
        this.add_first(this._n);
    }
};

function remove_edge(n1, n2){
    n1.remove_neighb(n2);
    n2.remove_neighb(n1);        
    print(n1.get_data() + ' ' + n2.get_data());//print to remove the node connection/edge
}

var inputs = readline().split(' ');
var N = parseInt(inputs[0]); // the total number of nodes in the level, including the gateways
var L = parseInt(inputs[1]); // the number of links
var E = parseInt(inputs[2]); // the number of exit gateways

var nodes = new Array(N);

for (var i = 0; i < N; i++) {
    nodes[i] = new Node(i);
}

for (var i = 0; i < L; i++) {
    var inputs = readline().split(' ');
    var N1 = parseInt(inputs[0]); // N1 and N2 defines a link between these nodes
    var N2 = parseInt(inputs[1]);
    
    nodes[N1].add_neighb(nodes[N2]);
    nodes[N2].add_neighb(nodes[N1]);
}

var exits = [];

for (var i = 0; i < E; i++) {
    var EI = parseInt(readline()); // the index of a gateway node
    exits[i] = nodes[EI];
}

// game loop
while (true) {
    var SI = parseInt(readline()); // The index of the node on which the Skynet agent is positioned this turn
    
    var shortest_path = new Array(E);
    var min_length = Number.MAX_VALUE;
    var path_to_remove = null;
    
    for(var i = 0; i < E; i++){
        
        shortest_path[i] = new Graph(nodes[SI], exits[i], nodes);
        var len = shortest_path[i].length();
        if((len !== 0) && (len < min_length)){
            min_length = len;
            path_to_remove = shortest_path[i];
        }
    }
    
    // Write an action using print()
    // To debug: printErr('Debug messages...');
   remove_edge(path_to_remove.get_node(0),path_to_remove.get_node(1))
}