Programming Paradigms coursework from Stanford's CS107 curriculum.
See the assignment PDF for detailed algorithm explanation and implementation requirements.
This repository hosts my completed CS107 Assignment 2 solution: a C++ recreation of the “Oracle of Bacon” game. It memory-maps the Stanford-provided IMDB dataset and performs a breadth-first search (BFS) to print the shortest collaboration chain between any two actors (capped at six movies).
This project explores the entertainment industry's interconnected network by implementing a breadth-first search algorithm that discovers the shortest path connecting any two actors through their shared film appearances. The implementation demonstrates advanced C++ concepts including low-level memory manipulation, STL containers, and graph traversal algorithms.
- Memory-mapped IMDB:
imdb::getCreditsandimdb::getCastwalk the rawactordata/moviedatablobs using only pointer arithmetic, no preprocessing step needed. - Shortest-path search:
six-degrees.ccruns a BFS over alternating actor/movie nodes while tracking visited entities to avoid cycles and stop once paths exceed six hops.
imdb.h/.cc,imdb-utils.h- IMDB access layer built over memory-mapped binaries.path.h/.cc- Lightweight container for storing and printing actor/movie hops.six-degrees.cc– Interactive CLI that ties everything together.imdb-test.cc– Stand-alone harness for validating the IMDB layer.six-degrees-checker32/64– Staff-provided runtime/memory checkers.Assignment-2-Six-Degrees.pdf,Assignment-2-Six-Degrees-FAQs.pdf– Original specification and FAQ for reference.
The first build automatically clones the official dataset into data/little-endian/. To refresh it:
rm -rf data/
make dataRun the interactive game:
./six-degreesEnter two actor names (press Enter to quit). If a path of length ≤ 6 exists, the chain is printed; otherwise the program reports that no path was found.
./six-degrees-checker64 ./six-degrees
./six-degrees-checker64 ./six-degrees -m