The Daily WTF: Curious Perversions in Information Technology

pjt33 · 2009-08-03 Reply Admin

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.

2009-08-03 Reply Admin

Something for the Perl haters here:

#!/usr/bin/perl

@soldiers = (1..$ARGV[0]);
@soldiers = grep {++$i % $ARGV[1]} @soldiers while @soldiers > 1;
print @soldiers;

2009-08-03 Reply Admin

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);
?>

Leilock · 2009-08-03 Reply Admin

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);
}

2009-08-03 Reply Admin

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 ;)

2009-08-03 Reply Admin

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])

;)

2009-08-04 Reply Admin

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;
		}
	}
}

2009-08-04 Reply Admin

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)

zzo38 · 2009-08-04 Reply Admin

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:

#~

2009-08-04 Reply Admin

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);
}

}

2009-08-05 Reply Admin

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.

2009-08-05 Reply Admin

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

mol1111 · 2009-08-06 Reply Admin

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

2009-08-09 Reply Admin

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;
}

2009-08-10 Reply Admin

    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

2009-08-10 Reply Admin

    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

2009-08-10 Reply Admin

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

2009-08-10 Reply Admin

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.

2009-08-11 Reply Admin

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;
}

2009-08-14 Reply Admin

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;
}

2009-08-18 Reply Admin

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;
    }

2009-08-18 Reply Admin

//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;
    }

2010-04-17 Reply Admin

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

2010-06-19 Reply Admin

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.

2010-07-31 Reply Admin


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");
    }

}

2013-08-20 Reply Admin

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.

2013-12-24 Reply Admin

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+ . ;

2014-01-06 Reply Admin

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?

2024-06-13 Reply Admin

Josephus' Circle

Leave a comment on “Josephus' Circle”