QB64 Phoenix Edition
100 prisoners' problem - Printable Version

+- QB64 Phoenix Edition (https://staging.qb64phoenix.com)
+-- Forum: QB64 Rising (https://staging.qb64phoenix.com/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://staging.qb64phoenix.com/forumdisplay.php?fid=3)
+---- Forum: Programs (https://staging.qb64phoenix.com/forumdisplay.php?fid=7)
+---- Thread: 100 prisoners' problem (/showthread.php?tid=1625)

100 prisoners' problem - TempodiBasic - 04-15-2023

Hi
here a mathematical issue showed by a problem.

I have taken from Rosetta Code the issue and the solutions posted in different program language.
There is also a solution posted using QB64. Here the link QB64 100 prisoners

Quote:The Problem
  • 100 prisoners are individually numbered 1 to 100
  • A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
  • Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
  • Prisoners start outside the room
  • They can decide some strategy before any enter the room.
  • Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
  • A prisoner can open no more than 50 drawers.
  • A prisoner tries to find his own number.
  • A prisoner finding his own number is then held apart from the others.
  • If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.

Quote:The task
  1. Simulate several thousand instances of the game where the prisoners randomly open drawers
  2. Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
  • First opening the drawer whose outside number is his prisoner number.
  • If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).


Show and compare the computed probabilities of success for the two strategies, here, on this page.

The solution posted on that site has for founding the mathematical CHAIN knowledge, if i can use no professional words  in a group of randomly creating set of values (index/key  and its internal value) linked using the internal value to call the next item of the set, it happens that chains (subgroup of the original set) born naturally.

The code from Rosetta Code in QB64
Code: (Select All)
Const Found = -1, Searching = 0, Status = 1, Tries = 2
Const Attempt = 1, Victories = 2, RandomW = 1, ChainW = 2
Randomize Timer

Dim Shared Prisoners(1 To 100, Status To Tries) As Integer, Drawers(1 To 100) As Integer, Results(1 To 2, 1 To 2) As Integer
Print "100 prisoners"
Print "Random way to search..."
For a = 1 To 10000
    Init
    Results(RandomW, Attempt) = Results(RandomW, Attempt) + 1
    RandomWay
    If verify% Then Results(RandomW, Victories) = Results(RandomW, Victories) + 1
Next

Print: Print "Chain way to search..."
For a = 1 To 10000
    Init
    Results(ChainW, Attempt) = Results(ChainW, Attempt) + 1
    ChainWay
    If verify% Then Results(ChainW, Victories) = Results(ChainW, Victories) + 1
Next
Print: Print "RandomWay Results: "
Print " Attempts "; Results(RandomW, Attempt); " "; "Victories "; Results(RandomW, Victories); " Ratio:"; Results(RandomW, Victories); "/"; Results(RandomW, Attempt)
Print: Print "ChainWay Results:"
Print " Attempts "; Results(ChainW, Attempt); " "; "Victories "; Results(ChainW, Victories); " Ratio:"; Results(ChainW, Victories); "/"; Results(ChainW, Attempt)
End

Function verify%
    Dim In As Integer
    Print "veryfing "
    verify = 0
    For In = 1 To 100
        If Prisoners(In, Status) = Searching Then Exit For
    Next
    If In = 101 Then verify% = Found
End Function

Sub ChainWay
    Dim In As Integer, ChainChoice As Integer
    Print "Chain search"
    For In = 1 To 100
        ChainChoice = In
        Do
            Prisoners(In, Tries) = Prisoners(In, Tries) + 1
            If Drawers(ChainChoice) = In Then Prisoners(In, Status) = Found: Exit Do
            ChainChoice = Drawers(ChainChoice)
        Loop Until Prisoners(In, Tries) = 50
    Next In
End Sub

Sub RandomWay
    Dim In As Integer, RndChoice As Integer
    Print "Random search"
    For In = 1 To 100
        Do
            Prisoners(In, Tries) = Prisoners(In, Tries) + 1
            If Drawers(Int(Rnd * 100) + 1) = In Then Prisoners(In, Status) = Found: Exit Do
        Loop Until Prisoners(In, Tries) = 50
    Next
    Print "Executed "
End Sub


Sub Init
    Dim I As Integer, I2 As Integer
    Print "initialization"
    For I = 1 To 100
        Prisoners(I, Status) = Searching
        Prisoners(I, Tries) = Searching
        Do
            Drawers(I) = Int(Rnd * 100) + 1
            For I2 = 1 To I
                If Drawers(I2) = Drawers(I) Then Exit For
            Next
            If I2 = I Then Exit Do
        Loop
    Next I
    Print "Done "
End Sub

and its output

[Image: immagine-2023-04-15-123315412.png]

Bplus code
Code: (Select All)
_Title "100 Prisoners Problem" ' b+ 2022-07-17
Randomize Timer
Dim slots(1 To 100) As Long
For i = 1 To 100
    slots(i) = i
Next
Do
    freed = 0: executions = 0
    Do
        GoSub shuffle
        For p = 1 To 100 ' prisoner number
            count = 1: test = p: madeit = -1
            While count <= 50
                If slots(test) = p Then Exit While Else test = slots(test)
                count = count + 1
                If count > 50 Then madeit = 0: Exit For
            Wend
        Next
        If madeit Then freed = freed + 1 Else executions = executions + 1
    Loop Until (freed + executions) = 100000
    Print "Freed"; freed
    Print "Exceutions"; executions
    Print
    Print "Press any for another run of 100,000... "
    Sleep
    Cls
Loop Until _KeyDown(27)
End
shuffle:
For i = 100 To 2 Step -1
    Swap slots(Int(Rnd * i) + 1), slots(i)
Next
Return


'  I saw this last night and just have to check out the solution in code!
' https://www.youtube.com/watch?v=iSNsgj1OCLA

' So 100 prisoners go into a room one at a time and have 50 chances to draw their number from mailbox slots
' they must return the numbers in same box they checked.

' If all the prisoners find their number they go free else they are all executed. Whew!

' But there is a strategy that if used gives them around a 31% chance of being set free!

'       A 31% Change of being set free, how can this be!?

' Here is the startegy, go into the room and pull the number from slot that matches your number.
' From that number go to the number found in the box, contimue in this manner until you find your
' number or you've drawn from 50 slots. If you hit 50 then everyone is doomed might as well start
' another run on the experiment.

' If we run this strategy 100000 times will we get around 31,000 Set Frees and 69,000 Executions?

' Let's see...

' Wow! as predicted

and its output

[Image: immagine-2023-04-15-124335135.png]



References:
Youtube chain method for 100 prisoners
Chain strategy 100 prisoners (the same used by Bplus)
Probability chain rule
wikipedia page 100 prisoners
math stackexchange page 100 prisoners solution

---------------------------------------------------------------------------------
welcome some other implementations of chain method.

RE: 100 prisoners' problem - bplus - 04-15-2023

Yeah my code only confirms that the strategy works as predicted getting around 31% successes if followed.

Rosetta Code task asks to compare using the strategy to just randomly selecting slots with numbers until you reach 50 (failure) or you find yours 50/100 = 50:50 chance but the chance 100 people find theirs randomly is what?

.5^100 = mighty slim partner!

RE: 100 prisoners' problem - SMcNeill - 04-15-2023

Optimal strategy is just have everyone agree to open the first box on the left.

First guy goes in, opens that box, sees number 57..  comes out and yells "57".  Prisoner 57 goes in and gets his number.  Next guy goes in, checks the first box left on his left, walks out and yells that number....

Continue until finished.

RE: 100 prisoners' problem - bplus - 04-15-2023

(04-15-2023, 02:31 PM)SMcNeill Wrote: Optimal strategy is just have everyone agree to open the first box on the left.

First guy goes in, opens that box, sees number 57..  comes out and yells "57".  Prisoner 57 goes in and gets his number.  Next guy goes in, checks the first box left on his left, walks out and yells that number....

Continue until finished.

Sorry,
   

RE: 100 prisoners' problem - SMcNeill - 04-15-2023

That's 100 Prisoner Problem Wiki-style(tm); it's not the same as what Tempodi presented to us.  He never mentioned the lack of communication after the prisoners went into the room and came back out.  Big Grin

RE: 100 prisoners' problem - TempodiBasic - 04-16-2023

(04-15-2023, 02:31 PM)SMcNeill Wrote: Optimal strategy is just have everyone agree to open the first box on the left.

First guy goes in, opens that box, sees number 57..  comes out and yells "57".  Prisoner 57 goes in and gets his number.  Next guy goes in, checks the first box left on his left, walks out and yells that number....

Continue until finished.

Steve your is a Creative solution  but it breaks some rules:




Quote:Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
A prisoner can open no more than 50 drawers.
A prisoner tries to find his own number.
A prisoner finding his own number is then held apart from the others.
If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.

these variations are who find own number is held apart & if all 100 prisoners find own number will be pardoned all, if any don't then all sentence stand.

So intuitively the mission is impossible. It need that all prisoners find they own number because it is sufficient that one fails and all sentences stand. 
I think this is the cause that had led the participans to develop the solution for the wiki version of 100 prisoners problem.
And so I follow the path.

RE: 100 prisoners' problem - bplus - 04-16-2023

The reference I gave at the bottom of my code comment section gave a nice explanation why that strategy works. Apparently in randomized serial numbers list there are pools of non intersecting groups, just need a randomized list that pools no more than 50 in a chain (where the word 'chainway' came from in thatQB64 RC code).

Might be interesting to look at a successful random pooling of a list and see/predict the outcome of the run. It shouldn't matter who goes first nor the order of prisoners following the strategy, their fate was written in the shuffle of numbers.

RE: 100 prisoners' problem - SMcNeill - 04-16-2023

(04-16-2023, 11:04 AM)TempodiBasic Wrote: Steve your is a Creative solution  but it breaks some rules:

Quote:Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
A prisoner can open no more than 50 drawers.
A prisoner tries to find his own number.
A prisoner finding his own number is then held apart from the others.
If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.

I guess I was looking at the problem differently than you guys.

I was thinking a prisoner could go in, open one box, read the number, and then close the box.   By opening *no more* than 50 boxes, I assumed he could walk out and try again later.  For example, he could open the first box, walk out, and then have a chance to go back in again later to open another box.  Unless you find your own number, you're put back in with the group of other prisoners.  The rules say you can devise a strategy before anyone enters the room; it doesn't say whether or not they can talk to each other after entering the room.  I was under the assumption that this was one of those "simple solutions that nobody ever thinks about" type problems which was supposed to highlight the value of teamwork.

Kinda like the school teacher who brings a big bag of candy bars to school and divides his students up into pairs to play tic-tac-toe, with the winner of any game getting a candy bar.  A reward to foster true competition!! Most of the class struggles to get a candy bar, except for these two kids over in the corner who end up with a whole stack of them by the time the exercise was over.  Their means of winning so many?  They simply took turns losing to each other, as the rules never stated that the students couldn't work together to get the rewards!

The way this was wrote up reminded me of that -- a simple solution which only required a little working together to defeat the impossible puzzle.  

I wonder what the odds of winning would be if you just had each prisoner open one box until they found their number, and then move on to the next box and repeat until finished.

For example, box #1 would have the number 27 inside...  The first 27 people would all use one opening until they got that value to the right person, and then the next 73 people would all have a 1/99 chance of getting their number on the first try, rather than a 1/100 chance.  If the next number was 83, then they'd get 2 values in one pass, putting them on the road towards success.  No talking involved then, and if the numbers had several sequential sequences in them, winning should be easily doable in 50 passes.

RE: 100 prisoners' problem - SMcNeill - 04-16-2023

Sequential checking of boxes until the proper number is found:

Code: (Select All)
Dim Shared As Integer Boxes(1 To 100), PC(1 To 100)
Dim Shared As Integer Win, Lose, Games
Games = 1000
For i = 1 To Games
    SetChances
    ShuffleCards
    Box = 1
    For Turns = 1 To 50
        For Prisoner = 1 To 100
            CheckBox Prisoner, Box
        Next
    Next
    GameResult
Next
PrintResult








Sub ShuffleCards
    Randomize Timer
    For i = 1 To 100: Boxes(i) = i: Next
    For i = 1 To 100: Swap Boxes(i), Boxes(Int(Rnd * 100) + 1): Next
End Sub

Sub SetChances
    For i = 1 To 100: PC(i) = 0: Next 'reset each prisoner to not having a card
End Sub

Sub CheckBox (Prisoner, Box)
    If PC(Prisoner) = -1 Then Exit Sub 'prisoner has found his number
    If Prisoner = Boxes(Box) Then
        PC(Prisoner) = -1 '-1 indicated he found his box
        Box = Box + 1 'prisoners now move on to the next box
    End If
End Sub

Sub GameResult '-1 for loss, +1 for win
    For i = 1 To 100
        If PC(i) <> -1 Then Lose = Lose + 1: Exit Sub
    Next
    Win = Win + 1
End Sub

Sub PrintResult
    Print "Of"; Games; "there were"; Win; "which were won, and"; Lose; "which were lost."
    Print Using "Win Ratio: ###.###"; Win / Games
    Print Using "Lose Ratio: ###.###"; Lose / Games
End Sub


   


Strategy here is as I described above:  Each prisoner just starts checking at the first box, until his number comes up, then the prisoners move on to checking the next box.  This assumes that they only open 1 box per trip inside, and that they don't have to check all 50 boxes in a single trip.  They go in, check, walk out. Others take a turn, then they walk back in and check once again for their number.

50ish percent chance for a full pardon seems to me to be much better than just an impossible task.  Wink

RE: 100 prisoners' problem - bplus - 04-17-2023

In case anyone besides me wants to take a peek into the cycles created by random shuffles of 100 numbers here is my "100 Prisoners Group Analysis"

Code: (Select All)
_Title "100 Prisoners Group Analysis" ' b+ 2023-04-17
$Console:Only
Randomize Timer
Dim As Long slots(1 To 100), i, p, visit, c, cycleN

For i = 1 To 100
    slots(i) = i
Next
Do
    GoSub shuffle
    Cls
    ReDim As Long cycle(1 To 100), count(1 To 100)
    cycleN = 0
    For p = 1 To 100 ' prisoner number
        If cycle(p) = 0 Then
            c = 1
            cycleN = cycleN + 1 ' new cycle number
            cycle(p) = cycleN
            visit = slots(p)
            Print "Cycle Number:"; cycleN; " first visit "; visit;
            While visit <> p
                cycle(visit) = cycleN ' assign cycle number to number visit
                c = c + 1
                visit = slots(visit) ' get next number to visit
                Print visit;
            Wend
            count(cycleN) = c
            Print: Print
        End If
    Next
    Print " Note: these cycles end on the prisoner number that started cycle."
    Print: Print
    For i = 1 To cycleN
        Print "Cycle Number:"; i; " Visit Count:"; count(i)
    Next
    Print: Print "     ...zzz"
    Sleep
Loop Until _KeyDown(27)
End
shuffle:
For i = 100 To 2 Step -1
    Swap slots(Int(Rnd * i) + 1), slots(i)
Next
Return

Sample Output of a Run:
   
Here Prisoner 3 failed to find es number in under 50 draws.