Last active
May 22, 2017 17:11
-
-
Save beldar/faa66f0c8ba5e052d161216401548b38 to your computer and use it in GitHub Desktop.
Given a large hash table whose keys are movie names and whose values are a list of actors in those movies, write a function to determine the Bacon number of a particular actor.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Given a large hash table whose keys are movie names and whose values are a | |
// list of actors in those movies, write a function | |
// to determine the Bacon number of a particular actor. | |
'use strict'; | |
const BaconNumbers = function( movies ) { | |
if ( !movies ) throw new Error('Movies argument is required'); | |
this.source = 'Kevin Bacon'; | |
this.graph = this.createGraph(movies); | |
this.distances = this.dijkstra(); | |
}; | |
BaconNumbers.prototype.getRest = (a, i) => a.slice(0,i).concat(a.slice(i+1, a.length)); | |
BaconNumbers.prototype.createGraph = function(movies) { | |
return Object.values(movies).reduce((hash, actors) => { | |
actors.forEach((actor, i) => { | |
if (!hash[actor]) hash[actor] = []; | |
hash[actor] = hash[actor].concat(this.getRest(actors, i)); | |
}); | |
return hash; | |
}, {}); | |
}; | |
BaconNumbers.prototype.dijkstra = function() { | |
let distance = {}, | |
prev = {}, | |
vertices = {}, | |
graph = this.graph, | |
start = this.source, | |
u; | |
// Setup distance sentinel | |
Object.keys(graph).forEach(function(v_i) { | |
distance[v_i] = Infinity; | |
prev[v_i] = null; | |
vertices[v_i] = true; | |
}); | |
distance[start] = 0; | |
while (Object.keys(vertices).length > 0) { | |
// Obtain a vertex whose distance is minimum. | |
u = Object.keys(vertices).reduce(function(prev, v_i) { | |
return distance[prev] > distance[v_i] ? v_i : prev; | |
}, Object.keys(vertices)[0]); | |
graph[u].forEach(function(edge) { | |
let dist = distance[u] + 1; | |
if (distance[edge] > dist) { | |
distance[edge] = dist; | |
prev[edge] = u; | |
} | |
}); | |
// Mark visited | |
delete vertices[u]; | |
} | |
return distance; | |
}; | |
BaconNumbers.prototype.getNumber = function( target ) { | |
return this.distances[target]; | |
}; | |
const movies = { | |
"Iron Man": ["Robert Downey Jr", "Gwyneth Paltrow", "Terrence Howard"], | |
"Iron Man 3": ["Robert Downey Jr", "Guy Pearce", "Gwyneth Paltrow"], | |
"Super Troopers": ["Jay Chandrasekhar", "Kevin Heffernan"], | |
"The Day After Tomorrow": ["Dennis Quaid", "Jake Gyllenhaal", "Emmy Rossum"], | |
"The Phantom of the Opera": ["Gerard Butler", "Emmy Rossum", "Patrick Wilson"], | |
"How I Met Your Mother": ['Josh Radnor', "Jason Segel", "Cobie Smulders", "Kevin Heffernan"], | |
"Despicable Me": ['Steve Carell', 'Jason Segel', 'Russel Brand', "Michael Fassbender"], | |
"The Nightmare Before Christmas": ["Danny Elfman", "Chris Sarandon", "Catherine O'Hara"], | |
"Homeland": ["Claire Danes", "Damian Lewis", "Morena Baccarin", "Mandy Patinkin"], | |
"Memento": ["Guy Pearce", "Carrie-Anne Moss", "Joe Pantoliano"], | |
"The Matrix": ["Keanu Reeves", "Laurence Fishburne", "Carrie-Anne Moss"], | |
"The Fugitive": ["Harrison Ford", "Tommy Lee Jones", "Sela Ward"], | |
"The Lord of the Rings: The Fellowship of the Ring": ["Elijah Wood", "Ian McKellen", "Orlando Bloom"], | |
"The Curious Case of Benjamin Button": ["Brad Pitt", "Cate Blanchett", "Tilda Swinton"], | |
"Se7en": ["Morgan Freeman", "Brad Pitt", "Gwyneth Paltrow"], | |
"X-Men: First Class": ["James McAvoy", "Michael Fassbender", "Jennifer Lawrence", "Kevin Bacon"], | |
"The Hunger Games": ["Jennifer Lawrence", "Josh Hutcherson", "Liam Hemsworth"], | |
"The Expendables": ["Sylvester Stalone", "Arnold Swartzenhigger"], | |
"The Expendables 2": ["Sylvester Stalone", "Liam Hemsworth", "Randy Couture"], | |
"Paranoia": ["Liam Hemsworth", "Gary Oldman", "Harrison Ford"] | |
}; | |
const bn = new BaconNumbers( movies ); | |
console.log('Kevin Bacon: ', bn.getNumber('Kevin Bacon')); | |
console.log('Jennifer Lawrence: ', bn.getNumber('Jennifer Lawrence')); | |
console.log('Jason Segel: ', bn.getNumber('Jason Segel')); | |
console.log('Josh Radnor: ', bn.getNumber('Josh Radnor')); | |
console.log('Jay Chandrasekhar: ', bn.getNumber('Jay Chandrasekhar')); | |
const assert = require('assert'); | |
assert.equal(bn.getNumber('Kevin Bacon'), 0, 'Kevin Bacon'); | |
assert.equal(bn.getNumber('Jennifer Lawrence'), 1, 'Jennifer Lawrence'); | |
assert.equal(bn.getNumber('Jason Segel'), 2, 'Jason Segel'); | |
assert.equal(bn.getNumber('Josh Radnor'), 3, 'Josh Radnor'); | |
assert.equal(bn.getNumber('Jay Chandrasekhar'), 4, 'Jay Chandrasekhar'); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment