4
\$\begingroup\$

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 so the shortest code wins. Have Fun!

\$\endgroup\$
  • 4
    \$\begingroup\$ Shouldn't the close vote people add some useful comment? \$\endgroup\$ – user9206 Oct 24 '16 at 12:23
  • 7
    \$\begingroup\$ Better a close vote with no explanation than nothing at all. If it results in the question being put on hold then a reason will be displayed, and others can comment with suggestions for improvement. The idea of putting on hold is to prevent answers coming in until the challenge is ready, so answers aren't invalidated by any changes that need to be made to the wording. It's a positive thing. \$\endgroup\$ – trichoplax Oct 24 '16 at 13:15
  • 3
    \$\begingroup\$ What needs to be quick is putting on hold. That prevents any answers so then improvements can be made slowly until it's ready. I've just read through and decided it isn't yet clear to me, so I've voted to put on hold as unclear. That was the urgent bit. Now I can take the time to try and explain what I found unclear so the challenge can be edited and then reopened. \$\endgroup\$ – trichoplax Oct 24 '16 at 13:24
  • 4
    \$\begingroup\$ For future challenges, I recommend leaving them in the sandbox for a few days to gather feedback before posting here on main. I've done this for all of my challenges except one, and that one didn't go well... I find the sandbox works well for fine tuning and potentially making changes that are harder to make after posting. \$\endgroup\$ – trichoplax Oct 24 '16 at 13:34
  • 4
    \$\begingroup\$ It's worth considering this meta post on non observable requirements. Is it a requirement that code follows the steps described and uses the same method? Or is any code that gives output with the equivalent probability distribution valid? \$\endgroup\$ – trichoplax Oct 24 '16 at 13:54
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I think you've misunderstood the problem. This always prints 100, while the number of times the prisoners have entered the room is variable. \$\endgroup\$ – Dennis May 10 '18 at 15:34
  • \$\begingroup\$ it only prints at the end like @mbomb's answer \$\endgroup\$ – user78881 May 10 '18 at 16:48
  • \$\begingroup\$ As it should. But your answer counts the number of different prisoners that have entered the room, so the result is always 100. \$\endgroup\$ – Dennis May 10 '18 at 16:56
  • \$\begingroup\$ Oh You want the iterations, I see. \$\endgroup\$ – user78881 May 10 '18 at 16:57
  • \$\begingroup\$ That's better, but the output is still incorrect. Compare your answer with mbomb's. \$\endgroup\$ – Dennis May 10 '18 at 17:08
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.