QuestionQuestion

Transcribed TextTranscribed Text

The Josephus Circle The Josephus Circle The Josephus Problem is an interesting logic problem that is often referenced in Computer Science and Mathematics. Below is a description of the problem: "There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive." Visualizing the Problem Below shows one instance of the problem with n = 4 and k = 2. At each step the current position of the game, called the cursor, is highlighted. From this position the cursor moves k positions to the left (or right, in this case). The player at that position is removed and the cursor moves again. The game continues until only one play remains. 1. The players are arranged into a circle and one player is assigned the cursor (Santiago): 2. The cursor is moved k=2 steps to the right: 3. Billy is removed and now Anna has the cursor: 4. The cursor is moved k=2 steps to the right: 5. Arya is removed and Anna once again has the cursor: 6. The cursor is moved k=2 steps to the right: 7. Only Santiage remains, who is declared the winner. Solving the Problem with a Linked List This problem can be modeled with a circular linked list, where the last node in the list references the first node in the list. Notice how you can use the links below to solve the Josephus problem from left-to-right. You can also model the problem with a circular doubly linked list. This allows the problem to be solved from left-to-right and right-to-left. We will use this data structure for our solution to the problem. Getting Started Begin by downloading the following starter files: Each of the files are described below: JosephusGame This file solves the Josephus problem using the student-completed JosephusCircle class. DO NOT ALTER THIS FILE! GameException An unchecked custom exception class that must be completed by you. Direction An enum that is used to determine if the Josephus problem is solved left-to-right or right-to-left. The enum supports the following values: LEFT, RIGHT. JosephusNode A doubly-linked list node. This node class is not an inner class, so you will need to use getters/setters to access the fields in the class. They should not be public. JosephusCircle This class manages a doubly-linked list of players. Your job is to implement this doubly linked list according to the methods below The JosephusGame class will then call each of the methods to solve the Josephus problem. The methods and their Javadocs are listed below: Method Javadoc Description public JosephusCircle(int playerCount) Creates a new JosephusCircle object with the maximum players given. @param playerCount the maximum number of players that can play in this circle public void addPlayer(String player) Adds a new player to the game from left-to-right in the internal linked list. @param player the new player name @throws GameException thrown when the maximum number of players has already been reached and this method is invoked public void circularize() Converts the internal linked list that maintains this circle of players into a circular linked list. public String moveCursor(Direction direction, int steps) Moves the current player (the cursor) from the current position the given number of steps to the left or right @param direction which direction to move the cursor @param steps how many steps to move the cursor @return the player the cursor ends up on after moving public void removeAtCursor(Direction direction) Removes the player at the cursor position from the circle. @param direction moves the cursor one position to the left or right depending on the direction public String getCircle() Returns a string representing the internal state of the circle, with the following format: <-- Player A <--> Player B <--> Player C <--> Player D --> @return a string representation of the circle of players public boolean isGameOver() Returns true if the game is over. That is, this method will return true if only one player remains in the circle. @return true if game over, otherwise false Example Output Below is two examples of output as the program is running. Your output should directly mirror this text. Example #1 - Left-to-right with n=4, k=2 Welcome to the Josephus game! Please enter a number of players: 4 Please enter a number of steps: 2 Please enter the direction the game will be played (left/right) left Enter player name: santiago Enter player name: arya Enter player name: billy Enter player name: anna Current circle: <-- SANTIAGO <--> arya <--> billy <--> anna --> Moving 2 to the left. Removed player: billy Current circle: <-- santiago <--> ARYA <--> anna --> Moving 2 to the left. Removed player: anna Current circle: <-- santiago <--> ARYA --> Moving 2 to the left. Removed player: arya Game over! The winner is: santiago Example #2 - Right-to-left with n=10, k=7 Welcome to the Josephus game! Please enter a number of players: 10 Please enter a number of steps: 7 Please enter the direction the game will be played (left/right) right Enter player name: josh Enter player name: terrance Enter player name: simbi Enter player name: lawrence Enter player name: sarah Enter player name: cho Enter player name: juan Enter player name: ichiro Enter player name: lilly Enter player name: william Current circle: <-- JOSH <--> terrance <--> simbi <--> lawrence <--> sarah <--> cho <--> juan <--> ichiro <-- > lilly <--> william --> Moving 7 to the right. Removed player: ichiro Current circle: <-- josh <--> terrance <--> simbi <--> lawrence <--> sarah <--> cho <--> juan <--> LILLY <--> william --> Moving 7 to the right. Removed player: cho Current circle: <-- josh <--> terrance <--> simbi <--> lawrence <--> sarah <--> JUAN <--> lilly <--> william --> Moving 7 to the right. Removed player: sarah Current circle: <-- josh <--> terrance <--> simbi <--> lawrence <--> JUAN <--> lilly <--> william --> Moving 7 to the right. Removed player: juan Current circle: <-- josh <--> terrance <--> simbi <--> lawrence <--> LILLY <--> william --> Moving 7 to the right. Removed player: william Current circle: <-- JOSH <--> terrance <--> simbi <--> lawrence <--> lilly --> Moving 7 to the right. Removed player: simbi Current circle: <-- josh <--> terrance <--> LAWRENCE <--> lilly --> Moving 7 to the right. Removed player: terrance Current circle: <-- josh <--> LAWRENCE <--> lilly --> Moving 7 to the right. Removed player: lilly Current circle: <-- JOSH <--> lawrence --> Moving 7 to the right. Removed player: lawrence Game over! The winner is: josh

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/*
*
*
* JosephusCircle.java
*
* This class will let the user input all the information for the game
* and have updates the the current game status
*/

package game;

import exceptions.GameException;

/**
* This is the JosephusCircle class.
*
* @author Davy Jones
* @version 1.0
*
*/
public class JosephusCircle {

// fields
private int playerCount;
private JosephusNode head;
private JosephusNode cursor;

/**
* This is the JosephusCircle constructor that takes in an int playerCount.
*
* @param playerCount
*            This is an int input to generate int number of players.
*/
public JosephusCircle(int playerCount) {
this.playerCount = playerCount;
}

/**
* This method adds players to the liked list of player string type.
*
* @param player
*            This parameter take in a string that assigns a name to the player.
*/
public void addPlayer(String player) {
if (head == null) {
head = new JosephusNode(player, null, null);
cursor = head;
} else {
JosephusNode current = head;
int count = 1;
while (current.getNext() != null) {
current = current.getNext();
count++;
}
if (count >= playerCount)
throw new GameException("Error: Cannot add player. Maximum number of players has already been reached.");
else
current.setNext(new JosephusNode(player, null, current));

}
}

/**
* This method converts the internal linked list that maintains the circle of...

By purchasing this solution you'll be able to access the following files:
Solution.docx and JosephusCircle.zip.

$45.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats