Talk:100 prisoners

Wikipedia link?

Despite the heading on the task page claiming otherwise, there does not appear to be a wikipedia entry for "100 prisoners" --Thundergnat (talk) 00:56, 5 November 2019 (UTC)

Fixed.     -- Gerard Schildberger (talk) 19:04, 5 November 2019 (UTC)

Thanks. (Although I'm in two minds - maybe wikipedia should just be another reference)? --Paddy3118 (talk) 20:40, 5 November 2019 (UTC)

Well, if that's where you obtained the description, then leave it as is;   but Wiki's description is more more dire   (with a penalty of execution for all if any prisoner fails).   Brutal.     Not   G   rated.     -- Gerard Schildberger (talk) 20:55, 5 November 2019 (UTC)

I copied this part too, as otherwise the problem is not clearly stated: what if any fails? It wasn't even mentioned. Eoraptor (talk) 12:34, 7 November 2019 (UTC)

big speed up

Thanks to (userid)   Craigd   (using zkl),   his observation/optimization of:       if one prisoner fails, they all do.

A big decrease in time used.

It's programmers like Craigd that make me say:       Damn!     Why didn't   I   think of that ?!?!     -- Gerard Schildberger (talk) 20:28, 5 November 2019 (UTC)

That's in the Python too; the first failing prisoner breaks out of the for prisoner in ... loop. --Paddy3118 (talk) 20:48, 5 November 2019 (UTC)

I can't read   Python,   but I read   zkl   comments very well.     -- Gerard Schildberger (talk) 06:15, 7 November 2019 (UTC)

Well, it's in the statement of the problem (on Wikipedia, now also on RC): "If just one prisoner does not find his number, all prisoners die." So one just has to think of reading the problem statement. Eoraptor (talk) 12:29, 7 November 2019 (UTC)

Test at 10 prisoners too?

Would it be worth asking for a test run at 10 prisoners as well (as I did in the Perl 6 entry) to verify that the logic is correct for random selection? Right now, with 100 prisoners the random portion could be just be: "Fail" and it would be only be wrong 7.89e-29 percent of the time. If tested with 10, the prisoners should be pardoned ~.097 percent of the time. Though I see that the task has already been promoted out of draft after... ~18 whole hours? What's the rush? --Thundergnat (talk) 22:45, 5 November 2019 (UTC)

No card viewed en route to a find needs further checking

If any prisoner finds their card within the number of steps allowed, all card numbers viewed en route can also be found in exactly the same number of steps.

Only numbers not yet seen at all are in different cycles, and still need to be checked.

If your colleague found their card, and saw yours en route, there’s no need for you to look in the boxes. Hout (talk) 12:56, 7 November 2019 (UTC)

You speak of the optimized version?

The rules state that each prisoner may open only 50 drawers and cannot communicate with other prisoners

So the start drawer is drawer_number= prisoner_number
Horst.h (talk) 13:19, 7 November 2019 (UTC)

That’s right, and thats why every prisoner starts exactly one full cycle length away from their card. Prisoners don’t talk to each other, but when the simulator has checked one number in the cycle it has checked them all. Hout (talk) 14:45, 7 November 2019 (UTC)

Each prisoner in a particular cycle group enters that cycle at a different absolute position, but at exactly the same relative position - immediately after their target card, which itself points at (contains the 1-based index of) their start position. Every prisoner in that group needs exactly the same number of steps - the full cycle - to complete the chain and reach their target. If the cycle length is 50 or less, all prisoners with numbers in that cycle reach their card. If the cycle length is 51 or more, none of them do. Hout (talk) 14:55, 7 November 2019 (UTC)

Finally, not only does a single find (a single cyclical pathway of length <= 50) tell us that every prisoner with a number on that path can reach their card, and needs no further checking - it also tells us that once the combined (summed) lengths of the viable paths we have seen reaches 50, no more further checking of any kind at all is needed. Survival of all has been established - no room remains for any cycle-path that is long enough to fail. Hout (talk) 15:14, 7 November 2019 (UTC)