Codingame Solution: TAN Network

The administration of the Loire-Atlantique region, located in France, has decided to open up a large amount of public transportation information to the public. The public transport company in charge for this area is named TAN.

One part of this information is the list of TAN stops, timetables and routes. The region wants to provide TAN users with a tool which will allow them to calculate the shortest route between two stops using the TAN network.

Solution

We're given the distance measure based on a spherical earth projection, which can be implemented in JavaScript like this:

var dist = function(lat1, lon1, lat2, lon2) {
    var x = (lon2 - lon1) * Math.cos(((lat1 + lat2) / 2));
    var y = (lat2 - lat1);

    return Math.sqrt(x * x + y * y) * 6371;
};

Since we need to find the shortest route based on the given measure, we need an algorithm to do this for us on a given graph. I think the best way to solve this problem is using an A*-algorithm. I think the implementation is pretty straightforward and for reusability, I implemented a little class called Graph:

function Graph() {

  var info = {};
  var map = {};

  var H = null;

  this.addEdge = function(node1, node2) {

    if (map[node1] === undefined) {
      map[node1] = [];
    }
    map[node1].push(node2);
  };

  this.addInfo = function(id, k, v) {

    if (info[id] === undefined) {
      info[id] = {};
    }
    info[id][k] = v;
  };

  this.setHeuristic = function(h) {
    H = h;
  };

  this.getShortestPath = function(start, stop) { // A*

    function path(P, current) {

      var res = [
        info[current]
      ];

      while (current in P) {
        current = P[current];
        res.unshift(info[current]);
      }
      return res;
    }

    var closedset = [];
    var openset = [start];
    var came_from = {};

    var g_score = {};
    var f_score = {};

    g_score[start] = 0;
    f_score[start] = g_score[start] + H(info, start, stop);

    while (openset.length > 0) {

      // current := the node in openset having the lowest f_score[] value
      var cur;
      var min = f_score[openset[0]];
      var min_i = 0;
      for (var i = 1; i < openset.length; i++) {
        if (min > f_score[openset[i]]) {
          min = f_score[openset[i]];
          min_i = i;
        }
      }
      cur = openset[min_i];

      if (cur === stop) {
        return path(came_from, stop);
      }

      // remove current from openset
      var index = openset.indexOf(cur);
      if (index !== -1) {
        openset.splice(index, 1);
      }

      //add current to closedset
      closedset.push(cur);

      var neighbors = map[cur];

      for (var i = 0; i < neighbors.length; i++) {

        var neighbor = neighbors[i];

        // if neighbor in closedset
        if (closedset.indexOf(neighbor) !== -1) {
          continue;
        }

        var tentative_g_score = g_score[cur] + H(info, cur, neighbor);

        if (-1 === openset.indexOf(neighbor) || tentative_g_score < g_score[neighbor]) {
          came_from[neighbor] = cur;
          g_score[neighbor] = tentative_g_score;
          f_score[neighbor] = g_score[neighbor] + H(info, neighbor, stop);
          if (-1 === openset.indexOf(neighbor)) {
            openset.push(neighbor);
          }
        }
      }
    }
    return null;
  };
}

The implementation isn't optimal, since the open set is scanned linearly. Using a heap structure would speed up things, but isn't needed for this problem though. Okay, using the Graph class, we can set up the heuristic and read in the data:

var G = new Graph;

G.setHeuristic(function(info, a, b) {

  var lat1 = info[a].lat;
  var lon1 = info[a].lon;

  var lat2 = info[b].lat;
  var lon2 = info[b].lon;

  return dist(lat1, lon1, lat2, lon2);
});

function parseCoord(c) {

  return parseFloat(c) / 180 * Math.PI;
}

var startPoint = readline();
var endPoint = readline();
var N = +readline();

for (var i = 0; i < N; i++) {
  var stop = readline().split(",");
  var id = stop[0];

  G.addInfo(id, 'name', stop[1].slice(1, -1));
  G.addInfo(id, 'lat', parseCoord(stop[3]));
  G.addInfo(id, 'lon', parseCoord(stop[4]));
}

var M = parseInt(readline());
for (var i = 0; i < M; i++) {
  var route = readline().split(" ");
  G.addEdge(route[0], route[1]);
}

Having set up the input processing and the graph implementation, the only thing needed is running the shortest path method and print out the path:

var nodes = G.getShortestPath(startPoint, endPoint);

if (nodes === null) {
  print("IMPOSSIBLE");
} else {
  for (var i = 0; i < nodes.length; i++) {
    print(nodes[i].name);
  }
}