Homework 8: Paranoia Game

Assigned

• April 24, 2024

Due

• May 1, 2024 11:59pm

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 as in flag football. A tagged player is then removed 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—who 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 player_list.c and player_list.h. It should contain a standard linked list implementation as we’ve practiced in class (with a player_node_t type for the nodes of the list and a player_list_t type for the linked list itself). You should implement the following linked list operations and expose them in player_list.h:

void player_list_init(player_list_t* lst)

Initialize an empty list. The lst parameter must point to usable memory that can hold a player_list_t.

void player_list_destroy(player_list_t* lst)

Free all memory allocated as part of the provided list.

void player_list_append(player_list_t* lst, char* name)

Add a player to the end of the given list. This function should take ownership of the memory pointed to by the name parameter.

bool player_list_remove(player_list_t* lst, char* name)

Remove the player with the provided name from the list. Return true if a matching player was found and removed, or false otherwise.

size_t player_list_length(const player_list_t* lst)

Return the number of players in the given list.

void print_as_target_ring(const player_list_t* lst)

Print the current list, interpreting it as the target ring. For example, 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 prints:

Jackie is the final person remaining.

Finally if there is no one in the target ring, then print_as_target_ring prints:

There are no targets left.

void print_as_tagged_list(const player_list_t* lst)

Print the current list interpreting it as the tagged list. For example, if the list contains the names [John, Jane, Mary] the function prints:

Tagged List:
John
Jane
Mary

If no one has been tagged yet, the function outputs:

No people have been tagged yet.

The Paranoia Driver

Write the main function for this program in a file named paranoia.c. You should use two lists: one for the target ring, and another for the tagged list. The program should behave as follows:

1. 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.

2. 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 the user provides an invalid input.

3. Once there is one person left, the game prints the final contents of the target ring and tagged list and exits.

Hints and Resources

Here are a few hints that may help you with your implementation:

1. You are welcome to borrow elements of previous linked list implementations you’ve completed as you work in this assignment. That includes linked list code from class and labs.
2. 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.
3. You will need to be very careful about heap allocations in your program. I strongly recommend that you use AddressSanitizer during your development to detect and fix any memory errors.

Grading

Your assignment will be graded on a scale of 0–-100 points based on the following criteria:

• The program includes a working Makefile with correctly-defined targets all, clean, and paranoia (10 points)
• The program correctly adds players to the target list (20 points)
• The program correctly runs multiple rounds of the paranoia game (30 points)
• The program can print the target list correctly (10 points)
• The program can print the tagged list correctly (10 points)
• The program correctly detects the end of the game and exits (10 points)
• The program gracefully handles invalid inputs (10 points)

Code Quality

There will be potential deductions for any code quality violations. There are eight requirements for quality code on this assignment:

1. Indent the body of all loops and conditionals one level deeper than the code just outside the loop. Be consistent with your indentation style.
2. Use curly braces for every loop or conditional body, regardless of the number of lines.
3. Include comments that explain what your code does. There should be at least one comment by the start of each loop and if–else block that explains what the purpose of that code is. The comment should not simply restate the code; it should add information for a human who reads the code and is confused.
4. Give variables descriptive names that help a reader understand what they will be used for.
5. Do not read from or display the value of any variable without first initializing it.
6. Your code must compile with no errors and no warnings.
7. Your code may not use any global variables.
8. Your code must not contain errors such as memory leaks, use-after-free errors, double frees, or buffer overruns. You can check for this by building the program with AddressSanitizer and running through your test cases.

Acknowledgements

This assignment was adapted from Peter-Michael Osera’s version of CSC 161. Stuart Reges and Marty Stepp inspired the design of the original assignment.