Last active
December 30, 2015 14:48
-
-
Save feugy/6506b3711a1271f948bb to your computer and use it in GitHub Desktop.
Solution for coding game "TAN Network" - https://www.codingame.com/games/puzzles/29 (weighten pathfinding)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Return a stop by its id | |
| * @param {String} id - stop's id | |
| * @return {Object} the full stop object | |
| */ | |
| const getById = id => stops.find(n => n.id === id) | |
| /** | |
| * Compute distance between two nodes | |
| * @param {Object} a - first node, with `lat` and `lng` attributes | |
| * @param {Object} b - second node, with `lat` and `lng` attributes | |
| * @return {Number} distance between two nodes | |
| */ | |
| const getDistance = (a, b) => { | |
| const x = (b.lng - a.lng) * Math.cos((a.lat + b.lat) / 2) | |
| const y = b.lat - a.lat | |
| return Math.sqrt(x * x + y * y) * 6371 | |
| } | |
| // read ids of start and stop stations | |
| const trip = { | |
| start: readline(), | |
| end: readline() | |
| } | |
| // read full list of stops | |
| const stops = [] | |
| let n = +readline() | |
| while(n--) { | |
| let [id, name, ,lat, lng] = readline().split(',') | |
| stops.push({ | |
| id: id, | |
| name: name.substr(1, name.length - 2), | |
| lat: +lat * Math.PI / 180, | |
| lng: +lng * Math.PI / 180, | |
| links: [], | |
| // initialized all stops weight to infinity, with no previous | |
| weight: Infinity, | |
| previous: null | |
| }) | |
| } | |
| // enrich stops list with links | |
| n = +readline() | |
| while(n--) { | |
| let [startId, endId] = readline().split(' ') | |
| getById(startId).links.push(stops.findIndex(n => n.id === endId)) | |
| } | |
| // use stops object instead of ids | |
| trip.start = getById(trip.start) | |
| trip.end = getById(trip.end) | |
| /** | |
| * Use Dijkstra algorithm to find shortest path between two stops | |
| * @param {Object} start - start stop | |
| * @param {Object} end - destination stop | |
| * @return {Array<Object>} ordered array of stops for the smallest path | |
| */ | |
| let getShortPath = (start, end) => { | |
| let analyzed = stops.concat() | |
| // start has the first weight | |
| start.weight = 0 | |
| while(analyzed.length > 0) { | |
| // choose next analyzed node as the one with smallest weight | |
| let next = analyzed.reduce((min, stop) => | |
| stop.weight < min.weight ? stop : min) | |
| analyzed.splice(analyzed.indexOf(next), 1) | |
| // for each of its links... | |
| next.links.forEach(i => { | |
| let linked = stops[i] | |
| // affect a weight by adding distance between nodes to existing ditance | |
| let weight = next.weight + getDistance(next, linked) | |
| // and update linked weight if its previous distance was bigger | |
| // (meaning we found a better way) | |
| if (linked.weight > weight) { | |
| linked.weight = weight | |
| // update previous node to reflect the better path | |
| linked.previous = next | |
| } | |
| }) | |
| } | |
| let result = [] | |
| // now that all nodes were weighten, goes back from end to start | |
| for (let stop = end; stop; stop = stop.previous) { | |
| result.unshift(stop) | |
| } | |
| return result | |
| } | |
| // after having searched for shortest path, if end still has an | |
| let path = getShortPath(trip.start, trip.end) | |
| print(trip.end.weight === Infinity ? 'IMPOSSIBLE' : path.map(s => s.name).join('\n')) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment