Author |
Topic: 100 prisoners & a light bulb (Read 167295 times) |
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #600 on: Mar 24th, 2008, 7:20am » |
|
It seems the counters on level 0 and observers on levels /\////// seemed to be the most perspective. Current state and most common gen: 3498.78 3497.31 3456.88 3456.88 857 857 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,371,298|325,317|278 3496.03 3495.62 3463.18 3463.18 2574 2574 6260.80 0.00 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,371,298|325,317|278 The combination with "Rezyk": 3743.90 3742.53 3536.31 3536.31 291 291 7:0:9,6:0:8,6:0:8,5:0:7,4:0:6,4:0:6,5:0:6,5:0:6,5:0:6,5:0:6,5:0:6,5:0:6, 5:1:6,4:1:5,4:1:5,3:1:4|1861,632,419|522,417,411,330|362:172,551|311:172 3730.32 3729.80 3688.08 3688.08 465 465 0.00 6668.00 7:0:9,6:0:8,6:0:8,5:0:7,4:0:6,4:0:6,5:0:6,5:0:6,5:0:6,5:0:6,5:0:6,5:0:6, 5:1:6,4:1:5,4:1:5,3:1:4|1861,632,419|522,417,411,330|362:172,551|311:172 here x:y in binary phase lengths denotes x ... len of the phase, y ... number of days to end of phase being crown subphases Other notation ... see page 23. I have to stop the simulation for a while ... but I will return to it at idle time ... there is additional statistics ... average of extra runs ... the runs not finished until next top phase. (6260.80 for the observers only is average of runs where third counter phase was run, and 6668.00 is average of combination with Rezyk when 2nd top phase was run ... this is average of bigger sample and even with that it's much bigger ... this makes it evident that observers are much valuable than crown phase reduction.) I am near to declare this algorithm as the current best one. Comparison to the two level counting scheme: 3500.79 3500.79 3468.37 3468.37 283705 283705 9:0:14,6:0:11,5:0:10,5:1:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,4:1:9| 2015,1744,481 ---------- current state: 3474,02 3471,07 3463,48 3463,48 3137 3137 6242,02 0,00 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,371,298|325,317|278 The experiment is very unstable ... we should wait a while ... 3478,28 3476,06 3469,15 3469,15 3365 3365 6277,57 0,00 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,371,298|325,317|278 3489,87 3489,30 3461,97 3461,97 5662 5662 6283,94 0,00 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,371,298|325,317|278 And I should run the experiment also for 8 counters on the bottom level ... I am currently doing it ... it's even more promissing! And the winner is : Current state for 8 counters /\//////...: 3474 is the average of all 413151 simulations run on all mutations of parameters. 3467 is the average of all 179786 simulations run after last "global kill" on all mutations. 3455 is the average of all 28031 simulations on the listed gen (the most successfull to the population size gen) 3456 is the average of all 27555 simulations after last "global kill" on the gen. 5619 is the the gen average on the extra long runs (being 3 times on level 0) Actually there is another very promissing gen run 16242 times with the average 3445,5 3473.98 3466.73 413151 179786 3454.98 3456.22 28031 27555 5619.40 0.00 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|271,277|278 3445.50 16242 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|271,280|270 And the fresh ones: 3471.92 3465.78 551778 138627 3449.93 3455.21 29862 13620 5602.37 0.00 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|271,280|270 3422.49 1635 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|276,280|270 The 16 counters are much worse: 3494.61 3494.18 295327 ? 3473.94 3473.94 10946 10946 10946 6345.38 0.00 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,379|465,377,380,298|325,317|282 3454.47 1660 7:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,5:0:6,5:0:6,5:1:6, 5:1:6,4:1:5,4:1:5,4:1:5|1702,581,382|465,377,380,298|325,317|287 I have stopped the simulation for 16 counters as it was evidently beaten by 8 counters. May be I will rerun simulation for two level counting to let it stabilise more ... Actually there were some more simulations ... last state was ? 3485 ? 1000204 ? 3467 ? 315234 ? ? 9:0:14,6:0:11,6:0:11,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3:1:8|1973,16 63,404 And this seems to be beaten.
|
« Last Edit: Mar 26th, 2008, 3:02pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #601 on: Mar 29th, 2008, 12:41am » |
|
Final state of simulation for two level counters: 3491.09 3494.29 531541 118593 3460.19 3475.24 20125 20125 485 8:0:13,6:0:11,5:0:10,5:0:10,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9|2005,1 690,415 3457.26 3459.34 14606 14606 12580 10:0:15,6:0:11,5:0:10,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3:1:8|1980,1 668,405 3452.66 9315 9:0:14,6:0:11,6:0:11,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3:1:8|2059,16 63,412 (First gen was most simulated in the history of 531541 simulations with total average 3491.09, 2nd most after last reset (118593) simulations (with average 3494.29) and third most in the last small round) Current state of simulation for 0 level counters and 8 binaries with observers with /\////.. order of binary levels: 3469.47 3466.15 944088 347990 3449.73 3430.83 30530 30530 318 5604.04 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|271,280|270 3444.24 3445.34 24387 24387 23048 5601.52 0:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|356 ,364,292|278,277|265 3446.78 756 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2314,574,440|36 4,373,299|279,284|298 ... actually the most used gen is the same 944088 simulations in total with average 3469.47, 347990 simulations after the last reset with average 3466.15. Current winner is /\//// 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|278,277|265 with average near the bottom of the range 3445-3466.
|
« Last Edit: Mar 30th, 2008, 12:30am by Hippo » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #602 on: Apr 3rd, 2008, 1:09pm » |
|
I have a new solution(I think) but it may be AlexH's. I want to make sure no one has thought of the idea before I try and make the code because it will take me a while. Anyways could someone explain AlexH's leadless binary solution? because I think that may be my solution I can find his solution in the thread though I only find it mentioned in this post http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1027805293;start=350#363 Anyway I'll explain my solution and someone can tell me if its been posted. So I was thinking of the solution where there is one leader, and he counts everyone once and then announces the win. But I realized that if a prisoner turns the light on there is only a 1/100 that the counter will go in the next day. So I thought well if there are two counters that becomes 2/100 which is twice as good. But with 2 people with 50 tokens, there has to be a way for them to communicate with each other that they each have 50. What I noticed is that like in the original Paul Hammond's Multi-stage counting scheme you had to designate a lead counter that would count the other assistant counters. But when there are only two counters both can send there tokens and both can receive. So both are lead counters. So my solution is basically having 8 or 16 counters (I'm not sure which would work best.) Use Gypo's Stage 0 method of distributing the badges. Thing to note (badges will have to be different sizes. So if using 16 the first 4 badges hold 6 (not including them selves) and the rest hold 5. You can only pass a full badge so it won't matter that they are different. In my example I will say that we are using 8 counters. Also I don't know what the stage lengths should be yet so we will just assume they are there and we will eventually get through to the next stages. Ok After the stage 0 which should last 32 days Then starts stage 1 which is like the other stage 1s where the counters count and fill badges. After Stage 1 you have stage2, stage 3, and stage 4 We will assume that all the badges are filled. Stage 2 What happens is half the people pass the badges and half the people receive them. So if a counter sees the light is off and he has an odd amount of badges and at least one of those is filled, he turns it on and drops a badge. If a counter sees it is on and he has an odd amount of badges he turns it off and picks up the badge. So hopefully we end up with 4 people both with 2 full badges Eventually we will get to Stage 3 which is just like stage 2, except you only pass if you have 2 complete badges. Now we have 2 people each with 4 full badges Then Stage 4 if a person has 4 full badges and the light is off he turns it on and drops the badges. If a person has 4 badges and he sees the light on he picks it up and can declare victory, if he has 4 full badges as well. That person should have at most 1 unfilled badge. If there wasn't a win by stage 4 go back to stage 1. Anyway I think you can see what happens. So do you think this would be an improvement? It makes it so each counter can count each other instead of one designative lead counter. One problem I see is that if the it repeats by going back to stage 1. Then there could be wasted days in the other stages. For example. Lets say 4 people have unfilled badges and 4 people have filled. After stage 2 we would have 4 people with 1 filled and 1 unfilled. Now when it gets back to stage 2, nothing will happen because you can only pass 1 badge. So that stage was a complete waste of time. I'm interested in what you think of this solution.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #603 on: Apr 3rd, 2008, 2:52pm » |
|
Your solution is on the right way, but the way is much longer ... I will guess this solution will long around 3900100 days in average. Two stages counting is faster because the most expensive part of the phase is distributing last few tokens/badges and there is no such high risk to be in a wrong phase. The solution proposed by me differs from yours by observers stop method. This method adds to the system very high level of stability actually its pros are bigger than cons corresponding to cost of too many levels. Observers stop which can be used on only binary phases allows prisoners not having badges to remain active. Each observed swith on during level with badges of size 2k means at least 2k badges are collected. Each observed switch from on to off during level with badges of size 2k means at least 2k+1 badges are collected and left the stage with badges of size 2k. Such observations can be in very short time summed up to know all badges were already collected (advantage is that an arbitrary prisoner can declare stop). My first attempts were with binary phases with badge sizes x,1,2,4,2,1,x,1,2,4,2,1,x,1,2,4,2,1,x .... (or ending on level 8, x ... counters phase). Crucial brakthrough was when I changed the strategy to sequence x,1,2,4,2,1,x,1,2,4,x,1,2,4,x,... The downward phase is very important to spread the knowledge ... typically the upward phase ends with (one 8 badge in 16 badges case), one 4 badge, one 2 badge and one 1 badge, remaining badge was not filled yet. This leads to situatin most of the time in downward phases the light is on ... and several prisoners know at the end at least one 1 badge is missing. If the prisoner responsible to collect the badge is among them, he will declare the victory as he creates the badge. If he is not among them, typically soon after the on-off on level 1 the victory is declared. (Actually in most cases the 4th phase is the last and this is not exception when the 3rd phase is last.) It seems this strategy with well chosen parameters has average around 3450 beating two level counting by around 10-15 days. Here is the list of days of last few experiments with the "most spread gen". 4572, 3155, 4745, 3458, 4429, 2871, 2923, 2892, 3602, 3247, 3206, 3635, 3094, 2877, 2817, 2888, 2784, 3641, 2846, 2955, 2823, 3680, 2838, 3186, 3568, 3656, 3421, 3359, 2786, 2721, 4129, 3777, 3073, 2915, 3051, 4195 on Apr 3rd, 2008, 4:09pm, Wardub wrote: I've got a question, is mine different that Alex H's? Could someone explain his. Also Hippo I am not fully understanding you solution. Where in this thread is it so I can look it up. |
| Original binary AlexH algorithm didn't used the initial counting phase, and two counting levels didn't use binary phases. Ideas of my algorithm can be found on pages 21,22,23,24,25. 3466.19 3455.05 2156391 27756 3448.82 3473.46 34868 35 5621.36 0.00 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2277,559,415|35 6,364,292|278,277|265 3418.30 3418.30 1860 1860 5589.36 0.00 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2292,566,421|36 1,369,297|276,282|279 3448.93 81 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10|2220,542,402|35 3,353,279|261,276|268 There are only two prephase patterns for all the most succesfull gens: 10:0:17,8:0:15,6:1:13,5:1:12,4:1:11,4:1:11,4:1:11,4:1:10 and 10:0:17,7:0:14,6:0:13,5:0:12,4:1:11,4:1:11,4:1:11,5:1:11
|
« Last Edit: Feb 20th, 2009, 11:45am by Hippo » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #604 on: Apr 3rd, 2008, 4:09pm » |
|
Ya thinking about it a little more I would say my multiple stages would be come pretty inefficient if one of the stages failed. Which would mean each stage would have to be longer. Anyways I still plan on writing the code for fun. I've got a question, is mine different that Alex H's? Could someone explain his. Also Hippo I am not fully understanding you solution. Where in this thread is it so I can look it up. One last thing, I'm not the greatest programmer and I only have java. I'm thinking I will make a class prisoner. Is there a way in my main to create 100 different prisoners? with like a for loop or something. other wise I will have to do something like prisoner prisoner1 = new prisoner a total of 100 times. Thanks.
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #605 on: Apr 6th, 2008, 8:46pm » |
|
on Apr 3rd, 2008, 2:52pm, Hippo wrote:Your solution is on the right way, but the way is much longer ... I will guess this solution will long around 3900100 days in average. Two stages counting is faster because the most expensive part of the phase is distributing last few tokens/badges and there is no such high risk to be in a wrong phase. |
| WOW I finally finished the program and I got 3905.46 or something after only 50,000 iterations. I think my program is slow but I'll run it over night when I go to bed. So it wasn't even close to the best solution so far. But I was happy it made it under 4000 days. I have another idea but it will likely be over 4000. It has three stages. Basically after stage 0. you have 50 people with 2 tokens. and then its like the 10 counter strategy. I'm hoping by lowering the amount of people each counter has to count will speed up stage 1. Then stage 2 is like all the others with the crown. This probably won't work but I'm trying to come up with new ideas atleast
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #606 on: Apr 7th, 2008, 7:46am » |
|
I guess 4250\pm 100 . You have lost snowroll prephases, reducing number of tokens to collect say to 100*2/3 using only say 100*2/3 days. Actually collecting first 50 tokens requires time much smaller to time to collect the remaining 50. The phase switching cost is higher than the gain. The problem are phases with small number of active prisoners. The expected dalay between their visits is 100/a where a is the number of active prisoners. The phase switching problem is that you don't know during planning the phase lengths which level will be the lowest which was not finished yet. All runs where the phase ended prematurely must wait for all other levels to be able to continue. The most costy is gathering of the last tokens/badges on the level. So the levels cannot be short even when we expected only small number of tokens is left here. Shorter binary phase than 150 is nonsense, 300 (for expected two badges) is enough. For counter phase less than 200 is nonsense, 400 seems to be enough(depends on number of levels ...). on Apr 8th, 2008, 9:22pm, Wardub wrote:Do you have code in java of your method? I assume not. O well. |
| Actually not. I have codded it in fox (Yes I know not the best choice). The code is not very nice ... on Apr 8th, 2008, 9:22pm, Wardub wrote: EDIT: Hippo I see that you have been testing methods. I would also like to test the two leading solutions, which I believe are yours and the SMQ and Leonid. Could you tell me the cycle lengths for each stage? Its probably because its late but I can't seem to find you solution. Is it a build off of a previous one? and which one. Thanks for the help. |
| The best so far parameters can be found on this (25) page. The prephase lengths are included in the length of the first phase. On the page 23 the decodding of the string is described ... the Rezyk post.
|
« Last Edit: Apr 15th, 2008, 1:46am by Hippo » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #607 on: Apr 8th, 2008, 9:22pm » |
|
Actually I got my method in around 3980 days. Under 4000 again . And I understand why the methods don't work as well. Because their is a bigger risk of one of the stages failing with more stages. I haven't really thought of a way to improve the second portion so I wanted to try and speed up the first stages and hopefully it would be enough to compensate for the later stages. Didn't work. Anyways I haven't been able to look at your solution yet, but I plan on this weekend when I have time. Do you have code in java of your method? I assume not. O well. EDIT: Hippo I see that you have been testing methods. I would also like to test the two leading solutions, which I believe are yours and the SMQ and Leonid. Could you tell me the cycle lengths for each stage? Its probably because its late but I can't seem to find you solution. Is it a build off of a previous one? and which one. Thanks for the help.
|
« Last Edit: Apr 8th, 2008, 10:20pm by Wardub » |
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #608 on: Apr 17th, 2008, 9:21pm » |
|
Sorry for double post. HMM I seem to be having trouble replicating results of Gypos method with SWFs improvements. I am getting around 4000 days. When the expected is under 3500 days. I am really curious why this is. I am using {6,5,5,5,5,5,4,4,4,4} for stage 0 cycles and badge sizes of {12,11,11,10,10,10,9,9,9,9} I am using 2000,1600,300,300 for stage cycles. I am really confused, and I would really like to write a program that can get under 3600 days. Ill post my code. Its in java and not the most optimally written. Code: class inmates{ boolean badge; int token; int countSize; int count; int badges; int overCount; boolean lightBulbState; boolean badgeFull; int numberOfDays; boolean countersBadgesFull; boolean crown; int badgePerson = 0; int badgeAssign = 0; int totalBadges = 0; boolean firstBadge = true; int crownBearer = 0; int [] CYCLES = {6,5,5,5,5,5,4,4,4,4}; int [] BADGES = {12,11,11,10,10,10,9,9,9,9}; int winCount = 100; public inmates(){ badge = false; numberOfDays = 0; token = 1; countSize =0; count = 0; badgeAssign = 0; winCount = BADGES[0]*BADGES.length; badges = 0; overCount = 0; badgeFull = false; countersBadgesFull = false; crown = false; totalBadges = CYCLES.length; } // Stage 0 uses short cycle days to distribute the badges. public inmates[] stage0(inmates[] prisoners){ boolean lightState = false; int days0 = 0; for(int j = 0; j < CYCLES.length; j++) { for(int i = 0; i < CYCLES[j]; i++) { int Select = (int)(Math.random()*100); days0++; if (lightState) { if(i==0) { assignBadge(prisoners,Select,BADGES[0],CYCLES[j-1]+BADGES[0]-BADGES[j-1]); prisoners[Select].token--; } else if(i == CYCLES[j]-1 && j == CYCLES.length-1) { assignBadge(prisoners,Select,BADGES[0],i+BADGES[0]-BADGES[j]); } else if(!prisoners[Select].badge && prisoners[Select].token < 1) { lightState = false; assignBadge(prisoners,Select,BADGES[0],i+BADGES[0]-BADGES[j]); } else prisoners[Select].token--; } else if(!lightState && i==0) { if ((prisoners[Select].badge) || (prisoners[Select].token >=1)){ prisoners[Select].token--; lightState = true; } else { assignBadge(prisoners,Select,BADGES[0],0+BADGES[0]-BADGES[j]); } } else if(!lightState && j==CYCLES.length-1 && i==CYCLES[j]-1) { //System.out.println(j + " " + i); if((!prisoners[Select].badge) && (prisoners[Select].token>0)){ prisoners[Select].token--; lightState = true; } } } } //end setLight(prisoners,lightState); setDays(prisoners,days0); return prisoners; } // Assigns prisoner a badge with certain amount of tokens. First badge also gets crown public void assignBadge(inmates[] inmates,int person, int size, int tokens){ inmates[person].badge = true; inmates[person].token += tokens; inmates[person].countSize += size; inmates[person].badges++; badgePerson++; inmates[person].badgeAssign = badgePerson; if(firstBadge) { inmates[person].crown = true; firstBadge = false; crownBearer = person; } } // Sets the light state public void setLight(inmates[] prisoners,boolean lightState){ for(int i = 0; i<100; i++) prisoners[i].lightBulbState = lightState; } // Gets light state ------------------------------------------------------------------------ ----- public boolean getLight(){ return lightBulbState; } //Sets day number ------------------------------------------------------------------------ ------------ public void setDays(inmates[] prisoners,int days){ for(int i = 0; i<100; i++) prisoners[i].numberOfDays = days; } // Get day number ------------------------------------------------------------------------ ------------- public int getDays(){ return numberOfDays; } // ------------------------------ Stage 1 ---------------------------------------------- // Counters try to fill their badges public inmates[] stage1(inmates[] prisoners, boolean lightBulb, boolean last){ numberOfDays++; boolean lightState = lightBulb; int Select = (int)(Math.random()*100); if(lightState == true){ if((prisoners[Select].badge) && (prisoners[Select].token < (BADGES[0]*prisoners[Select].badges))){ prisoners[Select].token++; lightState = false; } else if(last){ if(prisoners[Select].badge){ prisoners[Select].overCount++; lightState = false; if(prisoners[Select].badge && prisoners[Select].token >= (BADGES[0])) { lightState = true; prisoners[Select].token-=BADGES[0]; prisoners[Select].badges--; if(prisoners[Select].badges ==0) prisoners[Select].badge = false; } } else{ prisoners[Select].token++; lightState = false; } } } else if((lightState == false) && (!last)){ if(prisoners[Select].overCount > 0) { prisoners[Select].overCount--; lightState = true; } else if((!prisoners[Select].badge) && (prisoners[Select].token > 0)){ prisoners[Select].token--; lightState = true; } } else if(lightState == false && last) { if(prisoners[Select].token >= BADGES[0] && (prisoners[Select].crown == false)) { prisoners[Select].token-=BADGES[0]; prisoners[Select].badges--; lightState = true; if(prisoners[Select].badges == 0) prisoners[Select].badge = false; } } setLight(prisoners,lightState); setDays(prisoners,numberOfDays); return prisoners; } //end stage 1 |
|
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb escape.java
« Reply #609 on: Apr 17th, 2008, 9:22pm » |
|
second part of class and the main that runs the program Code:// ------------------------------------------------- Stage 2 ------------------------------------- // Counter with crown counts up filled badgess public inmates[] stage2(inmates[] prisoners, boolean lightBulb, boolean last){ numberOfDays++; boolean lightState = lightBulb; int Select = (int)(Math.random()*100); if(lightState == true) { if(prisoners[Select].crown || (last)) { prisoners[Select].token+=BADGES[0]; lightState = false; prisoners[Select].badges++; prisoners[Select].badge = true; } } else if(lightState == false && (!last)) { if((prisoners[Select].badge) && (prisoners[Select].token>= BADGES[0])) { lightState = true; prisoners[Select].badges--; prisoners[Select].token-=BADGES[0]; if(prisoners[Select].badges == 0) prisoners[Select].badge = false; } } if(lightState == false && last) { if(prisoners[Select].overCount > 0) { lightState = true; prisoners[Select].overCount--; } else if(!prisoners[Select].badge && prisoners[Select].token > 0) { lightState = true; prisoners[Select].token--; } } setLight(prisoners,lightState); setDays(prisoners,numberOfDays); return prisoners; } public boolean checkWin(inmates[] prisoners){ for(int i = 0; i<100; i++) if(prisoners[i].token==BADGES[0]*BADGES.length) return true; return false; } public boolean check1(inmates[] prisoners){ for(int i = 0; i < 100; i++) if((!prisoners[i].badge && prisoners[i].token >0) || prisoners[i].overCount>0) return false; return true; } } //START OF MAIN ------------------------------------------------------------ public class escape { public static void main(String [] args) { int times = 10000; double fail1=0; double fail2=0; double finalCount = 0; int runTime = 0; boolean lightBulb = false; boolean Game = false; int[] winCount = new int[times]; for(int j = 0; j < times; j++) { Game = false; runTime = 0; finalCount = 0; int [] Cycle = {2000,1600,300,300}; inmates[] prisoner = new inmates[100]; for(int i = 0; i < prisoner.length; i++) prisoner[i] = new inmates(); prisoner = prisoner[1].stage0(prisoner); while(Game == false) { for(int i = 0; i < Cycle[0]; i++) { lightBulb = prisoner[1].getLight(); if(i==Cycle[0]-1) prisoner = prisoner[1].stage1(prisoner,lightBulb,true); else prisoner = prisoner[1].stage1(prisoner,lightBulb,false); if(runTime == 0) { if(prisoner[1].checkWin(prisoner)) { runTime++; winCount[j] = prisoner[1].getDays(); Game = true; } } } Cycle[0] = Cycle[2]; if(!prisoner[1].check1(prisoner)) fail1++; for(int i = 0; i < Cycle[1]; i++) { lightBulb = prisoner[1].getLight(); if(i==Cycle[1]-1) prisoner = prisoner[1].stage2(prisoner,lightBulb,true); else prisoner = prisoner[1].stage2(prisoner,lightBulb,false); if(runTime == 0) { if(prisoner[1].checkWin(prisoner)) { runTime++; winCount[j] = prisoner[1].getDays(); Game = true; } } } Cycle[1] = Cycle[3]; if(!prisoner[1].checkWin(prisoner)) fail2++; } } for(int i = 0; i < times; i++) finalCount+= winCount[i]; System.out.println(finalCount/times); |
| I left off some of the stuff at the top and bottom because they were useless. My program runs fine but I can't replicate their days. I would like to write a program that can get under 3600 days, what method should I use? preferably easiest to code for a beginner and in java. Ok my code came out funny so Ill just attach it as well. I would really appreciate it if someone could try and run my program(it does work) and try and figure out if my answers are wrong or not.
|
« Last Edit: Apr 17th, 2008, 9:40pm by Wardub » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #610 on: Apr 18th, 2008, 12:31am » |
|
I am not an expert on java, but there are some strange things in your code. 1) You use BADGES[0] more often I would expected. The conditions to check don't require it. 2) There is no need to distribute information about current day to all prisoners. Only the selected one got new information and can stop the process so there is also no need to ask each prisoner if he wants to stop. So it is sufficient to update current date for the selected prisoner. 3) Actually you don't need to maintain countsize and compare tokens with countsize. Equal comparision can be obtained by lowering the tokens by the value to be added to countsize and compare to zero instead. Creating third counter ... overcount I didn't catch at all. 4) There are some possible improvements in prephases ... 2nd-3rd day hook and redistribution days, but these can short the computation by say 3-4 days. Especially 1) makes it difficult for me to check the correctness of the code. But I would expected there is a bug. For the parameters you have described the average run time should be under 3700 (probably near 3500).
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #611 on: Apr 18th, 2008, 11:38am » |
|
Let me try and explain it a little. And I am no means an expert at java either. 1.) I have different size badges, but it is easier to compare if all the badges are the same size. So BADGES[0] is the size of all badges. Then it adds fake tokens to prisoners that get smaller badges. So everyone counts up to BADGES[0]. This means in my program there are more than 100 tokens but I am fairly sure it runs correctly. 2. I know this, and the prisoner doesn't really keep track of anything. It more or less makes sure that everyone is on the same day, and that the lightbulb is in the right state every time someone enters. I know its inefficient but it was the easiest way I could come up with. No prisoner gets any extra information by this. 3. I don't think i used countsize or a lot of variables. I just added some that I thought I might need and ended up not using them. Over count is on the last day of stage 1. If the light is on and the person selected has a full badge then they need to pick up that token or else it will be lost. But then they have to many tokens. So overcount is basically a count of tokens more than their number of (badges*badgesize) I probably could of just added the token. And then added an if prisoner.token>badgeSize) then turn light on and subtract a token. But I didn't think of it right away. 4. Not sure what you mean by 2-3 day hook and redistribution. To clarify a few things. I first wanted to replicate gypos method, but I thought I could improve it by changing the cycle lengths in stage 0. I ran some simulations and it takes about 13.2 days on average for a prisoner to go into the room twice the first time. So I was going to make the first cycle be 13 days and progressively decrease it. BADGES[0] will always be the badge size. This means the prisoner with the crown must count up to BADGES[0] * number of badges. When it assigns badges the prisoner gets how ever many people have been since the beginning of the cycle + (Size of the badge[0] - badge[j] where j is which badge it assigns.) So a little example with int [] CYCLES = {6,5,5,5,5,5,4,4,4,4}; int [] BADGES = {12,11,11,10,10,10,9,9,9,9}; first badge assigned gets however many passed plus 12-12. Then the next person gets however many have passed + 12-11. So he gets an extra token and now counts to 12. this happens for everyone so everyone counts up to the same amount, and it is easier to check because now a badge is full if tokens >=BADGES[0] Hope that makes sense. And thanks for trying to help me out. Edit: I believe it works correctly but I am getting a lot more failures I believe after the stage 1 then others are getting and this is raising the average. I think the problem might be in stage 0 or stage 1. Could you perhaps see on average how many people are counted after the stage 0? I would like to see if that matches. I gotta go now, I'll come back and post how many people on average have no tokens after stage 0 completes.
|
« Last Edit: Apr 18th, 2008, 11:44am by Wardub » |
IP Logged |
|
|
|
alien2
Uberpuzzler
Gender:
Posts: 6991
|
|
Re: 100 prisoners & a light bulb
« Reply #612 on: May 22nd, 2008, 10:26am » |
|
Quote:Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion? |
| Who cares about an optimal plan if it will work after, perhaps, 50 years? I'd wait for no more than 10 years. So within this decade I'd be sure to make the assertion if the warden picks me.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 100 prisoners & a light bulb
« Reply #613 on: May 23rd, 2008, 5:06am » |
|
on May 22nd, 2008, 10:26am, Iceman wrote: Who cares about an optimal plan if it will work after, perhaps, 50 years? I'd wait for no more than 10 years. So within this decade I'd be sure to make the assertion if the warden picks me. |
| Current "best" approaches have expected run-times of less than a decade.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #614 on: Nov 22nd, 2008, 11:33pm » |
|
I have spoke to frends about the history of improvements of the problem what made me find one more improvement in the algorithm ... I didin't finish all the experiments, but it's very promissing. For 8 counters with binary observers, /\///... order of phases and fine tuned snowball prephases my average of the enitre population of mutation algorithm is under 3433 days. Best gens so far are around 13 days better. The trick should be tested on 2 level counters scheme as well on 16 counters with bineary observers ... improvements may be even better for these cases. So stay tuned So what was the improvement?: The trick where "2nd night of the snowball signalling the light off means there is badge and one less token compared to light on signal" can be used for 1st night of the secondary snowballs. This wouldn't be good enough if we don't prevent double badge situations. Taking 2nd badge after 1st subsnowball night is devastating. Trick is in increasing the number of tokens by 2 and letting light on in such situation. This double badge prevention can be more generalized ... if a prisoner with 2 badges is near the bulb in prephase when light is off, he switches it on and leaves badge and appropriate number of tokens in the room. Actually there is much better generalisation I didn't implement yet ... almost what Rezyk described in "passing terminology". Each night of all snowball prephases has defined amount of badges and tokens represented by light on signal and amout of badges and tokens represented by light off signal. When prisoner enters, he collects the amount corresponding to light status and checkes if he is able to leave the light on signal of the following night. If he is "able", he lights on and leaves the badges and tokens according the next night signalling. To be "able" means he has (either more badges or equal amount of badges and tokens*) as the next night signalling. This generalisation makes improvement even in situation prisoner with one badge enters in the middle of interrupted snowball (light off) and he can leave everything he collected to let the snowball continue (rare case, in this situation with snowball running it's better to continue than interrupt it, so this is better to restart than let it interrupted). One more trick not implemented yet: The redistribution subphases neednot signal the same number of tokens as finished snowball. They are to prevent 2 badges in one prisoner hands ... to distribute 2 badges goal to 2 prisoners. We know that 2nd badge was collected by full snowball (we don't take 2nd badge before snowball end), the first one neednot be. Sending all tokens collected in the already finished snowball typically creates 2nd goal smaller. It seems to me decreasing the signal by 1 token would improve the goal distribution (when goals for fully successfull snowballs are chosen almost equal). ---------------- * actually if expected collection in the rest of the snowball phase is greater than the tokens he should keep, it's better to restart even in this case. So each badger in such situation computes the expected collection ... or it can be precomputed. (I don't expect the number of tokens he keeps (which would be much less than expected goals) make big impaction to "lighting on" behaviour in collection phase.) For the case 10:0:17,7:0:14,6:0:13,5:0:12,4:1:11,4:1:11,4:1:11,5:1:11 i have made some calculations ... if the badger defined by the first snowball gathers 3,4,5 or 6 tokens, he can restart the 2nd snowball even 2nd day when he must became nonbadger with upto 3 tokens. This is the only case nonbadger with 3 tokens may be created in "optimal" algorithm. Badger with 3,4 or 5 tokens can restart 3rd snowball creating nonbadger with upto 2 tokens. Badger with 3 or 4 tokens can restart 4th and 8th snowball creating nonbadger with upto 1 token. Finaly badger with 3 tokens can restart 5th, 6th and 7th snowball without remaining tokens. It seems the condition is the number of remaining nights of snowball after restart night is sufficient to be more than number of tokens left in nonbadger hands, but for wrongly chosen snowball lengths the result would not be so easily described. ---------------- After some experiments: The cons of restarting is increase of probability doublebadger is created. This is why I restart with remaining tokens only when the remaining length of snowball is at least one more night longer now. Pessimistic restarting ... at most 2 tokens remains in prisoner hand when becoming nonbadger, At least 2 more nights of snowball than remaining tokens in prisoner hand (if some token remain). For 2 level counting 8:0:13,6:0:11,5:0:10,5:0:10,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9|2081,1 743,444 gets around 3505, average of whole population 3532. Does not seem to converge to under 3460. (5:0:12,4:0:10,4:0:10,4:0:10,4:0:10,4:0:10,4:0:10,4:0:10,4:0:10,3:0:9|19 69,1600,300,300 got around 3670) But I should rerun it on the gen 9:0:14,6:0:11,6:0:11,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3,1,8|1973,16 63,404 having best results (~3467) without snowball optimisation. For 8 counters with observers binary /\//// 10:0:17,7:0:14,6:0:13,5:0:12,4:1:11,4:1:11,4:1:11,5:1:11|2234,556,418|35 3,366,311|272,282|292 gets around 3414, average of whole population 3427.
|
« Last Edit: Dec 1st, 2008, 2:30pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #615 on: Nov 26th, 2008, 6:49am » |
|
Icarus notes about problem history History BanderSnatch - Complete cycle scheme. Run-time = 1.0608 x 1044 days. Captain Caveman (quoting from a slash-dot site) - Single stage counting scheme ("Leader solution"). Run-time = 10418 days (28.5 years). sjbrown - Distribution scheme, stage length = 1, only the prisoner can pass his marker. Run-time ~ 8230 years (per Mattian). S. Owen - Distribution Scheme, stage length = 1 (anyone possessing a marker can pass it): Run-time 252 years (per Mattian). Salem - Single stage counting scheme with 100 day "snowball" round. Run-time =9367 days (~25.6 years, per Mattian). AlexH - Single stage counting scheme with short "snowball" round. Run-time = 9321 days (per Mattian). Paul Hammond - Multi-stage counting scheme (future cycles start from scratch). Run-time = 3964 days (~10.8 years, per Mattian). AlexH - Multi-stage counting scheme (future cycles are continuations, stage lengths vary between cycles). Run-time ~ 3600 days AlexH - Leaderless binary counting scheme. Run-time ~ 4250 days biwema - Counting scheme with mixed-value tokens: Run-time = 3600 days. SWF - Counting scheme with multi-leader snowball round. Run-time = 3535.6 days. Rezyk - Counting scheme (consolidation round, greedy leader, 2nd cycle degeneration). Run-time = 3532 days. gypo - Counting scheme (borrowing against badges). Run-time = 3489 days Paul Hammond - Distribution scheme with stage length >1. Run-time ~ 54,000 days (148 years) rmsgrey - Distribution scheme with varying stage lengths between cycles: Run-time ~ 53,000 days (145 years) As Icarus is out of there ... I should insert myself into the table... . Leonid Broukhis + SMQ - improved gypo's 2 level counting scheme by optimisation of mutlisnowball prephases - declared around 3460 days. Hippo - observers method with /\/\/\ order of binary phases added to binary scheme of AlexH. Run time around 3800 days. Hippo - Bottom stage 2k counters with multiple snowballs, binary observers /\/\/\ phases above. Run time for 24 counters for well chosen parameters around 3490 days. Run time for 23 counters for well chosen parameters around 3490 days. Hippo - Bottom stage 23 counters with multiple snowballs, binary observers /\//// phases above. Run time around 3465 days. Hippo - Badge delay in first possible fail night in multiple snowballs applied to 8 counters with binary observers /\////. Runtime under 3430 days. Hippo - Badge delay in first possible fail night in multiple snowballs applied to 12 counters with binary observers /\//// and ternary top phase. Runtime under 3390 days. Algorithm (with small diferences /\/\) actualy mentioned on Hippo, but rejected without tests at that time. Hippo - Badge delay in first possible fail night, pessimistic restarting in multiple snowballs applied to 2 level counting scheme so far above 3490 (far from improvement from declared 3460).
|
« Last Edit: Feb 20th, 2009, 12:34pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #616 on: Dec 2nd, 2008, 2:39am » |
|
I have rerun the algorithm with pessimistic restarting and badge distribution dalay of first fail night on the gen 9:0:14,6:0:11,6:0:11,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3,1,8|1973,16 63,404. And first few simulation had average around 3430, but a serie of long runs occurs and the average went to around 3530. May be parametrisation of phase lengths is not optimal. If first phase fails, it's probable one counter remains, but it's remaining goal may be bigger than 1 (especially for double badger case). On the other side, for 2nd level, the probability the crown goal remain higher than 1 is much smaller. May be section for bottom phase lengths and section from top phase lenghts may improve the behaviour (3 values in first section, 2 values in second one).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb 100prisOOP.zip
« Reply #617 on: Dec 2nd, 2008, 3:26pm » |
|
on Nov 26th, 2008, 6:49am, Hippo wrote: You seem skeptical. Working code attached; the reported mean is 3460.43 days for 10,000 trials and 3464.61 days for 1,000,000 trials (with a standard deviation around 673). --SMQ
|
« Last Edit: Dec 2nd, 2008, 3:31pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #618 on: Dec 2nd, 2008, 5:57pm » |
|
The problem with a simulation is with the quality of pseudorandom generator. I am surprised with the inconsistency of my experiments on 2 level counting. ... previous experiments with best gen around 3467 but population average around 3485. And current results (after I hope improved snowball phases) worse. I haven't run the experiments now for long time (around an hour) as the binary method looked much more perspective (I hope to beat even 3400 days, but 3410 is much more realistic result). I had implemented it in slow environment and it takes around 3 days before the gen stabilises. It will be rerun later. Probably I should compute standard deviation as well... [edit] There is slight difference in my encodding of phase lengths ... according to your code, I should use gen ...|2009,1600,300,300. I suppose the code is from may 2006 so you fill badge sizes by positive tokens collect badges to given count as was recomended at that time ... I would use negative token counts instead of setting badge sizes. Actually when filling 2 badges, it does not matter one is already filled so you can move goal to only one of them.... hold one of them and send others. The first snowball fail possibility dalay was not implemented even for the 2nd night. (snowball restarting was not implemented, too) ... so I hope for more than 10 days of improvement. P.S.: Your signalling between two prephases would be described by 1 day goal reassignment in my terminology. The 0 in 9:0:13 would mean the night "between two prephases" is used by snowball signalling ... badger selected last day should send one of his tokens back, if selected earlier the prisoner is counted. ... This is the number of nights of signalling method I use in the gen. [/edit]
|
« Last Edit: Dec 3rd, 2008, 7:49am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #619 on: Dec 2nd, 2008, 7:15pm » |
|
on Dec 2nd, 2008, 5:57pm, Hippo wrote:The problem with a simulation is with the quality of pseudorandom generator. |
| Well, one of the problems, at least. The code I attached above uses the Mersenne Twister generator, which was specifically developed for running Monte Carlo simulations where the subtle correlations of a simpler generator could be influential. Quote:Probably I should compute standard deviation as well... |
| Well, I'm not sure it's the most useful measure here, since the staging groups results together into peaks. When I get a chance I'm going to unpdate my code above to compute std. dev. for each stage separately and see what that looks like. I haven't looked at it in a while, but I'm not convinced that Leonid searched the entire parameter space of that algorithm: maybe there's another day or two to be found in it yet. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #620 on: Dec 6th, 2008, 1:06am » |
|
Thanks for the link, I will replace the generator and we will see the difference ... after some time Hmm, making Uniform distribution from MT19937 by modulo (throwing away small number of values to make each class of the same size) ... the results of simulation give population average around 3526 and best gen so far around 3504 (started by gen corresponding to your algorithm). ... I should check my code carefully. ... after a long while ... (simulation of more than 3 500 000 games) gives the total average 3428, with the most spread gen 10:0:17,7:0:14,6:0:13,5:0:12,3*(4:1:11),5:1:11|2236(10+7+6+5+3*5+6+2187) ,559,421|356,371,317|273,286|292 having around 30700 simulations with average 3416. All the best gens give the same prephase. The gen with |2229(49+2180),579,430|368,375,327|289,303|309 having around 30000 simulations with average 3412. (Of course these simulations are on 8 counters with binary phases in order /\///// with observers and 8 snowballs each with first fail night hook) The simulations are with MT19937 generator used to select a prisoner by mod 100 operation after throwing away some random values to make sure each mod class has the same number of results. The situation was not changed until the end of simulation process. (the average of the 2nd gen around 3412 with 31023 simulations, total average around 3427, average around 3416 for most spread gen with 31175 simulatios). Third most spread had average around 3422. Fourth most spread gen (with 26168 ) simulations had average around 3407 (10:0:17,7:0:14,6:0:13,5:1:12,3*(4:1:11),5:1:11|2223,553,421|352,363,310 |273,281|296).
|
« Last Edit: Jan 2nd, 2009, 4:46am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #621 on: Feb 17th, 2009, 2:00pm » |
|
New progress noted in n prisoners and k state switch, I have started experiments with counters with binary /\//// observers and with ternary top phase (first fail hook in snowballs, and carefull snowball restarting) and I was very surprised by success of this strategy. I got under 3390 average of all simulations, (3377 after last of 3 restarts) most spread gen had average around 3355: 3:0:9,3:1:9,3:1:9,3:1:9,3:1:8,3:1:8,3:1:8,3:1:8,3:1:8,3:1:8,3:1:8,3:1:8| 1928,657,665|440,442,439|506,512|378 I was very surprised by very short snowballs with big prevention of doublebadge ... it was common to all most successfull gens. on Jan 17th, 2008, 6:50am, SMQ wrote: Although I can't find the paper at the moment, I believe the single leader solution to the IBM version has indeed been proven optimal. --SMQ |
| Actualy yes and no, the nC2 case has better solution they use single counter to count 2*n tokens. Better solution is to count to n tokens. (It requires waiting for reset not to count the possible initial switch on. Only the counter can change the switch state at beginning, other prisoner starts signalling after observing switch state change. This is why counter switches on with nonzero probability (switching always off). I would switch as counter on with probability (n-tokens collected)/n, but this may not be optimal). I would guess this method took around n(n+4) visits in average compared to around 2n(n+1) of IBM.
|
« Last Edit: Feb 20th, 2009, 2:17pm by Hippo » |
IP Logged |
|
|
|
cheeku
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #622 on: Mar 10th, 2009, 3:42am » |
|
Hi This could be one of the possible solution: 100th Prisoner will be the coordinator who will finally announce that all 100 Prisoners have visited the room. Algo: Everyone has to switch on the bulb once if bulb is off. And 100th prisoner has to switch off the bulb whenever he enter the room and finds it ON. eg:Lets say, 21st prisoner comes on the 1st day => he will switch ON the bulb. 51th Prisoner comes on the second day. He wont do anything and keep the bulb ON... This will continue till the turn of 100th prisoner comes and he switch it OFF. Now 21st prisoner turn is over and he wont do anything now onwards whatever be the status of bulb. And 100th prisoner will keep counting whenever he finds the bulb ON and would announce when he does it 99 times.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #623 on: Mar 10th, 2009, 5:20am » |
|
That is indeed one possible solution, known around here as the "single leader" solution. On average it will take almost 30 years for the prisoners to be freed that way. Can you think of any possible improvements? --SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #624 on: Mar 10th, 2009, 6:58am » |
|
Before this thread spills over to yet another page -- 25 pages is enough -- I'm going to lock it and start two new ones: one for general discussion and one for advanced solutions. --SMQ
|
|
IP Logged |
--SMQ
|
|
|
|