100 Prisoners and a light bulb

Question

100 Prisoners and a light bulb

You may have seen this puzzle over on the puzzles exchange or perhaps heard it somewhere else. If you are unfamiliar with this puzzle check out:

100 Prisoners and a Light bulb

The gist of this puzzle is that there are 100 prisoners, each one is separated from one another and must go into a room one at a time. The prisoner selected to go into the room is selected uniformly at random each time. In this room there is a light bulb and a switch, the prisoner must either turn the light on, turn the light off, or do nothing. At any given time one of the prisoners may say that all 100 prisoners have been in the room at least once. If he is correct they are all freed, if they are incorrect they are all killed. Prior to being separated the group of prisoners may discuss a strategy and they may never communicate again.

One working strategy:

The prisoners select one prisoner as the leader. When anyone else enters the room they do nothing unless it's the first time they enter the room and the light is off; in that case, they turn the light on. When the leader enters the room and the light is on then he turns the light off and maintains a counter, adding one to it. Once he counts 99 (the light has been turned on once for every other prisoner) he knows that all 100 (including himself) have been in the room, and he claims their freedom.

The code challenge:

Take no input into your program.

Simulate the strategy and output the number of times a prisoner entered the room before the leader claimed their freedom.

n represents the number of times a prisoner enters the room for the first time.
k represents the leader of the prisoners.
d represents a data structure holding boolean values for each prisoner.
l represents a boolean value to hold the state of the light bulb.
i represents the number of iterations of the puzzle before it ends.

Examples:

Randomly pick an element from d. if l is false and k[rand] is false then l is now true and d[rand] is true. i = i + 1

Randomly pick an element from d. if l is true and d[rand] is false then do nothing. i = i + 1

Randomly pick an element from d. if l is false and d[rand] is true then do nothing. i = i + 1

Randomly pick an element from d. if d[rand] = k and if l is false then do nothing. i = i + 1

Randomly pick an element from d. if d[rand] = k and if l is true, set l to false, add 1 to n. i = i + 1

Randomly pick an element from d. if d[rand] = k and if l is true and n = 99 then end puzzle. i = i + 1 and output i.

this is code-golf so the shortest code wins. Have Fun!

Answer 1

Python 2, 133 bytes

I used binary operations to keep track. I had if(i<1)*b:... but I think that's an off-by-one error. Not sure.

from random import*
L=2**99-1
b=l=c=0
while l<99:
    i=randint(0,99)
    if(i>98)*b:b=0;l+=1
    elif(L&1<<i)*(b<1):b=1;L|=1<<i
    c+=1
print c

Try it online

Less golfed:

from random import*
L=[1for _ in range(100)]
b=l=c=0
while l<99:                         # check leader's count of prisoners
    i=randint(0,99)
    if b and i==99:b=0;l+=1         # if light on and leader, turn off and count
    elif L[i] and b<1:b=1;L[i]=0    # else if new prisoner and light off, turn on
    c+=1                            # iterations
print c

Answer 2

CJam (26 bytes)

100,1a*0-{{__100mr>!}g;}%,

Dissection

100,1a*0-  e# Generate a list [1 1 1 2 1 3 1 ... 98 1 99] representing (in reverse order)
           e# the number of prisoners at each step who can advance to the next step
{          e# For each element in the list...
  {        e#   While we fail to select a suitable prisoner...
    __     e#     dup twice: once to leave on stack as a counter, and once for comparison
    100mr  e#     Select a random prisoner
    >!     e#     Test whether that prisoner is suitable
  }g
  ;        e#  Pop to avoid overcounting by one
}%
,          e# Count up the values we left on the stack

Answer 3

Perl 5, 77 bytes

++$i,($s=0|rand 100)?!$a[$s]&&!$l++&&$a[$s]++:$l&&++$n&($l=0)while$n<99;say$i

Try it online!

Answer 4

Python 3, 164 bytes, aka garbage :)

from random import*
d={}
a=l=n=p=0
for i in range(100):
 d[i]=0
while n<100:
 a+=1
 p=randint(0,99)
 if p==50:
  l=0
 else:
  l=1
 if d[p]==0:
  d[p]=1
  n+=1
print(a)