Reading · Coding and administration articles by ttsiodras

(July 2010)

Unbelievable puzzle... Look at the code below, or better yet, download and run it...

import itertools
def CheckSolution(prisoners, perm):
    for i in xrange(prisoners):
        attempt = 0
        idx = i
        found = False
        while attempt < prisoners/2:  
            if perm[idx] == i:  
                found = True    
                break
            else:
                idx = perm[idx]  
            attempt += 1
        if not found:
            return False  
    return True  
def main():
    for prisoners in xrange(4, 12, 2):  
        total = 0
        success = 0
        for perm in itertools.permutations(xrange(prisoners)):
            total += 1
            if CheckSolution(prisoners, perm):
                success += 1
        print "When", prisoners, "prisoners,",
        print "Saved:", success, "/", total,
        print "(%5.2f)" % (100.0*success/total)
if __name__ == "__main__":
    main()

You'll get this:

bash$ python ./100prisoners.py
When 4 prisoners, Saved: 10 / 24 (41.67)
When 6 prisoners, Saved: 276 / 720 (38.33)
When 8 prisoners, Saved: 14736 / 40320 (36.55)
When 10 prisoners, Saved: 1285920 / 3628800 (35.44)

Index

Updated: Fri Aug 9 22:48:30 2013

100 prisoners - I want to break free

Comments