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.

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

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