The Daily WTF: Curious Perversions in Information Technology

2009-07-29 Reply Admin

Delphi

program Josephus;

{$APPTYPE CONSOLE}

uses
  SysUtils;


{ SafeIndex : Returns zero-based index of safe location in Josephus' Circle.
  - soldierCount : number of soldiers in initial circle
  - killEvery : interval at which to kill off soldiers
}
function SafeIndex(
  soldierCount : Integer;
  killEvery : Integer
) : Integer;
var
  count : Integer;
  safe : Integer;
begin
  count := 1;
  safe := 0;

  while (count < soldierCount) do begin
    Inc( count );
    safe := (safe + killEvery) mod count;
  end;

  Result := safe;
end; // SafeIndex


procedure WriteUsage;
begin
  WriteLn('Usage: Josephus <soldierCount> <killEvery>');
end;


var
  killEvery : Integer;
  killEveryStr : String;
  safe : Integer;
  soldierCount : Integer;
  soldierCountStr : String;

begin
  if ParamCount < 2 then begin
    WriteUsage;
    Exit;
  end;

  soldierCountStr := ParamStr( 1 );
  killEveryStr := ParamStr( 2 );

  try
    soldierCount := StrToInt( soldierCountStr );
    killEvery := StrToInt( killEveryStr );

  except
    on EConvertError do begin
      WriteLn('Arguments must be numeric.');
      WriteUsage;
      Exit;
    end;
  end;

  safe := SafeIndex( soldierCount, killEvery );
  WriteLn('Safe index: ' + IntToStr( safe ));
end.

db2 · 2009-07-29 Reply Admin

Wongo:
Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):
Soldiers: 2, Last Spot: 2 Soldiers: 3, Last Spot: 2 Soldiers: 4, Last Spot: 1 Soldiers: 5, Last Spot: 4 ...snip... Soldiers: 37, Last Spot: 19 Soldiers: 38, Last Spot: 22 Soldiers: 39, Last Spot: 25 Soldiers: 40, Last Spot: 28 Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

It looks like this works:

n = number of soldiers k = skip ahead interval (3 in this example) i = "safe spot" index (1-based)

i = 1;
for (int c = 2; c <= n; c++) {
  i = (i + k) % c;
  if (i == 0) {
    i = c;
  }
}
return i;

2009-07-29 Reply Admin

Of course that is Excel + VBA, not pure VBA.

VBA's bad reputation drives me nuts...it's a good language for what it's intended uses are...so I can't help but be the ass who points out:

1)There's no need to manipulate values on a worksheet, you can use variables and it will run much faster. Each time code touches a worksheet object you pay a large price in speed. Better to do everything in memory and only kick the final result. You can also use Debug.Print to write to the immediate window. Do While Range(checker).Value > 1 will perform much better if replaced by a check against an internal variable, particularly for large loops.

You should use Columns("A:D").ClearContents instead of four separate calls; faster to both write and run. No need to clear columns if you keep data in memory. (arrays?)
It's a bad habbit to use code like: Range(somthing).Method, doing this will break if you accidentally activate a different worksheet while the code is running. When you reference "Range", you are implictly saying Application.ActiveWorksheet.Range, which users can break easily. It's much better to explictly declare which worksheet you want to operate on, using something like sheet1.Range(something) or Worksheets("ExternalSheetName").Range(something) (and bonus points if you use with blocks to reduce the number references to higher level objects)
No need to type cast strings when using & for string concatination. strMyString = "Some Text " & i runs faster than strMyString ="Some text" & Cstr(i)
using code to write worksheet functions is a bit much, there are times where that is useful, but you have the values in code so why not just add them in code too?
Dim cur As String: cur = "C" & CStr(j), not sure if this is considered bad form or not, but I'd wager dimming a var inside a loop slows things significantly. You're replacing the value of this variable each time, no need to redim it.

2009-07-29 Reply Admin

halber_mensch:
Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:
{1,2,3,4,5} {1,3,5} {3}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

2009-07-29 Reply Admin

justsomedude:
Of course that is Excel + VBA, not pure VBA..
{snip}

Quote fail...that was in reference to the vba post on page 1...

2009-07-29 Reply Admin

