Given the Josephus Problem.

Josephus Problem

N people (numbered 1 to N) are standing in a circle. Person 1 kills Person 2 with a sword and gives it to Person 3. Person 3 kills Person 4 and gives the sword to Person 5. This process is repeated until only one person is alive.

Task: (Medium) Given the number of people N, write a program to find the number of the person that stays alive at the end. (Hard) Show each step of the process.

(The description from Sololearn application)"

This is my code. The forEachRemaining method solution is correct? I have to do something with this inherited method, but it has no meaning.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.function.Consumer;

class CyclicIterator implements Iterator {

private final List list;
private Iterator iterator;

public CyclicIterator(List list) {
    this.list = list;
    initIterator(list);
}

private void initIterator(List list) {
    this.iterator = list.iterator();
}

@Override
public boolean hasNext() {
    return !list.isEmpty();
}

@Override
public Object next() {
    if (!this.iterator.hasNext())
        initIterator(list);
    return this.iterator.next();
}

@Override
public void remove() {
    this.iterator.remove();
}

@Override
public void forEachRemaining(Consumer action) {
    throw new UnsupportedOperationException("This method has no meaning in CyclicIterator class!");
}
}

public class JosephusProblem {

public static void main(String[] args) {
    execution(0);
    execution(1);
    execution(2);
    execution(4);
    execution(6);
}

private static void execution(int members) {
    if (members < 1) {
        System.out.println("The parameter (members) has to be bigger than 0!");
        return;
    }
    if (members == 1) {
        System.out.println("There is olny one person, so he is the survivor. Peaceful version! :)");
        return;
    }
    LinkedList<Integer> list = new LinkedList();
    for (int index = 0; index < members; index++)
        list.add(index + 1);
    Iterator<Integer> it = new CyclicIterator(list);
    System.out.println("For " + members + " members: ");
    while (members-- > 1) {
        System.out.print(it.next() + " kills " + it.next() + ", ");
        it.remove();
    }
    System.out.println("\n The survivor: " + it.next());
}

}

The documentation for forEachRemaining states that the behavior is equivalent to

while (hasNext())
    action.accept(next());

so why not just put that there?

  • I think that would be an infinite loop. The hasNext() is always true if the list is not empty. – MAttti Nov 15 at 21:28
  • Of course the next line has a next() call in it … action.accept(next()). – K.Nicholas Nov 15 at 22:48

Your indentation is off: there should be a level also after class, not only in methods:

class CyclicIterator {
    // Class members here
}

Always try to instantiate to an interface, not an implementation: This:

LinkedList<Integer> list = new LinkedList();

Should be:

List<Integer> list = new LinkedList<>();

Note there the diamond operator <> to actually get a genericized list. Without it, you should have got a compiler warning about using raw lists. The diamond operator is shorthand for giving the generic type to the implementation: List<Integer> list = new ArrayList<Integer>();

I would also prefer using System.out.format to just smashing strings together in a println call: System.out.format("For members %s:%n");

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.