Clojure experiment on https://en.wikipedia.org/wiki/100_prisoners_problem

prisoners-100.clj

(ns prisoners.core)

;;
;; Clojure experiment on 100 prisoners problem.
;;
;; See https://en.wikipedia.org/wiki/100_prisoners_problem
;;

(defn best-tries
  "Returns the infinite sequence of drawers contents a prisoner will get.
  This is the best strategy as explained in wikipedia page"
  [prisoner drawers]
  (lazy-seq
    (cons (nth drawers prisoner) (best-tries (nth drawers prisoner) drawers))))

(defn naive-tries
  "Strategy where each prisoner takes his number and the following numbers
  (rolling at beginning when end reached)"
  [prisoner drawers]
  (->> drawers
       repeat
       flatten
       (drop prisoner)))

(defn succeeds?
  "True if a prisoner applying fn-tries finds his number
  within half the number of drawers attempts"
  [prisoner drawers fn-tries]
  (->> (fn-tries prisoner drawers)
       (take (/ (count drawers) 2))
       (some #{prisoner})))

(defn saved?
  "True if all prisoners succeed"
  [prisoners drawers fn-tries]
  (every? #(succeeds? % drawers fn-tries) prisoners))

(defn nb-saved
  [fn-tries nb-attempts nb-prisoners]
  (let [prisoners (range nb-prisoners)]
    (->> (repeatedly #(saved? prisoners (shuffle prisoners) fn-tries))
         (take nb-attempts)
         (filter true?)
         count)))

(defn success-rate
  "Computes the success rates for some attempts of a strategy
  for a given number of prisoners"
  [fn-tries nb-attempts nb-prisoners]
  (-> (nb-saved fn-tries nb-attempts nb-prisoners)
      (/ nb-attempts)
      double))

(comment
  (success-rate best-tries 10000 100)
  (success-rate naive-tries 10000 10))