Work alone or with a partner of your choice. If you would like to find a partner but don't have anyone in mind, post your availability on the #general channel on Slack.
You'll need a dictionary file (i.e. a list of words you're going to consider legal). Here's a large list of English words.
I like word games. I do the New York Times crossword every day, and I will play Boggle with anybody willing to play with me (and when they're not, I just play alone on my phone). Scrabble, Bananagrams, acrostics, Perquackey, Text Twist, just fooling around with anagrams? Bring 'em on.
Sometimes I play my games strictly—no dictionaries and no web searches allowed. But sometimes it's fun to cheat. What's the best possible Scrabble word I could make out of these seven letters? Can I find the Boggle board with the largest possible number of words on it? What words could go into 17-down in my current crossword puzzle?
If you choose this project option, you will write a program that answers question #1 below and also either question #2 or question #3 (i.e. you only have to implement two of these, but one of them has to be #1):
Your program's command-line syntax should be:
(only the two that are relevant to your project, of course).
NOTE: since your Unix shell will interpret * in its own special way, you'll need to put wildcard search strings between single-quotes, like:
A very long time ago, I started playing around with what my family referred to as the "handshake game." The idea is that you try to construct chains from one person to another, where each link is a pair of people who have met each other (they've shaken hands, at least metaphorically). The example I usually use as an example is this five-step chain from me to Mozart:
Cool.
This weird game hit the mainstream with the first productions in 1990 of the John Guare play Six Degrees of Separation, followed soon after by the film version. What happened next was silly and hilarious: somebody cooked up the idea of "Six Degrees of Kevin Bacon" to use this same chains-of-people idea, where two actors/actresses would be connected to one another if they both appeared in the same movie. Kevin Bacon was clearly chosen partly because he has acted in many, many movies, but also because "Kevin Bacon" sort of rhymes with "Separation." Want to play with this idea? You're in luck. You can go to The Oracle of Kevin Bacon to discover that Regina King is connected to silent film megastar Mary Pickford like so:
(Watch out, though. The Oracle is sometimes a bit too simple-minded. It turns out that Jason Robards, Sr. was in Paris, while his son, Jason Robards, Jr., was the one in Enemy of the State.)
Around this same time, the same idea blossomed into a popular area of study in mathematics and the theory of algorithms, in part due to the emergence of online social networks that have generated gigantic datasets of interconnections between people and organizations.
For this project, you are going to use IMDB's movie data to recreate the Kevin Bacon oracle's main feature: given two movie performers, find the shortest sequence of other performers connecting them, along with the movies shared by successive pairs of performers in the chain.
I'm not going to specify a command line syntax for this project, but do make it as simple and intuitive as you can. You might also want to add some features to make the program more convenient to use. For example, you might allow your user to type:
to get a list of all the movies Ellen Page has been in, or:
to get the cast list for Alien. But at minimum, you'll want to implement something like:
to find the shortest path between those two actors.
I grabbed the data made available by IMDb for non-commercial use, and did a little preprocessing on it. The resulting data consists of three comma-separated values files:
NOTE: I was unable to find an online service that provides rich movie cast data in an easily downloadable form. IMDb's downloadable data is fine as far as it goes, but they only include the most prominent cast members in each movie. For example, "Star Wars: Episode IV - A New Hope" only includes Mark Hamill, Carrie Fisher, Harrison Ford, and Alec Guinness as cast members. Thus, your graph will be a lot sparser than the graph used by The Oracle of Kevin Bacon, which gets its data by downloading and parsing the entirety of Wikipedia in search of movie casts. Your graph's connections will mean something like "these two actors costarred in a movie" as opposed to "these two actors acted in the same movie". That's OK, but it's important to be aware of before you start testing your program.
ANOTHER NOTE: I used only the English movie titles provided by IMDb. So, for example Das Leben der Anderen appears in movies.csv as The Lives of Others.
A readme file containing:
Both of these projects will require you to implement a graph (for the word ladders and the actor chains) on which you will peform breadth-first search. Because this is a project in a course called Data Structures, I expect you to implement your own graph class.
Want to use a list, an array, a stack, a queue, or a map/search-structure? Feel free to use the ones built in to Java.
Start early, ask questions, and have fun!