handout #9

CSE143—Computer Programming II

Programming Assignment #3

due: Thursday, 7/7/05, 9 pm

(courtesy of Stuart Reges)

This assignment will give you practice with linked lists.  You are to write a class AssassinManager that allows a client to manage a game of assassin.  Each person playing assassin has a particular target that he/she is trying to assassinate.  One of the things that makes the game more interesting to play 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 who other people are trying to assassinate).  You are working on a program for the “game administrator” who needs to keep track of who is stalking whom and the history of who killed whom.

The game of assassin is played as follows.  You start out with a group of people who want to play the game.  For example, let's say that we have five people playing whose names are Joe, Sally, Jim, Carol and Chris.  A circular chain of assassination targets is established (what is called the “kill ring” in the sample log of execution).  For example, we might decide Joe should stalk Sally, Sally should stalk Jim, Jim should stalk Carol, Carol should stalk Chris and Chris should stalk Joe.

Joe --> Sally --> Jim --> Carol --> Chris

 ^                                    |

 |                                    V

 +--------<--------<---------<--------+

When someone is assassinated, the chain needs to be relinked by “skipping” that person.  For example, suppose that Jim is assassinated first (obviously this would have been by Sally).  Sally needs a new target, so we give her Jim's target: Carol.  Thus, the chain becomes:

          +-------->--------+

          ^                 |

          |                 V

Joe --> Sally     Jim     Carol --> Chris

 ^                                      |

 |                                      V

 +--------<--------<---------<--------+

The main program has been written for you and is called AssassinMain.  It reads a file of names, shuffles the names, and constructs an object of type AssassinManager.  You are writing the AssassinManager class.  The main program then asks the user for the names of the victims in order until the game is over (until there is just one player left alive), calling methods of the AssassinManager class to carry out the tasks involved in administering the game.

Your class will keep track of two different lists: the list of those currently alive and the list of those who are dead.  Each is to be stored in a linked list.  We are requiring you to use our node class which is called AssassinNode.  The AssassinNode class has three data fields: one for the name of the person, one for the name of the killer and a “next” field to keep track of the next value in the list.  The AssassinNode class appears at the end of this write-up.

Your class should have the following public methods.

Method

Description

AssassinManager(String[] names)

Constructs an assassin manager object, adding the names from the array into the kill ring in order[1] as the starting point for the game.  Throws an IllegalArgumentException if the array is null or if it has 0 length.

void printKillRing()

Prints the names of the people in the kill ring, one per line, indented four spaces, with output of the form “<name> is stalking <name>”.

void printGraveyard()

Prints the names of the people in the graveyard, one per line, indented four spaces, with output of the form “<name> killed by <name>”.  Produces no output if graveyard is empty.

boolean killRingContains

(String name)

Returns true if the given name is in the current kill ring, returns false otherwise.  Ignores case in comparing names.

boolean graveyardContains

(String name)

Returns true if the given name is in the current graveyard, returns false otherwise.  Ignores case in comparing names.

boolean gameOver()

Returns true if the game is over (i.e., if the kill ring has just one person in it), returns false otherwise.

String winner()

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

void kill(String name)

Records the killing of the person with the given name, transferring the person from the kill ring to the front of the graveyard.  Throws an IllegalArgumentException if the given name is not part of the current kill ring and throws an IllegalStateException if the game is over.  Ignores case in comparing names.

This is meant to be an exercise in linked list manipulation.  As a result, you will be required to adhere to the following rules:

·        You must use our AssassinNode class for your lists.  You are not allowed to modify it.

·        You may not construct any arrays or ArrayLists or other data structures to solve this problem.  You must solve it using linked lists.  You can examine the array of Strings passed to the constructor, but you are not allowed to modify it.

·        If there are n names in the array of Strings passed to your constructor, you should ask for a new AssassinNode exactly n times.  This means that as people are killed, you have to move their node from the kill ring to the graveyard without creating any new nodes.

The main effect of the rules above is that your constructor will create an initial set of nodes (the initial kill ring) and then your class will not create any more nodes for the rest of the program execution.  That means that you need to solve the problem of moving people from the kill ring to the graveyard by rearranging references, not by creating new nodes.

Notice in the description of the methods that you have to throw particular exceptions under certain circumstances.

For this particular program, it can be convenient to store the kill ring in what is known as a “circular” linked list.  Normally lists have the value “null” stored in the next field of the last node of the list.  Such lists are known as “null terminated” lists.  In a circular list, the final element stores a reference to the first element in the list.  The assassin task involves a circular chain of targets, so this can be a convenient structure to use.  It can also lead to infinite loops and other problems.  The code is about as difficult to write either way, so use whichever approach appeals to you more.

You will probably want to write a testing program that allows your program to be developed in stages.  When your class is in good shape, you can use the AssassinMain program to make sure it works properly.  A log of execution for AssassinMain appears at the end of this write-up.

You are allowed to declare whatever data fields you want for your class, but you should try to keep these to a minimum.  You can get by with just two data fields (one for each list) and you shouldn’t need much more.  If you have unnecessary data fields (data fields that could be turned into local variables), you will lose style points.

In terms of correctness, your class must provide all of the functionality described above.  In terms of style, we will be grading on your use of comments, good variable names, consistent indentation and good coding style to implement these operations.

You MUST name your file AssassinManager.java and turn it in electronically from the “assignments” link on the class web page.  A collection of files needed for the assignment is included on the web page as ass3.zip.  You will need to have AssassinNode.java, AssassinMain.java and Scanner.java all in the same directory as your AssassinManager.java in order to run AssassinMain.  Don’t forget to compile each file.

