Assignment 1: Six Degrees of Kevin Bacon

This handout was adapted from Jerry Cain’s Spring 2021 offering.

Craving a little Oscar trivia? Try your hand at an Internet parlor game about Kevin Bacon’s acting career. He’s never been nominated for an Oscar, but he’s still immortal – based on the premise that he is the hub of the entertainment universe. Mike Ginelli, Craig Fass and Brian Turtle invented the game while students at Albright College in 1993, and their Bacon bit spread rapidly after convincing then TV talk-show host Jon Stewart to demonstrate the game to all those who tuned in. From these humble beginnings, a website was built, a book was published and a nationwide cult-fad was born.

When you think about Hollywood heavyweights, you don’t immediately think of Kevin Bacon. But his career spans over 40 years through films such as Flatliners, The Air Up There, Footloose, The River Wild, JFK and Animal House. To brush up on your Bacon lore and play online, visit http://oracleofbacon.org.

This assignment is first and foremost a systems programming assignment, but it’s also an opportunity to review your C++ while simultaneously exercising some software engineering and low-level memory manipulation skills. You’ll also get to see that low-level C coding and high-level C++ data structuring can coexist in the same application.

Due Date: Tuesday, June 29th, 2021 at 11:59pm, PDT.

Note: We’re requiring this assignment be turned in on time so that we can give you prompt feedback in preparation for the second assignment. If you need an extension, come talk to us in advance.

Overview of the functionality

The game takes the form of a trivia challenge: supply any two names, and your friend/opponent has to come up with a sequence of movies and mutual co-stars connecting the two. In this case, your opponent takes on the form of an executable, and that executable is infuriatingly good.

Jack Nicholson and Meryl Streep? That’s easy:

$ ./search "Meryl Streep" "Jack Nicholson (I)"
Meryl Streep was in "Close Up" (2012) with Jack Nicholson (I).

Mary Tyler Moore (loved her!) and Red Buttons? Not so obvious:

$ ./search "Mary Tyler Moore" "Red Buttons"
Mary Tyler Moore was in "Change of Habit" (1969) with Regis Toomey.
Regis Toomey was in "C.H.O.M.P.S" (1979) with Red Buttons.

Barry Manilow and Lou Rawls? Yes!

$ ./search "Barry Manilow" "Lou Rawls"
Barry Manilow was in "Bitter Jester" (2003) with Dom Irrera.
Dom Irrera was in "A Man Is Mostly Water" (2000) with Lou Rawls.

It’s the people you’ve never heard of that are far away from each other:

$ ./search "Danzel Muzingo" "Liseli Mutti"
Danzel Muzingo was in "My Day in the Barrel" (1998) with Chala Savino.
Chala Savino was in "Barbershop: The Next Cut" (2016) with Troy Garity.
Troy Garity was in "Sunshine" (2007) with Cliff Curtis (I).
Cliff Curtis (I) was in "Rapa Nui" (1994) with Liseli Mutti.

Optionally, the search executable accepts an extra argument to limit the search to something other than 6.

$ ./search "Danzel Muzingo" "Liseli Mutti" 4
Danzel Muzingo was in "My Day in the Barrel" (1998) with Chala Savino.
Chala Savino was in "Barbershop: The Next Cut" (2016) with Troy Garity.
Troy Garity was in "Sunshine" (2007) with Cliff Curtis (I).
Cliff Curtis (I) was in "Rapa Nui" (1994) with Liseli Mutti.
$ ./search "Danzel Muzingo" "Liseli Mutti" 3
No path between those two people could be found.

Getting set up

Getting the code

Go ahead and clone the starter repository that we’ve set up for you. Do so by typing this:

$ git clone /usr/class/cs110/repos/assign1/$USER assign1

This line places a copy of the starter files dedicated to you in your current working directory. git is the name of the source control framework we use to keep track of your changes and minimize the chances you lose any of your work.

If you’re not enrolled in the course and you don’t have a repo, email me and I’ll create one for you. In the meantime, start by cloning the read-only guest repo (i.e. /usr/class/cs110/repos/assign1/guest) and working with that until your repo is available. Then you can clone your real repo and copy your work over, file by file, from the guest copy to the one linked to your SUNet ID.

As you make progress toward a solution, you can invoke ./tools/sanitycheck to commit local changes and run a collection of tests that compare your solution to my own. And be sure your solutions are free of memory leaks and errors, since we’ll be running your code through valgrind. Note: there’s a bug in valgrind that surfaces with virtually any C++ program. You can suppress this error by copying the /usr/class/cs110/tools/config/.valgrindrc file into your home directory (or copying its contents into an existing ~/.valgrindrc file):

$ more /usr/class/cs110/tools/config/.valgrindrc
--memcheck:leak-check=full
--show-reachable=yes
--suppressions=/usr/class/cs110/tools/config/cs110.supp
$ cp /usr/class/cs110/tools/config/.valgrindrc ~

