cancel
Showing results for
Did you mean:

## One hundred prisoners  Valued Contributor

The One Hundred Prisoners problem has a famously counter-intuitive solution, nicely explained on YouTube:

Exploring it in q is illuminating!

George Berkeley kicked this off in the Vector Dōjō :

A problem I found interesting, and maybe you will too...You can view a vector `v = (1 0 2 3 5 6 4)` as a permutation, i.e. given an index `i`, the permutation sends `i` to `v[i]`. If we apply the permutation multiple times, then eventually we end up where we started. In fact, if we look at `v`, we can see it breaks down into the following cycles:
```0 -> 1 -> 0
2 -> 2
3 -> 3
4 -> 5 -> 6 -> 4```
Given a permutation, return the number of cycles! (so 4 for the given `v`)
``````q)v:1 0 2 3 5 6 4
q)v scan 0
0 1
q)(v scan)each 0 2 3 4
0 1
,2
,3
4 5 6``````
Each item belongs to one and only one cycle. Above, we see all the items, so we see there are only four cycles. A more brute-force approach:
``````q)(v scan)each v
1 0
0 1
,2
,3
5 6 4
6 4 5
4 5 6``````
`0 1` and `1 0` are the same cycle. Sorting each cycle lets us remove duplicates and count.
``````q)distinct(asc v scan)each v
`s#0 1
`s#,2
`s#,3
`s#4 5 6

q)count distinct(asc v scan)each v
4``````
Rian Ó Cuinnegáin linked the problem to the One Hundred Prisoners problem. The key to the problem (spoiler) is that in 100-item permutations, there is about a one-in-three chance that the maximum cycle length is no more than 50. (Above, it is 3.)
``````q)max(count v scan)each v
3
q)max{(count x scan)each x} -100?100
44
q)max{(count x scan)each x} -100?100
55
q)max{(count x scan)each x} -100?100
90``````
This could be smarter. Consider the last case. The longest cycle has 90 items. Once it is found, we have the cycle length for all 90 of its items. We no longer need to evaluate the other 89.
Let’s work on a state with three items: the cycle length for each index, the permutation itself, and the untested indices.
``````q)show q:-10?10 / test
5 0 1 9 2 6 8 4 7 3
q)is:(#[;0]count@;::;til count@)@\: / initial state
q)is q
0 0 0 0 0 0 0 0 0 0
5 0 1 9 2 6 8 4 7 3
0 1 2 3 4 5 6 7 8 9``````
Now a step function that updates the state by evaluating the next index.
``````q)step:{[c;p;i] if[count i;c[r]:count r:p scan i 0];(c;p;where not c)} .

q)step is q
8 8 8 0 8 8 8 8 8 0
5 0 1 9 2 6 8 4 7 3
3 9``````
Above, the cycle of which 0 is a member has length 8. After the first step, only two indices remain to evaluate.
So much less work to do:
``````q)p:-100?100

q)\t:1000 max(count p scan)each p
134
q)\t:1000 max first step over is p
13``````
This approach also quickly gives us the answer to the question George first posed: how many cycles are in the permutation? The first item of a scan result is of course the initial state; we count the rest.
``````q)-1+ count step scan is v
4
q)-1+ count step scan is p
6``````
My thanks to Vector Dōjō tutors Rian Ó Cuinnegáin and Cillian Murphy for their work on this.
The Vector Dōjō will meet again online soon. In the meantime, members fool around with problems like these in the Iverson College workspace on Slack. (DM me at sjt@5jt.com for an invitation.)
The 100 Prisoners Riddle feels completely impossible even once you know the answer. This video is sponsored by Brilliant. The first 200 people to sign up via https://brilliant.org/veritasium get 20% off a yearly subscription. Special thanks to Destin of Smarter Every Day (https://ve42.co/SED) ...    