Would be interesting to see a non recursive implementation of this, as Go does not optimize recursion very well from what I understand.
josephus.go
packagejosephusimport"math"// Survivor indicates which man will be the survivor of a Josephus permutationfuncSurvivor(sizeuint,stepsuint)uint{ifsize==1{return0}ifsize<steps{return(Survivor(size-1,steps)+steps)%size}floor:=size-uint(math.Floor(float64(size/steps)))returnuint(math.Floor(float64((steps*((Survivor(floor,steps)-size%steps)%floor))/(steps-1))))}
josephus_test.go
packagejosephusimport"testing"typetestCasestruct{descriptionstringinput[]uintexpecteduint}funcTestSurvivor(t*testing.T){testCases:=[]testCase{{"1 man",[]uint{1,5},0,},{"more men than steps",[]uint{7,3},3,},{"less men than steps",[]uint{3,5},0,},{"another with more men than steps",[]uint{15,2},14,},{"another with less men than steps",[]uint{5,17},3,},}for_,test:=rangetestCases{ifresult:=Survivor(test.input[0],test.input[1]);result!=test.expected{t.Fatalf("FAIL: %s - Survivor(%+v): %d - expected: %d",test.description,test.input,result,test.expected)}t.Logf("PASS: %s",test.description)}}
No its right, what the Josephus permutation is doing is telling us which solider will survive after all eliminations have happened. The example above gives us soldier 4, which, in a standard array would be position 3 in the array as arrays start at 0 and count up.
Example:
In Go, if you had a slice that represented the group of solders in the example, you would get the index of soldier in the slice that will survive the elimination.
If you wanted to print a more human readable output using the result of the Josephus permutation, you would simply do something like:
I needed to Go find the formula for this one. This is essentially my implementation of it in Go.
Formula was found here en.wikipedia.org/wiki/Josephus_pro...
Would be interesting to see a non recursive implementation of this, as Go does not optimize recursion very well from what I understand.
josephus.go
josephus_test.go
Correct me if I'm wrong.
Your test case for
n = 7, k = 3
checks for an expected result of 3, but based on the same example above, the results should be 4.Is there a mistake in the test cases?
No its right, what the Josephus permutation is doing is telling us which solider will survive after all eliminations have happened. The example above gives us soldier 4, which, in a standard array would be position 3 in the array as arrays start at 0 and count up.
Example:
In Go, if you had a slice that represented the group of solders in the example, you would get the index of soldier in the slice that will survive the elimination.
If you wanted to print a more human readable output using the result of the Josephus permutation, you would simply do something like:
Which would produce the output:
I see, if the array starts from 0, the results from your test cases would make sense.
Thanks for clarifying!
Thank you for the question! In the future if my test cases look different than the examples given I will clarify the reason in my original post.