• (cs) in reply to Manu
    Manu:
    quick C# Implementation:

    public static uint Josephus(uint n, uint k) { uint safespot = 1;

    for (int numbers = 1; numbers <= n; numbers++)
    {
        safespot += 3;
        while (safespot > numbers)
        {
            safespot -= numbers;
        }
    }
    
    return safespot;
    

    }

    Also, this will still need a bit of brainpower to do in the head, but better than any modulo or recursive calls out there.

    Except that your while loop is a modulo operation. Other problems with your code include: failure to use k; performing the operation x % 1; and using the wrong base case. You should initialise safespot to k-1 and start numbers at 2.

  • Wladimir Palant (unregistered)

    Something for the Perl haters here:

    #!/usr/bin/perl
    
    @soldiers = (1..$ARGV[0]);
    @soldiers = grep {++$i % $ARGV[1]} @soldiers while @soldiers > 1;
    print @soldiers;
  • n00b (unregistered)

    How many WTFs are in my PHP code?

    <?php
    function theLastOneAlive($soldiers, $skip){
    	for($i=1; $i<=$soldiers; $i++){
    		$arr[$i]=$i;
    	}
    	$key=0;
    	for($i=0; $i<$soldiers; $i++){
    		unset($alive);		
    		foreach($arr as $v){
    			if($v!==null)
    				$alive[]=$v;
    		}
    		$key=$key+$skip-1;
    		$key=$key%count($alive);
    		$arr[array_search($alive[$key], $arr)]=null;
    	}
    	return $alive[0];
    }
    echo theLastOneAlive(12,3);
    ?>
  • (cs)

    It's not super exciting, but since it's my bread and butter I decided to post a .NET (C#) version of this puzzle using a simple generic collection.

    using System.Collections.Generic;
    
    public static class JosephusCircle
    {
        public static int FindSafeSpot(int numberOfSoldiers, int solidersToSkip)
        {
            Queue<int> theSoliders = new Queue<int>();
            for (int i = 0; i < numberOfSoldiers; i++)
                theSoliders.Enqueue(i);
    
            while (theSoliders.Count > 1)
            {
                for (int i = 0; i < solidersToSkip; i++)
                    theSoliders.Enqueue(theSoliders.Dequeue());
                theSoliders.Dequeue();
            }
    
            return theSoliders.Dequeue();
        }
    }

    ...and to be scientific, I created a test project to run a few scenarios. I came up with the numbers by drawing and working out the answers on paper first, which hurt my eyes after a while!

    [TestMethod]
    public void Scenarios()
    {
        int safeIndex = JosephusCircle.FindSafeSpot(12, 2);
        Assert.AreEqual(9, safeIndex);
    
        safeIndex = JosephusCircle.FindSafeSpot(17, 3);
        Assert.AreEqual(4, safeIndex);
        
        safeIndex = JosephusCircle.FindSafeSpot(40, 2);
        Assert.AreEqual(27, safeIndex);
    }
  • Darryl Dixon (unregistered)

    One line Python implementation (true one-liner, no semicolons - needs Python 2.4+):

    [poplist.rotate(-(killcounter-1)) or poplist.popleft() for x in locals().setitem('soldiers', 12) or locals().setitem('killcounter', 3) or locals().setitem('poplist', import('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and import('sys').stdout.write("The only one left is %s\n" % locals().getitem('poplist')[0])

    You can set the values of 'soldiers' and 'killcounter' appropriately for your situation ;)

  • Darryl Dixon (unregistered) in reply to Darryl Dixon
    Darryl Dixon:
    One line Python implementation (true one-liner, no semicolons - needs Python 2.4+):

    [poplist.rotate(-(killcounter-1)) or poplist.popleft() for x in locals().setitem('soldiers', 12) or locals().setitem('killcounter', 3) or locals().setitem('poplist', import('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and import('sys').stdout.write("The only one left is %s\n" % locals().getitem('poplist')[0])

    You can set the values of 'soldiers' and 'killcounter' appropriately for your situation ;)

    Also, if you prefer to get some output while it runs:

    [poplist.rotate(-(killcounter-1)) or import('sys').stdout.write("Just killed number: %d\n" % poplist.popleft()) for x in locals().setitem('soldiers', 12) or locals().setitem('killcounter', 3) or locals().setitem('poplist', import('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and import('sys').stdout.write("The only one left is %s\n" % locals().getitem('poplist')[0])

    ;)

  • Snakiej (unregistered)
    namespace Josephus
    {
    	internal class Program
    	{
    		private static void Main(string[] args)
    		{
    			int safeSpot = CalculateSafeSpot(40, 3);
    		}
    
    		private static int CalculateSafeSpot(int numberOfSoldiers, int step)
    		{
    			var isAliveBools = new bool[numberOfSoldiers];
    
    			for (int index = 0; index < isAliveBools.Length; index++)
    			{
    				isAliveBools[index] = true;
    			}
    
    			int currentStep = 1;
    
    
    			for (int x = 0; /* check in body */; /* increment in body */)
    			{
    				while (currentStep < step)
    				{
    					x++;
    
    					if (x >= numberOfSoldiers)
    						x -= numberOfSoldiers;
    
    					if (isAliveBools[x])
    					{
    						currentStep++;
    					}
    				}
    
    				currentStep = 0;
    				//x += step;
    
    
    				if (CountTrue(isAliveBools) == 1)
    				{
    					return x;
    				}
    
    				isAliveBools[x] = false;
    			}
    		}
    
    		private static int CountTrue(bool[] array)
    		{
    			int length = array.Length;
    			int noOfTrue = 0;
    
    			for (int x = 0; x < length; x++)
    			{
    				// evil code!
    				if (array[x] && ++noOfTrue > 1)
    				{
    					return noOfTrue;
    				}
    			}
    
    			return noOfTrue;
    		}
    	}
    }
  • David D. Davidson (unregistered)
    Anonymous:
    In response to Wongo:

    There's a formula in the Online Encyclopaedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A054995

    Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

    Noone's pointed this out yet, but that formula is useless computationally, since the constant K can only be calculated by knowing the answers you're trying to generate in advance. See the paper linked to at that OEIS link, "Functional iteration and the Josephus problem" Beginning of section 5.

    (WHY DOES THIS KEEP GETTING FLAGGED AS SPAM?? FFFFFFFFFFFFFUUUUUUUUUU LET ME POST DAMMIT)

  • (cs)

    I invented FlogScript for code-golfing, and I did code-golfing this one too:

    (,{ZoAu(;.,(}Fd~;)

    Addendum (2009-08-04 16:21): Please note that this is not an entire program, it is only a part that makes this calculation, and will not make any input/output by itself. To make it input/output, add this code to the beginning of the program:

    "~
    this allows multiple calculations, one on each line of input. For the program to do only one calculation (it starts after EOF is read from the input), use this instead:
    #~

  • CJBV (unregistered)

    Somebody already put one similar, but here it goes

    public class JosephusCircle { public static void main(String[] args) { System.out.println("Surviving soldier = " + getSurvivorSolderIndex(12, 3)); System.out.println("Surviving soldier = " + getSurvivorSolderIndex(41, 3)); System.out.println("Surviving soldier = " + getSurvivorSolderIndex(40, 7)); }

    public static int getSurvivorSolderIndex(int totalSoldiers, int soldiersToSkip)
    {
    	int currentSoldier = 0;
    	java.util.ArrayList<Integer> soldiers;
    	
    	soldiers = new java.util.ArrayList<Integer>();
    	for ( int i = 1; i <= totalSoldiers; i++ )
    	{
    		soldiers.add(i);
    	}
    	
    	while ( 1 < soldiers.size() )
    	{
    		int soldierToDieIndex;
    		
    		soldierToDieIndex = (currentSoldier + soldiersToSkip - 1)
    				% soldiers.size();
    		System.out.println("Soldier to die = " + soldiers.get(soldierToDieIndex));
    		soldiers.remove(soldierToDieIndex);
    		currentSoldier = soldierToDieIndex;
    	}
    	
    	return soldiers.get(0);
    }
    

    }

  • Mark Bohan (unregistered)

    Sorry not to provide any programming examples but the whole idea inspired the following! :-)

    In order to decide who would not pay the tab, the drinkers sat at a circular table and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the the first tab and the counting resumed at one. The process continued until there was no one left. Paddy Joe, who quite agreed with the whole "we should all pay a tab" idea, figured out the perfect way to have a free nights drinking: be the last man standing.

  • Paul N (unregistered) in reply to Mark Bohan
    Mark Bohan:
    Sorry not to provide any programming examples but the whole idea inspired the following! :-)

    In order to decide who would not pay the tab, the drinkers sat at a circular table and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the the first tab and the counting resumed at one. The process continued until there was no one left. Paddy Joe, who quite agreed with the whole "we should all pay a tab" idea, figured out the perfect way to have a free nights drinking: be the last man standing.

    If he is standing at the end of a free nights drinking, he isn't trying hard enough
  • (cs)

    If anybody interested, I created index for the entries. Index. I cannot put it here directly, because it thinks it's a spam.

  • serious (unregistered)

    using good ol' c and a ring of structs:

    #include <stdio.h>
    #include <stdlib.h>
    
    unsigned int josepus(unsigned int, unsigned int);
    
    struct solider {
      unsigned int id;
      unsigned int dead;
      struct solider* next;
    };
    
    int main(int argc, char** argv) 
    {
      if (argc <= 2) {
        printf("USAGE: %s <soliders> <skip>\n", argv[0]);
      } else {
        josepus(atoi(argv[1]), atoi(argv[2]));
      }
      
      return 0;
    }
    
    
    unsigned int josepus(unsigned int soliders, unsigned int skip) 
    {
      unsigned int i;
      unsigned int deaths = 0;
      struct solider* solfirst;
      struct solider* solnew;
      struct solider* sol;
    
      solfirst = (struct solider*) calloc(1,sizeof(struct solider));
      solfirst->id = 0;
      solfirst->dead = 0;
    
      sol = solfirst;
    
      for (i=1; i<soliders; i++) {
        solnew = (struct solider*) calloc(1, sizeof(struct solider));
    
        solnew->id = i;
        solnew->dead = 0;
        
        sol->next = solnew;
        sol = solnew;
      }
    
      sol->next = solfirst;
    
      sol = solfirst;
      i=0;
    
      while(1) {
        if (sol->dead == 0) {    
          if (i == skip-1) {
    	sol->dead = 1;
    	deaths++;
    	
    	if (deaths == soliders) {
    	  printf("LAST MAN STANDING: %u\n", sol->id);
    	  return sol->id;
    	}
          }
          i = (i+1) % skip;
        }
        sol = sol->next;
      }
      return 0;
    }
    
    
  • Cedric Mamo (unregistered)
        public static int josephus(int numOfSoldiers, int skip)
        {
            ArrayList<Integer> soldiers = new ArrayList<Integer>();
            for (int i = 1; i <= numOfSoldiers; i++)
            {
                soldiers.add(i);
            }
    
            int location = 0;
            while (soldiers.size() > 1)
            {
                location += 2;
                if (location >= soldiers.size()) location -= soldiers.size();
                if (location != soldiers.size() - 1) soldiers.remove(location);
                else
                {
                    soldiers.remove(location);
                    location = 0;
                }
            }
            return soldiers.get(0);
        }

    my solution with java... brute forcing it :D

  • Cedric Mamo (unregistered)
        public static int josephus(int numOfSoldiers, int skip)
        {
            ArrayList<Integer> soldiers = new ArrayList<Integer>();
            for (int i = 1; i <= numOfSoldiers; i++) soldiers.add(i);
            
            int location = 0;
            while (soldiers.size() > 1)
            {
                location += (skip - 1);
                if (location >= soldiers.size()) location -= soldiers.size();
                if (location != soldiers.size() - 1) soldiers.remove(location);
                else
                {
                    soldiers.remove(location);
                    location = 0;
                }
            }
            return soldiers.get(0);
        }

    updated version... the last one i posted always skipped counted 3 people regardless of the parameter xD silly mistake xD

  • Watson Ladd (unregistered) in reply to Satanicpuppy

    Recursion is not a bitch to maintain. You just need to understand what the property of the recursive function is, and how the fixed-point operator works. Loops are a real bitch: Hoare logic is annoying because the hypothesis keeps changing at each line. Recursion is much more natural

  • Someone (unregistered)

    The obligatory ABAP example:

    DATA: numSoldiers TYPE I VALUE 12,
          numSkip TYPE I VALUE 3,
          soldiers TYPE TABLE OF BOOL WITH HEADER LINE,
          soldier TYPE BOOL,
          counter TYPE I,
          liveCt TYPE I.
    
    WHILE SY-TABIX < numSoldiers. "Build soldier set
      APPEND 'X' TO soldiers.
    ENDWHILE.
    
    counter = 1.
    liveCt = numSoldiers.
    WHILE liveCt > 1. "While there is still more than one solider...
      LOOP AT soldiers. "Loop through the soldiers
        IF soldiers = ' '. "Skip the dead ones
          CONTINUE.
        ENDIF.
    
        IF counter > numSkip. "Reset counter when it runs over
          counter = 1.
        ENDIF.
    
        IF counter = numSkip AND liveCt > 1. "Your number is up
          soldiers = ' '.
          MODIFY soldiers.
          liveCt = liveCt - 1.
        ENDIF.
    
        counter = counter + 1.
    
      ENDLOOP.
    ENDWHILE.
    
    LOOP AT soldiers. "Find position of last soldier
      IF soldiers = 'X'.
        WRITE SY-TABIX.
      ENDIF.
    ENDLOOP.
    
    
  • Martin B. (unregistered) in reply to phil

    Nice idea with the plot. I was wondering if there is some pattern - and there is a result:

    [image]

    The x-axis represents step size and y-axis represents number of soldiers int the circle. Both axis are plotted from 1 to 600. Each pixel represents one computed safe spot - plotted from 1 (black) to maximum (white). Since on each line there are results with the same number of soldiers I was able to set maximum for safe spot value to number of soldiers so that the pattern is easy to see. That also means it doesn't make sence to compare colors of pixels on different lines.

    Here's the code, I used PNGwriter library (pngwriter.sourceforge.net):

    #include <pngwriter.h>
    
    void make_png(int s_max, int n_max, const char* filename)
    {
        int safe_index = 0;
        double r,g,b; // colors
    
        pngwriter png(s_max,n_max,0,filename);
    
        for (int s=1; s<=s_max; s++) {
            for (int n=1; n<=n_max; n++) {
                safe_index = (safe_index + s) % n;
                r = g = b = (double)(safe_index + 1)/n;
                png.plot(s,n,r,g,b);
            }
        }
    
        png.close();
    }
    
    int main(int argc, char**argv)
    {
        make_png(600,600,"wtf.josephus.600x600.linear-n.png");
        return 0;
    }
    
  • Tom (unregistered)

    Yeah, I know it is lame, long, counting from zero etc. At least I got to brush up on linked lists...

    #include <stdio.h>
    #include <stdlib.h>
    
    struct _tSoldier
    {
            int pos;
            struct _tSoldier *next;
            struct _tSoldier *prev;
    };
    typedef struct _tSoldier tSoldier;
    
    tSoldier *CreateRing(int i_iNumOfSoldiers)
    {
            if (i_iNumOfSoldiers < 1)
            {
                    printf("no.\n");
                    return NULL;
            }
            tSoldier *pFirst = (tSoldier *) malloc(sizeof(tSoldier));
            pFirst->pos = 0;
            pFirst->prev = NULL;
            pFirst->next = NULL;
            tSoldier *pCreatedLast = pFirst;
            int i = 1;
            tSoldier *pNew;
            while (i < i_iNumOfSoldiers)
            {
                    pNew = (tSoldier *) malloc(sizeof(tSoldier));
                    pNew->pos = i;
                    pNew->prev = pCreatedLast;
                    pCreatedLast->next = pNew;
                    pNew->next = NULL;
                    pCreatedLast = pNew;
                    i++;
            }
            /* closing the circle */
            pNew->next = pFirst;
            pFirst->prev = pNew;
            return pFirst;
    }
    
    
    /**
     * @return 0 if there is only one person left in ring, 1 otherwise.
     */
    int KillFromRing(tSoldier ** io_ppSoldier)
    {
            if (((*io_ppSoldier)->next == *io_ppSoldier)
                || ((*io_ppSoldier)->prev == *io_ppSoldier))
            {
                    printf("Cannot kill last from ring");
                    return 0;
            }
            else
            {
                    tSoldier *pNext = (*io_ppSoldier)->next;
                    tSoldier *pPrev = (*io_ppSoldier)->prev;
                    tSoldier *pDelMe = *io_ppSoldier;
                    pNext->prev = pPrev;
                    pPrev->next = pNext;
                    *io_ppSoldier = pNext;
                    printf("x%dx ", pDelMe->pos);
                    free(pDelMe);
                    return 1;
            }
    }
    
    void PassOnSword(tSoldier ** io_ppSoldier, int i_iNumToSkip)
    {
            int i = 0;
            for (i = 0; i < i_iNumToSkip; i++)
            {
                    printf("[%d] ", (*io_ppSoldier)->pos);
                    *io_ppSoldier = (*io_ppSoldier)->next;
            }
    }
    
    int GetSaveSpot(int i_iNumOfSoldiers, int i_iNumToSkip)
    {
            tSoldier *pSoldier = CreateRing(i_iNumOfSoldiers);
            do
            {
                    PassOnSword(&pSoldier, i_iNumToSkip);
            }
            while (KillFromRing(&pSoldier));
            return pSoldier->pos;
    }
    
    int main(void)
    {
            int iSaveSpot = GetSaveSpot(41, 2);
            printf("\nSave Spot is %d.\n", iSaveSpot);
            return 0;
    }
    
  • Ricardo Custodio .NET Developer (unregistered)

    public static void Main(string[] args) { //global vars int soldiers = 12; int soldiersToSkip = 3;

            //Create List            
            List<bool> soldiersList = new List<bool>();
            
            //Load List
            for (int i = 0; i < soldiers; i++)
            {
                soldiersList.Add(true);
            }
    
            int countAlive;
            int SoldierToKill = -1;
            while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)
            {
                for (int i = 0; i < soldiersToSkip; i++)
                {
                    SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);
                }
                //Kill Soldier
                soldiersList[SoldierToKill] = false;
            }
    
            Console.WriteLine("Considered the zero as the first position of circle.");
            Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));
            Console.WriteLine(soldiersList.FindIndex(delegate(bool soldier) { return soldier; }));
            Console.ReadLine();
        }
    
        private static int returnNextAlive(int index, List<bool> soldiersList)
        {
            int AliveIndex = 0;
            for (int i = index; i < index + soldiersList.Count; i++)
            {
                if (i >= soldiersList.Count)
                {
                    if (soldiersList[i - soldiersList.Count])
                    {
                        AliveIndex = i - soldiersList.Count;
                        break;
                    }
                }
                else
                if (soldiersList[i])
                {
                    AliveIndex = i;
                    break;
                }
            }
            return AliveIndex;
        }
    
  • Ricardo Custodio .NET Developer (unregistered) in reply to Ricardo Custodio .NET Developer

    //updated and parametrized public static void Main(string[] args) { //Test int soldiers = 40; int soldiersToSkip = 3; int SafePos = JosephusSafePos(soldiers, soldiersToSkip);

            //Result
            Console.WriteLine("Considered the zero as the first position of circle.");
            Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));
            Console.WriteLine(SafePos);
            Console.ReadLine();
        }
    
        private static int JosephusSafePos(int soldiers, int soldiersToSkip)
        {
            //Create List
            List<bool> soldiersList = new List<bool>();
    
            //Load
            for (int i = 0; i < soldiers; i++)
            {
                soldiersList.Add(true);
            }
    
            int countAlive;
            int SoldierToKill = -1;
            while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)
            {
                for (int i = 0; i < soldiersToSkip; i++)
                {
                    SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);
                }
                //Kill Soldier
                soldiersList[SoldierToKill] = false;
            }
    
            return soldiersList.FindIndex(delegate(bool soldier) { return soldier; });
    
        }
    
        private static int returnNextAlive(int index, List<bool> soldiersList)
        {
            int AliveIndex = 0;
            for (int i = index; i < index + soldiersList.Count; i++)
            {
                if (i >= soldiersList.Count)
                {
                    if (soldiersList[i - soldiersList.Count])
                    {
                        AliveIndex = i - soldiersList.Count;
                        break;
                    }
                }
                else
                if (soldiersList[i])
                {
                    AliveIndex = i;
                    break;
                }
            }
            return AliveIndex;
        }
    
  • Wagner Amaral (unregistered)

    I know, old topic... Yeah, I haven't read all the coment either... Anyway, worth mentioning, this problem appears in D. Knuth's Concrete Mathematics book

  • oksupra.com (unregistered)

    Supra shoes are so popular all over the world. Whatever you take on Supra being in the Supra Skytop Shoes market. Now Supra Strapped Shoes also very popular attention. It is nice that they actually took the time to make Supra Skate Shoes that work well. Supra shoes is a brand that has been inspired, designed and marketed by passionate individuals. We have brought to you the fullest selection of Supra footwear at cheapest price.

  • Pyrexkidd (unregistered)
    
    package JosephusCircle;
    import java.util.Scanner;
    public class JosephusCircle {
    
        public static void main(String[] args) {
            Scanner console = new Scanner(System.in);
            int soldiers;
            int counting_index, numAlive;
            boolean lastOneStanding = false;
            System.out.print("Please Enter the Number of Soilders: ");
            numAlive = soldiers = console.nextInt();
            System.out.print("Please Enter How Many to skip: ");
            counting_index = console.nextInt();
            boolean unit[] = new boolean[soldiers];
            for (int i = 0; i < unit.length; i++){
                unit[i] = true;
            }
            int counter = 1;
            while(!lastOneStanding){
                for( int i = 0 ; i < unit.length; i++){
                    if (unit[i]){
                        counter++;
                        if (counter == counting_index){
                            counter = 1;
                            numAlive--;
                            unit[i] = false;
                        }
                    }
                }
                if (numAlive == 1){
                    lastOneStanding = true;
                }
            }
            System.out.print(unit.length + "\n");
            for (int i = 0; i < unit.length; i++){
                System.out.print("Index: " + i + " Alive: " + unit[i] + "\n");
            }
            int i = 0;
            for ( ; !unit[i]; i++ ){}
            System.out.print("Best Location to Stand: " + (i + 1) + "\n");
        }
    
    }
    
  • Sean (unregistered) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    nah, just make sure God is a singleton.
  • Mark Wills (unregistered)

    Here it is in Forth:

    40 value #soldiers
    #soldiers value remain
    0 value position
    create soldiers #soldiers chars allot
    
    : init ( --)
        #soldiers 0 do 1  soldiers i +  c!  loop
        -1 to position  #soldiers to remain ;
    
    : soldiers' ( -- addr) soldiers position + ;
    
    : position++ ( --)
        position 1+ #soldiers mod to position ;
    
    : kill3rd ( --)
        0 begin
            position++  soldiers' c@ if 1+ then
          dup 3 = until drop
          0 soldiers' c!  position 1+ .  -1 +to remain ;
    
    : killThem ( --) init begin remain 0> while kill3rd repeat
        cr ." Last man standing at position " position 1+ . ;
    
  • Carrie (unregistered) in reply to Anon
    Anon:
    Josephus' Circle, AKA Eeny, meeny, miny, moe. The solution is to argue about how many words are in the rhyme and whether the person selected at the end is "it" or "not it".

    You mean you don't append 'this means you will not be it' to the end of the rhyme?

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article