< Back

Six Degrees of Kevin Bacon

The Kevin Bacon game was developed in 1994 by three bored college students. The goal of the game is simple: Given some movie star, find the shortest sequence of co-stars that results in someone who co-starred with Kevin Bacon. The game is actually an quirky exploration of what is known as "small world phenomenon," the idea that any two human beings in the world can be connected by a seemingly small number of peers.

For this assignment, you will write an interactive program that allows users to determine the length of the shortest path from the users chosen celebrity to Kevin Bacon, commonly referred to as that celebrity's Bacon number.

---

Setup

Create a directory assignment7 under assignments in your cs120 directory. All code for the assignment should be stored in this directory.

cd ~/cs120/assignments
mkdir assignment7
cd assignment7

---

Details

It is postulated that all movie stars can be connected to Kevin Bacon through their co-stars, using 6 or fewer connections. These connections are through the co-stars other movies. A movie star's Bacon number is length of the smallest such chain of connections that results in Kevin Bacon.

Kevin Bacon is the only person in the Universe with a Bacon number of 0. Any celebrity who has starred in a movie with Kevin Bacon has a Bacon number of 1, the only co-star they have to use is Kevin Bacon. If the movie star starred in a movie which had a co-star that has starred in a movie with Kevin Bacon, they have a Bacon number of two.

For this assignment, you will be given access to a database of actors an movies. You are granted the ability to query this database for the movies of a particular actor, as well as actors for a particular movie. The database provided includes EVERYONE who has a Bacon number of 6 or below, using the contents of TheMovieDB.org. You can find the module file here, and the documentation on the course webpage.

The goal of the program is to find the length of the shortest path between the users chosen celebrity, and Kevin Bacon. The process is fairly straight forward: Get all of the movies for the chosen celebrity, get all of the celebrities from those movies, get all of the movies for that new set of celebrities, get all of the celebrities for that new set of movies, etc.

Your program should prompt the user for a celebrity, and then output their Bacon Number.

$ ./compute_bacon.py
Who do you want to find the Bacon number of? Kevin Bacon
Kevin Bacon Bacon number is 0

$ ./compute_bacon.py
Who do you want to find the Bacon number of? Tom Hanks
Tom Hanks Bacon number is 1

$ ./compute_bacon.py
Who do you want to find the Bacon number of? Billy Dee Williams
Billy Dee Williams Bacon number is 2

---

Submission

You are required to submit a tar file to http://cseval.roanoke.edu/. On cseval, there is a link for Assignment 7. You can create a tar file by issuing the following commands:

cd ~/cs120/assignments
tar czvf assignment7.tgz assignment7/

Both partners must submit through cseval!

---

"Hacker" Prompt

1. Optimizations: As you likely noticed, your program is ultimately going to perform a lot of repeated computations. For example, Robert Duvall starred in The Conversation with Billy Dee Williams. So when computing Billy Dee Williams' Bacon number, you will actually generate the list of his movies multiple times. You could probably speed your program up, if you were to remove anyone who you have seen before on this set of connections. See if it increases your performance.

2. Bacon Sets: Some of the actors might want to start a set of clubs, based off of their Bacon Numbers. They'll need a list of all of the people who have a particular Bacon number. Allow a user to enter a particular Bacon number, to retrieve a list of all Actors with the specified Bacon number.

3. Bacon Paths (Very Challenging): The fun part of the Kevin Bacon game isn't generating the actual Bacon number, but figuring out the path between an arbitrary celebrity and Kevin Bacon. The straight forward, brute-force approach would be to keep track of all of the possible chains separately, until you find one that hits Kevin Bacon. However, it is very likely that your computer doesn't have enough memory to keep track of all of those values.

   One method would be to back-track. Whenever you add a movie to a list, you could also tag it with the actor that put it there. The same with movies. Then you just have to follow the new, literal chain back to the original celebrity.