The Josephus Problem

Description

This problem goes back to Josephus Flavius, a 1st century Roman historian.  The story is slightly bloody.

 

41 rebels are trapped in a cave, surrounded by enemy troops. They decide to commit suicide: they line up in a circle and systematically kill every other one, going around and around, until only one rebel is left -- who supposedly kills himself  (fat chance). 

Who is the lone survivor? 

 

Clearly, we can represent the rebels by a list of numbers {1,2,...,41}  and we can simulate the demise of the corresponding rebel by manipulating this list.  For example, we could just mark the dead rebels by switching item i to -i (a standard hack, and a true abuse of negative numbers). Actually, it will be more interesting to generalize slightly: let us deal with the problem for an arbitrary number n of rebels. So, our original list is   {1,2,...,n} , and we have to make a n-1 deletions in the right place to find the survivor.

A good implementation will sometimes differ from a verbatim translation of the original problem. For example, marking the deceased rebels in the list without actually removing them turns out to be a bad idea: we will have to skip over the dead bodies. It is easier to actually remove items from the list. However, it is still quite complicated to do the necessary bookkeeping (we have to skip over the next element, and we have to be careful when we reach the end of the list). If we use an array to simulate this problem, the things can be quite complicated. We need to remove every other element in the array to remove dead bodies. Besides there is a huge cost to filling the holes in the array since we have to shift elements to fill the holes. Here is a simple idea that dissolves all these difficulties, once and for all. Let’s think about a linked list to do this problem. Not just a linked list, but a circular linked list. One step in our simulation will be to

 Rotate the list to the left by one position, and then delete the first element.

 

This does implement the every-other-guy protocol of the rebels. Make sure you understand why. Also note that the description of the problem is really a bit ambiguous: we might also delete the first element, and then rotate. As it turns out, the results are slightly easier to describe in the other version.

Here is a run of the simulation for   n = 16 rebels. The sequence of survivors is shown after each death, but rotated a bit. In the end, rebel number 1 is the lucky one.

    1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16
     3   4   5   6   7   8   9   10  11  12  13  14  15  16  1
     5   6   7   8   9   10  11  12  13  14  15  16  1   3
     7   8   9   10  11  12  13  14  15  16  1   3   5
     9   10  11  12  13  14  15  16  1   3   5   7
     11  12  13  14  15  16  1   3   5   7   9
     13  14  15  16  1   3   5   7   9   11
     15  16  1   3   5   7   9   11  13
     1   3   5   7   9   11  13  15
     5   7   9   11  13  15  1
     9   11  13  15  1   5
     13  15  1   5   9
     1   5   9   13
     9   13  1
     1   9
     1
 

And here are the results of the simulation for all rebel numbers up to 100. The x-axis is the number of rebels, and the y-axis is the lone survivor.

Clearly, there is a lot of regularity here. Increasing n by 1 increases the number of the survivor by 2 for a while, but then a reset occurs and the survivor number goes back to 1. It is tempting to find a nice, concise description for this effect, but we will not pursue the analysis at this time. Sometime in your life you will learn that there is a ridiculously simple way to calculate the survivor by manipulating the binary expansion of the number of rebels.

Concepts Covered

The following concepts are covered in this lab

·        Interfaces – List and Comparable

·        Circular Singly Linked Lists

·        Debugging with Testers

Files

The project is organized into the following four files:

The node.java defines Node type and methods of basic building block Node, that can be used to build a circular linked list as the main data structure. Such a list consists of nodes containing the data element (an Integer object), plus a pointer next, pointing to the next node, respectively. Moreover, the last node in the list points to the first. Thus, the nodes really form a linked circle. The list header points to the first node.

CircularLL.java is a class that contains methods necessary to solve the Josephus problem and you need to complete them as well as complete the driver program to produce the desired output.

One advice of thought is to test your circular LL class before using it in the josephus program. This way you know that your LL methods are working properly. Once you test this, solving the Josephus problem is easy.

The input/output conventions are as follows. Program can be managed from a simple command line menu.

1. Solve Josephus problem for some n 

> java josephus 41




41     19


2. Solve Josephus problem for a range of values. 

> java josephus 10 20




10     5
11     7
12     9
13     11
14     13
15     15
16     1
17     3
18     5
19     7
20     9
 

3. Solve the Josephus problem for a single value, but display the state of the line after each shooting.  Here the option “-a” indicates that we need to show all steps in the process.

 

See Josephus.java for more details. 

 
> java josephus –a 10 




 1  2  3  4  5  6  7  8  9 10 
 3  4  5  6  7  8  9 10  1 
 5  6  7  8  9 10  1  3 
 7  8  9 10  1  3  5 
 9 10  1  3  5  7 
 1  3  5  7  9 
 5  7  9  1 
 9  1  5 
 5  9 
 5
 

4. Start solving the Josephus problem, but stop when you reach a certain list size. Here –s 5 indicates that when the list reaches size 5, we need to output the remaining list. The 10 is the size of the original list

 

See Josephus.java for more details. 

 
> java josephus –a 10 –s 5




 1  3  5  7  9 
 

Procedures

The class CircularLL implements List interface (length, append and toString) as well as define new methods. You must implement the following methods.

public void clear();

public int size();

public void add(Object O);

public String toString();

public boolean contains(Object O);

public boolean isEmpty();

public Object remove(int index);

public void rotate(int n); // rotate the list by n elements. If n is positive do clockwise rotation, and if n is negative do counter clockwise rotation.


You may add any other private methods if you wish.  Note that data type inside a node object is an Integer object. You can create an Integer object from an int n using

Integer N = new Integer(n); See Integer class in the API to see which methods are useful in completing this assignment.

 

You also need to complete the driver program, josephus.java. It must take command line arguments, process them, and call the correct circular LL methods to solve the problem. You may not necessarily use all of the methods implemented from the List interface to solve the josephus problem, but implementation of all List methods is part of the assignment.

 

 

Handing in your Solution

Your solutions should be in the form of .zip files. When we grade your solution we will unzip the folder and test the code.

Your teaching assistants will show you how to zip up the files for submission.

All labs are submitted to afs. The folder to submit your program is

/afs/Andrew.cmu.edu/course/15/111-M07/handin/lab2/yourid 

 

Grading Criteria

The following grading criterion is strictly enforced.

1.      A program that does not compile  - 0 points

2.      A program that is 24 hours later – max of 50% of the grade

3.      A program that is more than 48 hours late – 0 points

100 points total, distributed as follows:

·        Circular linked list class works with Integer Tester : 50 points

·         Circular linked list class works with String Tester : 10 points

·        Solving the Josephus : 30 points

·        Style: Commenting and indenting: 10 

Make sure that your program compiles and runs properly. As usual, take the 10 style points seriously; poorly commented spaghetti code is not acceptable.