(Credit to Stuart Reges and Marty Stepp for the original inspiration for this homework!)

Paranoia

In this homework, you will write a program that uses linked lists to keep track of players in a game of Paranoia. Paranoia (also known by a variety of other names such as Assassin) is a popular "real-life" game where every player is assigned a unique target that only they know about. They must then "tag" that target in a way agreed upon by the group, e.g., with a nerf gun, taking a flag from them ala flag football. A tagged player is then removed them from the game and the person who tags that player inherits their target.

An Example Game and Program Execution

Suppose that we have a Paranoia game consisting of five players: Jane, John, Jackie, Jared, and Jesse. Each of the players is assigned one of the other players as an initial target. This assignment of targets forms a target ring, e.g.,

Jane --> John --> Jackie --> Jared --> Jesse
 ^                                        |
 ------------------------------------------

Here, the assignments of targets are:

Jane is targeting John.
John is targeting Jackie.
Jackie is targeting Jared.
Jared is targeting Jesse.
Jesse is targeting Jane.

When one player eliminates their target, the target is removed from the ring. For example, if Jackie tags Jared, then the ring is updated as follows:

Jane --> John --> Jackie --> Jesse
 ^                              |
 --------------------------------

Now Jackie targets Jesse, Jared's target. Everyone else's targets remain the same. This process continues until only one person is left. For example, if Jane eliminates John and Jackie eliminates Jesse, we have the following ring:

Jane --> Jackie
 ^           |
 -------------

Finally, if Jackie eliminates Jane, then the ring only contains one person---Jackie---whom is the winner:

Jackie

Our program will query the user for the names to enter into the game. It then repeatedly queries the user for names of people who were eliminated until there is only one person left. On every round, the program reports both the list of targets as well as an ordered list of people eliminated so far. Here is a sample invocation of the program emulating the scenario above:

$> ./paranoia
Enter a player's name (press enter to begin game): Jane
Enter another player's name: John
Enter another player's name: Jackie
Enter another player's name: Jared
Enter another player's name: Jesse
Enter another player's name:
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jared
  Jared is stalking Jesse
  Jesse is stalking Jane
No people have been tagged yet!

There are 5 people left!
Enter a target: Jared
Jared was tagged!
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jesse
  Jesse is stalking Jane
Tagged List:
  Jared

There are 4 people left!
Enter a target: John
John was tagged!
Target Ring:
  Jane is stalking Jackie
  Jackie is stalking Jesse
  Jesse is stalking Jane
Tagged List:
  Jared
  John

There are 3 people left!
Enter a target: Jesse
Jesse was tagged!
Target Ring:
  Jane is stalking Jackie
  Jackie is stalking Jane
Tagged List:
  Jared
  John
  Jesse

There are 2 people left!
Enter a target: Jane
Jane was tagged!
Jackie is the final person remaining!
Tagged List:
  Jared
  John
  Jesse
  Jane

Note that when the user specifies a target that does not exist (either because they have been tagged already or were never a player to begin with) the game reports an error and continues:

There are 5 people left!
Enter a target: Jerry
Jerry is not a target!
Target Ring:
  Jane is stalking John
  John is stalking Jackie
  Jackie is stalking Jared
  Jared is stalking Jesse
  Jesse is stalking Jane
No people have been tagged yet!

The Paranoia Program

Your program should be broken up into two parts:

A linked list implementation that holds the names of people. This linked list implementation will be used for both the target ring and the tagged list.
A main program driver that queries the user for a set of player names and then plays a game of Paranoia.

The Paranoia Linked List

The linked list implementation should be placed in files called plist.c and plist.h. It should contain a standard linked list implementation as described in class (with a pnode definition for the nodes of the list and a plist definition for the linked list itself). You should implement the following linked list operations and expose them in plist.h:

pnode* make_node(char *name, pnode *next): allocates a new node on the heap with the given values.
plist* make_list(): allocates a new, empty list on the heap.
void free_node(pnode *node): frees the given node.
void free_list(plist *list): frees the given list.
void list_insert(plist *list, char *name): inserts the given name (as a string) into the end of the list.
boolean list_remove(plist *list, char *name): removes the given name from the list, returning true if the name is found and removed and false otherwise.
int list_size(plist *list): returns the number of elements in the list.
void print_as_target_ring: prints the current list interpreting it as the target ring, e.g., if the list contains the names [John, Jane, Mary], print_as_target_ring would output:
```
Target Ring:
John is stalking Jane
Jane is stalking Mary
Mary is stalking John
```
If there is only one person in the target ring, then print_as_target_ring produces:
```
Jackie is the final person remaining!
```
```
Finally if there is no one in the target ring, then `print_as_target_ring` produces:
```
```
There are no targets left!
```
void print_as_tagged_list(plist *list): prints the current list interpreting it as the tagged list, e.g., if the list contains the names [John, Jane, Mary], the function outputs:
```
Tagged List:
John
Jane
Mary
```
If no one has been tagged yet, the function outputs:
```
No people have been tagged yet!
```

The Paranoia Driver

Inside of a file called paranoia.c you should implement the main function for the program. It should use two lists---one for the target ring and the other for the tagged list. The program should behave as follows:

Repeatedly prompt the user for names to enter into the initial target ring. Your program should be able to handle names of unbounded size. You should stop prompting the user when they enter a blank line and then move to the next phase.
Repeatedly play rounds of Paranoia with the user. This consists of querying the user for a target that was eliminated and then updating the target ring and tagged list accordingly. Again, the program should behave gracefully if a target not in the target ring is specified.
Once there is less than one person left, the game prints the final contents of the target ring and tagged list and exits.

To get user input from the user, I highly recommend using the getline function found in stdio.h that we wrote in a previous lab. Alternatively, you can use the various charlist and my_getline implementations we created in previous labs.

Memory Management

You will need to be very careful about heap allocations in your program! In particular:

For every heap allocation you make, you should ask yourself: "whom is responsible for cleaning up this chunk of memory?"
You need to ensure that you avoid leaking not just your linked list nodes, but the strings they hold pointers to.

Use ASan liberal in your development process to ferret out memory error bugs.