Remember that Weekly Individual Homework should be completed alone. See course syllabus for the consequences of academic dishonesty.
computer science
Description
COLLABORATION IS NOT PERMITTED ? Remember that Weekly Individual Homework should be completed alone. See course syllabus for the consequences of academic dishonesty.
Overview
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.
Topics
linked list
Josephus Problem
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.
Example Output
- Note that the randomly generated elimination count is printed at the beginning of the solution and then each cycle the person at that count is eliminated.
- e.g. The elimination count in Example 1 is 4.
- Note that the printing of the circle changes every cycle where the first person printed is the person after the person that was just eliminated
- e.g. in Example 1, Robin is eliminated on the first cycle, so Anh becomes the first person printed after that.
- Note that once this count is larger than the size of the circle, you will see that counting continues at the front of the circle after reaching the end.
- e.g. in Example 2, when only 1-Qiao, 2-Nur remain but the count is 3, Qiao is eliminated because the counting started back at the beginning after Nur.
Example 1
=== Elimination count is 4 === Remaining survivors: 1-Muhammad, 2-Jose, 3-Amandeep, 4-Robin, 5-Anh, 6-Fumi, 7-Roshani, 8-Noah, 9-Isaac, 10-Keerthi, 11-Peter Continue elimination? Robin eliminated! Remaining survivors: 1-Anh, 2-Fumi, 3-Roshani, 4-Noah, 5-Isaac, 6-Keerthi, 7-Peter, 8-Muhammad, 9-Jose, 10-Amandeep Continue elimination? Noah eliminated! Remaining survivors: 1-Isaac, 2-Keerthi, 3-Peter, 4-Muhammad, 5-Jose, 6-Amandeep, 7-Anh, 8-Fumi, 9-Roshani Continue elimination? Muhammad eliminated! Remaining survivors: 1-Jose, 2-Amandeep, 3-Anh, 4-Fumi, 5-Roshani, 6-Isaac, 7-Keerthi, 8-Peter Continue elimination? Fumi eliminated! Remaining survivors: 1-Roshani, 2-Isaac, 3-Keerthi, 4-Peter, 5-Jose, 6-Amandeep, 7-Anh Continue elimination? Peter eliminated! Remaining survivors: 1-Jose, 2-Amandeep, 3-Anh, 4-Roshani, 5-Isaac, 6-Keerthi Continue elimination? Roshani eliminated! Remaining survivors: 1-Isaac, 2-Keerthi, 3-Jose, 4-Amandeep, 5-Anh Continue elimination? Amandeep eliminated! Remaining survivors: 1-Anh, 2-Isaac, 3-Keerthi, 4-Jose Continue elimination? Jose eliminated! Remaining survivors: 1-Anh, 2-Isaac, 3-Keerthi Continue elimination? Anh eliminated! Remaining survivors: 1-Isaac, 2-Keerthi Continue elimination? Keerthi eliminated! Isaac is the last survivor!
Example 2
=== Elimination count is 3 === Remaining survivors: 1-Muhammad, 2-Beza, 3-Ibrar, 4-Nur, 5-Krystal, 6-River, 7-Soham, 8-Leon, 9-Will, 10-Qiao Continue elimination? Ibrar eliminated! Remaining survivors: 1-Nur, 2-Krystal, 3-River, 4-Soham, 5-Leon, 6-Will, 7-Qiao, 8-Muhammad, 9-Beza Continue elimination? River eliminated! Remaining survivors: 1-Soham, 2-Leon, 3-Will, 4-Qiao, 5-Muhammad, 6-Beza, 7-Nur, 8-Krystal Continue elimination? Will eliminated! Remaining survivors: 1-Qiao, 2-Muhammad, 3-Beza, 4-Nur, 5-Krystal, 6-Soham, 7-Leon Continue elimination? Beza eliminated! Remaining survivors: 1-Nur, 2-Krystal, 3-Soham, 4-Leon, 5-Qiao, 6-Muhammad Continue elimination? Soham eliminated! Remaining survivors: 1-Leon, 2-Qiao, 3-Muhammad, 4-Nur, 5-Krystal Continue elimination? Muhammad eliminated! Remaining survivors: 1-Nur, 2-Krystal, 3-Leon, 4-Qiao Continue elimination? Leon eliminated! Remaining survivors: 1-Qiao, 2-Nur, 3-Krystal Continue elimination? Krystal eliminated! Remaining survivors: 1-Qiao, 2-Nur Continue elimination? Qiao eliminated! Nur is the last survivor!
Instructions
Part 1: Get the starter files
For this assignment, you are provided with a number of starter files: Josephus.zip
- The only file that you will edit is JosephusSim.java
- The only file that you will run is JosephusDriver.java
- PersonNode.java - is the building block node class for implementing your circularly linked list.
PersonNode
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. |
Part 2: Build JosephusSim.java
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! |
Part 3: Test your JosephusSim using JosephusDriver
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
- set a breakpoint in the main on your `simulation` object at its creation (line 7)
- pull out your object from the debug panel
- step through your code over and over until you figure out when things go wrong
What to Submit
- Your completed JosephusSim.java
- Please include at the end of this file your final output from JosephusDriver.java
Submission Requirements
You should do the following for _all_ assignments submitted for this course.
Program Comment
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 ...
Program Output
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 | |||||
