The Josephus Problem works as follows.

A bunch of people sit around in a circle. A court jester is asked to choose a king from them and must kill the rest. He decides to kill every other man. So, he spares the first man, kills the second, spares the next, kills the next, etc., going around the circle until there is only one man left alive who becomes the king.

In this assignment, you need to solve find the king using three different methods:

Here is a starter kit of code. First, a Main class that sets up a CircularQueue without the josephus method written:

public class Main {

	public static void main(String[] args) {
		CircularQueue<Person> people = new CircularQueue<Person>();
		people.enqueue(new Person("Kyle"));
		people.enqueue(new Person("Toly"));
		people.enqueue(new Person("Audrey"));
		people.enqueue(new Person("Alistair"));
		people.enqueue(new Person("Phillip"));
		
		System.out.println(josephus(people) + " is the king!");
	}
	
	public static Person josephus(CircularQueue<Person> m) {
        return null;   // you need to write the real code here--null is just a placeholder
	}

Here is code for a minimalist Person class:

public class Person {
	private String name = "Anonymous";
	
	public Person() {}
	
	public Person(String name) {
		this.name = name;
	}
	
	public String toString() {
		return name;
	}
}

Here is the code for a minimal Queue interface

public interface Queue<E> {
	public boolean isEmpty();
	public void enqueue(E element);
	public E dequeue();
	public E peek();
	public E next();   	// next allows advancement through
						// the queue without dequeueing
	public int size();
}

And for a CircularQueue...

import java.util.LinkedList;
import java.util.ListIterator;

public class CircularQueue<E> implements Queue<E> {
	private LinkedList<E> ll = new LinkedList<E>();
	private ListIterator<E> li = ll.listIterator();
	
	public CircularQueue() {}
	
	public void enqueue(E o) {
		if (li.hasNext()) {
			li.next();
			li.add(o);
		} else {
			li.add(o);
		}
	}
	
	public E dequeue() {
		if (ll.size() == 0) return null;
		
		if (!(li.hasNext())) {
			li = ll.listIterator();  // go to front
		}
		
		E item = li.next();
		li.remove();
		return item;
	}
	
	public E next() {
		if (!(li.hasNext())) {
			li = ll.listIterator();
		}
		return li.next();
	}
	
	public int size() {
		return ll.size();
	}
	
	public E peek() {
		if (ll.size() == 0) return null;
		
		if (!(li.hasNext())) {
			li = ll.listIterator();  // go to front
		}
		
		E item = li.next();
		li.previous();      // back up
		return item;
	}
	
	public void print() {   // utility method
		ListIterator<E> li = ll.listIterator();
		
		while (li.hasNext()) {
			System.out.print(li.next() + ", ");
		}
	}
}

1. Write a program that solves the Josephus problem using a circular queue of people.

Now, suppose we number the people at the table, starting at 1, and going around the circle to N. It turns out that if you know N, you can determine which person will survive using binary arithmetic. Here is a table to illustrate:

Number of contenders Binary Survivor position Binary
1
1
1
1
2
10
1
1
3
11
3
11
4
100
1
1
5

101
3
11
6
110
5
101
7
111
7
111
8
1000
1
1
9
1001
3
11
10
1010
5
101
11
1011
7
111
12
1100
9
1001
13
1101
11
1011
14
1110
13
1101
15
1111
15
1111

If you take the binary number for the number of people sitting at the table (contenders), convert it to binary, then remove the first 1 in the binary number and tack it onto the end of that binary number, you get the binary value for the surviving contender. For example, suppose there are 12 contenders. 12 is written as 1100 in binary. We remove the first 1 in 1100 to leave us 100. Then we tack it on the end and have 1001. Then we convert this to decimal and get 9. This moving of the 1 is called a circular left shift. We move all the digits to the left, pushing the leftmost one off the map and wrapping it around to the last position.

It is probably easiest to do this by treating binary numbers as Strings since you can use charAt() and substring() to take a string of 0s and 1s and produce the desired result.

2. Write a Josephus solver that uses binary arithmetic and circular left shifting to determine which contender will survive.

HINT: You may find Integer.toBinaryString() and Integer.parseInt(num, 2) to be extremely helpful.

3. Write a function that uses log2N and calculates the survivor. (There is a formula--it can be done!)