Skip to content

Instantly share code, notes, and snippets.

@kai-koch
Created December 14, 2012 01:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kai-koch/4281820 to your computer and use it in GitHub Desktop.
Save kai-koch/4281820 to your computer and use it in GitHub Desktop.
This is one solution of the travelling robot problem from http://armelnene.blogspot.co.uk/2012/04/traveling-robot-problem.html Usage: Copy and paste into your browser's JavaScript console, after setting the desired values at the end of the script or use node.js to run the script. This solution sorts the distances a robot can walk by the km/(time…
/**
* @fileOverview This is one solution of the travelling robot problem from
* http://armelnene.blogspot.co.uk/2012/04/traveling-robot-problem.html
*
* Usage: Copy and paste into your browser's JavaScript console, after setting
* the desired values at the end of the script or use node.js to run the script.
*
* This solution sorts the distances a robot can walk by the
* km/(time + cooldown)-ratio descending.
* Higher ratios will be used first. If ratios are equal for some distances the
* longer distance is preferred
*
* @author Kai Koch
* @version 1.0
*/
/**
* Data class of distance
*
* @param {number} km distance interval
* @param {number} time time to travel the distance
*
* @class
* @property {number} km Distance interval
* @property {number} time Time it takes to travel the distance interval
* @property {number} ratio Ratio of km per (time + cooldown).
* @constructor
*/
function Distance(km, time) {
'use strict';
this.km = km;
this.time = time;
this.ratio = 0;
}
/**
* Sets the ratio with the given cooldown time
*
* @param {number} cooldown length of the break the robot takes after
* traveling a distance.
*
* @memberOf Distance
*/
Distance.prototype.setRatio = function (cooldown) {
'use strict';
this.ratio = this.km / (this.time + cooldown);
};
/**
* The Robot: customizeable with cooldown time and an array of distances it can
* travel.
* O(log n) for sorting the distances with n = number of distances.
* O(n*k) n = number of distances, k = actual steps the robot needs to take
*
* @param {number} cooldown Length of the break the robot takes after
* traveling a distance.
* @param {Distance[]} distances An array of distances a robot can travel
* @param {number} distanceToTravel Distance the Robot has to travel
*
* @class
* @property {number} cooldown Length of the break the robot takes of after
* traveling a distance.
* @property {Distance[]} distances An array of distances a robot can travel.
* @property {number} distanceToTravel Distance the Robot has to travel
* @property {number[]} fastesRoute An array with the steps the robot should
* take to arrive in minimal time.
* @property {number} timeTaken Time taken to travel the distance incl. the last
* cooldown the robot takes when arriving at the given distance
* @constructor
*/
function Robot(cooldown, distances, distanceToTravel) {
'use strict';
var i = 0;
var len = distances.length;
this.cooldown = cooldown;
this.distances = [];
this.distanceToTravel = distanceToTravel;
this.fastestRoute = [];
this.timeTaken = 0;
// Calculate km/time ratio with the robots cooldown time and fill the
// distances array
// O(n) with n = number of the diffrent distances a robot can travel
while (i < len) {
distances[i].setRatio(this.cooldown);
this.distances.push(distances[i]);
i += 1;
}
// Sort the distances ratio descending. Higher and preferred km per time
// ratios, come first.
// O(log n)
this.distances = this.distances.sort(this.compareDistancesByRatioDesc);
// max. O(n*k) with n = number of distances and k = the number of actual
// steps the robot has to take.
this.setFastesRoute();
}
/**
* Compare function used when the km/time ratios are equal. now sort descending
* by km. Large km intervals are preferred<br>
* If function returns less than 0, sort a to a lower index than b.<br>
* If function returns returns 0, do not change the order of the two compared
* elements<br>
* If function returns greater than 0, sort b to a lower index than a.
*
* @param {Distance} a
* @param {Distance} b
* @return {number}
*
* @memberOf Robot
*/
Robot.prototype.compareDistancesByKmDesc = function (a, b) {
'use strict';
return b.km - a.km;
};
/**
* Compare function to sort the Distances array descending by ratio.<br>
* If function returns less than 0, sort a to a lower index than b.<br>
* If function returns returns 0, do not change the order of the two compared
* elements<br>
* If function returns greater than 0, sort b to a lower index than a.
*
* @param {Distance} a
* @param {Distance} b
* @return {number}
*
* @memberOf Robot
*/
Robot.prototype.compareDistancesByRatioDesc = function (a, b) {
'use strict';
var retVal = b.ratio - a.ratio;
// Ratio tie sort by km DESC instead!
if (retVal === 0) {
retVal = this.compareDistancesByKmDesc(a, b);
}
return retVal;
};
/**
* Calculate the fastest Route for the robot.<br>
* max. O(n*k) with n = number of distances and k = the number of actual steps
* the robot has to take. Does not nessesarily iterate over all n, when the
* preferred distances fit nicley in the distance to travel. The lower the
* km-value of the preferred route is the higher is k.
*
* @memberOf Robot
*/
Robot.prototype.setFastesRoute = function () {
'use strict';
var i = 0;
var k = 0;
var len = this.distances.length;
var curDistanceStep = 0;
var distanceTraversed = 0;
var leftDistanceToTravel = this.distanceToTravel;
var partialRouteCount = 0;
while (i < len) {
curDistanceStep = this.distances[i].km;
partialRouteCount = leftDistanceToTravel / curDistanceStep;
if (partialRouteCount >= 1) {
partialRouteCount = Math.floor(partialRouteCount);
while (k < partialRouteCount) {
this.fastestRoute.push(this.distances[i].km);
this.timeTaken += this.distances[i].time + this.cooldown;
k += 1;
}
k = 0;
distanceTraversed = partialRouteCount * this.distances[i].km;
leftDistanceToTravel -= distanceTraversed;
}
if (leftDistanceToTravel === 0) {
break;
}
i += 1;
}
};
/**
* String representation
*
* @return {string} String representation of the results
*
* @memberOf Robot
*/
Robot.prototype.toString = function () {
var val = '';
val = 'Distance to Travel: ' + this.distanceToTravel +
'\nTime taken to reach distance: ' + (this.timeTaken - this.cooldown) +
'\nTime including last cooldown: ' + this.timeTaken +
'\nPath taken: [' + this.fastestRoute.join(', ') + ']';
return val;
};
// Values you like to have calculated
var cooldown = 2;
var distances = [
new Distance(1, 10),
new Distance(2, 5),
new Distance(3, 3),
new Distance(5, 2),
new Distance(10, 1)
];
var distanceToTravel = 43;
// Calculate it
console.log('Initializing Robot ...');
var daRobot = new Robot(cooldown, distances, distanceToTravel);
console.log(daRobot.toString());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment