Solution to the prisoner puzzle

A few days pack I posted the prisoners puzzle and I think it’s time to give the solution.

solution

Obviously the prisioners can only use the both switches to communicate with one another after the planning phase so we have to come up with a good plan.

The idea I had is to seperate the prisioners in one boss and minions – the boss will figure out when every minion was inside the room at least once and will
demand their freedom. The minions will only react to the switches.

To indicate if someone new was in the room the idea is to use the right switch. Whenever the boss comes into the room and sees that this one is switched on it will mean
that another minion was in the room. He then will switch it off. In any other case he will just switch the left one – the left one is really only the “I don’t care” switch.

When a minion enters the room and sees the switch off it will turn it on if he did not so already twice! If not he just switches the left one.

Why twice: well the problem is the very first prisoner that enters the room. We cannot know the initial configuration of the switches, nor does a prisioner know if he came in
first or if the boss was already there. So when the switch was on the boss cannot know if another minion came before or if he is the first person in the room and the switch was on.

Therefore every minion will signal twice that he was in the room and so after a probably very long time the boss will have 44 on-states of the right switch and will know that every minion was in the room at least one (maybe all where in twice and maybe one was only in there once, when the initial state of the right switch was on) – but no matter what every minion must have been there once, because all will only switch the right one twice and so if one was not in the room the maximum count of right-switch-on the boss could have seen is:
\[21 * 2 + 1 = 43\]

Code

the implementation of the two types of prisoners is easy:

let createMinion() : Prisoner =
    let reported = ref 0
    fun (left, right) ->
        if not right && !reported < 2
        then
            reported := !reported + 1
            SwitchRight
        else
            SwitchLeft

let createBoss() : Prisoner =
    let counted = ref 0
    fun (left, right) ->
        if right
        then
            counted := !counted + 1
            if !counted = (Count-1)*2 
            then DemandRelease 
            else
                SwitchRight
        else
            SwitchLeft

let prisoners : Prisoner array =
    createBoss() :: List.init (Count-1) (fun _ -> createMinion())
    |> Array.ofList

As you can see both use a local ref-cell to count up their task and answer accordingly.

The complete code snippet is thus:

namespace PrisonerPuzzle

type Switches = bool * bool

module Prisoners =
    
    let Count = 23
    
    type Action =
        | SwitchLeft
        | SwitchRight
        | DemandRelease

    type Prisoner = Switches -> Action

    let createMinion() : Prisoner =
        let reported = ref 0
        fun (left, right) ->
            if not right && !reported < 2
            then
                reported := !reported + 1
                SwitchRight
            else
                SwitchLeft

    let createBoss() : Prisoner =
        let counted = ref 0
        fun (left, right) ->
            if right
            then
                counted := !counted + 1
                if !counted = (Count-1)*2 
                then DemandRelease 
                else
                    SwitchRight
            else
                SwitchLeft

    let prisoners : Prisoner array =
        createBoss() :: List.init (Count-1) (fun _ -> createMinion())
        |> Array.ofList

module Warden =

    type Action =
        | Continue of Switches
        | ReleaseAll
        | ExecuteAll

    let private rnd = System.Random()

    let initialState : Switches = 
        (rnd.Next 2 = 0, rnd.Next 2 = 0)

    type T = Switches -> Action

    let createWarden (prisoners : Prisoners.Prisoner array) : T =
        let took = System.Collections.Generic.HashSet<Prisoners.Prisoner>()
        fun ((left,right) : Switches) ->
            let pNr = rnd.Next Prisoners.Count
            let prisoner = prisoners.[pNr]
            took.Add prisoner |> ignore

            System.Console.Clear()
            System.Console.WriteLine ("pick prisoner number {0}", pNr)
            System.Console.WriteLine ("{0} of {1} have been in the room", took.Count, Prisoners.Count)

            match prisoner (left,right) with
            | Prisoners.SwitchLeft  -> Continue (not left ,right)
            | Prisoners.SwitchRight -> Continue (left, not right)
            | Prisoners.DemandRelease when took.Count = Prisoners.Count
                -> ReleaseAll
            | _ -> ExecuteAll

module Main =

    let rec loop (warden : Warden.T) (state : Switches) =
        match warden state with
        | Warden.Continue state' -> loop warden state'
        | Warden.ReleaseAll      -> printf "relase them all ... grmpf"
        | Warden.ExecuteAll      -> printf "bring me their HEADS ... yeah"

    [<EntryPoint>]
    let main _ = 
        printfn "Starting the game..." 
        let prisoners = Prisoners.prisoners
        let warden = Warden.createWarden prisoners
        let switches = Warden.initialState
        loop warden switches
        0 // return an integer exit code