Convincing Myself of a Puzzle's Answer (Random Numbers with the P2)
![Duane Degn](https://forums.parallax.com/uploads/userpics/621/nYR252DBM43HX.jpg)
A recent Veritasium video got me wondering. As the video title suggests, the answer to the puzzle doesn't seem right.
Here's the video:
I stopped the video six minutes in so I could convince myself the puzzle's answer really was correct.
Writing a program to generate random prisoner combinations was fun. I started out with just using ten prisoners and ten boxes until I felt confident I have the sorting logic correct.
Even though I know the success rate should be around 30%, I was still really surprised to see this was correct.
There has got to be better algorithms than the way I did this. My system of filling the boxes with random numbers seems awkward but I felt like it would be cheating to search the internet for a better algorithm.
Here's a section of the output from one run of a hundred sets.
0:sortIndex = 87 0:Debug All Boxes, sortIndex = 87 0:box[0] = 54, 62, 26, 3, 48, 23, 16, 22, 39, 6, 68, 52, 80, 25, 20, 2, 0, 74, 91, 11 0:box[20] = 82, 72, 30, 8, 61, 60, 96, 7, 71, 35, 83, 45, 18, 24, 93, 78, 12, 65, 63, 90 0:box[40] = 41, 79, 85, 81, 21, 9, 51, 92, 64, 57, 50, 73, 17, 40, 15, 98, 10, 47, 37, 70 0:box[60] = 19, 32, 33, 95, 76, 94, 84, 5, 13, 27, 59, 28, 38, 97, 87, 58, 99, 46, 56, 1 0:box[80] = 89, 43, 86, 53, 4, 31, 49, 77, 36, 29, 88, 42, 75, 69, 67, 55, 44, 14, 34, 66 0:End FindLoops(), successes = 100 0:completeSuccessCount = 28. All convicts are freed. Index 88 through 98 were cut. 0:sortIndex = 99 0:Debug All Boxes, sortIndex = 99 0:box[0] = 0, 53, 44, 35, 50, 18, 89, 34, 61, 52, 84, 96, 25, 16, 56, 95, 33, 30, 3, 20 0:box[20] = 91, 85, 67, 82, 65, 8, 6, 24, 71, 55, 31, 70, 36, 43, 38, 72, 73, 83, 17, 7 0:box[40] = 88, 77, 62, 4, 64, 75, 2, 92, 14, 29, 13, 90, 76, 26, 94, 32, 58, 5, 15, 23 0:box[60] = 21, 59, 39, 28, 22, 27, 74, 86, 10, 60, 51, 93, 42, 63, 87, 68, 37, 80, 40, 49 0:box[80] = 19, 46, 78, 98, 45, 1, 81, 99, 57, 66, 11, 97, 47, 54, 79, 12, 9, 69, 41, 48 0:End FindLoops(), successes = 38 0: Only 38 out of 100 convicts tested were successful. All are executed. CON '' 0:Final completeSuccessCount = 28, numberOfSorts = 100 0: End program.
The attached program uses my funky multi port serial object. The object includes a lock so it can be used from multiple cogs. Sorry for not cleaning things up more but I didn't really want to spend much more time on this. I'll be happy to answer any questions about my strange serial object.
You should use Parallax Serial Terminal.exe for the output. I don't think the normal debug window will display the data correctly.
If any of you care to look at my code, I'd be very interested to hear how the algorithms could be improved.
Comments
Hello Duane,
I checked out the video and looked over your code briefly, so did you use an algorithm that I have seen to shuffle a deck of cards contained in an array?
Sorry for not replying sooner. I've been away from the forum for a few months.
I don't know if the algorithm is used to shuffle cards or not. I just used my own algorithm. As I previously mentioned, I didn't want to "cheat" by seeing what others have done to solve this sort of problem. I imagine this sort of algorithm as been independently developed many times. I still think there are likely better ways to "shuffle" numbers. I just wanted to see if I could come up with a solution myself.
Interesting ... Something along these lines might have a real application in project I have.
Attached is some Perl code I wrote that consistently shows about a 33.7% Success rate after 1000 iterations ..
Example Output:
Box contents:
$Box[1]: 25, 95, 90, 30, 43, 53, 69, 13, 86, 48
$Box[11]: 88, 98, 32, 67, 31, 63, 49, 42, 41, 34
$Box[21]: 16, 9, 26, 56, 46, 7, 40, 83, 19, 57
$Box[31]: 20, 54, 52, 10, 70, 92, 99, 8, 24, 36
$Box[41]: 61, 78, 28, 55, 97, 89, 81, 38, 12, 44
$Box[51]: 74, 91, 65, 2, 85, 66, 84, 94, 80, 4
$Box[61]: 14, 5, 45, 77, 11, 76, 6, 87, 64, 50
$Box[71]: 79, 96, 33, 3, 22, 37, 15, 93, 60, 68
$Box[81]: 23, 39, 72, 73, 18, 29, 1, 17, 21, 82
$Box[91]: 71, 100, 58, 62, 27, 75, 59, 35, 47, 51
Loop #1 :25 46 89 21 16 63 45 97 59 80 68 87 ::12
90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 ::37
Loop #2 :95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 ::37
Loop #3 :90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 ::37
Loop #4 :30 57 84 73 33 52 91 71 79 60 ::10
Loop #5 :43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 ::37
Loop #6 :53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 ::37
Loop #7 :69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 ::37
Loop #8 :13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 ::37
Loop #9 :86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 ::37
Loop #10 :48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 ::37
Loop #11 :88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 ::37
Loop #12 :98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 ::37
Loop #13 :32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 ::37
Loop #14 :67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 ::37
Loop #15 :31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 ::37
Loop #16 :63 45 97 59 80 68 87 1 25 46 89 21 ::12
Loop #17 :49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 ::37
Loop #18 :42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 ::37
Loop #19 :41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 ::37
Loop #20 :34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 ::37
Loop #21 :16 63 45 97 59 80 68 87 1 25 46 89 ::12
Loop #22 :9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 ::37
Loop #23 :26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 ::37
Loop #24 :56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 ::37
Loop #25 :46 89 21 16 63 45 97 59 80 68 87 1 ::12
Loop #26 :7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 ::37
Loop #27 :40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 ::37
Loop #28 :83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 ::37
Loop #29 :19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 ::37
Loop #30 :57 84 73 33 52 91 71 79 60 4 ::10
Loop #31 :20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 ::37
Loop #32 :54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 ::37
Loop #33 :52 91 71 79 60 4 30 57 84 73 ::10
Loop #34 :10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 ::37
Loop #35 :70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 ::37
Loop #36 :92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 ::37
Loop #37 :99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 ::37
Loop #38 :8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 ::37
Loop #39 :24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 ::37
Loop #40 :36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 ::37
Loop #41 :61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 ::37
Loop #42 :78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 ::37
Loop #43 :28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 ::37
Loop #44 :55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 ::37
Loop #45 :97 59 80 68 87 1 25 46 89 21 16 63 ::12
Loop #46 :89 21 16 63 45 97 59 80 68 87 1 25 ::12
Loop #47 :81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 ::37
Loop #48 :38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 ::37
Loop #49 :12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 ::37
Loop #50 :44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 ::37
Loop #51 :74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 ::37
Loop #52 :91 71 79 60 4 30 57 84 73 33 ::10
Loop #53 :65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 ::37
Loop #54 :2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 ::37
Loop #55 :85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 ::37
Loop #56 :66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 ::37
Loop #57 :84 73 33 52 91 71 79 60 4 30 ::10
Loop #58 :94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 ::37
Loop #59 :80 68 87 1 25 46 89 21 16 63 45 97 ::12
Loop #60 :4 30 57 84 73 33 52 91 71 79 ::10
Loop #61 :14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 ::37
Loop #62 :5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 ::37
Loop #63 :45 97 59 80 68 87 1 25 46 89 21 16 ::12
Loop #64 :77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 ::37
Loop #65 :11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 ::37
Loop #66 :76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 ::37
Loop #67 :6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 ::37
Loop #68 :87 1 25 46 89 21 16 63 45 97 59 80 ::12
Loop #69 :64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 ::37
Loop #70 :50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 ::37
Loop #71 :79 60 4 30 57 84 73 33 52 91 ::10
Loop #72 :96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 ::37
Loop #73 :33 52 91 71 79 60 4 30 57 84 ::10
Loop #74
Loop #75 :22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 ::37
Loop #76 :37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 ::37
Loop #77 :15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 ::37
Loop #78 :93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 ::37
Loop #79 :60 4 30 57 84 73 33 52 91 71 ::10
Loop #80 :68 87 1 25 46 89 21 16 63 45 97 59 ::12
Loop #81 :23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 ::37
Loop #82 :39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 ::37
Loop #83 :72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 ::37
Loop #84 :73 33 52 91 71 79 60 4 30 57 ::10
Loop #85 :18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 ::37
Loop #86 :29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 ::37
Loop #87 :1 25 46 89 21 16 63 45 97 59 80 68 ::12
Loop #88 :17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 ::37
Loop #89 :21 16 63 45 97 59 80 68 87 1 25 46 ::12
Loop #90 :82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 ::37
Loop #91 :71 79 60 4 30 57 84 73 33 52 ::10
Loop #92 :100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 ::37
Loop #93 :58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 ::37
Loop #94 :62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 ::37
Loop #95 :27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 ::37
Loop #96 :75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 98 35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 ::37
Loop #97 :59 80 68 87 1 25 46 89 21 16 63 45 ::12
Loop #98 :35 70 50 44 55 85 18 42 78 93 58 94 62 5 43 28 83 72 96 75 22 9 86 29 19 41 61 14 67 6 53 65 11 88 17 49 12 ::37
Loop #99 :47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 100 51 74 3 90 82 39 24 56 66 76 37 ::37
Loop #100 :51 74 3 90 82 39 24 56 66 76 37 99 47 81 23 26 7 69 64 77 15 31 20 34 10 48 38 8 13 32 54 2 95 27 40 36 92 ::37
There is another pattern that emerges as well within the "loops" as far as the length of loops on successful box patterns. (See Attached images) The number positions within a loop for the first image are 0 meaning the prisoner opened the box with his/her number in it... followed by 28, 30 , and 33.
Another observation after 1000 attempts (reshuffling of the boxes) ... A successful box shuffle pattern that would allow ALL of the prisoners to be free can be determined if the first 8 prisoners (<--on average 5) were able to close their own loop within 50 attempts.
So you would only need 8 prisoners to go through the "Box Room" to determine the outcome of successive attempts.
**EDIT:
I just ran 10,000 shuffles and the success rate was 34% with Max attempts before fail being 9 (avg. 5) as opposed to 8 prisoners mentioned above
**
I'm not getting the same results.
I ran 1000 shuffles and these are my results.
I'm getting up to 51 attempts before a fail.
I'll try 10,000 shuffles while I'm eating dinner.
I think I'm not understanding something about what you're doing. I don't know if our code logic is different or if my English reading comprehension is lacking. I will likely need to look at this again in the morning with a fresh brain. My brain starts complaining in the evening when I try to use it to think.
Either way, thanks for playing along. It's a lot more fun when someone else is joining the experiment.
I've attached the code I used for 1000 sorts.
That's probably because I am using a Perl script instead of a Propeller 2 script ... I haven't programmed a Propeller in many years now.
Perl reads a lot like C. I have included a 2 page PDF that consists of the entire Perl Program broken down into "easy to read" blocks.
The main block to focus on is the "Shuffle the Deck". It basically selects two random boxes, ensuring that they are indeed different boxes and swaps the contents. It does this 100000 times to effectively shuffle the entire deck.
Other than making the data array "human readable" the other main block to focus on is the "Show the Loops" which simply follows the chain of boxes forming a loop. If the chain gets to 51 the loop terminates. The loop will also terminate if the box contains it's own number. If the loop completes before creating a loop of 51, then the Success variable is incremented and the next "prisoner" starts the loop process.
If at least 9 prisoners have successfully completed their loop, then the odds are very high that the remaining 91 prisoners will be successful (<- assuming they understand how numbers work <smirk> )
The interesting patterns I saw were that the loops "snapped" to a few specific lengths within a "successful box set" and their relationship allowed them to overlap other loops, but a smaller loop could not be embedded within a larger loop.