5 ms·
The prisoners elect a counter. His count is initially 0, but increases to 1 the first time he walks into the room. Whenever he visits the lightbulb he will do
by slashcom 19y ago
The prisoners elect a counter. His count is initially 0, but increases to 1 the first time he walks into the room. Whenever he visits the lightbulb he will do the following:
1) If the lightbulb is off, leave the room.
2) If the lightbulb is one, turn it off and increment his count.
Every other prisoner follows the following rules:
1) If the lightbulb is on, do not touch it.
2) If the lightbulb is off and you have not flipped it on before, flip it on.
3) If the lightbulb is off but you have previously flipped it on, then do not touch it.
When the counter reaches 100, he may tell the guard that everyone has visited.
- amichail 19y agoHow many days does this take on average?
- brlewis 19y agoI haven't done a simulation, but I would guess not much more than 10,000. Almost every visit of the counter would decrement the number of prisoners who haven't flipped yet by one.
- amichail 19y agoThere's a solution that takes around 3500 days.
- brlewis 19y agoCurse you, amichael! No! No, I am not going to try to solve this problem tonight. I'm going to do ourdoings.com coding on the train ride home. I am not going to think about prisoners, light bulbs and distributed systems. I'll check in tomorrow and see if someone else has posted the answer, but I won't try to come up with it myself. You tempt me, but I resist. :-)
- curi 19y agoFirst 99 days: if bulb on: do not touch if bulb off: if you haven't been visited before, consider yourself counted, and do nothing. if you have been in here before, turn it on. you are now the counter. look at the day number (1-based). if it's day 36, then 35 people (including yourself) have visited the room. day 100: if bulb off, and you haven't been there before, declare victory (super lucky!) if off, but you have been there before, you're the counter and the count is 99. if bulb on: turn it off. after day 100: use the original solution with a counter. speedup: you get about 12.2 people counted in the first 100 days. normally it's somewhere around one person counted per 100 days. so total time is around 100 + 87.8*100. a bit better. not near 3500 though.
- curi 19y agoi wrote code. 1000 trials. naive mean: 10389.832 my strategy's mean: 9392.652 i think the improvement was a little less good than i guessed because i jumpstart getting the first dozen or so people counted, and they are a little easier to count than the last people.
- curi 19y agoHere's a paper on the subject: http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul... It includes my answer :)
- shayan 19y agocan you run mine through and see how many days you get!
- corentin 19y agoI'm working on a solution using the current day (modulo the population) as a kind of covert channel to keep track of the number of prisoners who already visited the room (the basic idea is that, if the light is on on day 64, at least 64 people have visited the room). I still have a bug in my algorithm and I'm not even sure it will really work.
- mrtron 19y agoGood guess. 100 runs: Average: 10163 Lowest: 7762 Highest 12391 If I knew how to paste code in here, I would show you my simple python script to test it. Edit: 1000 runs: Average: 10109 Lowest: 7389 Highest 13461
- brett 19y agohttp://news.ycombinator.com/item?id=32766 http://news.ycombinator.com/item?id=32766 It would probably be helpful if that information was readily available via a link near the "add comment" and "reply" buttons
- oditogre 19y agoAlong with all other relevant info for working with text in comments.
- mrtron 19y agoThanks. import random def run(): prisoners = {} for x in range(100): prisoners[x]=0 days=0; counter=0; bulb=0 while counter<100: prisoner = random.randint(0, 99) days += 1 if prisoner == 0: if bulb == 1: bulb = 0; counter += 1 else: if prisoners[prisoner] == 0 and bulb == 0: bulb=1 return days
- slashcom 19y agoI just realized I used "one" instead of "on". :-P Some statistics from my little python simulation: n: 1000 (I ran my simulation 1000 times) Mean: 10425.721 days Stddev: 1005.34467779 days Min: 7506 days Q1: 9711 days Median: 10391 days Q3: 11074 days Max: 14090 days Note: can someone tell me how to do single linebreaks in the comments?
- DanielBMarkham 19y agoSomebody should do an Ask PG for this. The line breaks in the comments drive me nuts. Sometimes they work, sometimes they don't. Sometimes you can start with them working and then they're not working again.