COLLABORATION IS NOT PERMITTED ? Remember that Weekly Individual Homework should be completed alone. See course syllabus for the consequences of academic dishonesty.
In this assignment, you will be simulating a math problem, called the Josephus Permutation
, where people standing in a circle are eliminated according to a given count until there is only one person remaining.You will implement a class that manages the setup, elimination, and tracking of the people in the circle.
linked list
The Josephus problem is essentially a game of elimination. There simulation begins with a circle of people (this will be read in from a text file) and an elimination count (this will be randomly generated in your constructor). Your program will eliminate people in the circle using the provided count by counting to that number pointing at each person in the circle until the elimination count is reached; the person at that number is then eliminated from the circle.
=== Elimination count is 4 === Remaining survivors: 1Muhammad, 2Jose, 3Amandeep, 4Robin, 5Anh, 6Fumi, 7Roshani, 8Noah, 9Isaac, 10Keerthi, 11Peter Continue elimination? Robin eliminated! Remaining survivors: 1Anh, 2Fumi, 3Roshani, 4Noah, 5Isaac, 6Keerthi, 7Peter, 8Muhammad, 9Jose, 10Amandeep Continue elimination? Noah eliminated! Remaining survivors: 1Isaac, 2Keerthi, 3Peter, 4Muhammad, 5Jose, 6Amandeep, 7Anh, 8Fumi, 9Roshani Continue elimination? Muhammad eliminated! Remaining survivors: 1Jose, 2Amandeep, 3Anh, 4Fumi, 5Roshani, 6Isaac, 7Keerthi, 8Peter Continue elimination? Fumi eliminated! Remaining survivors: 1Roshani, 2Isaac, 3Keerthi, 4Peter, 5Jose, 6Amandeep, 7Anh Continue elimination? Peter eliminated! Remaining survivors: 1Jose, 2Amandeep, 3Anh, 4Roshani, 5Isaac, 6Keerthi Continue elimination? Roshani eliminated! Remaining survivors: 1Isaac, 2Keerthi, 3Jose, 4Amandeep, 5Anh Continue elimination? Amandeep eliminated! Remaining survivors: 1Anh, 2Isaac, 3Keerthi, 4Jose Continue elimination? Jose eliminated! Remaining survivors: 1Anh, 2Isaac, 3Keerthi Continue elimination? Anh eliminated! Remaining survivors: 1Isaac, 2Keerthi Continue elimination? Keerthi eliminated! Isaac is the last survivor!
=== Elimination count is 3 === Remaining survivors: 1Muhammad, 2Beza, 3Ibrar, 4Nur, 5Krystal, 6River, 7Soham, 8Leon, 9Will, 10Qiao Continue elimination? Ibrar eliminated! Remaining survivors: 1Nur, 2Krystal, 3River, 4Soham, 5Leon, 6Will, 7Qiao, 8Muhammad, 9Beza Continue elimination? River eliminated! Remaining survivors: 1Soham, 2Leon, 3Will, 4Qiao, 5Muhammad, 6Beza, 7Nur, 8Krystal Continue elimination? Will eliminated! Remaining survivors: 1Qiao, 2Muhammad, 3Beza, 4Nur, 5Krystal, 6Soham, 7Leon Continue elimination? Beza eliminated! Remaining survivors: 1Nur, 2Krystal, 3Soham, 4Leon, 5Qiao, 6Muhammad Continue elimination? Soham eliminated! Remaining survivors: 1Leon, 2Qiao, 3Muhammad, 4Nur, 5Krystal Continue elimination? Muhammad eliminated! Remaining survivors: 1Nur, 2Krystal, 3Leon, 4Qiao Continue elimination? Leon eliminated! Remaining survivors: 1Qiao, 2Nur, 3Krystal Continue elimination? Krystal eliminated! Remaining survivors: 1Qiao, 2Nur Continue elimination? Qiao eliminated! Nur is the last survivor!
For this assignment, you are provided with a number of starter files: Josephus.zip
There is a provided file called PersonNode. This file is essentially a custom list node class where the data is always a String name. The name field is final because the name in a node should not ever be changed. Instead, the node's next pointer should be manipulated to "move" the node when necessary.
In particular, it provides the following fields and methods:
public final String name  You can access, but not change the name field. 
public PersonNode next  You can access and manipulate the next pointer. 
PersonNode(String name)  Constructs a new PersonNode with the given name and a next of null. 
PersonNode(String name, PersonNode next)  Constructs a new PersonNode with the given name and the given next pointer. 
Implement this class according to the following specification:
Method  Description 

JosephusSim(String fileName)  The constructor will likely be your longest method in this assignment. It should:

void eliminate()  This method should

boolean isOver()  Returns true if there is only one person left in the circle; false otherwise. 
String toString() 
Be careful about infinite loops in this method because the list is circular! 
Run the JosephusDriver and see if your code works. Your output does not need to match mine exactly in format, but it should be close.
If it does not, I recommend using the debugger to
You should do the following for _all_ assignments submitted for this course.
Include a comment at the beginning of your program with the following information and a description of the program in your own words:
// Your name here // CS 143 // HW Core Topics: ... // // This program will ...
Include the output from a single run of your program as a block comment at the end of the program. This comment should come one blank line after the last closing curly brace in your code.
}
/* Paste the output from JGrasp here. Altering output will earn you an automatic zero for the assignment. */
Criteria  Ratings  Pts  

Constructor: loads people into a singly linked PersonNode list  
Constructor: makes the list circular  
Constructor: elimination count is at least 1; is not more than half the size of the list  
eliminate(): finds the person to eliminate counts the appropriate amount; prints name to be eliminated  
eliminate(): properly eliminates removes node with eliminated person; updates circle; updates size  
isOver() checks if only one person is left  
toString(): prints last survivor  
toString(): prints remaining survivors no infinite loop; handles fencepost comma  
style / submission requirements variable names, indentation, formatting, etc; comments as needed; header and output provided; general code structuring  
Total Points: 25.0 