Skip to content

Commit 03a73a3

Browse files
committed
Added hard/shortest_path
1 parent c319edc commit 03a73a3

File tree

2 files changed

+202
-0
lines changed

2 files changed

+202
-0
lines changed

hard/shortest_path.js

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
/**
2+
* Using the JavaScript language, have the function shortestPath(strArr) take
3+
* strArr which will be an array of strings which models a non-looping Graph.
4+
* The structure of the array will be as follows: The first element in the array
5+
* will be the number of nodes N (points) in the array as a string. The next N
6+
* elements will be the nodes which can be anything (A, B, C .. Brick Street,
7+
* Main Street .. etc.). Then after the Nth element, the rest of the elements in
8+
* the array will be the connections between all of the nodes. They will look
9+
* like this: (A-B, B-C .. Brick Street-Main Street .. etc.). Although, there
10+
* may exist no connections at all.
11+
*
12+
* An example of strArr may be: ["4","A","B","C","D","A-B","B-D","B-C","C-D"].
13+
* Your program should return the shortest path from the first Node to the last
14+
* Node in the array separated by dashes. So in the example above the output
15+
* should be A-B-D. Here is another example with strArr being
16+
* ["7","A","B","C","D","E","F","G","A-B","A-E","B-C","C-D","D-F","E-D","F-G"].
17+
* The output for this array should be A-E-D-F-G. There will only ever be one
18+
* shortest path for the array. If no path between the first and last node
19+
* exists, return -1. The array will at minimum have two nodes. Also, the
20+
* connection A-B for example, means that A can get to B and B can get to A.
21+
*
22+
* https://www.coderbyte.com/results/bhanson:Shortest%20Path:JavaScript
23+
*
24+
* @param {array} strArr
25+
* @return {string} or -1 for no path
26+
*/
27+
function shortestPath(strArr) {
28+
// Parse input data
29+
const numNodes = parseInt(strArr[0]);
30+
const nodes = strArr.slice(1, numNodes + 1);
31+
const paths = strArr.slice(numNodes + 1, strArr.length);
32+
33+
// Hash table to store entry into all nodes so we can enter the graph anywhere
34+
const map = new Map();
35+
36+
// Add empty nodes
37+
nodes.forEach(node => {
38+
map.set(node, new Node(node));
39+
});
40+
41+
// Add paths
42+
paths.forEach(path => {
43+
const [start, end] = path.split('-');
44+
map.get(start).addEdge(map.get(end));
45+
map.get(end).addEdge(map.get(start)); // bi-directional
46+
});
47+
48+
// Per spec, start and end are first and last node as given respectively
49+
const start = nodes[0];
50+
const end = nodes[nodes.length - 1];
51+
52+
const shortestPath = map.get(start).pathTo(end);
53+
54+
if (shortestPath.length === 0) {
55+
return -1;
56+
}
57+
58+
return shortestPath.join('-');
59+
}
60+
61+
function Node(key) {
62+
this.key = key;
63+
this.edges = [];
64+
}
65+
66+
Node.prototype.addEdge = function(edge) {
67+
this.edges.push(edge);
68+
};
69+
70+
// Returns shortest path as array or [] if no path available
71+
// Guarantees shortest path by trying all possibilities
72+
Node.prototype.pathTo = function(endKey, visited = []) {
73+
if (visited.includes(this.key)) {
74+
return [];
75+
}
76+
77+
if (this.key === endKey) {
78+
return [this.key];
79+
}
80+
81+
const childrenPaths = [];
82+
for (let i = 0; i < this.edges.length; i++) {
83+
const edge = this.edges[i];
84+
const copy = visited.slice();
85+
copy.push(this.key);
86+
const children = edge.pathTo(endKey, copy);
87+
if (children.length > 0) {
88+
const selfAndChildren = [];
89+
selfAndChildren.push(this.key, ...children);
90+
childrenPaths.push(selfAndChildren);
91+
}
92+
}
93+
childrenPaths.sort((a, b) => a.length - b.length);
94+
95+
return childrenPaths.length > 0 ? childrenPaths[0] : [];
96+
};
97+
98+
module.exports = shortestPath;

hard/shortest_path.test.js

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
const shortestPath = require('./shortest_path');
2+
3+
describe('shortestPath()', () => {
4+
test('finds shortest path', () => {
5+
expect(
6+
shortestPath([
7+
'5',
8+
'A',
9+
'B',
10+
'C',
11+
'D',
12+
'F',
13+
'A-B',
14+
'A-C',
15+
'B-C',
16+
'C-D',
17+
'D-F'
18+
])
19+
).toBe('A-C-D-F');
20+
21+
expect(
22+
shortestPath(['4', 'X', 'Y', 'Z', 'W', 'X-Y', 'Y-Z', 'X-W'])
23+
).toBe('X-W');
24+
});
25+
26+
test('passes Coderbyte.com tests', () => {
27+
expect(
28+
shortestPath([
29+
'6',
30+
'Z',
31+
'B',
32+
'C',
33+
'A',
34+
'Y',
35+
'Q',
36+
'B-C',
37+
'A-B',
38+
'A-Z',
39+
'C-Y',
40+
'Z-Y',
41+
'C-Q'
42+
])
43+
).toBe('Z-Y-C-Q');
44+
45+
expect(shortestPath(['2', 'First Street', 'Third Street'])).toBe(-1);
46+
47+
expect(
48+
shortestPath([
49+
'7',
50+
'D',
51+
'A',
52+
'N',
53+
'I',
54+
'E',
55+
'L',
56+
'B',
57+
'D-A',
58+
'A-N',
59+
'E-B',
60+
'E-L'
61+
])
62+
).toBe(-1);
63+
64+
expect(
65+
shortestPath([
66+
'9',
67+
'Z',
68+
'B',
69+
'C',
70+
'D',
71+
'R',
72+
'A',
73+
'Y',
74+
'Q',
75+
'E',
76+
'A-Z',
77+
'A-R',
78+
'Z-Y',
79+
'Z-C',
80+
'C-B',
81+
'Y-Q',
82+
'Q-D',
83+
'D-E',
84+
'R-E'
85+
])
86+
).toBe('Z-A-R-E');
87+
88+
expect(
89+
shortestPath([
90+
'5',
91+
'N1',
92+
'N2',
93+
'N3',
94+
'N4',
95+
'N5',
96+
'N1-N3',
97+
'N3-N4',
98+
'N4-N5',
99+
'N5-N2',
100+
'N2-N1'
101+
])
102+
).toBe('N1-N2-N5');
103+
});
104+
});

0 commit comments

Comments
 (0)