The Josephus Problem

Problem Statement:

A group of soldiers is surrounded by the enemy from all the sides. There is no hope of victory for them and they have only 1 horse. In order to choose which soldier amongst them gets the chance to get on the horse and escape/call for reinforcements, they devise a method. The soldiers are arranged in a circle. A number n is picked up at random from a chit-box. Then a name is also picked up at random from another box. Starting from the soldier whose name came from the box, they count clockwise till n. When the count reaches n, that soldier is removed from the circle and is no longer counted. The counting then starts again from the next soldier. This is done continuously till only one soldier remains and that soldier is allowed to escape on the horse.

Implementation:

We use a Circular Linked List to solve the problem, as the last node in a circular list is connected to the first, thus there is no node with next address null at any time. The list is traversed n times and when a soldier has to be removed, that particular node is deleted from the list. Eventually, the list will have only 1 node pointing to itself (it is still a circular list) and containing the name of the soldier that can escape.

Now, java.util already has Linked List functionalities, yet it seemed prudent to make the readers understand the inner functionalities of the list. Hence, a new class of Circular Linked List is made complete with add, delete, search functionalities.

	import java.util.Scanner;
	public class CircularLinkedList {
	String info;
	CircularLinkedList address;
	static CircularLinkedList listPointer = null;
	static CircularLinkedList nodePointer = null;
	static int numberOfNodes = 0;
	static Scanner input = new Scanner(System.in);
	public CircularLinkedList() {
	info = "";
	address = null;
	}
	public static void main(String[] args) {
	String info;
	System.out.println("Enter the info in first node");
	info = input.next();
	addFirstNode(info);
	int choice;
	do{
	System.out.println("Enter 1 for adding a node, 2 for deleting a node, 3 to search a node, 4 to exit");
	System.out.println("What do you want to do?");
	choice = input.nextInt();
	switch(choice){
	case 1 : {
	System.out.println("Enter the info in the node");
	info = input.next();
	addNode(info);
	break;
	}
	case 2 :{
	System.out.println("Enter the info of the node you want to delete");
	info = input.next();
	deleteNode(info);
	break;
	}
	case 3 : {
	System.out.println("Enter the info of the node you want to search");
	info = input.next();
	searchNode(info);
	break;
	}
	default : System.out.println("Give appropriate choice");
	}
	}while(choice != 4);
	}
	public static void addFirstNode(String info){
	CircularLinkedList node = new CircularLinkedList();
	node.info = info;
	node.address = node;
	listPointer = node;
	nodePointer = node;
	numberOfNodes = 1;
	viewList();
	}
	public static void addNode(String info){
	CircularLinkedList node = new CircularLinkedList();
	node.info = info;
	node.address = listPointer;
	nodePointer.address = node;
	nodePointer = node;
	numberOfNodes++;
	System.out.println("Node added");
	viewList();
	}
	public static void deleteNode(String info){
	CircularLinkedList tempPointer = listPointer;
	CircularLinkedList tempNodePointer = nodePointer;
	while(!tempPointer.info.equals(info)){
	tempPointer = tempPointer.address;
	tempNodePointer = tempNodePointer.address;
	}
	tempNodePointer.address = tempPointer.address;
	listPointer = tempPointer.address;
	nodePointer = tempNodePointer;
	System.out.println(tempPointer.info + " deleted");
	numberOfNodes--;
	viewList();
	}
	public static void viewList(){
	CircularLinkedList temp = listPointer;
	for (int counter = 0; counter < numberOfNodes; counter++) {
	System.out.print("[" + temp.info + ", " + temp.address + "]");
	temp = temp.address;
	}
	System.out.println();
	}
	public static CircularLinkedList searchNode(String info){
	CircularLinkedList temp = listPointer;
	while(!temp.info.equals(info)){
	temp = temp.address;
	if(temp == listPointer){
	System.out.println("Node not in the list!!");
	return null;
	}
	}
	return temp;
	}
	}

view raw Circular Linked List hosted with ❤ by GitHub

The actual Josephus Class that calls this CircularLinkedList class is as follows:

	import java.util.Scanner;
	import <package>CircularLinkedList;
	public class JosephusProblem {
	public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	String soldierName;
	boolean isFirst = true;
	System.out.println("Enter the names of the soldiers in clockwise order. Press '-' key when done." );
	do{
	soldierName = input.next();
	if(soldierName.equals("-")){
	break;
	}
	else if(isFirst){
	CircularLinkedList.addFirstNode(soldierName);
	isFirst = false;
	}
	else{
	CircularLinkedList.addNode(soldierName);
	}
	}while(!soldierName.equals("-"));
	System.out.println("Pick up a chit from the number box. Enter the number");
	int number = input.nextInt();
	System.out.println("Pick up a chit from the name box. Enter the name");
	String name = input.next();
	josephus(number, name);
	}
	public static void josephus (int number, String name){
	CircularLinkedList startingNode, temp;
	while(CircularLinkedList.numberOfNodes != 1){
	startingNode = CircularLinkedList.searchNode(name);
	temp = startingNode;
	for (int counter = number; counter > 1; counter--) {
	temp = temp.address;
	}
	name = temp.address.info;
	CircularLinkedList.deleteNode(temp.info);
	}
	System.out.println("The soldier that can escape on the horse is : " + name);
	}
	}

view raw Josephus Class hosted with ❤ by GitHub

An example of the output is as follows:

 Enter the names of the soldiers in clockwise order. Press '-' key when done. a
[a, labWorkDSA.CircularLinkedList@ec5aba9]
b
Node added
[a, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@ec5aba9]
c
Node added [a, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@423252d6][c, labWorkDSA.CircularLinkedList@ec5aba9]
d
Node added [a, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@423252d6][c, labWorkDSA.CircularLinkedList@5fbd8c6e][d, labWorkDSA.CircularLinkedList@ec5aba9]
e
Node added [a, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@423252d6][c, labWorkDSA.CircularLinkedList@5fbd8c6e][d, labWorkDSA.CircularLinkedList@154ebadd][e, labWorkDSA.CircularLinkedList@ec5aba9]
-
Pick up a chit from the number box. Enter the number
5
Pick up a chit from the name box. Enter the name
a
e deleted
[a, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@423252d6][c, labWorkDSA.CircularLinkedList@5fbd8c6e][d, labWorkDSA.CircularLinkedList@ec5aba9]
a deleted
[b, labWorkDSA.CircularLinkedList@423252d6][c, labWorkDSA.CircularLinkedList@5fbd8c6e][d, labWorkDSA.CircularLinkedList@5388ebd2]
c deleted
[d, labWorkDSA.CircularLinkedList@5388ebd2][b, labWorkDSA.CircularLinkedList@5fbd8c6e]
d deleted
[b, labWorkDSA.CircularLinkedList@5388ebd2]
The soldier that can escape on the horse is : b