Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 1x 1x 1x 1x 1x 1x 1x 3x 3x 3x 17x 17x 5x 17x 12x 12x 17x 17x 16x 17x 1x 1x 17x 3x 3x 3x 3x 3x 3x 12x 12x 20x 20x 2x 2x 18x 20x 11x 11x 11x 11x 20x 10x 10x 10x 1x 1x 1x 1x 1x 1x 1x | // The function returns the number of degrees of separation between the two people.
// If no connection can be made through friends or friends of friends etc then return -1.
const solution = (
connections: string[],
name1: string,
name2: string
): number => {
const graph: { [key: string]: string[] } = {};
// build a graph
for (let connection of connections) {
const [left, right] = connection.split(":");
if (!graph[left]) {
graph[left] = [right];
} else {
graph[left].push(right);
}
if (!graph[right]) {
graph[right] = [left];
} else {
graph[right].push(left);
}
}
// use breadth first search to find the shortest path
const queue = [name1];
const searched: string[] = [];
let degrees = 0;
while (queue.length) {
let size = queue.length;
for(let x = 0; x < size; x++) {
const person = queue.shift() as string;
if (person === name2) {
return degrees;
}
if (!searched.includes(person)) {
const personFriends = graph[person];
queue.push(...personFriends);
searched.push(person);
}
}
degrees++;
}
return -1;
};
// TODO: draw graph connection result
export default solution;
|