The Josephus Problem is always an amusing one. Fairly grizzly in nature... you line up N people in a circle and starting at the top you count off K number of people and then kill that person. You then repeat the K count from the next person over and eliminate that person from the group.. this continues until you are down to one person.

I forget sometimes people get asked for sequences on job interviews.. but damned if this didn't take me three minutes to knock out. Oh Probability and Combinatorics class - how I miss you!


'-- the Josephus Problem sequence
Dim listOfPeople As New List(Of Int32)

Dim lHowManyPeopleTotal As Int32 = 30
Dim lNthPerson As Int32 = 3

Dim location As Int32 = 0 '-- the temporary location to remove from the collection.

'-- fill our list with numbered people.
For i As Int32 = 1 To lHowManyPeopleTotal
listOfPeople.Add(i)
Next

lNthPerson -= 1 '-- remember the array list starts its index at 0

While listOfPeople.Count > 1 '-- run until there is only one item in the list left.
location += lNthPerson '-- from our current location add the number of steps we need to take.

While location >= listOfPeople.Count '-- if that number of steps is more than the items in the array wrap around.
location = location - listOfPeople.Count '-- this will happen frequently when when the # of steps is greater than the number of items.
End While

Console.WriteLine(listOfPeople(location)) '-- show what was removed
listOfPeople.RemoveAt(location) '-- remove it.
End While

Console.WriteLine("winner! " + listOfPeople(0).ToString) '-- show the winning spot!