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.
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.
- 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.
=== 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
Remaining survivors: 1-Anh, 2-Fumi, 3-Roshani, 4-Noah, 5-Isaac, 6-Keerthi, 7-Peter, 8-Muhammad, 9-Jose, 10-Amandeep
Remaining survivors: 1-Isaac, 2-Keerthi, 3-Peter, 4-Muhammad, 5-Jose, 6-Amandeep, 7-Anh, 8-Fumi, 9-Roshani
Remaining survivors: 1-Jose, 2-Amandeep, 3-Anh, 4-Fumi, 5-Roshani, 6-Isaac, 7-Keerthi, 8-Peter
Remaining survivors: 1-Roshani, 2-Isaac, 3-Keerthi, 4-Peter, 5-Jose, 6-Amandeep, 7-Anh
Remaining survivors: 1-Jose, 2-Amandeep, 3-Anh, 4-Roshani, 5-Isaac, 6-Keerthi
Remaining survivors: 1-Isaac, 2-Keerthi, 3-Jose, 4-Amandeep, 5-Anh
Remaining survivors: 1-Anh, 2-Isaac, 3-Keerthi, 4-Jose
Remaining survivors: 1-Anh, 2-Isaac, 3-Keerthi
Remaining survivors: 1-Isaac, 2-Keerthi
Isaac is the last survivor!
=== 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
Remaining survivors: 1-Nur, 2-Krystal, 3-River, 4-Soham, 5-Leon, 6-Will, 7-Qiao, 8-Muhammad, 9-Beza
Remaining survivors: 1-Soham, 2-Leon, 3-Will, 4-Qiao, 5-Muhammad, 6-Beza, 7-Nur, 8-Krystal
Remaining survivors: 1-Qiao, 2-Muhammad, 3-Beza, 4-Nur, 5-Krystal, 6-Soham, 7-Leon
Remaining survivors: 1-Nur, 2-Krystal, 3-Soham, 4-Leon, 5-Qiao, 6-Muhammad
Remaining survivors: 1-Leon, 2-Qiao, 3-Muhammad, 4-Nur, 5-Krystal
Remaining survivors: 1-Nur, 2-Krystal, 3-Leon, 4-Qiao
Remaining survivors: 1-Qiao, 2-Nur, 3-Krystal
Remaining survivors: 1-Qiao, 2-Nur
Nur is the last survivor!
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.
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.
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:
The constructor will likely be your longest method in this assignment. It should:
- Read all the names out of one of the provided text files (or one of your own) and create a linked list of PersonNode's with each person's name
- I recommend calling a helper method inside of your file processing loop to add the new name in a new node at the end of your list. This will be similar-ish to the add methods in 6c Reviewing ListNode and LinkedList except that we're working with PersonNodes.
- Then the singly linked list should be turned into a circularly linked list by pointing the last node's next at the first node
- In order to aid in eliminating people, you will need to continuously track the person /before/ the next person to begin counting at. At the beginning of the simulation this is the last node
- Generate and print an elimination count
- This count should not be larger than half the number of people in the list and it must be at least 1. (i.e. If there are 10 people in the list, this value should be a random number 1-5)
This method should
- Count to the next person that needs to be eliminated, moving the track field forward one node for each count in the process
- Print the person to be eliminated
- Eliminate the person that needs to be eliminated
- Update the circle's first node field pointer and the size of the circle
Returns true if there is only one person left in the circle; false otherwise.
- if the simulation is over,
- returns name of only person left as the last survivor
- prints all the people remaining in the circle
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
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.