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)

Are you trying to say, prisoner A is not in cycle I so add that cycle length and try a new one, until the right cycle is found or A is not pardoned.So you marking every drawer with number and its cycle-number and every prisoner with his number and cycle number to speed things up. Horst.h (talk) 16:18, 7 November 2019 (UTC)

No, not quite.

The first point is that the rules of the optimal strategy define any successful path from starting box to found card as a cycle. (If this is not immediately clear, consider taking one more move after we find our card. Where are we now ? Back at the start - by definition - our card contains the index of the box which the optimal strategy instructs us to start with).

The second point is that when we have run the test for one prisoner, and reached their card in 50 moves or less, we have collected a full cycle of this kind, from starting box to found card, (and any next move would lead us to the start again), so now we now know the whole route/path/cycle not only for our first prisoner, but for every prisoner whose number we met on that journey from first box to found card. We now know that all of those prisoners (because their numbers are on exactly the same cyclical path) do reach their card, and reach it in exactly the same number of steps as our first prisoner.

The third point is that after any successful test for a single prisoner (which can also be thought of as the collection of a new cycle-path) we need to do two things: 1. Only consider prisoners whose numbers have never yet turned up on any path seen so far. 2. Exit the test for that shuffle immediately, with an all survive result, if the total count of prisoner numbers seen so far, on all successful tests, already reaches 50.

It goes without saying, of course, that if we find a path longer than 50 (a prisoner doesn't find their card in 50 moves), then we also exit the test for that shuffle immediately, with an all perish result. Hout (talk) 16:36, 7 November 2019 (UTC)

All of this can be simplified: just compute the cycle decomposition of the initial permutation. If any cycle has length >50, bad luck, otherwise they all win. This can be done in O(n) where n is the length of the permutation.
See also this. Eoraptor (talk) 19:47, 7 November 2019 (UTC)

Thanks - good reference. Perhaps one to add to the task description page. Hout (talk) 20:00, 7 November 2019 (UTC)

Simulations need some judgement in how close one follows the actual, vs the need to demonstrate that the simulation is of the actual. --Paddy3118 (talk) 23:32, 7 November 2019 (UTC)

and judgement, of course, is not to be confused with naivety. The former is inevitably absent if the deeper structure of the problem remains obscure. The point of building a model is to help us understand, which often includes uncovering new efficiencies Hout (talk) 02:01, 8 November 2019 (UTC)

@Paddy3118, once you realize that all prisoners in the same cycle necessarily need the same number of attempts, the simulation amounts exactly to looking at the lengths of cycles in the cycle decomposition. There is no point pretending we don't know. And this makes the task much more interesting: I don't care too much about those 100 prisoners, but random permutations can be reused in other contexts. The amazing feat, here, is to have been able to hide cleverly the permutation stuff behind a seemingly impossible puzzle. Eoraptor (talk) 07:32, 8 November 2019 (UTC)