I am a Computer Scientist and Musician by training. A writer with interests in Philosophy, Economics, Technology, Politics, Business, the Arts and Fiction.
Published
Edited
Nov 23, 2020
md`# Travelling Salesman Problem`
d3 = require("d3@5", "d3-geo-projection@2")
import { MONOPOLY_NAME_TO_DATA } from '@nuuuwan/monopoly'
import { sum, range } from '@nuuuwan/list-utils'
RADIUS_OF_EARTH_M = 6_371_000
M_IN_KM = 1_000
function getDistance(startName, endName) {
return (
Math.round(
d3.geoDistance(
MONOPOLY_NAME_TO_DATA[startName].latLng,
MONOPOLY_NAME_TO_DATA[endName].latLng
) * RADIUS_OF_EARTH_M
) / M_IN_KM
);
}
[
// test
getDistance('Park Lane', 'Mayfair'),
getDistance('Mayfair', 'Park Lane'),
getDistance('Bond Street', 'Park Lane')
]
function getPathDistance(path) {
return sum(
path.map(function(name, i) {
if (i === 0) {
return 0;
}
return getDistance(path[i - 1], name);
})
);
}
[
// test
getPathDistance(['Park Lane', 'Mayfair']),
getPathDistance(['Park Lane', 'Mayfair', 'Bond Street'])
]
function getClosest(startName, visitedList) {
const startLatLng = MONOPOLY_NAME_TO_DATA[startName].latLng;
return Object.entries(MONOPOLY_NAME_TO_DATA).reduce(
function([closestName, closestDistance], [name, d]) {
if (startName != name && !visitedList.includes(name)) {
const distance = getDistance(startName, name);
if (!closestDistance || distance < closestDistance) {
closestName = name;
closestDistance = distance;
}
}
return [closestName, closestDistance];
},
[undefined, undefined]
);
}
[
// test
getClosest('Park Lane', []),
getClosest('Park Lane', ['Park Lane', 'Mayfair']),
getClosest('Park Lane', ['Mayfair']),
getClosest('Park Lane', ['Mayfair', 'Bond Street'])
]
function getGreedyShortestPath(startName) {
let name = startName;
let path = [name];
let distance = 0;
while (true) {
const [closestName, closestDistance] = getClosest(name, path);
if (closestName) {
path.push(closestName);
distance += closestDistance;
name = closestName;
} else {
break;
}
}
return [path, distance];
}
[
// test
getGreedyShortestPath('Park Lane'),
getGreedyShortestPath('Marylebone station'),
getGreedyShortestPath('Old Kent Road')
]
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
