Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition by John Mongan, Noah Kindler, Eric Giguere; ISBN: 978-1-118-26136-1
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old January 9th, 2015, 04:49 PM
Registered User
Points: 16, Level: 1
Points: 16, Level: 1 Points: 16, Level: 1 Points: 16, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Dec 2014
Posts: 4
Thanks: 0
Thanked 0 Times in 0 Posts
Default Six Degrees of Kevin Bacon

Here's what I got:
Code:
// Javascript
function mknode(label, adjacent) {
  return { label: label, adjacent: adjacent, baconNumber: -1 };
}

var angelinaJolie = mknode('Angelina Jolie', []),
    bradPitt = mknode('Brad Pitt', []),
    kevinBacon = mknode('Kevin Bacon', []),
    junoTemple = mknode('Juno Temple', []),
    billPaxton = mknode('Bill Paxton', []),
    tomHanks = mknode('Tom Hanks', []),
    noMoviesActor = mknode('No Movies Actor', []);


angelinaJolie.adjacent.push(bradPitt); // Mr and Mrs Smith
angelinaJolie.adjacent.push(junoTemple); // Malificent

bradPitt.adjacent.push(angelinaJolie); // Mr and Mrs Smith
bradPitt.adjacent.push(kevinBacon); // Beyond All Boundaries

kevinBacon.adjacent.push(bradPitt); // Beyond All Boundaries
kevinBacon.adjacent.push(junoTemple); // Black Mass
kevinBacon.adjacent.push(tomHanks); // Apollo 13
kevinBacon.adjacent.push(billPaxton); // Apollo 13

junoTemple.adjacent.push(kevinBacon); // Black Mass
junoTemple.adjacent.push(angelinaJolie); // Malificent

billPaxton.adjacent.push(kevinBacon); // Apollo 13
billPaxton.adjacent.push(tomHanks); // Apollo 13

tomHanks.adjacent.push(kevinBacon); // Apollo 13
tomHanks.adjacent.push(billPaxton); // Apollo 13

function baconNumber(actor) {
  var currentBaconNumber = 0,
      queue = [],
      v = null;

  if (actor.baconNumber !== -1) {
    return actor.baconNumber;
  }

  function enqueueIf(v) {
    if (v.baconNumber === -1) {
      v.baconNumber = currentBaconNumber;
      queue.push(v);
    }
  }

  enqueueIf(kevinBacon);

  while (queue.length) {
    v = queue.shift();

    if (v === actor) {
      return v.baconNumber;
    }

    currentBaconNumber = v.baconNumber + 1;

    v.adjacent.forEach(enqueueIf);
  }

  return -1;
}

console.log(baconNumber(junoTemple));
console.log(baconNumber(bradPitt));
console.log(baconNumber(billPaxton));
console.log(baconNumber(kevinBacon));
console.log(baconNumber(tomHanks));
console.log(baconNumber(noMoviesActor));
console.log(baconNumber(angelinaJolie));
Unlike the book's solution, It doesn't traverse the entire graph first; it does return the bacon number of the actor in constant time if it happened to calculate it during a previous invocation.
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
rotate text inm45 degrees. surendran Javascript How-To 1 January 25th, 2007 04:55 AM
Rotate a report by 90 degrees csecharith Beginning VB 6 1 January 15th, 2007 01:20 PM
Professional XML Databases from Kevin Williams & C efenih XML 1 May 6th, 2005 06:02 PM
rotate text 90 degrees lcsgeek Classic ASP Databases 2 September 15th, 2003 10:39 AM



All times are GMT -4. The time now is 10:14 PM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.