Capt. Obvious:
1 + (n-1)(k-1) mod n

Neither this nor 1+(n-1)k mod n works. Consider case 17 soldiers, the person to count 2 dies. So, n=17, k=2. The correct answer for those is index 2 (3 if indexed from 1).

for 1 + (n-1)k mod n: 1 + (17-1)2 mod 17 = 1 + 32 mod 17 = 16, which is incorrect. for 1 + (n-1)(k-1) mod n: 1 + (17-1)(2-1) mod 17 = 1 + 16 mod 17 = 17, which is also incorrect.

I assumed you mean % as taking precedence over addition, in C fashion. However, even if you actually meant (1 + (n-1)k) mod n or (1 + (n-1)(k-1)) mod n for 17,2 the results are 16 and 0, respectively. Also incorrect.

2009-07-29 Reply Admin

Wongo:
halber_mensch:
Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:
{1,2,3,4,5} {1,3,5} {3}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

2009-07-29 Reply Admin

By looking at that sequence I was able to come up with the following javascript solution:

function josephus3(count, seed) { var index = seed % 2 == 0 ? 1 : 2;

for (var i = 3; i <= count; i++)
{
  index += seed;
  while (index > i)
    index -= i;
}

return index;

}

First we determine the starting index based on whether the seed is even or odd.

Next we follow the pattern of the solution above, which is, every time you go up from two you add the seed to the index and if the new index is greater than i (the number of men) you subtract i.

I expected this to work with a seed of 3, but I was surprised when I found out it works with any seed. It was easy for me to write an algorithm to represent the pattern, whereas I don't think I could figure out the other more elegant approaches.

2009-07-29 Reply Admin

How's about a T-SQL function? I could probably tighten this up considerably but it works.

CREATE FUNCTION dbo.JosephusFunction
(
	@NumberOfSoldiers int,
	@SoldiersToSkip int
)
RETURNS int
AS
BEGIN

	DECLARE @i int, @TempSkip int;
	DECLARE @Soldiers table (SoldierNumber int, Dead bit);

	SET @i = 1;
	WHILE @i <= @NumberOfSoldiers
	BEGIN
		INSERT INTO @Soldiers VALUES (@i, 0);
		SET @i = @i + 1;
	END

	SET @i = 1;
	WHILE (SELECT COUNT(*) FROM @Soldiers WHERE Dead = 0) > 1
	BEGIN
		SET @TempSkip = @SoldiersToSkip + 1;
		WHILE @TempSkip > 0
		BEGIN
			SET @i = @i % @NumberOfSoldiers + 1;

			WHILE (SELECT Dead FROM @Soldiers WHERE SoldierNumber = @i) = 1
			BEGIN
				SET @i = @i % @NumberOfSoldiers + 1;
			END
		
			SET @TempSkip = @TempSkip - 1;
		END

		UPDATE @Soldiers
		SET Dead = 1
		WHERE SoldierNumber = @i;

	END

	RETURN (SELECT SoldierNumber - 1 FROM @Soldiers WHERE Dead = 0);
	
END

2009-07-29 Reply Admin

db2:
It looks like this works:
n = number of soldiers k = skip ahead interval (3 in this example) i = "safe spot" index (1-based)
i = 1;
for (int c = 2; c <= n; c++) {
  i = (i + k) % c;
  if (i == 0) {
    i = c;
  }
}
return i;

Brilliant! It works perfectly! Congrats, db2, you made my day!

Now, if we could just remove the loop and turn it into a formula, we might find out how Josephus did it "very quickly"...

2009-07-29 Reply Admin

Clojure!

(defn josephus [num-soldiers skip]
  (let [ax (fn [soldiers index]
             (let [real-index (if (> index (count soldiers))
                                (rem index (count soldiers))
                                index)]
               (concat (nthnext soldiers real-index)
                       (take (dec real-index) soldiers))))]
    (loop [alive (range 1 (inc num-soldiers))]
      (if (= (count alive) 1)
        (first alive)
        (recur (ax alive skip))))))

Most of this function is just the definition for the ax() function.

2009-07-29 Reply Admin

JavaScript 1.8:

    function j(n, k) n <= 1 ? 0 : (j(n - 1, k) + k) % n;

