Skip to content

Instantly share code, notes, and snippets.

@dlaxar

dlaxar/u6.js

Created November 26, 2012 20:50
Show Gist options
  • Save dlaxar/4150529 to your computer and use it in GitHub Desktop.
Save dlaxar/4150529 to your computer and use it in GitHub Desktop.
Download ZIP
MPCA #3
Raw
u6.js
// f(index, element, array)
Array.prototype.map = function(f) {
for(var i=0; i < this.length; i++) {
f(i, this[i], this);
}
}
var input =
"+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+\n" +
"| | | | | | | | | | | | | | | | |\n" +
"+ +--+--+ + + +--+--+ + +--+ +--+ + + +--+ +--+--+ +--+ +--+ + +--+ + + + + +--+--+--+--+--+--+ + + + +--+--+ +--+ +--+ +--+--+ + +--+ + +--+--+--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+ + + + + + + +--+--+ + +--+ +--+--+--+ +--+--+ +--+--+ + + + + + +--+--+ +--+--+ + +--+--+ + +--+ + +--+ +--+ +--+ + +--+--+ + +--+ + +--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + +--+--+--+--+--+ +--+--+ +--+ + + + +--+--+--+ + +--+--+ +--+--+--+ + +--+ + +--+--+--+--+ +--+ + + +--+--+--+ + +--+ + +--+ + +--+--+--+--+ + +--+--+\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + +--+--+ +--+--+--+ + + +--+ + + + + + +--+--+--+--+--+ + +--+--+ + +--+ + +--+--+ +--+ +--+--+ + +--+ +--+--+ +--+ + + +--+--+ + + + +--+--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+--+ + + +--+ + +--+--+--+--+--+--+ + + + +--+--+--+ + +--+ +--+--+ + +--+--+ +--+ +--+--+--+--+ + + + + +--+--+--+ + + +--+ +--+ + +--+ +--+--+--+ + +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + +--+ +--+ +--+--+--+ +--+ + + + + + +--+--+--+ + +--+--+ +--+ + +--+--+ + +--+ + +--+--+ + + +--+ + + + +--+--+--+--+--+ + +--+--+--+--+ +--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + + +--+ +--+--+--+--+--+ + +--+ +--+ +--+--+--+--+--+--+ +--+--+--+--+ + +--+--+--+ + + + +--+--+--+--+ +--+--+ + + + + +--+ + +--+ + +--+--+--+ + +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+--+ + +--+--+ + +--+ + +--+--+--+ +--+ + + + +--+ +--+ +--+ + +--+--+ + + + + +--+--+ + + +--+ +--+ + +--+--+ + + +--+--+ + + + +--+ + +--+\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+--+--+ + + + +--+ +--+ + +--+--+ + +--+--+--+--+ +--+ +--+ + +--+ + +--+--+ +--+--+--+--+--+--+--+ +--+ +--+ + +--+--+ +--+--+--+--+ + +--+--+ + + +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+--+ + + + + + + +--+ +--+--+ +--+ + + + +--+ +--+--+ + + +--+ + + +--+--+ + + +--+--+--+ + + +--+ + +--+--+ + + + + +--+--+ + +--+ +--+--+--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + + +--+--+ +--+ + + +--+--+ +--+--+--+--+--+ + +--+--+ +--+ + +--+--+ + + +--+--+ +--+--+--+--+ + +--+--+ + +--+ + + +--+ +--+ +--+ + + + +--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+ +--+--+ + + + +--+--+ +--+--+--+ + +--+ +--+--+--+--+--+ +--+--+--+ + +--+--+ +--+--+--+ +--+ +--+ + + + +--+--+--+ + +--+--+ +--+ + + + +--+ +--+\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + +--+ + + + +--+--+--+ +--+--+--+ + +--+ +--+--+ + +--+ + + +--+ +--+--+ + +--+--+ + +--+ +--+ +--+--+ +--+--+--+ +--+ + + + + +--+--+--+--+ + + +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+--+--+ + + + + +--+ +--+--+ +--+ +--+ + +--+ +--+--+--+ + +--+--+--+ + +--+--+ + + +--+--+ +--+ +--+--+--+--+ + +--+ + +--+ + +--+--+--+--+ +--+--+--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+--+--+ + +--+--+ + +--+--+ +--+ +--+ +--+--+ +--+--+--+ + +--+ +--+--+ +--+ + +--+ +--+ +--+ + +--+--+--+ +--+ +--+--+--+--+--+--+ + + + + + +--+--+--+--+\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+--+--+ +--+--+--+ +--+--+ +--+--+--+--+ + + +--+--+ +--+--+--+--+--+--+ +--+ +--+--+--+ + +--+ +--+ + + + +--+ +--+--+--+--+ + +--+--+--+ + + +--+--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + + + + +--+ + + + +--+--+ + + +--+ + + + +--+ + + + +--+ + + +--+--+--+ +--+--+--+--+ +--+ +--+--+--+--+--+--+ + + +--+--+ +--+--+ +--+ +--+ +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ + + + +--+--+ +--+ +--+--+--+--+--+ + + + +--+ + + + + + + + + + +--+ + +--+--+ + + + + +--+ + + +--+--+--+--+--+ +--+ + +--+--+--+--+ + + + +\n" +
"| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |\n" +
"+ +--+--+ + + +--+ +--+ + +--+ +--+ + + +--+ +--+ + +--+--+--+--+ +--+--+ + +--+ + +--+ +--+ +--+--+--+--+ + + +--+ +--+ + + +--+--+--+ + +--+--+ + +\n" +
"| | | | | | | | | | | | | | | |\n" +
"+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+";
//-- EDGE
var Edge = function(id) {
this.id = id;
this.connections = [];
this.graphIndex = -1;
};
Edge.prototype.toString = function() {
return "Edge(" + ((this.id >> 8) + ", " + (this.id & 0xFF)) + ")";
};
Edge.prototype.getConnections = function() {
return this.connections;
};
Edge.prototype.addConnection = function(edge, rating) {
this.connections.push({'edge': edge, 'rating': rating});
};
Edge.prototype.addConnectionDoSoCounterwise = function(edge, rating) {
this.addConnection(edge, rating);
edge.addConnection(this, rating);
};
//-- GRAPH - consists of multiple edges
var Graph = function() {
this.edges = [];
this.visited = [];
this.preceding = [];
this.distance = []
};
Graph.prototype.addEdge = function(edge) {
return this.edges.push(edge) - 1;
};
Graph.prototype.dijkstra = function(index) {
var currentEdge = index;
this.visited[this.edges.length - 1] = false; // create correct array length
this.preceding[this.edges.length - 1] = null; // create correct array length
this.distance[this.edges.length - 1] = null; // create correct array length
this.preceding[currentEdge] = null; //this.edges[currentEdge];
this.distance[currentEdge] = 0;
currentMinDistanceIndex = currentEdge;
while(this.haveUnvisited()) {
// set current item as visited
this.visited[currentMinDistanceIndex] = true;
currentEdge = currentMinDistanceIndex;
// closure variables
var v = this.visited;
var d = this.distance;
var p = this.preceding;
var e = this.edges;
var graphIndex = -1;
var minDist = -1;
var minIndex = -1;
// traverse over all connections
this.edges[currentEdge].getConnections().map(
function(index, connection, all) {
graphIndex = connection.edge.graphIndex;
// we are only interessted in not-visited connections/edges
if(!v[graphIndex] || v[graphIndex] === false) {
// check if the new distance would be shorter
if(!d[graphIndex] || d[graphIndex] > (d[currentEdge] + connection.rating)) {
// set distance if it is shorter than the old one
d[graphIndex] = d[currentEdge] + connection.rating;
p[graphIndex] = e[currentEdge];
}
// help to determine next element
if(minDist == -1 || d[graphIndex] < minDist) {
minDist = d[graphIndex];
minIndex = graphIndex;
}
}
});
// determine next element
currentMinDistanceIndex = (minIndex == -1 ? this.getShortestUnvisitedEdgeIndex() : minIndex);
}
console.log("DONE!");
console.log("distance from " + this.edges[0] + " to " + this.edges[this.edges.length-1] + " is " + this.distance[this.edges.length-1]);
console.log("To check follow the path:");
console.log(this.getShortestPath(this.edges.length-1));
};
Graph.prototype.haveUnvisited = function() {
for(var i = 0; i < this.visited.length; i++) {
if(!this.visited[i] || this.visited[i] === false) {
return true;
}
}
return false;
};
Graph.prototype.getShortestUnvisitedEdgeIndex = function() {
var minValue = -1;
var minIndex = -1;
for(var i = 0; i < this.distance.length; i++) {
if(!this.visited[i] && this.distance[i] && (minIndex == -1 || (this.distance[i] < minValue))) {
minValue = this.distance[i];
minIndex = i;
}
}
return minIndex;
}
Graph.prototype.getShortestPath = function(edgeIndex) {
if(this.preceding[edgeIndex] != null) {
return this.getShortestPath(this.preceding[edgeIndex].graphIndex) + " > " + this.edges[edgeIndex].toString();
}
return this.edges[edgeIndex].toString();
};
//-- parses the input and invokes the dijkstra algorithm
function buildGraph(input) {
var g = new Graph();
// parsing constants
var LINE_DISTANCE = 2;
var COL_DISTANCE = 3;
// array used for rapid access during parsing
var data = [];
var lines = input.split('\n');
var current, index;
// traverse over lines first
for(var i = 1; i < lines.length; i+=LINE_DISTANCE) {
var y = parseInt((i-1)/LINE_DISTANCE);
current = lines[i];
data[y] = [];
// and split the lines into collumns
for(var j = 1; j < current.length; j += COL_DISTANCE) {
var x = parseInt((j-1)/COL_DISTANCE);
data[y][x] = new Edge(x << 8 | y);
index = g.addEdge(data[y][x]);
data[y][x].graphIndex = index;
if(x >= 1 && current.charAt(j-1) != '|') {
data[y][x].addConnectionDoSoCounterwise(data[y][x-1], 1);
}
if(y >= 1 && lines[i-LINE_DISTANCE+1].charAt(j) != '-') {
data[y][x].addConnectionDoSoCounterwise(data[y-1][x], 1);
}
}
}
g.dijkstra(0)
}
buildGraph(input);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment