## Thursday, November 18, 2010

### Count Out (The Josephus Problem)

This problem was given in class.

n children are arranged in a circle and m words are used to count out the children in rounds. The last child wins.

The Problem
Given n children and m words and a starting position (say child 1), who wins?

This is a variation of the Josephus problem.

Here is a Java solution. Simply call josephus(n, m, s) to run.

/**
* Performs the counts in rounds and returns the index of the winner.
* circle is assumed to be an array of size n.
* @param n The number of children
* @param m The number of words
* @param start The starting position
* @return
*/
private int josephus(int n, int m, int start){
initialize(n);
int i = start;
while(circle[i] != i){
int pos = i;
int prev = pos;
for(int j = 1; j < m; j++){
prev = pos;
pos = circle[pos];
}
//remove current position
circle[prev] = circle[pos];
i = circle[pos];
}
return i;
}

The initialize(n) method simply initializes the circle array  so that each  position 0 points to position 1, position 1 points to position 2 etc. That is, position i points to position i + 1. This indicates that the circle is full. To drop a child out at position i, then position i - 1 will point to position i + 1.

/**
* Initializes the circle array.
* m <= n
* @param n Number of persons
*
*/
private void initialize(int n){
circle = new int[n];
for (int i = 0; i < n - 1; i++){
circle[i] = i + 1;
}
circle[n-1] = 0;
}