Non-recursive form:

    function j(n, k) { let p = 0, i = 1; while (i < n) p += k, p %= ++i; return p }

As mentioned at Wikipedia, a closed form exists for k = 2: j(n, 2) = 2 * (n - 2 ^ log2(n)) There is no closed form for k = 3; a good place to start is OEIS A054995.

2009-07-29 Reply Admin

Woops, that should be unset($roulette[$arrayIndex]); not unset($roulette[$value]);

Why must comments keep erroring out?

2009-07-29 Reply Admin

DesGrieux:
Wongo:
halber_mensch:
Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:
{1,2,3,4,5} {1,3,5} {3}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

2009-07-29 Reply Admin

Satanicpuppy:
Addison:
Alex Mont:
Thus our formula is (code in Python):
def J(n,k):
    if(n==1)
        return 0
    else
        return (J(n-1,k)+k)%n
This is sexy.
Truly, there is nothing sexier than recursion. It's especially elegant for problems like this one.

Unfortunately, it's a bitch to maintain, and a memory hog for larger functions.

Sexier: Cate Blanchett. Bitch to maintain: Well, possibly Ms Blanchett also, for all I know. Then again, why on earth would a correct recursive procedure be any more of a bitch to maintain than a correct iterative homologue? Memory hog: Tail recursion, my man. Tail recursion.

Other than that, all these solutions appear to assume a boolean state for each soldier of dead/alive. Whatever happened to death_not_found?

2009-07-29 Reply Admin

Wongo:
DesGrieux:
Wongo:
halber_mensch:
Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:
{1,2,3,4,5} {1,3,5} {3}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc. Sorry for wasting yout time :)

MHolt · 2009-07-29 Reply Admin

Naive, very much to the letter solution in Scheme:

