Problem

The Josephus Problem is a famous mathematical puzzle that goes back to ancient times. There are many stories to go with the puzzle. One is that Josephus was one of a group of Jews who were about to be captured by the Romans. Rather than be enslaved, they chose to commit suicide. They arranged themselves in a circle and, starting at a certain person, started counting off around the circle. Every nth person had to leave the circle and commit suicide. Josephus decided he didn’t want to die, so he arranged the rules so he would be the last person left. If there were (say) 20 people, and he was the seventh person from the start of the circle, what number should he tell them to use for counting off? The problem is made much more complicated because the circle shrinks as the counting continues.

Create an application that uses a circular linked list (like that in Programming Project 5.3) to model this problem. Inputs are the number of people in the circle, the number used for counting off, and the number of the person where counting starts (usually 1). The output is the list of persons being eliminated. When a person drops out of the circle, counting starts again from the person who was on his left (assuming you go around clockwise). Here’s an example. There are seven people numbered 1 through 7, and you start at 1 and count off by threes. People will be eliminated in the order 4, 1, 6, 5, 7, 3. Number 2 will be left.

I have managed to solve the following problem but I am afraid my code might contain bad practices or there might be ways to improve it. I would appreciate if someone can point out how I can make my code better as it will help me learn to write more beautiful code.

Node Class

public class Node {

    public int iData;
    public Node next;

    public Node(int x) {
        iData = x;
    }

    public void displayNode() {
        System.out.print(iData + " ");

    }

}

Code for Circular Linked List

public class CircularList {

    private Node first;
    private Node last;
    private Node current;
    private int count; // total items in the list
    public CircularList getCurrent;

    public CircularList() {
        first = null;
        last = null;
        current = null;
        count = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void step() {
        current = current.next;
    }

    public Node getCurrent() {
        return current;
    }

    public Node getFirst() {
        return first;
    }

    public void insert(int x) {
        Node newNode = new Node(x);

        if (isEmpty()) {
            first = newNode;
            current = first;
        } else {
            current.next = newNode;
        }

        newNode.next = first;
        last = newNode;
        step();
        count++;
    }

    public boolean search(int x) {
        Node search = first;
        int y = 0;

        while (search.iData != x && y < count) {
            search = search.next;
            y++;
        }

        if (search.iData == x) {
            System.out.println("Found the value: " + search.iData);
            return true;
        } else {
            System.out.println("Value not found in list");
            return false;
        }

    }

    public void delete(int x) {
        Node prev = first;
        Node curr = first.next;

        while (curr.iData != x) {
            prev = curr;
            curr = curr.next;

        }

        if (count == 1) {
            first = null;
            count--;
        } else if (curr == first) {
            prev.next = curr.next;
            first = curr.next;
            count--;
        } else {
            prev.next = curr.next;
            count--;
        }

    }

    public void displayList() {
        int x = 0;
        Node printer = first;

        while (x < count) {
            printer.displayNode();
            printer = printer.next;
            x++;
        }
        System.out.println("");

    }

}

Josephus Class

public class Josephus {

    private int numOfPeople; // number of people in a circle
    private int countNum; // number used for counting off
    private Node head;
    private Node tail;
    CircularList circle;

    public Josephus() {
        circle = new CircularList();
        numOfPeople = 0;
        countNum = 0;

    }

    public void setNumOfPeople(int x) {
        numOfPeople = x;

    }

    public int getNumOfPeople() {
        return numOfPeople;
    }

    public void setCountNum(int x) {
        countNum = x;
    }

    public int getCountNum() {
        return countNum;
    }

    public void addPeople() {
        for (int i = 1; i < numOfPeople; i++) {
            circle.insert(i);
        }
    }

    public void move() {

        for (int i = 0; i < countNum; i++) {
            tail = head;
            head = head.next;
        }

        System.out.println("KILLED : " + head.iData);

    }

    public void execute() {
        tail = null;
        head = circle.getFirst();
        while (numOfPeople != 2) {

            move();
            circle.delete(head.iData);
            tail = tail.next;
            head = head.next;
            numOfPeople--;
            display();
        }

    }

    public void display() {
        System.out.print("Alive:  ");
        circle.displayList();
    }

}

Main Class

public class Test {

