Prisoners visit a room where there is a light switch that is not connected to anything, when all the prisoners have visited the room they can confidently know that they were all in there saving them from the crocodiles.

SwitchProblemSolution.swift

//
// Description Switch problem in Swift solution
//
// Author: Paul Ossenbruggen
// Date: Nov 8, 2015
// Language: Swift 2.1
// See comment below for problem statement. This solves the second version where we don't know the state
// of the switch at the beginning.
//

import Foundation

//You are one of several recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:
//
//You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
//
//I have setup a "switch room" which contains a light switch, which is either on or off. The switch is not connected to anything.
//
//Every now and then, I will select one prisoner at random to enter the "switch room". This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.
//
//Each prisoner will visit the "switch room" arbitrarily often. More precisely, for any N, eventually each of you will visit the "switch room" at least N times.
//
//At any time, any of you may declare: "we have all visited the 'switch room' at least once". If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!
//
//Devise a winning strategy when you know that the initial state of the switch is off.
//Devise a winning strategy when you do not know whether the initial state of the switch is on or off.


// Solution: if a prisoner has never turned on the switch, he turns it on, if the switch was off.
// If he does turn it on, he remembers he has turned on the switch and never turns it on again.
// The leader sometimes gets selected, when he is selected, he checks the switch, if it is on then he
// counts the times the switch was on, if the number of times the switch was turned on equals the
// number of prisoners then he knows for sure that everyone has visited the switch room and they are
// free. Because the leader does not know the state of the switch when they start, he waits until he
// has visited the room and set the switch to off to begin counting and counts hiimself as having
// entered the room.

func prisonerSwitch(numPrisoners : Int) {
    let leaderIndex = 0
    
    guard numPrisoners != leaderIndex + 1 else {
        print("I visited")
        return
    }
    guard numPrisoners > 0 else {
        print("no prisoners")
        return
    }
    var prisonersState = [Bool](count: numPrisoners, repeatedValue: false)
    var switchState = Int(arc4random_uniform(UInt32(2))) == 0 ? true : false
    var countOfEveryoneEntered = 0
    var visits = 0
    
    func prisonerEnterRoom(var turnedOnSwitchBefore : Bool) -> Bool {
        visits += 1
        if !turnedOnSwitchBefore && !switchState {
            switchState = true
            turnedOnSwitchBefore = true
        }
        return turnedOnSwitchBefore
    }
    
    func leaderEnterRoom(var flippedSwitchBefore : Bool) -> Bool {
        visits += 1
        if !flippedSwitchBefore {
            flippedSwitchBefore = true
            countOfEveryoneEntered = 1
        }
        if switchState && flippedSwitchBefore {
            countOfEveryoneEntered += 1
        }
        switchState = false
        return flippedSwitchBefore
    }
    
    func printState(rand: Int) {
        print(prisonersState, rand, switchState, countOfEveryoneEntered, rand == 0 ? "leader" : "")
    }
    
    while true {
        let rand = Int(arc4random_uniform(UInt32(prisonersState.count)))
        var flippedSwitchBefore = prisonersState[rand]
        
        if rand == leaderIndex {
            flippedSwitchBefore = leaderEnterRoom(flippedSwitchBefore)
            if countOfEveryoneEntered == numPrisoners {
                print("all \(countOfEveryoneEntered) visited in \(visits) visits")
                break
            }
        } else {
            flippedSwitchBefore = prisonerEnterRoom(flippedSwitchBefore)
        }
        prisonersState[rand] = flippedSwitchBefore
        
        printState(rand)
    }
}
// run in playground
prisonerSwitch(10)

This won't solve the second problem, because the leader doesn't know in his first visit, if the switch was on from the beginning, or if other prisoner turned it on. In the first case, he is right to start counting from 1, that is, himself. But if other prisoner was there before, and turned it on, then the leader will not count that prisoner, never, because the prisoner will never turn the switch on again. In this case, the count will top the value of 1 prisoner less than the total count forever.

The correct answer is to change the behavior of the prisoners to turn on the switch two times. If there are 10 prisoner along with the leader (11 total) then each prisoner will turn the switch on 2 times, so the leader will have to count 20... but it happens that the leader can be sure that everybody entered the room as soon as the count gets to 19, because there can't be a half prisoner. This eliminates the need to know whether the switch was on or off from the beginning.

I have an answer that also works:

Rules - Only the leader can turn the switch on, and off. A regular prisoner can ONLY turn the switch on from off ONCE, AFTER he/she has seen at least one on state and one off state.

Process: State 0: nobody touches the switch, and only the leader keeps flipping the switch on/off or off/on every time he goes in. State 0 -> State 1: when the switch is off, a regular person who has seen at least 1 on and 1 off state can switch on the switch. In the future, this person is never allowed to touch the switch. State 1 -> State 1.5: When the leader comes in, he will see the change in switch state. Then he knows someone has been here. He goes up and flips the switch back down. Then in the coming days, he will keep flipping the switch every time he comes in, until State 2 happens. State1.5 -> State 2: when the switch is off, another regular person who has seen at least 1 on and 1 off state can switch on the switch. In the future, this person is never allowed to touch the switch. (similar to State 0 -> State 1) .....
When We reach State P-0.5, we can stop