DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Solving the Josephus Problem with StringBuffer and User-Inputs

1. Registered User
Join Date
Jun 2010
Posts
7

## Solving the Josephus Problem with StringBuffer and User-Inputs

Hello, everyone. I'm a first-year Computer Science student just taking my first Java class in the summer. We've been assigned to solve the ever-famous Josephus problem. I know that this forum has a previous post on the topic,
HTML Code:
`http://forums.devx.com/showthread.php?t=150127&highlight=josephus`
but I don't believe anyone posted the solution to the thread-starter's answer. I've used some of aesoprock00's coding in my own program.

This is my prompt: "N knights, numbered 0 to N-1, are sitting in a circle. Starting at person 0, a ball is passed. After M people touch the ball, the person holding the ball is eliminated, the circle closes ranks, and the game continues with the person sitting after the eliminated person starting with the ball. The last person remaining wins."

Write a program to accept two user inputs (not command line inputs) representing N (the number of people in the circle) and M (the number of people required to touch the ball before a person is eliminated). Initialize a StringBuffer to consist of the characters numbered 0 through N-1 (note: since there are (2)^16 = 65,536 Unicode characters, your program should be capable of solving Josephus' Problem up to this value of N).

This is my breakdown for solving the problem:

1. Use Scanner class to have user input two values for N and M.

2. Construct a StringBuffer such that characters from 0 to N-1 are accepted. In this case, the code would be: StringBuffer str = new StringBuffer(316574).

3. Construct an array to hold the character values of the killed off knights.

4. Construct a mechanism for solving the Josephus problem. The mechanism should be capable of calling values from the StringBuffer, store the values of the deleted knights into the array, and also remove the character values of the deleted knights from the StringBuffer. I used a series of "for" loops to achieve this.

Here is my code.

Code:
```public class JosephusTrial {

public static void main(String[] args) {
//Initiates the variables N and M for later use.
int N = 0;
int M = 0;

//Initiates index variable to use in later "for" loop.
int index = 0;

//Inputs Scanner object.
Scanner cmd = new Scanner(System.in);

//Asks user for input regarding the number of knights.
System.out.println("How many knights will be participating?");
String people = cmd.nextLine();
System.out.println("There will be " + people + " knights.");

//Asks user for input regarding the number of knights
//that must touch the potato before elimination.
System.out.println("Who will be the last person to touch the ball?");
String touch = cmd.nextLine();

System.out.println("Every " + touch + "nd " +
"person to touch the ball " + "will die.");

//Converts String inputs to integers.
N = Integer.parseInt(people);
M = Integer.parseInt(touch);

//Initiates Array to store the values of each killed knight.
int[] deleted = new int[N-1];

//Creates a new StringBuffer for the program.
//Since program must work for values 1 to 63,536, I added and set String
//Buffer capacity equal to total characters of all the numbers: 316,574.
int buffersize = 316574;
StringBuffer josephus = new StringBuffer(buffersize);
//int testbuffersize = josephus.capacity();
//System.out.println(testbuffersize);

//Creates each knight from N as a separate value.
for(int i = 0; i < N; i++) {
josephus.append((char)(i + 1));
}
//Starts loops that solves Josephus problem.
for(int i = 0; i < N-1; i++) {
if((index + M) > josephus.length()) {
index = (index + M) % (N);
//Calls the value of the killed knight from StringBuffer, stores
//it into Array, and then removes it from StringBuffer
deleted[i] = (int)josephus.charAt(index);
josephus.delete(index, (index+1));

} else{
index = (index + M);
deleted[i] = (int)josephus.charAt(index);
josephus.delete(index, (index+1));
}
}
System.out.println("Therefore, Knight No. " + " is the lone survivor.");
}
}```
The code is faulty at best. I've only studied Java for a month now and I have a bare-minimum understanding of the concepts I have to use in this program. I know for a fact that a "StringIndexOutOfBoundsException: String index out of range: 8" message will occur for the 3rd line of the else loop. However, my biggest problem is in creating the correct number of "spaces" in the StringBuffer, and then in using the right variables for the "for" loops and type-casting the output of the loops into the array.

Please assist in any way you can. Thank you.

2. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
You could debug your code by adding System.out.println() statements at many points int the program to show how variables' values change.

3. Registered User
Join Date
Jun 2010
Posts
7
Thanks for the reply, Norm. I'd appreciate it if you could point out a few places where adding println statements might help.

4. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
Look at the logic of the code. Any time that it computes a value, print it.
When it uses a value to index into a array, print it.

Why are you getting an out of bounds exception? Where is the index computed? What are the parts that go into computing that index? Show them.

5. Registered User
Join Date
Jun 2010
Posts
7
Thank you for your continued response.

Your advice helped me a lot in figuring out the coding for the first for loop that creates individual char values of the knights and stores them into the stringbuffer. However, I'm still having a problem designing the correct mechanism for solving the josephus problem. I'd appreciate it very much if you would take a second look at my for loop for that mechanism and point out how to correct my flaws. I'm posting that section of code again:

Code:
```//Starts loops that solves Josephus problem.
for(int i = 0; i < N; i++) {
if((index + M) > N) {
index = (index + M) % (N);
//System.out.println(index);
//Calls the value of the killed knight from StringBuffer, stores
//it into Array, and then removes it from StringBuffer
deleted[i] = (int)josephus.codePointAt(index);
System.out.println(deleted[i]);
josephus.delete(index, (index + 1));

} else{
index = (index + M);
deleted[i] = (int)josephus.codePointAt(index);
System.out.println(deleted[i]);
josephus.delete(index, (index + 1));
}
}```
Also, do you know how to print out the entire contents of a stringbuffer? I need that piece of information for my concluding println statement.

6. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
print out the entire contents of a stringbuffer
Can you create a String from its contents and print that? See the API doc for StringBuffer.
Or if too big, there are methods to create substrings.

Re your logic. Can you explain what the code you just posted is supposed to do. At the step by step level. For example why do you do this: index = (index + M) &#37; (N);

7. Registered User
Join Date
Jun 2010
Posts
7
Regarding the Stringbuffer: I followed your advice and tried placing the contents of the stringbuffer josephus into a new string called bufferstorage. I then attempted to print out the string; It did not print out. I'm pretty sure that I used the correct print method for the string, but you're probably a better judge than me:

Code:
```String bufferstorage = new String(josephus);
System.out.println(bufferstorage);```
NOTE: I inputted these statements after I double-checked that the stringbuffer does indeed have characters stored inside it. Perhaps I have to use substrings? If so, please let me know the correct method of doing so?

As for the logic behind the problem, I'll try to breakdown the mechanism for solving the Josephus problem as I understand it:

1. I need to create a "for" loop that creates individual values for N (the knights) and then store them into Stringbuffer josephus using the .append method: (This part is completed successfully)

Code:
```for(int i = 0; i < N; i++) {
josephus.append((char)(i + 1));
System.out.println("Knight No. " + (i + 1) + " created.");
}```
2. Next, I need to create a loop that continuously cycles through the entire contents of Stringbuffer josephus while deleting the character values stored at M (number of knights who touch ball before elimination) intervals. In addition to this, I need to find a way of storing all the deleted values into the array "deleted", while also making sure that Stringbuffer josephus keeps getting smaller and smaller till only 1 char value remains from N.

I copied most of the code used in the previously-posted sample from aesoprock00, another forum member who posed a similar problem 4 years back.
HTML Code:
`http://forums.devx.com/showthread.php?t=150127`
He believed that the code sample was successful in achieving the results; It hasn't worked for me. I was hoping that someone with more experience with Java would help me fix his sample so that it became functional.

8. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
What was the length of the String you tried to print? Did it have any non-visible characters in it? Characters less in value than a space.

System.out.println(deleted[i]);
Your println() should have more info than just the data:
System.out.println("dlted >" + deleted[i] + "< @ i=" + i + ", index=" + index);

I would think that the output would show you where the logic is wrong.
If I were to try to debug your code, that is the approach I'd take.

9. Registered User
Join Date
Jun 2010
Posts
7
Just to clarify, I'm not looking for the length of the String. I am already able to find it using the "Stringbuffer.length" method. Instead, I am trying to make the StringBuffer print out all of the char values it has stored. Technically, after the josephus problem is solved, StringBuffer should only have 1 value left from what it started. I am trying to see that value in my output. For different values of N and M, that single value left in the buffer could be in any position. Therefore, I can't use a index-specified method like Stringbuffer.codePointAt() to get the correct solution each time.

I debugged my coding a bit after you posted that println suggestion. However, it's taking me a little time to get through all the scenarios. Please give me an hour or so to check through it. I appreciate your patience with me. Here's what I've gotten through so far:

Code:
```for(int i = 0; i < N; i++) {
if((index + M) > N - 1) {
index = (index + M) % (N);
//System.out.println(index);
//Calls the value of the killed knight from StringBuffer, stores
//it into Array, and then removes it from StringBuffer
deleted[i] = josephus.charAt(M - 1);
//System.out.println(deleted[i]);
josephus.deleteCharAt(M - 1);

} else{
index = (index + M);
deleted[i] = josephus.charAt(M - 1);
System.out.println("dlted >" + deleted[i] + "< @ i=" + i +
", index=" + index);
josephus.deleteCharAt(M - 1);
}
}```
I'm recieving an out of bounds error at the "deleted[i] =josephus.charAt(M-1)" within the if loop because I believe that the (M-1) value is smaller than josephus.length. Please let me know how to correct this mistake.

10. Registered User
Join Date
Jul 2005
Location
SW MO, USA
Posts
299
I believe that the (M-1) value is smaller than josephus.length
Do you mean the M = 0 so M-1 is -1?

Where is the value of M set? Where is it changed? Why does the change code allow it to go to 0 if the logic requires that it be > 0?

11. Registered User
Join Date
Jun 2010
Posts
7
I'm so sorry about not answering your original question. The println(bufferstorage) method printed out a large blank gap in the output. Please take this information in consideration with my post just above this one (I need to solve both of these problems to get the correct program).

12. Registered User
Join Date
Jun 2010
Posts
7
Never mind, Norm, I was able to solve the program. I'm posting the full, fully-working code in case anyone in the future needs to use it. Thanks again for all your help.

Code:
```import java.io.*;
import java.util.Scanner;

public class JosephusTrial {

public static void main(String[] args) {
//Initiates the variables N and M for later use.
int N = 0;
int M = 0;

//Initiates index variable to use in later "for" loop.
int index = 0;

//Inputs Scanner object.
Scanner cmd = new Scanner(System.in);

//Asks user for input regarding the number of knights.
System.out.println("How many knights will be participating?");
String people = cmd.nextLine();
System.out.println("There will be " + people + " knights.");

//Asks user for input regarding the number of knights
//that must touch the potato before elimination.
System.out.println("Who will be the last person to touch the ball?");
String touch = cmd.nextLine();

System.out.println("Every " + touch + "nd " +
"person to touch the ball " + "will die.");

//Converts String inputs to integers.
N = Integer.parseInt(people);
M = Integer.parseInt(touch);

//Initiates Array to store the values of each killed knight.
final int arraysize = (N - 1);
int[] deleted = new int[arraysize];
//System.out.println(deleted.length); Double-checks spaces available in
//array to be (N - 1) spaces.

//Creates a new StringBuffer for the program.
//Since program must work for values 1 to 63,536, I added and set String
//Buffer capacity equal to total characters of all the numbers: 316,574.
int buffersize = 316574;
StringBuffer josephus = new StringBuffer(buffersize);

//Creates each knight from N as a separate value.
for(int i = 0; i < N; i++) {
josephus.append((char)(i + 1));
System.out.println("Knight No. " + (i + 1) + " created.");
}

//Starts loops that solves Josephus problem.
for(int i = 0; i < N - 1; i++) {
if((index + M) > (josephus.length()) - 1) {
index = (index + (M - 1)) % josephus.length();
//Calls the value of the killed knight from StringBuffer, stores
//it into Array, and then removes it from StringBuffer
deleted[i] = josephus.charAt(index);
System.out.println("Knight No. >" + deleted[i] + "< is dead");
josephus.deleteCharAt(index);

}
else{
index = (index + (M - 1));
deleted[i] = josephus.charAt(index);
System.out.println("Knight No. >" + deleted[i] + "< is dead");
josephus.deleteCharAt(index);
}
}

int char1 = josephus.charAt(0);

System.out.println("Therefore, Knight No. " + char1 +
" is the lone survivor.");

}
}```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source