Last active
December 31, 2015 12:02
-
-
Save feugy/e02c96df9835448f0cbd to your computer and use it in GitHub Desktop.
Solution for coding game "Blender - The money machine" - https://www.codingame.com/games/puzzles/32 (longest path, topological sorting)
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
| // Freely inspired by http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/ | |
| // get the building maps, considering that exist's ids are -1 | |
| let n = +readline() | |
| const rooms = [] | |
| while(n--) { | |
| const [i, money, next1, next2] = readline().split(' ').map(n => n === 'E' ? -1 : +n) | |
| rooms[i] = { | |
| id: i, | |
| money: money, | |
| links: [next1, next2], | |
| // initialize distance for each rooms | |
| dist: -Infinity, | |
| previous: null | |
| } | |
| } | |
| /** | |
| * Topological sort algorithm. | |
| * Caution: result are returned in reverse order. | |
| * @see http://www.geeksforgeeks.org/topological-sorting/ | |
| * | |
| * @param {Object} room - room curently sorted | |
| * @param {Array<Number>} visited - ids of already processed rooms | |
| * @param {Array<Number>} sorted - Resulted sorted ids, reversed | |
| */ | |
| const sortByTopology = (room, visited, sorted) => { | |
| visited.push(room.id) | |
| room.links.forEach(i => { | |
| const linked = rooms[i] | |
| if (!linked || visited.indexOf(i) >= 0) { | |
| return | |
| } | |
| sortByTopology(linked, visited, sorted) | |
| }) | |
| sorted.push(room.id) | |
| } | |
| /** | |
| * Find the longest path within the building | |
| * | |
| * @param {Object} start - starting room | |
| * @return {Array<Object>} longest path to any exit | |
| */ | |
| const findLongestPath = (start) => { | |
| const visited = [] | |
| const sorted = [] | |
| // initialize distance to starting point | |
| start.dist = start.money | |
| // use topological sorting on rooms | |
| rooms.forEach(room => { | |
| if (visited.indexOf(room.id) === -1) { | |
| sortByTopology(room, visited, sorted) | |
| } | |
| }) | |
| // and process each room now that they are sorted | |
| while(sorted.length) { | |
| const room = rooms[sorted.pop()] | |
| if (room.dist !== -Infinity) { | |
| room.links.forEach(i => { | |
| const linked = rooms[i] | |
| if (!linked) { | |
| return | |
| } | |
| // compute new distance, and update if better | |
| const dist = room.dist + linked.money | |
| if (linked.dist < dist) { | |
| linked.dist = dist | |
| linked.previous = room | |
| } | |
| }) | |
| } | |
| } | |
| // ending room is the one with highest distance | |
| const end = rooms.reduce((max, room) => room.dist > max.dist ? room : max) | |
| const path = [] | |
| // make the path from end to start | |
| for (let room = end; room; room = room.previous) { | |
| path.unshift(room) | |
| } | |
| return path | |
| } | |
| // find longest path and display end's distance | |
| const path = findLongestPath(rooms[0]) | |
| //printErr(path.map(r => r.id).join('>')) | |
| print(path.pop().dist) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment