MPCA #3

gistfile1.txt

MPCA #3

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);