Josephu's Circle

[Pyrexkidd]

Here is my attempt at Josephu's Circle problem. Curious to see if anyone had a different approach.

Best Regards.
PK

/*
 * Titus Flavius Josephus was an important first-century historian.
 * Having survived the siege and destruction of Jerusalem in 70 AD,
 * he authored several works on Jewish history, including The Jewish War
 * and Antiquities of the Jews. Not only have his writings given valuable
 * insight into first century Judaism, they provide an extra-Biblical
 * account of early Christianity. But aside from the books, and the writings,
 * and all of his other invaluable contributions to history, Josephus also told
 * the story of how he had escaped death by quickly standing in the "safe spot"
 * of what is now called Josephus’ Circle.

 * As the legend goes, Josephus and forty of his fellow soldiers retreated
 * from the siege of Yodfat to a small cave in the hills.
 * Surrounded by the Roman legion with no chance of escape, the soldiers saw
 * no other choice but to commit suicide. Like the people of Masada,
 * they would rather die than face capture.

 * In order to decide who would die in which order,
 * the soldiers stood in a circle and,
 * starting with the top of the circle and continuing clockwise, counted to three.
 * The third man got the ax and the counting resumed at one.
 * The process continued until there was no one left.
 * Josephus, who didn't quite agree with
 * the whole "we should all kill ourselves" idea,
 * figured out the perfect way to avoid death: be the last man standing.
 *
 * Your challenge: write the Josephus function.
 * There should be two inputs (number of soldiers, soldiers to skip)
 * and one output (index of the safe spot).
 *
 * Original Post:
 * http://thedailywtf.com/Articles/Programming-Praxis-Josephus-Circle.aspx
 */

package JosephusCircle;
import java.util.Scanner;

public class  JosephusCircle{

    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);

        //Initialize variables
        int solders, counting_index, numAlive;
        int counter = 0;
        boolean lastOneStanding = false;

        //Input Values
        System.out.print("Please Enter the Number of Soilders: ");
        numAlive = solders = console.nextInt();
        System.out.print("Please Enter How Many to skip: ");
        counting_index = console.nextInt();

        //Initialize array, solders alive are considered "True"
        boolean unit[] = new boolean[solders];
        for (int i = 0; i < unit.length; i++){
            unit[i] = true;
        }


        //loop iterates while lastOneStanding = false
        while(!lastOneStanding){
              // iterate through the array
              for( int i = 0 ; i < unit.length; i++){
                //Check if solder at position i is alive
                if (unit[i]){
                    counter++;
                    // counter == counting index kill that soldier
                    if (counter == counting_index){
                        counter = 1;
                        numAlive--;
                        unit[i] = false;
                    }
                }
            }
            //if numAlive == 1 set lastOneStanding to true to exit loop
            if (numAlive == 1){
                lastOneStanding = true;
            }
        }

        //Find location for last living solder
        int i = 0;
        for ( ; !unit[i]; i++ ){}
        System.out.print("Best Location to Stand: " + (i + 1) + "\n");
    }

}

[Eranga]

What you really want to know? Do you have any errors, or you are looking for an alternative?

[Pyrexkidd]

No, No errors.

Just curious if any one had a more elegant and/or efficient way of implementing this.

I kinda have a brute force method of coding and would like to improve my code.

So really I'm looking for ways to improve my code.

[JosAH]

Here is my attempt at Josephu's Circle problem. Curious to see if anyone had a different approach.

Here's a different approach:

import java.util.ArrayList;
import java.util.List;

public class T {

	public static void main(String[] args) throws Exception {

		List<Integer> people= new ArrayList<Integer>();
		
		for (int i= 0; i < 41; i++)
			people.add(i);
		
		int axe= 0;
		while (people.size() > 1)  {
			axe+= 3;
			axe%= people.size();
			people.remove(axe);
			System.out.println(people);
		}
		
	}
}

kind regards,

Jos

[rgrant222]

Try this. It's practically the same as Jos' version, but a little more object-oriented and flexible.

import java.util.ArrayList;

public class JosephusCircle {
    public static void main(String[] args) {
	int totalSoldiers = 0, numberToCount = 0;

	try {
		totalSoldiers = Integer.valueOf(args[0]);
		numberToCount = Integer.valueOf(args[1]) - 1;
	} catch (Exception ex) {
		System.err.println("syntax: JosephusCircle [totalSoldiers] "
				+ "[numberToSkip]");
		System.exit(1);
	}
	
	if (totalSoldiers < 1) {
		System.err.println("There must be at least one soldier!");
		System.exit(1);
	}

	if (numberToCount == 0) {
		printSafeSpot(totalSoldiers);
	}

	ArrayList<DeadManWalking> soldiers =
			new ArrayList<DeadManWalking>(totalSoldiers);

	for (int spot = 1; spot <= totalSoldiers; spot++) {
		soldiers.add(new DeadManWalking(spot));
	}

	int handOfDeath = 0;
	while (soldiers.size() > 1) {
		handOfDeath += numberToCount;
		handOfDeath %= soldiers.size();
		soldiers.remove(handOfDeath);
	}

	printSafeSpot(soldiers.get(0).getInitialSpot());
    }

    private static void printSafeSpot(int spot) {
	System.out.format("Safe spot is position %d.%n", spot);
	System.exit(0);
    }

}

class DeadManWalking {
    private int initialSpot;

    public DeadManWalking(int initialSpot) {
	this.initialSpot = initialSpot;
    }

    public int getInitialSpot() {
	return initialSpot;
    }
}

[rgrant222]

Also, I noticed that you specified that the first person in the circle should be counted as number one, and the third person should be the first to "get the axe." Thus using 3 as the number of people to skip results in the fourth person being the first one to die (0 + 3 = 3, which references the fourth element in the list), which is why handOfDeath is incremented by one less than the number of people to skip.

[JosAH]

Try this. It's practically the same as Jos' version, but a little more object-oriented and flexible.

What is the 'more object-oriented' part? I see a superfluous class for the rank of each soldier but ...

kind regards,

Jos

[rgrant222]

Yeah, that would be it. I did say "a little more," and you're right, it's arguably superfluous. Your solution was quite elegant! I didn't mean to give the impression that I thought negatively of it, so I'm sorry if I did.

[JosAH]

Yeah, that would be it. I did say "a little more," and you're right, it's arguably superfluous. Your solution was quite elegant! I didn't mean to give the impression that I thought negatively of it, so I'm sorry if I did.

Ok, now I understand; I simply stripped my solution down to the bare essentials (Occams razor); if I had some moving .gif images of exploding soldiers I might even have included a gui ;-)

kind regards,

Jos