Published
Edited
Dec 4, 2019
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
/**
* Takes an array of [dx, dy] vectors and returns an array of [x, y] positions
* @param {Array<Array<number>>} path
* @return {Array<Array<number>>}
*/
function wirePositions(path) {
let x = 0;
let y = 0;
const positions = [];

for (let [dx, dy] of path) {
while (dx || dy) {
let nextPos;
if (dx > 0) {
positions.push([(x += 1), y]);
dx -= 1;
} else if (dx < 0) {
positions.push([(x -= 1), y]);
dx += 1;
} else if (dy > 0) {
positions.push([x, (y += 1)]);
dy -= 1;
} else if (dy < 0) {
positions.push([x, (y -= 1)]);
dy += 1;
}
}
}
return positions;
}
Insert cell
/** Builds a set of the points pathA crosses (as a sparse 2D array) */
pointsForWirePath = path =>
wirePositions(path).reduce((positions, [x, y]) => {
if (!positions[x]) {
positions[x] = [];
}
positions[x][y] = true;
return positions;
}, [])
Insert cell
/**
* Returns the Manhattan distance from the origin to nearest point where the given paths cross
* @param {Array<Array<number>>} pathA
* @param {Array<Array<number>>} pathB
* @return {number}
*/
function findSmallestCrossingDistance(pathA, pathB) {
const positionsA = pointsForWirePath(pathA);

// Iterate over the points pathB crosses and see if any of them belong to positionsA;
// return the smallest
return wirePositions(pathB).reduce((min, [x, y]) => {
const dist = Math.abs(x) + Math.abs(y);
return dist < min && positionsA[x] && positionsA[x][y] ? dist : min;
}, Infinity);
}
Insert cell
Insert cell
Insert cell
/**
* Takes an array of [dx, dy] vectors and returns an array of [x, y, d] positions where `d` is the
* signal delay (number of steps in path)
* @param {Array<Array<number>>} path
* @return {Array<Array<number>>}
*/
function wirePositionsWithSignalDelay(path) {
let x = 0;
let y = 0;
let d = 1;
const positions = [];

for (let [dx, dy] of path) {
while (dx || dy) {
let nextPos;
if (dx > 0) {
positions.push([(x += 1), y, d++]);
dx -= 1;
} else if (dx < 0) {
positions.push([(x -= 1), y, d++]);
dx += 1;
} else if (dy > 0) {
positions.push([x, (y += 1), d++]);
dy -= 1;
} else if (dy < 0) {
positions.push([x, (y -= 1), d++]);
dy += 1;
}
}
}
return positions;
}
Insert cell
/** Builds a sparse 2D array of the signal delay for each point given path crosses */
pointsForWirePathWithSignalDelay = path =>
wirePositionsWithSignalDelay(path).reduce((positions, [x, y, d]) => {
if (!positions[x]) {
positions[x] = [];
}
positions[x][y] = d;
return positions;
}, [])
Insert cell
/**
* Returns the Manhattan distance from the origin to nearest point where the given paths cross
* @param {Array<Array<number>>} pathA
* @param {Array<Array<number>>} pathB
* @return {number}
*/
function findSmallestCrossingSignalDelay(pathA, pathB) {
// Build a set of the points pathA crosses (as a sparse 2D array)
const positionsA = pointsForWirePathWithSignalDelay(pathA);

// Iterate over the points pathB crosses and see if any of them belong to positionsA;
// return the smallest
return wirePositionsWithSignalDelay(pathB).reduce((dMin, [x, y, dB]) => {
if (positionsA[x] && positionsA[x][y] !== undefined) {
dMin = Math.min(dMin, positionsA[x][y] + dB);
}
return dMin;
}, Infinity);
}
Insert cell
Insert cell

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.
Learn more