Once you’re done and ready to turn everything in, you can type ./tools/submit, which will offer the option to run sanitycheck one last time before pushing all of your changes back to your /usr/class/cs110/repos/assign1/$USER repo. You can run the submission script as many times as you need to, and we’ll be sure to grade and code review your most recent submission.

Setting up your environment

We have compiled a list of tips for various tools here. In particular, unless you are attached to your current editor, we highly recommend trying VSCode (we have a how-to video linked on that page). VSCode should provide a much better experience than vim or emacs if you’re living far from campus, since it is better able to manage latency, and it also has code analysis features that are extremely useful when working with many files as you will in this class.

If you’re interested in vim (which you can also use inside of VSCode!), we have a video and cheat sheet, and if you’re interested in emacs, there is a great guide on the CS 107 website.

Do you live very far from campus or have a spotty internet connection? We are prototyping a system that would let you work locally on your own machine, instead of needing to connect to myth. Let us know if you would be interested in helping to try this out.

Overview of the assignment

There are two major components to this assignment:

Here is an overview of the files you will need for Task I:

Everything from Task I (except imdbtest.cc) contributes to the overall search application. You can run make to compile your code. There’s a sample executable at ./samples/search_soln for you to play with. Understand that my sample application and yours aren’t obligated to publish the same exact shortest path, but you should be sure that the path lengths themselves actually match.

In addition to the files used for Task I, there are these:

Task I: The imdb class

First off, you should complete the implementation of the imdb class, whose interface looks like this:

struct film {
  string title;
  int year;
};

class imdb {
public: 
  imdb(const string& directory);
  bool good() const;
  bool getCredits(const string& player, vector<film>& films) const;
  bool getCast(const film& movie, vector<string>& players) const;
  ~imdb();

private:
  const void *actorFile;
  const void *movieFile;
};

The constructor and destructor have already been implemented for you. All the constructor does is initialize actorFile and movieFile fields to point to on-disk data structures using the mmap routine you’ll learn about later on in the course. You don’t need to worry about how this works; all you need to know is that when you’re implementing the rest of this class, you can actorFile and movieFile as if they were pointing to normal buffers like those you used in CS 107, but under the hood, when you read something from those memory regions, the operating system reads it from the actor/movie files on disk. This enables our database to load much faster, as we only read the portions of the actor/movie file that we need for our search, instead of reading the entire (huge) files into memory.

You’ll need to implement the getCredits and getCast methods by manually crawling over these binary images in order to produce vectors of movies and actor names. When properly implemented, they provide lightning-speed access to a gargantuan amount of information, because the information is already compactly formatted in a prepared data structure that lives on the myths.

Understand up front that you are implementing these two methods to crawl over two arrays of bytes in order to synthesize data structures for the client. What appears below is a description of how that memory is laid out. You aren’t responsible for creating the data files in any way, but you are responsible for understanding how everything is encoded so that you can rehydrate information from its byte-level representation.

The Raw Data Files

The private actorFile and movieFile fields each address large blocks of memory. Each is configured to point to mutually referent database images, and the format of each is described below. The imdb constructor sets these pointers up for you, so you can proceed as if everything is initialized for getCast and getCredits to just work.

For the purposes of illustration, let’s assume that Hollywood has produced a mere three movies and that they’ve always rotated through the same three actors whenever the time came to cast their three films. Pretend those three films are these:

Remember, we’re pretending.

If an imdb instance is configured to store the above information, you might imagine its actorFile and movieFile fields being initialized—by the constructor I already wrote for you—as follows:

Each of the records for the actors and movies will vary in size. Some movie titles are longer than others; some films feature 75 actors, while others star only one or two. Some actors have prolific careers, while others are one-hit wonders. Defining a struct or class to overlay the blocks of data is a fine idea, except that doing so would constrain all records to be the same size. We don’t want that, because we’d be wasting a good chunk of memory when storing information about actors who appeared in just one or two films and about films that feature just a handful of actors.

However, by allowing the individual records to be of variable size, we lose our ability to binary search (hint: via the STL lower_bound algorithm) a sorted array of records. The number of actors and actresses is 2.5 million, and the number of movies is just shy of 700,000, so a linear search would be way too slow. All actors and movies are sorted by name (and then by year if two movies have the same name), so binary search is still within reach. The strong desire to binary search quickly motivated my decision to format the data files like this:

Spliced in between the number of records and the records themselves is an array of integer offsets. They’re drawn as pointers, but they really aren’t stored that way. We want the data images to be relocatable. Restated, we can’t embed actual memory addresses in the data images, because the binary image may be loaded into memory at different locations each time an imdb is created. By storing integer offsets, we can manually compute the location of Cher’s record, Madonna’s record, or Clerk’s record, etc, by adding the corresponding offsets to whatever actorFile or movieFile turns out to be. A more accurate picture of what gets stored (and this is really what the file format is) is this:

