Probabilistic brute force

main.clj

;; If I want to guess an N-bit number and I can guess each bit with
;; P% accuracy, how many guesses will I have to make before I guess
;; correctly? This program answers such questions.
;;
;; Example usage: lein run 6/10 512 # 6/10 probability for each of 512 bits.

(ns prob-brute-force.core)

(defn choose
  [a b]
  (let [n (apply *' (range a (- a b) -1))
        d (apply *' (range 1 (inc b)))]
    (/ n d)))

(defn brute-force-count
  "Compute how many things you'd have to try to get it right with a certain
  probability threshold."
  [threshold p size]
  (loop [i 0 c 0 tp 0]
    (let [badProbs (apply *' (repeat i (- 1 p)))
          goodProbs (apply *' (repeat (- size i) p))
          prob (*' badProbs goodProbs)
          maxNum (choose size i)
          maxTotalProb (+ tp (* maxNum prob))
          neededNum (/ (- threshold tp) prob)]
      (if (<= neededNum maxNum)
          (let [ans (bigint (+ c neededNum))]
            (if (> (+ c neededNum) ans) (inc ans) ans))
          (recur (inc i) (+ c maxNum) maxTotalProb)))))

(defn print-threshold-stats
  [ratio size threshold]
  (let [res (brute-force-count threshold ratio size)]
    (println "For threshold" threshold "need" res "tries")
    (println "That is a" (count (str res)) "digit number")))

(defn -main
  [ratioArg bitCountStr]
  (let [parts (clojure.string/split ratioArg #"/")
        n (read-string (first parts))
        d (read-string (last parts))
        size (read-string bitCountStr)
        p (/ n d)]
    (dorun (map (partial print-threshold-stats p size) [1/2 1/4 1/10]))))