Assassin Manager

Implementing and manipulating linked lists.

ed Workspace

Table of contents

1. AssassinMain
2. AssassinNode
3. AssassinManager
   1. Fields
   2. Method summary
   3. Development strategy
4. Sample output
5. Grading
6. Reflection
7. Submission

“Assassin” is a game often played on college campuses. Each person playing has a particular target that he/she is trying to “assassinate.” Generally “assassinating” a person means finding them on campus in public and acting on them in some way, e.g. saying “You’re dead,” squirting them with a water gun, or tagging them. One of the things that makes the game more interesting to play in real life is that initially each person knows only who they are assassinating; they don’t know who is trying to assassinate them, nor do they know whom the other people are trying to assassinate.

In this assignment, we will write a program that simulates a game of assassin following certain rules.

• Start with a group of people who want to play the game.
• A circular chain of assassination targets (called the “kill ring” in this program) is established.
• When someone is assassinated, the links need to be changed to “skip” that person.

Let’s walk through an example with five people playing: Carol, Chris, Jim, Joe, Sally. We might decide Joe should stalk Sally, Sally should stalk Jim, Jim should stalk Carol, Carol should stalk Chris, and Chris should stalk Joe. In the actual linked list that implements this kill ring, Chris’s next reference would be null. But, conceptually we can think of it as though the next person after Chris is Joe, the front person in the list.

Here is a picture of this “kill ring”:

Then, suppose Sally assassinates Jim. Sally needs a new target, so we give her Jim’s target: Carol. The kill ring becomes:

If the first person in the kill ring is assassinated, the front of the list must adjust. If Chris kills Joe, the list becomes:

As people are killed, we will move them from the “kill ring” (linked list of people currently alive) to the “graveyard” (linked list of those who are dead) by rearranging links between nodes. The game ends when only one node remains in the kill ring, representing the winner.

AssassinMain

A client program called AssassinMain is provided. It reads a file of names, shuffles the names, and constructs an object of our class AssassinManager. This main program then asks the user for the names of each victim to kill until there is just one player left alive (at which point the game is over and the last remaining player wins). AssassinMain calls methods of the AssassinManager class to carry out the tasks involved in administering the game.

AssassinNode

A complete AssassinNode class is provided. Do not make any changes to this class.

public class AssassinNode {
    public final String name; // this person's name (can't be changed)
    public String killer;     // name of who killed this person (null if alive)
    public AssassinNode next; // next node in the list

    public AssassinNode(String name) { ... }
    public AssassinNode(String name, AssassinNode next) { ... }
}

In lecture and section we have been looking at nodes of type ListNode that have just two fields: a field called data of type int and a field called next that points to the next value in the list. The AssassinNode class has three fields. The first two are fields for storing data called name and killer (they are used to store the name of a player and the name of the person who killed that player). The third field is called next and it serves the same purpose as the next field in the ListNode class.

AssassinManager

Fields

• a reference to the front node of the kill ring.
• a reference to the front node of the graveyard (null if empty).

Do not introduce any other fields.

Method summary

public AssassinManager(List<String> names)

Initializes a new assassin manager over the given list of people. Note that this constructor should not save the list parameter itself as a field, nor modify the list. Instead, build a new kill ring of list nodes that contains these names in the same order. If the list is empty, throw an IllegalArgumentException.

For example, if the given list contains ["John", "Sally", "Fred"], the initial kill ring should represent that John is stalking Sally who is stalking Fred who is stalking John (in that order). Asume that the names are non-empty, non-null strings and that there are no duplicates.

public void printKillRing()

Prints the names of the people in the kill ring, one per line, indented by four spaces, as “X is stalking Y”. If the game is over, then instead print “X is stalking X”.

For example, using the names in the example game above, the output is:

    Joe is stalking Sally
    Sally is stalking Jim
    Jim is stalking Carol
    Carol is stalking Chris
    Chris is stalking Joe

If the game is over and Chris is the winner, so Chris is the only name in the kill ring, the output is:

    Chris is stalking Chris

public void printGraveyard()

Prints the names of the people in the graveyard, one per line, with each line indented by four spaces, with output of the form “name was killed by name”. It should print the names in the opposite of the order in which they were killed (most recently killed first, then next more recently killed, and so on). It should produce no output if the graveyard is empty. For example, using the names from above, if Jim is killed, then Chris, then Carol, the output is:

    Carol was killed by Sally
    Chris was killed by Carol
    Jim was killed by Sally

public boolean killRingContains(String name)

Returns true if the given name is in the current kill ring and false otherwise. It should ignore case in comparing names, so “salLY” should match a node with a name of “Sally”.

