

The Problem

 100 prisoners are individually numbered 1 to 100
 A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
 Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
 Prisoners start outside the room
 They can decide some strategy before any enter the room.
 Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
 A prisoner can open no more than 50 drawers.
 A prisoner tries to find his own number.
 A prisoner finding his own number is then held apart from the others.
 If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand. 


The task

 Simulate several thousand instances of the game where the prisoners randomly open drawers
 Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
 First opening the drawer whose outside number is his prisoner number.
 If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).


Show and compare the computed probabilities of success for the two strategies, here, on this page.




References

 The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
 wp:100 prisoners problem
 100 Prisoners Escape Puzzle DataGenetics.
 Random permutation statistics#One hundred prisoners on Wikipedia.


(ns clojure-sandbox.prisoners)
 
(defn random-drawers []
  "Returns a list of shuffled numbers"
  (-> 100
      range
      shuffle))
 
(defn search-50-random-drawers [prisoner-number drawers]
  "Select 50 random drawers and return true if the prisoner's number was found"
  (->> drawers
      shuffle ;; Put drawer contents in random order
      (take 50) ;; Select first 50, equivalent to selecting 50 random drawers
      (filter (fn [x] (= x prisoner-number))) ;; Filter to include only those that match prisoner number
      count
      (= 1))) ;; Returns true if the number of matching numbers is 1
 
(defn search-50-optimal-drawers [prisoner-number drawers]
  "Open 50 drawers according to the agreed strategy, returning true if prisoner's number was found"
  (loop [next-drawer prisoner-number ;; The drawer index to start on is the prisoner's number
         drawers-opened 0] ;; To keep track of how many have been opened as 50 is the maximum
    (if (= drawers-opened 50)
      false ;; If 50 drawers have been opened, the prisoner's number has not been found
      (let [result (nth drawers next-drawer)] ;; Open the drawer given by next number
        (if (= result prisoner-number) ;; If prisoner number has been found
          true ;; No need to keep opening drawers - return true
          (recur result (inc drawers-opened))))))) ;; Restart the loop using the resulting number as the drawer number
 
(defn try-luck [drawers drawer-searching-function]
  "Returns 1 if all prisoners find their number otherwise 0"
  (loop [prisoners (range 100)] ;; Start with 100 prisoners
    (if (empty? prisoners) ;; If they've all gone and found their number
      1 ;; Return true- they'll all live
      (let [res (-> prisoners
                    first
                    (drawer-searching-function drawers))] ;; Otherwise, have the first prisoner open drawers according to the specified method
        (if (false? res) ;; If this prisoner didn't find their number
          0 ;; no prisoners will be freed so we can return false and stop
          (recur (rest prisoners))))))) ;; Otherwise they've found the number, so we remove them from the queue and repeat with the others
 
(defn simulate-100-prisoners []
  "Simulates all prisoners searching the same drawers by both strategies, returns map showing whether each was successful"
  (let [drawers (random-drawers)] ;; Create 100 drawers with randomly ordered prisoner numbers
    {:random (try-luck drawers search-50-random-drawers) ;; True if all prisoners found their number using random strategy
     :optimal (try-luck drawers search-50-optimal-drawers)})) ;; True if all prisoners found their number using optimal strategy
 
(defn simulate-n-runs [n]
  "Simulate n runs of the 100 prisoner problem and returns a success count for each search method"
  (loop [random-successes 0
         optimal-successes 0
         run-count 0]
    (if (= n run-count) ;; If we've done the loop n times
      {:random-successes random-successes ;; return results
       :optimal-successes optimal-successes
       :run-count run-count}
      (let [next-result (simulate-100-prisoners)] ;; Otherwise, run for another batch of prisoners
        (recur (+ random-successes (:random next-result)) ;; Add result of run to the total successs count
               (+ optimal-successes (:optimal next-result))
               (inc run-count)))))) ;; increment run count and run again
 
(defn -main [& args]
  "For 5000 runs, print out the success frequency for both search methods"
  (let [{:keys [random-successes optimal-successes run-count]} (simulate-n-runs 5000)]
    (println (str "Probability of survival with random search: " (float (/ random-successes run-count))))
    (println (str "Probability of survival with ordered search: " (float (/ optimal-successes run-count))))))