gistfile1.clj

(ns pfad.ch1)
(set! *warn-on-reflection* true)

;; Compute the smallest natural number not in a given finite set of X
;; natural numbers.


;; Array based solution

;; minfree = search . checklist

;; search :: Array Int Bool -> Int
;; search = length . takeWhile id . elems

;; checklist :: [Int] -> Array Int Bool
;; checklist xs = accumArray (V) False (0,n)
;;                (zip (filter (<= n) xs) (repeat True))
;;                where n = length xs

(def l [8 23 9 0 12 11 1 10 13 7 41 4 14 21 5 17 3 19 2 6])

(defn checklist [xs]
  (let [n (count xs)
        true-map (zipmap
                  (filter #(<= % n) xs)
                  (repeat true))]
    (for [i (range n)]
      (get true-map i false))))

(defn search [bools]
  (count (take-while identity bools)))

(defn min-free [xs]
  (-> xs checklist search))

;; Divide and conquer

(defn part-by [f? xs]
  [(filter f? xs)
   (filter (comp not f?) xs)])

(defn min-from [a n xs]
  (let [b (+ a 1 (int (/ n 2)))
        [us vs] (part-by #(< % b) xs)
        m (int (count us))]
    (cond
     (= (int 0) n) a
     (= m (- b a)) (recur b (- n m) vs)
     :otherwise    (recur a m us))))

(defn min-free-dc [xs]
  (min-from 0 (count xs) xs))

(defn rand-list [n]
  (let [remove-list [(rand-int n)]]
    (remove #(some #{%} remove-list)
            (range 0 (inc n)))))