1.3.37.md

Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange them- selves in a circle (at positions numbered from 0 to N–1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated.

Solution is to re-add to queue people, which need to be skipped until one person is left.

func josephus(peopleCount: Int, turn: Int) -> Int {
    var queue = Queue<Int>()
    for i in 1...peopleCount {
        queue.enqueue(i)
    }

    while queue.count > 1 {
        for _ in 1..<turn {
            queue.enqueue(queue.dequeue()!)
        }
        queue.dequeue()
    }

    return queue.dequeue()!
}