AssassinNode Class

// The AssassinNode class is used to store the information for one

// player in the game of assassin.  Initiallly the "killer" field

// is set to null, but when the person is killed, this should be

// set to the name of the killer.

 

public class AssassinNode {

    public String name;        // this person's name

    public String killer;      // name of who killed this person

    public AssassinNode next;  // next node in the list

 

    public AssassinNode(String name) {

        this(name,null);

    }

 

    public AssassinNode(String name, AssassinNode next) {

        this.name = name;

        this.killer = null;

        this.next = next;

    }

}

AssassinMain Class

// Class AssassinMain is the driver program for the assassin management task.

// It reads names from the file names.txt, shuffles them, and uses them to

// start the game.  The user is asked for the name of the next victim until

// the game is over.

 

import java.io.*;

import java.util.*;

 

public class AssassinMain {

    public static void main(String[] args) throws FileNotFoundException {

        // read names into an ArrayList

        Scanner input = new Scanner(new File("names.txt"));

        ArrayList names = new ArrayList();

        while (input.hasNextLine())

            names.add(input.nextLine());

 

        // shuffle the names and build an AssassinManager

        Collections.shuffle(names);

        String[] data = (String[])names.toArray(new String[names.size()]);

        AssassinManager manager = new AssassinManager(data);

 

        // prompt the user for victims until the game is over

        Scanner console = new Scanner(System.in);

        while (!manager.gameOver())

            oneKill(console, manager);

 

        // report who won

        System.out.println("Game was won by " + manager.winner());

        System.out.println("Final graveyard is as follows:");

        manager.printGraveyard();

    }

 

    // Handles the details of recording one victim.  Shows the current kill

    // ring and graveyard to the user, prompts for a name and records the

    // kill if the name is legal.

    public static void oneKill(Scanner console, AssassinManager manager) {

        System.out.println("Current kill ring:");

        manager.printKillRing();

        System.out.println("Current graveyard:");

        manager.printGraveyard();

        System.out.println();

        System.out.print("next victim? ");

        String name = console.nextLine();

        if (manager.graveyardContains(name))

            System.out.println(name + " is already dead.");

        else if (!manager.killRingContains(name))

            System.out.println("Unknown person.");

        else

            manager.kill(name);

        System.out.println();

    }

}

Log of execution (user input underlined)

Current kill ring:

    Bobby Warner is stalking Joe Martin

    Joe Martin is stalking Ruth Martin

    Ruth Martin is stalking Tad Martin

    Tad Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Erica Kane

    Erica Kane is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Bobby Warner

Current graveyard:

 

next victim? Joe Martin

 

Current kill ring:

    Bobby Warner is stalking Ruth Martin

    Ruth Martin is stalking Tad Martin

    Tad Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Erica Kane

    Erica Kane is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Bobby Warner

Current graveyard:

    Joe Martin killed by Bobby Warner

 

next victim? Joe Martin

Joe Martin is already dead.

 

Current kill ring:

    Bobby Warner is stalking Ruth Martin

    Ruth Martin is stalking Tad Martin

    Tad Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Erica Kane

    Erica Kane is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Bobby Warner

Current graveyard:

    Joe Martin killed by Bobby Warner

 

next victim? tad martin

 

Current kill ring:

    Bobby Warner is stalking Ruth Martin

    Ruth Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Erica Kane

    Erica Kane is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Bobby Warner

Current graveyard:

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? BOBBY warner

 

Current kill ring:

    Ruth Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Erica Kane

    Erica Kane is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Ruth Martin

Current graveyard:

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? ERICA KANE

 

Current kill ring:

    Ruth Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Anita Santos

    Anita Santos is stalking Jackson Montgomery

    Jackson Montgomery is stalking Ruth Martin

Current graveyard:

    Erica Kane killed by Phoebe Wallingford

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? anita SANTOS

 

Current kill ring:

    Ruth Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Jackson Montgomery

    Jackson Montgomery is stalking Ruth Martin

Current graveyard:

    Anita Santos killed by Phoebe Wallingford

    Erica Kane killed by Phoebe Wallingford

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? stuart reges

Unknown person.

 

Current kill ring:

    Ruth Martin is stalking Phoebe Wallingford

    Phoebe Wallingford is stalking Jackson Montgomery

    Jackson Montgomery is stalking Ruth Martin

Current graveyard:

    Anita Santos killed by Phoebe Wallingford

    Erica Kane killed by Phoebe Wallingford

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? phoebe wallingford

 

Current kill ring:

    Ruth Martin is stalking Jackson Montgomery

    Jackson Montgomery is stalking Ruth Martin

Current graveyard:

    Phoebe Wallingford killed by Ruth Martin

    Anita Santos killed by Phoebe Wallingford

    Erica Kane killed by Phoebe Wallingford

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner

 

next victim? ruth martin

 

Game was won by Jackson Montgomery

Final graveyard is as follows:

    Ruth Martin killed by Jackson Montgomery

    Phoebe Wallingford killed by Ruth Martin

    Anita Santos killed by Phoebe Wallingford

    Erica Kane killed by Phoebe Wallingford

    Bobby Warner killed by Jackson Montgomery

    Tad Martin killed by Ruth Martin

    Joe Martin killed by Bobby Warner


[1] By “order”, we mean the following:  If the String array contains the names Alpha at index 0, Bravo at index 1 and Charlie at index 2, then Alpha is stalking Bravo, Bravo is stalking Charlie and Charlie is stalking Alpha.