Because the numbers are what they are, we would expect Cher’s 16-byte record to sit 16 bytes from the front of actorFile, Liberace’s 24-byte record to sit 32 bytes within the actorFile image, and so forth. Looking for Moonstruck? Its 28-byte record can be found 36 bytes ahead of whatever address is stored in movieFile. Note that the offsets tell me where records are relative to the base address, and the differences between consecutive offsets tell me how large the records are.

Because all of the offsets are stored as four-byte integers (and ints are four bytes, even on 64-bit systems like the myths), and because they are in a sense sorted if the records they reference are sorted, we can use binary search. Woo.

To summarize:

The Actor Record

The actor record is a packed set of bytes collecting information about an actor and the movies he or she’s appeared in. We don’t use a struct or class to overlay the memory associated with an actor, because doing so would constrain the record size to be the same for all actors. Instead, we lay out the relevant information in a series of bytes, the number of which depends on the length of the actor’s name and the number of films they’ve appeared in. Here’s what gets manually placed within each entry:

  1. The name of the actor is laid out character by character, as a normal null-terminated C-string. If the length of the actor’s name is even, then the string is padded with an extra '\0' so that the total number of bytes dedicated to the name is always an even number. The information that follows the name is most easily interpreted as a short, and the myths often constrain addresses manipulated as short *s to be even.
  2. The number of movies in which the actor has appeared, expressed as a two-byte short. (Some people have been in more than 255 movies, so a single byte isn’t always enough). If the number of bytes dedicated to the actor’s name (always even) and the short (always 2) isn’t a multiple of four, then two additional '\0''s appear after the two bytes storing the number of movies. This padding is conditionally done so that the four-byte integers that follow sit at addresses that are multiples of four (again, because the 64-bit myth's might be configured to require this).
  3. An array of offsets into the movieFile image, where each offset identifies one of the actor’s films.

Here’s what Cher’s record would look like:

The Movie Record

The movie record is only slightly more complicated. The information is compressed as follows:

  1. The title of the movie, terminated by a '\0', so the character array behaves as a normal C-string incidentally wedged into a larger binary data figure.
  2. The year the film was released, expressed as a single byte. This byte stores the year, minus 1900. Since Hollywood is less than 256 years old, it was fine to just store the year as an offset from 1900. If the total number of bytes used to encode the name and year of the movie is odd, then an extra '\0' sits in between the one-byte year and the data that follows.
  3. A two-byte short storing the number of actors appearing in the film, padded with two additional bytes of zeroes if needed.
  4. An array of four-byte integer offsets, where each integer offset identifies one of the actors accessible via actorFile. The number of offsets here is, of course, equal to the short read during step 3.

One major gotcha: Some movies share the same title even though they are different. (The Manchurian Candidate, for instance, was first released in 1962, and then remade in 2004. They’re two different films with two different casts.) If you look in the imdb-utils.h file, you’ll see that the film struct provides operator< and operator== methods. That means that two films know how to compare themselves to each other using infix == and <. You can just rely on the < and == to compare two film records. In fact, you have to, because the movies in the movieData binary image are sorted to respect film::operator<.

It’s best to work on the implementation of the imdb class in isolation, not worrying about the details of the search algorithm you’ll eventually need to write. I’ve provided a test harness to exercise the imdb all by itself, and that code sits in imdbtest.cc. The make system generates a test application called imdbtest which you can use to verify that your imdb implementation is solid. I provide my own version in ./samples/imdbtest_soln (samples is a symbolic link in your repo to a shared directory with solution executables) so you can run your version and my version side by side and make sure they match character for character.

Note: Your implementation will be—and in fact is intended to be—an interesting mix of C and C++. You’ll be relying on your mad C skills to crawl over the binary images, and you’ll be leveraging your C++ mastery to lift that data up into C++ objects. As part of your implementation, you’ll need to binary search over the actor and movie offsets to find the actor or movie of interest.

You’re required to use the STL lower_bound algorithm to perform these binary searches, and you’re also required to use C++ lambdas (also known as anonymous functions with capture clauses) to provide nameless comparison functions that lower_bound can use to guide its search. See the Tips and Tidbits section below for more information.

You’re back in pure C++ mode. At this point, I’m assuming your imdb class works flawlessly, and the fact that there’s some clever pointer gymnastics going on in the imdb.cc file is fully disguised by a delightfully simple imdb interface. Building on top of your imdb class, no pointer arithmetic is required!

For this task, you should use the services of your imdb and my path class (discussed below) to implement a breadth-first search for the shortest possible path. Leverage the STL containers as much as possible to get this done. Here are the STL classes I used in my solution:

