dcsimg


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 12 of 12

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

Hybrid View

  1. #1
    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. #2
    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. #3
    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. #4
    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. #5
    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. #6
    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. #7
    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. #8
    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. #9
    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. #10
    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. #11
    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. #12
    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.");
            
        }
    }

Similar Threads

  1. Josephus Problem, problem.
    By aesoprock00 in forum Java
    Replies: 2
    Last Post: 01-28-2006, 07:18 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center