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.

bacon.js

// 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');