You’re welcome to take any approach you want to, provided it generates some shortest path between the supplied actors. We don’t require you generate the same exact path as my solution does, but we do expect the length of your shortest path to match mine.

Tips and Tidbits

Assignment 1 has been the same for the last several years, and I’ve seen a lot of submissions. In prior quarters, I’ve let students struggle through the roadblocks they face as part of the C and C++ review process. However, those struggles were mitigated by the ability to hang out with others for help. Since there’s no hanging out for a while, I figured I’d itemize what the pain points have been in the past and provide some hints to press through them.

Understanding lower_bound and Lambdas

Most students have a difficult time with the idea of an anonymous function and how it should be used with lower_bound. Fundamentally, an anonymous function is a function we don’t bother naming. In the context of imdb::getCredits, the relevant lower_bound call should look like this:

`const int *countp = (const int *) actorFile;
const int *begin = (const int *) actorFile + 1;
const int *end = begin + *countp;
const int *found = lower_bound(begin, end, player, [this](int offset, const string& player) {
    return compareActorAtOffset(offset, player);
});`

begin and end are the addresses bracketing the array of integer offsets, player is the name we’re searching for, and that intimidating fourth argument is the anonymous comparison function. The comparison function is used by the implementation of lower_bound to compare offsets (or really, the strings reachable from those offsets) to the player key.

Even if it looks strange, you’ll probably agree that the fourth parameter resembles the parameter list and body of a traditional function. What’s different? The function doesn’t have a name (that’s what makes it anonymous), and it makes use of a capture clause, which is the [this] portion at the beginning.

The assumption here is that compareActorAtOffset is a const private helper method of the imdb class, and it would need to be implemented to crawl over the image of actor data according to the assignment specification. It needs to be a method so that it has access to the private actorFile field needed to find the actor at the supplied offset. Its implementation needs to return true if and only if the actor name at the provided offset is lexicographically less than the supplied player. It’s that true or false that helps lower_bound internally execute its binary search to either discover where the actor string’s offset is or where its offset would need to be inserted if everything were to remain sorted.

Reasonable question: Why not just pass in compareActorAtOffset itself as a fourth parameter, as with this:

const int *countp = (const int *) actorFile;
const int *begin = (const int *) actorFile + 1;
const int *end = begin + *countp;
const int *found = lower_bound(begin, end, player, compareActorAtOffset); // won't compile

Well, the fourth parameter needs to be a traditional function, and methods—blocks of code invoked on behalf of an object—aren’t traditional functions.

Another reasonable question: What’s the [this] all about?

That’s called a capture clause, and it’s a list of variables in the surrounding scope that needs to be shared with the body of the anonymous function for it to do its job properly. In this case, we capture this, which is a keyword variable that always stores the address of the object being accessed. If we omit this from the capture clause and just pass in an empty one, as with this:

const int *countp = (const int *) actorFile;
const int *begin = (const int *) actorFile + 1;
const int *end = begin + *countp;
const int *found = lower_bound(begin, end, player, [](int offset, const string& player) {
    return compareActorAtOffset(offset, player); // won't compile! no access to this!
});

then the compiler wouldn’t know what object the call to compareActorAtOffset references.

Interpreting lower_bound's return value

It’s common to assume lower_bound returns something NULL-like whenever the underlying binary search for the key—getCredits's player parameter, for example—fails. In fact, the return value means one of two slightly different things, depending on whether the key is present or not. Let’s limit our discussion to the use of lower_bound within imdb::getCredits.

The union of bullet points one and two means you can’t simply look at the lower_bound return value and know whether the actor is present. You need to do a little more work to see whether the return value leads to the matching actor name. If it does, you carry on and look for his or her credits. If not, you bail early and return false, because nonexistent actors aren’t allowed to be in movies.

Write utility functions

You don’t need to be pedantic about it, but you should unify the crunchy pointer arithmetic needed to resuscitate an actor and a film from the data images to helper functions. The (char *), (short *), and (int *)-casting gymnastics is by far the most error-prone form of coding we’ll require of you all quarter, so it’s best to consolidate as much of it to just one or two places, and to rely on those utilities to enhance the narrative of your getCredits and getCast methods.

Making Search Fast

A lot of students are interested in making their breadth-first search for paths between two actors as fast as possible. When the search is slower than the sample executable by more than a factor of three or four, then it is most often caused by making a lot of unnecessary copies of offset arrays. In the past I’ve seen students pull all integer offsets into a dedicated vector and then call lower_bound on the vector endpoints. Don’t do that. The linear copies are expensive and totally unnecessary. The offset arrays directly reachable from actorFile and movieFile are perfectly valid arrays.

If you really want to investigate optimizations to make the search faster you can do one or both of the following (my solution actually does the first, but doesn’t do the second):

Additional Hints