(define josephus
  (lambda (n skip)
    (let ([S (build-list n #t)]
	  [a n])
      (letrec ([inner
		(lambda (i c)
		  (if (> a 1)
		      (if (car (list-ref S i))
			  (if (< c skip)
			      (begin
				(inner (modulo (1+ i) n) (1+ c)))
			      (begin
				(set-car! (list-ref S i) #f)
				(set! a (- a 1))
				(inner (modulo (1+ i) n) 0)))
			  (inner (modulo (1+ i) n) c))
		      (get-alive 0)))]
	       [get-alive
		(lambda (i)
		  (if (eq? (car (list-ref S i)) #f)
		      (get-alive (1+ i))
		      (begin (display "With ")
			     (display n)
			     (display " soldiers and killing every ")
			     (display (1+ skip))
			     (display "th, the safe spot is: ")
			     (1+ i))))])
	(inner 0 0)))))

(define build-list
  (lambda (n val)
    (if (zero? n)
	'()
	(cons (cons val '()) (build-list (- n 1) val)))))

And a test session:

Petite Chez Scheme Version 7.4
Copyright (c) 1985-2007 Cadence Research Systems

> (load "josephus.scm")
> (josephus 12 2)
With 12 soldiers and killing every 3th, the safe spot is: 10
> (josephus 41 2)
With 41 soldiers and killing every 3th, the safe spot is: 31
>

samanddeanus · 2009-07-29 Reply Admin

(define (josephus n q)
  (let solve ((i 1) (jn 0))
    (if (< n i)
	(+ 1 jn)
	(solve (+ i 1) (remainder (+ jn q 1) i)))))

Edit: Use one-based index

Addendum (2009-07-29 14:13): (q is "number to skip", so kill every q+1 th) -- I originally had it the other way but then edited it.

2009-07-29 Reply Admin

The solution is:

"Hey everyone, I'll watch the door while you guys sort this out."

2009-07-29 Reply Admin

Andreas Kromann:
My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc. Sorry for wasting yout time :)

Nah, I knew you were on to something... Couldn't have found it myself anyway (or maybe with lots more time).

db2 · 2009-07-29 Reply Admin

Wongo:
Brilliant! It works perfectly! Congrats, db2, you made my day!
Now, if we could just remove the loop and turn it into a formula, we might find out how Josephus did it "very quickly"...

Granted, I haven't tested it for other values of k, or for weird edge cases, but I was able to precisely reproduce your list of safe spots by putting a Console.WriteLine() at the bottom of the loop body.

2009-07-29 Reply Admin

Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

s0be · 2009-07-29 Reply Admin

Perl Monk:
Perl Golf'd:
$p[$-1]=$ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

77 chars :-)

My perl approach:

'@A=(1..$ARGV[0]);while($A[1]){$j=shift@A;push(@A,$j)if(++$i)%$ARGV[1]}print@A

78 chars :-)

2009-07-29 Reply Admin

Wongo:
DesGrieux:
Wongo:
halber_mensch:
Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:
{1,2,3,4,5} {1,3,5} {3}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

2009-07-29 Reply Admin

Ev:
Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

samanddeanus · 2009-07-29 Reply Admin

(define (josephus n m)
  (let loop ((d 1))
    (if (> d (* m n))
	(- (+ (* n m) n 1) d)
	(loop (ceiling (* d (/ (+ m 1) m)))))))

Iterative and runs in logarithmic time

Addendum (2009-07-29 14:08): NOTE: m is number to skip as listed in article -- so every m+1 is killed.

2009-07-29 Reply Admin

Why Prolog gets no love... K is step size, I is 0 based index, N is number of unluckies.

josephus(0,1,_).
josephus(I,N,K) :- M is N-1, josephus(J,M,K), I is (J+K) mod N, !.

Cut is not absolutely necessary.

2009-07-29 Reply Admin

horizon:

assuming that the starting position is 0:

int f(int numberOfSoldiert, int numberOfSkips)
{
   return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers;
}

Great, I believed there is a very simple solution... Because of "VERY FAST" phrase. This solution has constant time, all others are n dependent.

2009-07-29 Reply Admin

Here's another javascript version

function josephus(n,k){
  if ( n <= 1 ) {
    return 1;
  }
  var data = [];
  for ( var i = 0; i < n; i++ ) {
    data[i] = i+1;
  }
  var l = n;
  for ( var i = (k-1)%l; l > 1; i = (i+k-1)%(--l) ) {
    data.splice(i,1);
  }
  return data[0];
}

2009-07-29 Reply Admin

Good old C. Still no 860 iterations. First method 398 steps; recursive method does n-1 recursions; iterative solution loops n-1 times.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int StrSurvive (int n, int k)
{
	char *soldiers;
	int surv, i, pos, count = 0;

	soldiers = (char *) malloc (n+1);
	memset (soldiers, 'O', n);
	soldiers[n] = 0;
	for (pos = 0, surv = n; surv > 1; surv--)
	{
		for (i = 0; ;)
		{
			count++;
			if (soldiers[pos] == 'O')
				if (i == k)
					break;
				else if (++i == k)
					soldiers[pos] = 'X';
			if (++pos == n)
				pos = 0;
		}
		printf ("%s\n", soldiers);
	}
	printf ("Count = %d\n", count);
	return pos;
}

int RecSurvive (int n, int k)
{
	if (n == 1)
		return 0;
	else
		return (RecSurvive(n-1,k)+k)%n;
}

int LoopSurvive (int n, int k)
{
	int i, pos = 0;

	for (i = 1; i < n; i++)
		pos = (pos + k) % n;
	return pos;
}

void main(void)
{
	printf ("Pos = %d\n", StrSurvive (41, 3));
	printf ("Pos = %d\n", RecSurvive (41, 3));
	printf ("Pos = %d\n", LoopSurvive (41, 3));
}

2009-07-29 Reply Admin

Here's another Python version that replaces the recursion with a for loop. Same basic solution, but without the potential memory issue.

def jos(soldiers, skip):
    safe = 0
    for x in xrange(2, soldiers+1):
        safe = (safe + skip) % x
    return safe

2009-07-29 Reply Admin

this should be fitting for the daily wtf

struct position{ int id; position * nextGuy; position * lastGuy; };

int safe(int people, int count){ position * circle = new position; position * head = circle;

circle->id = 1; for ( int c = 2; c < people+1; c++){ position * temp = new position; temp->id = c; temp->lastGuy = head; head->nextGuy = temp; head = temp; } circle->lastGuy = head; head->nextGuy = circle;

while( circle->lastGuy != circle->nextGuy ){ for(int c = 0;c < count; c++ ){ circle = circle->nextGuy; } head=circle; circle=circle->nextGuy;

  head->lastGuy->nextGuy = head->nextGuy;

  head->nextGuy->lastGuy = head->lastGuy;

  delete head;

}

int result = circle->id; delete circle; return result; }

2009-07-29 Reply Admin

Anon:
Ev:
Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

Give me n soldiers and an axe.

Maurits · 2009-07-29 Reply Admin

Perl Golf. 83 characters including perl -e and the two given arguments 40 and 3. 69 characters between the quotes.

perl -e"@=(1..$ARGV[0]);++$c%$ARGV[1]?$i++:splice@,$i%=@,1while$#;print@_" 40 3

Addendum (2009-07-29 13:24): Shaved off three characters by using "shift" instead of $ARGV[0].

80 characters for the whole thing; 66 between the quotes.

perl -e"@=(1..shift);++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

http://blogs.msdn.com/matthew_van_eerde/archive/2009/07/29/bad-perl-josephus-problem.aspx

Addendum (2009-07-29 14:00): 78/64 dropping the parentheses.

perl -e"@=(1..shift);++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

Addendum (2009-07-29 14:09): Actually dropping the parentheses.

perl -e"@=1..shift;++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

2009-07-29 Reply Admin

Ops!

In LoopSurvay, please change

pos = (pos + k) % n;

to

pos = (pos + k) % (i+1);

herosp · 2009-07-29 Reply Admin

public string DoJosephus(int soldiersCount, int soldiersToSkip) { List<string> soldiers = new List<string>(soldiersCount); for (int j = 0; j < soldiersCount; j++) soldiers.Add((j+1).ToString()); int i = soldiersToSkip - 1; do { i = GetStep(i, soldiers.Count); soldiers.RemoveAt(i); if (i + soldiersToSkip > soldiers.Count) i = i - soldiers.Count; i = i + soldiersToSkip - 1;

        } while (soldiers.Count>1);
        return soldiers[0];
    }

    private int GetStep(int i, int count)
    {
        if (i < count) return i;
        else i = i - count;
        return GetStep(i, count);
    }

2009-07-29 Reply Admin

A batch file solution:

@echo off rem - argument 1 is number of soldiers, argument 2 is the number to count to each time

call :josephus %1 %2

echo the survivor is at index %survivor% exit /b

:josephus set soldiers=%1 set /a soldiersnext="soldiers-1" set count=%2 if %soldiers% neq 1 call :josephus %soldiersnext% %count% set soldiers=%1 set /a survivor="(count+survivor)%%soldiers" exit /b

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

SR:
d3matt:
Code Dependent:
Dave:
foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
Shouldn't God be static?
yes... the God class is a singleton...
d3matt: I've got a billion or so Hindus on the phone who don't agree

I thought there needed to be three pointers to the same object.

2009-07-29 Reply Admin

Wrote this during my lunch break. Compiles in Turbo Pascal 5.0, uses pointers...

Program JosephusCircle;
Type
  Jptr = ^ Jnode;
  Jnode = record
            Number : integer;
            Next : Jptr;
            Prev : Jptr;
          end;
var
  n : integer;
  s : integer;

Function MakeCircle(Size : integer) : Jptr;
var
 lcv : integer;
 lst : Jptr;
 fst : Jptr;
 prv : Jptr;
begin
 new(fst);
 fst^.Next := nil;
 fst^.Prev := nil;
 fst^.Number := 1;
 prv := fst;
 for lcv := 2 to Size do
   begin
     new(lst);
     prv^.Next := lst;
     lst^.Prev := prv;
     lst^.Next := nil;
     prv := lst;
     lst^.Number := lcv;
   end;
 lst^.Next := fst;
 fst^.Prev := lst;
 MakeCircle := fst;
end;

Function Kill(var Doomed : Jptr) : Jptr;
begin
  Doomed^.Prev^.Next := Doomed^.Next;
  Doomed^.Next^.Prev := Doomed^.Prev;
  Kill := Doomed^.Next;
  Doomed^.Next := nil;
  Doomed^.Prev := nil;
  Dispose(Doomed);
end;

Function Josephus(Number,Skip : integer) : integer;
var
  cur : Jptr;
  lcv : integer;
begin
  cur := MakeCircle(Number);
  repeat
    for lcv := 1 to Skip do cur := cur^.next;
    cur := kill(cur);
  until cur^.next = cur;
  Josephus := cur^.Number;
  cur := kill(cur);
end;

begin
  Write('Number of Soldiers: ');
  Readln(n);
  Write('Number to Skip: ');
  Readln(s);
  Writeln('Safe Spot: ',Josephus(n,s));
end.

2009-07-29 Reply Admin

#include <stdio.h>
int f(n,k){return n<=1?0:(f(n-1,k)+k)%n;}
main() {
  int g; for (g = 0; g < 48; ++g)
    printf("josephus %d skip %d = %d\n", (int)(g/3)+1, (g%3)+2, f((int)(g/3)+1,(g%3)+2));
}

Thank you, CLR.

2009-07-29 Reply Admin

What have I learned today?

If I'm going to have a Judeo circle of mass [suicide|assisted suicide], be the one who announces the skip number AFTER the circle is formed.

2009-07-29 Reply Admin

yes the last

push into an array all the loosers with a for loop that counts 3 and inside the for put an if for checking the actual array if is in the array dont push it and continue checking the array of the standing soldiers

for this u need 2 arrays one for loop and put it into a function and done

my inglish is bad i know

:)

halber_mensch · 2009-07-29 Reply Admin

Anon:
No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

k is the skip, count is k+1. You count to three and thus skip over two guys. 1 2 3 4 5 6 7 8 9 etc. If your count is one, your k is 0 in which case J(5,0) yields 5. But our count is 2 and the k is 1 to skip every other guy.

TGV · 2009-07-29 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).

Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

2009-07-29 Reply Admin

God, that took me so much longer than it should have - and I'm not even proud of the code :-(

Anyways, here goes my python implementation:

def josephus(n, s):
  soldiers = range(1,n+1)
  position = 0
  counter = 1

  while soldiers.count(0) < n - 1:
    position += 1
    if position == n:
      position = 0
    
    if not soldiers[position] == 0:
      counter += 1
      
    if counter == s:
      soldiers[position] = 0
      counter = 0

  soldiers.sort(reverse=True)
  print "The safe spot was number %i of %i." % (soldiers[0], n)

2009-07-29 Reply Admin

jos n = rfilter [1..n] !! (2*n-5) 
  where rfilter xs = filter (xs ++ rfilter xs)
        filter (x:y:z:rs) = x:y:filter rs

Just for the fun of it: A Haskell version featuring infinite recursion.

2009-07-29 Reply Admin

powershell

function josephus {
	param([int] $soldiers = 41, [int]$skip = 2)
	$alive = [System.Collections.ArrayList] (1 .. $soldiers)
	$dead = $skip
	while ($alive.count -ne 1) {
		$alive.removeAt($dead)
		$dead = ($dead + $skip) % $alive.count
	}
	$alive
}

samanddeanus · 2009-07-29 Reply Admin

(define (create-circle n)
  (let ((initial-pair (list n)))
    (let iter ((i (- n 1)) (accum initial-pair))
      (if (zero? i)
          (begin (set-cdr! initial-pair accum) accum)
          (iter (- i 1) (cons i accum))))))

(define (josephus n m)
  (let iter ((circle (create-circle n)))
    (if (eq? (car circle)
	     (cadr circle))
	(car circle)
	(let ((skipped-m (list-tail circle m)))
	  (set-car! skipped-m (cadr skipped-m))
	  (set-cdr! skipped-m (cddr skipped-m))
	  (iter skipped-m)))))

Note: m is the "number to skip" as in the spec, so you kill every m+1 th

Addendum (2009-07-29 17:09): This is intended to model the actual chopping process, not to be efficient.

2009-07-29 Reply Admin

Just started learning Haskell so ... but this seems to work

-- josephus try

joHelper xs = if null (drop 2 xs) then drop 1 xs else joHelper ((drop 3 xs) ++ (take 2 xs))

josephus i = head (joHelper [1..i])

Josephus' Circle

Leave a comment on “Josephus' Circle”