public boolean graveyardContains(String name)

Returns true if the given name is in the current graveyard and false otherwise. It should ignore case in comparing names, so “CaRoL” should match a node with a name of “Carol”.

public boolean gameOver()

Returns true if the game is over (the kill ring has one person) and false otherwise.

public String winner()

Returns the name of the winner of the game, or null if the game is not over.

public void kill(String name)

Records the assassination of the person with the given name, transferring the person from the kill ring to the front of the graveyard. This method should not change the relative order of the kill ring, so the links of who is killing whom should stay the same other than the person who is being killed. This method should ignore case in comparing names. Set the node’s killer field to whomever killed the person with the given name. Throw an IllegalStateException if the game is over, or throw an IllegalArgumentException if the given name is not part of the kill ring. If both of these conditions are true, the IllegalStateException takes precedence.

Development strategy

The kill method is the hardest one, so write it last. Use the debugger and println statements to debug problems, such as NullPointerException, infinite loops, etc.

The jGRASP debugger has a structure viewer to see what a linked list looks like by dragging one of the fields from the debug window outside the window. By default the viewer won’t show the name in each node (it will show a “?” instead). Fix this by clicking the wrench icon, then in the “Value Expressions” box, type: _node_.name, Click OK to show the names in the nodes. Drag the width scrollbar to see the names better.

Testing code is not required for this assignment, but it will help to write some testing code anyways. AssassinMain requires every method to be written in order to compile, which makes implementation tricky, and it doesn’t cause any of the required exceptions.

Some students try to store the kill ring using a “circular” linked list (where the list’s final element stores a next reference back to the front ). It is significantly more difficult to write bug-free code using a circular list. While circular lists are not disallowed, we will not provide assistance for this approach.

Sample output

AssassinMain should reproduce the format and behavior demonstrated in this log. User input follows each question mark ? below.

Welcome to the CSE143 Assassin Manager

What name file do you want to use this time? names3.txt
Do you want the names shuffled? (y/n)? n

Current kill ring:
    Athos is stalking Porthos
    Porthos is stalking Aramis
    Aramis is stalking Athos
Current graveyard:

next victim? Aramis

Current kill ring:
    Athos is stalking Porthos
    Porthos is stalking Athos
Current graveyard:
    Aramis was killed by Porthos

next victim? Athos

Game was won by Porthos
Final graveyard is as follows:
    Athos was killed by Porthos
    Aramis was killed by Porthos

Grading

Use the Output Comparison Tool, run AssassinMain, and follow along with the expected output.

This is meant to be an exercise in linked list manipulation. Follow these rules while implementing AssassinManager.

1. Do not construct any arrays, ArrayLists, LinkedLists, Stacks, Queues, or other data structures. Work with list nodes!
2. If there are N names in the list of strings passed to the constructor, create exactly N new AssassinNode objects. As people are killed, move their node from the kill ring to the graveyard by changing references without creating any new node objects or changing the name fields of the nodes. It is okay to declare more local variables of type AssassinNode (e.g. current) since variables are not objects themselves (they store references to objects) and therefore don’t count against the limit of N nodes.
3. AssassinManager should be efficient. It should not have any nested loops that loop over the names. In the Complexity lesson, we’ll see that this means that all methods should run in O(N) time where N is the number of names in the list.

Commenting errors

• Method header does not describe the purpose of each parameter or does not describe the meaning of the return value of a non-void method.
• Commenting on a specific client of the class, e.g. AssassinMain.

Readability errors

• Nondescriptive names for local variables or methods.

Control structure errors

• Bad use of if/else, e.g. empty branch, if/if instead of if/else, poor factoring, unnecessary tests.
• Bad use of loops. For example, including an unnecessary check before a loop that repeats the loop test.

Method errors

• Not throwing exceptions at the top of a method when detecting the error does not require significant computation.
• Using if/else instead of if for exception code (non-exception code should not be in an else branch).
• Modifying a parameter to a method when such modification was not part of the intended behavior.

Miscellaneous errors

• Failure to simplify code. For example, not factoring out common code, extra tests or loops that aren’t necessary. Create private “helper” method(s) to capture repeated code.

Reflection

Create a new file reflection.txt and write a paragraph-long reflection answering the following questions (along with anything else you find appropriate):

1. What did you learn this week?
2. What did you enjoy in the course this week?
3. What did you find challenging or frustrating this week?
4. What did you find particularly helpful for your learning this week?

Submission

Submit AssassinManager.java and reflection.txt to Grade-It!