MP 7 An interactive story

Goals and Overview

In this MP you will:

• Create a “Choose Your Own Adventure Story” (CYOA)
• Implement an Adjacency List with correct running times.
• Find interesting sub-structures in the course-wide CYOA story

Checking Out the Code

From your CS 225 git directory, run the following on EWS:

git fetch release
git merge release/mp7 -m "Merging initial mp7 files"

If you’re on your own machine, you may need to run:

git fetch release
git merge --allow-unrelated-histories release/mp7 -m "Merging initial mp7 files"

MP 7.1: Create a Choose Your Own Adventure

An interactive story presents a reader with a narrative and allows her a choice of options to advance the story. For example, the story may read:

Zoey walks into a long hallway, where she sees three doors. The first, a large old oak door, is slightly ajar; the second, a narrow passageway that looks as though it leads into another hallway; and the third, a sterile metal door that is propped open with a large stone. Uncertain which way to travel, she takes a second to consider each choice.

From the above narrative, the reader chooses where Zoey advances next through an interactive choice:

• After a moment, Zoey chooses to travel through the oak door.
• With a bit of fear, Zoey chooses to travel through the narrow passageway.
• Walking to the end of the hallway, Zoey chooses to travel through sterile metal door.

At the core, every interactive story makes a graph. Each vertex is a narrative and each edge is a choice that leads from one narrative to another. In this activity, you will write your own interactive story and construct a graph of your story.

Format Specification

Your story will consist of several Markdown (.md) files that has one narrative and any options to move forward in the story. For example, waf-zoey.md is already in your data folder:

Zoey walks into a long hallway, where she sees three doors. The first, a large old oak door, is slightly ajar; the second, a narrow passageway that looks as though it leads into another hallway; and the third, a sterile metal door that is propped open with a large stone. Uncertain which way to travel, she takes a second to consider each choice.

# waf-zoey-oak
After a moment, Zoey chooses to travel through the oak door.

# waf-zoey-narrow
With a bit of fear, Zoey chooses to travel through the narrow passageway.

# waf-zoey-metal
Walking to the end of the hallway, Zoey chooses to travel through sterile metal door.

Note the following bits:

• The first section of the file is the narrative.
• Each interactive choice is defined by a line starting with #, followed by the key (filename, without .md) for the next vertex.
• The text for each interactive choice follows the # header line.

Story Requirement

To complete Part 1, your story must feature at least one of these ten people that you and your peers felt was most influential (in random order):

• Bill Gates, founder of Microsoft, author, and philanthropist - Wikipedia: Bill Gates
• Taylor Swift, Taylor Swift (and actually really actually made the list!!) - Wikipedia: Taylor Swift
• Lebron James, basketball superstar - Wikipedia: Lebron James
• Sheryl Sandberg, chief operating officer (COO) of Facebook, author - Wikipedia: Sheryl Sandberg
• Karlie Kloss, “Kode with Klossy”, model, and entrepreneur - Wikipedia: Karlie Kloss
• Elon Musk, Tesla, SpaceX, and more - Wikipedia: Elon Musk
• Grace Hopper, pioneer in programming, invented early compiler related tools - Grace Hopper
• Steve Jobs, former CEO of Apple Inc. - Wikipedia: Steve Jobs
• Emma Watson, actress, activist - Wikipedia: Emma Watson
• Albert Einstein, theoretical physicist, theory of relativity - Wikipedia: Albert Einstein

You do not need to only feature these people (you can feature others!) but your story must feature at least one of these people. This will help you find others who have similar stories to join with you during Part 3.

In addition to the featured person(s), the following conditions must be met:

• You must delete waf-*.md files – write your own story! :)
• Your interactive story must have at least 8 narratives (8 files, 8 vertices). You are encouraged to have more!
• Your interactive story must have at least 13 choices (13 edges). You are encouraged to have more!
• At least one narrative must have at least 3 choices (one vertex must have at least 3 outbound edges).
• Exactly one narrative must be the beginning of the story (one vertex must have no incoming edges, you can never return all the way to the start).
• At least one narrative must be the ending of the story (an ending vertex will have no outbound edges). You can have multiple endings.
• Your story must tell a story. It cannot simply be letters/words that lead to other letters/words. Be creative, have fun.
• Your story must be something you would be proud to show your parents and have your name attached to it. If your story is beyond “G/PG rated”, you will get a 0 on the full assignment.

Part 1: Strict Due Date

Your story is due December 3, 2018 (hard deadline, no grace period). You will earn extra credit for this MP by combining your story with others – more on that soon!

Testing

Once you complete Part 2, you will have a program to test the format of your graph.

Submission

To commit your changes to the repository type:

git add -u
git add data
git commit -m "<your message>"
git push origin master

MAKE SURE all of your data files are added and all of the waf-* files are deleted!

MP 7.2: Adjacency List

You have been provided with an incomplete Graph implementation for an adjacency list implementation. You must complete all functions in Graph.hpp without editing Graph.h. This means you must make use of the std::unsorted_map that maintains the vertices and std::list that maintains the edges.

Runtime Required

In this MP, tests are designed to ensure you have an implementation that runs in the running time described in lecture of the adjacency list, with the exception of vertex/edge removal. You will find several test cases require a specific running time to be met.

Most importantly, ensure your Graph::incidentEdges and Graph::isAdjacent functions run in times described in lecture.

./mp7 main file

The main.cpp file loads your interactive story from your data directory. A complete implementation of Part 2 will allow you to verify the format of your story in Part 1.

Tip on std::reference_wrapper

std::reference_wrapper<class T> is a useful utility that lets std::container based structures like std::list to be able to store references to data instead of needing to internally copy data into the container data structure. To access the reference from the std::reference_wrapper<class T>, please use the std::reference_wrapper<class T> member function T& get() const noexcept to retrieve the wrapped reference.

Test Suite

Additional unit tests similar to how we will grade your MP are provided for you in tests.

make test
./test

MP 7.3: Creative Sub-Structures

The final thing to do in MP7 is to create a shortest path algorithm! You must find and return the shortest path between a given start vertex and end vertex.

Complete Graph<K,V>::shortestPath(...) within Graph2.hpp. This function will allow you to find your shortest path in the course-wide graph!

git fetch release
git merge release/mp7 -m "Merging mp7 part 3 files"

git fetch release
git merge --allow-unrelated-histories release/mp7 -m "Merging mp7 part 3 files"

Grading Information

The following files are used to grade MP7 so far:

• All .md files in data directory, for Part 1
• Graph.hpp, for Part 2
• Graph2.hpp, for Part 3

All other files will not be used for grading.

Submission

To commit your changes to the repository type:

git add -u
git commit -m "<your message>"
git push origin master