package reaver;

/**
 * Title:         The Josephus game
 * Description:   A program that uses a one dimensional array to play the Josephus game.
 *                In this game M players form a circle and count off by N.
 *                Every Nth player is eliminated. the last one left is the Winner
 *
 * @author        Mr. Reaver
 * @version       1.0
 */

public class CountOff
{
    static int m = 21;              // Quantity of initial players.
    static int n = 9;              // Interval at which players are killed.
    static int current = m-1;        // A pointer to the current player.
    static boolean[]  circle = new boolean[m];   // The circle of players. true=alive, false=dead.
    static int round    = 1;   // Game starts at round 1.

    public static void main(String[] args)
    {
        // Degenerate cases:
        if(m==0)
        {
            System.out.println("No players in the game. No winner.");
            return;
        }

        if(n==0)
        {
            System.out.println("Cannot eliminate the 0th player. No winner.");
            return;
        }

        // Make sure everyone in the circle starts alive
        for(int i=0; i<circle.length; i++)
            circle[i] = true;

        // While the game is still going...
        while(!endOfGame(1))
        {
            printCircle();      // Display the status of the circle
            killNextPlayer();   // Kill the next n'th player
            round++;            // Update the round #
        }
        printCircle();
        System.out.println("The game has ended! The surviving players are: ");
        System.out.println("For " + m + " players counted off by " + n + ", the winner is "+getAWinner());
    }

    // ------------------------------------------------------
    // Kill the next player
    // ------------------------------------------------------
    public static void killNextPlayer()
    {
        // Move n players
        for(int i=0; i<n; i++)
        {
            moveToNextPlayer();
        }

        // Kill the 'current' guy
        circle[current] = false;
    }

    // ------------------------------------------------------
    // Move "current" to point to the next alive player
    // ------------------------------------------------------
    public static void moveToNextPlayer()
    {
        do
        {
            // Move to the next element in the array
            current = (current+1)%m;
        // Repeat if we have moved merely to a dead guy
        }while(!circle[current]);
    }

    // ------------------------------------------------------
    // Have we eliminated enough players?
    // ------------------------------------------------------
    public static boolean endOfGame(int winners)
    {
        int playersLeft = 0;

        // +1 for every alive player we find
        for(int i=0; i<circle.length; i++)
            if(circle[i])
                playersLeft++;

        // Game ends when we are left with the # winners in a game
        return playersLeft<=winners;
    }

    // ------------------------------------------------------
    // Print out the status of the circle
    // ------------------------------------------------------
    public static void printCircle()
    {
        System.out.print("Round "+round+" \t");

        for(int i=0; i<m; i++)
        {
            if(circle[i])
                System.out.print("\t"+(i+1));   // This shows the # of the existing players
            else if(i==current)
                System.out.print("\t[_]");      // This shows the last player to be killed
            else
                System.out.print("\t_");        // This shows a general dead guy
        }

        System.out.println("");
    }

    public static int getAWinner()
    {
        for(int i=0; i<circle.length; i++)
          if(circle[i])
            return i+1;
        return -1;
    }
}