    public static void main(String[] args) {
        Josephus suicide = new Josephus();

        suicide.setNumOfPeople(8);
        suicide.addPeople();
        suicide.display();

        suicide.setCountNum(3);
        suicide.execute();

    }

}

Output

Alive:  1 2 3 4 5 6 7 
KILLED : 4
Alive:  1 2 3 5 6 7 
KILLED : 1
Alive:  2 3 5 6 7 
KILLED : 6
Alive:  2 3 5 7 
KILLED : 5
Alive:  2 3 7 
KILLED : 7
Alive:  2 3 
KILLED : 3
Alive:  2
  • You have not even started to solve the problem. You are supposed to be able to compute which step number Josephus would give them to start the count so that he will be last surviving person. – toto2 Aug 24 '14 at 17:34
  • @toto2 i thought that was the problem, to figure out who is left alive. techyrajeev.blogspot.com/2012/02/… i came across this solution and they come up with similar solution – user2733436 Aug 24 '14 at 17:45
  • The link you give is just an implementation of a circularly linked list with a removal method. It does not solve the problem which is described in your post: What step value should Josephus give them if he is 7 out of 20? – toto2 Aug 24 '14 at 17:50
  • @toto2 yea you are right, what i did was read the problem and looked online and noticed that many solutions such as this also webspace.ship.edu/deensley/mathdl/Joseph.html were simply showing the order of elimination. So i should take this a step further. if you can make any suggestions as to how i should go from here i will be glad. i apologize. – user2733436 Aug 24 '14 at 17:51
  • See Also: stackoverflow.com/a/29803864/300311 – Erick Robertson Apr 28 '15 at 3:21
up vote 3 down vote accepted

[Not a review of your solution, since it does not exist yet, but a review of your CircularList so far.]

It does not make much sense to have a first and last node in a circularly linked list. Maybe you can keep a node as an entry point, but you should not make it visible. You should actually not make any node accessible at all from CircularList.

The search and delete methods are ambiguous, unless each value can only be present once in a CircularList. If you decide do use this convention, you should check that a value is not a duplicate at insertion.

Defining an insertion method is quite tricky. About the only possibility I see is to insert some value before or after the first instance of some target value. It is better to not have an insertion method. You would only add values at construction; the constructor would take in a list of values.

You can easily make CircularList generic. It requires only a few modifications.

CircularList

You assign to last, but never use last in any other way. You could just eliminate that useless member variable. Also, the search() method is never used.

Your design keeps a reference to a node as a kind of insertion/deletion cursor. That's fine, but I don't see why there should be a first and a current node, not to mention why a getFirst() method should be exposed. If the list is circular, then there should be no "first" node. If you have a deletion cursor, then the .delete() method should take no parameters — it should just delete whichever node is the current one.

Your code would be more standard and versatile if you implemented .toString() instead of .displayList().

Josephus

You have an off-by-one error in addPeople(), causing one fewer person to be added.

This class lacks coherence. To start with, the constructor is what I would call "half-assed". After constructing a Josephus object, it's not in a useful state until you call .setNumOfPeople() and .addPeople().

Is it ever useful to call .addPeople() twice? Probably not, as doing so would put the Josephus object in a weird state. Therefore, you should design your classes such that each object enforces its own consistency. In this case, setting the number of people and populating the circular list is initialization logic, which should be available through the constructor and only through the constructor:

public Josephus(int numberOfPeople) {
    circle = new CircularList();
    for (int i = 0; i < numberOfPeople; i++) {
        circle.insert(i);
    }
}

public int getNumberOfPeople() {
    // You should implement CircularList.size() if you want a getNumberOfPeople()
    return circle.size();
}

The setCountNum() and associated methods should be named setSkip() etc. In my opinion, it should default to 1, because 0 is not useful.

Does the execute() method execute one person, or does it execute the entire simulation? It's not clear without reading the code.

Your CircularList has a concept of a "current" node, so I don't see why the Josephus class also needs to keep references to specific head and tail nodes. Not only is it duplicating work that should be done by the CircularList, it is also violating the abstraction by meddling with its internals.

Simplification

That is a lot of code to write to solve this problem. Given that Java has a built-in LinkedList class, you should try to take advantage of it. Note that you don't need to actually implement a circular list by manipulating pointers; you merely need to provide the illusion that the list is circular by implementing an iterator.

This is an interesting problem. In the original Josephus problem, there are 41 men with every third selected (N=41, step=3, start=1). Here's one way to solve it using collections in java.util:

import java.util.*;

public static void main(String[] argv) 
{
    List<Integer> r;
    System.out.println(r = josephus(41, 3, 1));                     // show entire sequence
    System.out.printf("Person %d is last\n", r.get(r.size() - 1));  // who's last?
}

// remove N elements in equal steps starting at specific point
static List<Integer> josephus(int N, int step, int start)
{
    if (N < 1 || step < 1 || start < 1) return null;

    List<Integer> p = new LinkedList<Integer>();
    for (int i = 0; i < N; i++)
        p.add(i+1);

    List<Integer> r = new LinkedList<Integer>();
    int i = (start - 2) % N;
    for (int j = N; j > 0; j--) {
        i = (i + step) % N--;
        r.add(p.remove(i--));
    }

    return r;
}

josephus(41,3,1)

On this image from here, n is used instead of N and m instead of step in the code above. start value is 1, which is common.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.