Classic "100 doors" simulation in Clojure I read this question about the "100 Doors" puzzle, and thought that it would make for a good quick exercise.

I ended up with two implementations. The first is more straightforward and uses a vector to store the boolean state of each door.

This is quite slow though, and having a vector of true and falses seems off, so I decided to instead try making it use a set of open doors, and just toggle membership of the set. This is much faster, although the logic is a bit more complex.

I'd like just general feedback on anything that's here. The need for oneth-range is unfortunate (as is its name), and any suggestions to avoid its use would be nice. I know this can probably be solved entirely using simple math, but I'd like suggestions on the "manual" algorithm.

; Example of set-version usage and time
(let [n 5000]
  (time
    (find-open-doors-for n n)))
"Elapsed time: 939.315276 msecs"
=&gt; (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900)




(ns irrelevant.hundred-doors-vec)

(defn- new-doors [n-doors]
  (vec (repeat n-doors false)))

(defn- multiple-of? [n mutliple]
  (zero? (rem n mutliple)))

(defn- oneth-range
  "Returns a range without 0. Max is inclusive."
  ([] (rest (range)))
  ([max] (rest (range (inc max)))))

(defn- toggle-doors
  "Toggles the state of every nth door."
  [doors every-n]
  (mapv #(if (multiple-of? % every-n)
           (not %2)
           %2)
        (oneth-range), doors))

(defn- toggle-doors-for [doors max-n]
  (reduce toggle-doors doors (oneth-range max-n)))

(defn find-open-doors-for
  "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."
  [n-doors n]
  (let [doors (new-doors n-doors)
        toggled (toggle-doors-for doors n)]

    (-&gt;&gt; toggled
         (map vector (oneth-range))
         (filter second)
         (map first))))




(ns irrelevant.hundred-doors-set)

(defrecord Doors [open n-doors])

(defn- new-doors [n-doors]
  (-&gt;Doors #{} n-doors))

(defn- multiple-of? [n multiple]
  (zero? (rem n multiple)))

(defn- oneth-range
  "Returns a range without 0. Max is inclusive."
  ([] (rest (range)))
  ([max] (rest (range (inc max)))))

(defn- toggle-doors
  "Toggles the state of every nth door."
  [doors every-n]
  (update doors :open
    (fn [open]
      (reduce (fn [acc-set n]
                (cond
                  (not (multiple-of? n every-n)) acc-set
                  (open n) (disj acc-set n)
                  :else (conj acc-set n)))
              open
              (oneth-range (:n-doors doors))))))

(defn- toggle-doors-for [doors max-n]
  (reduce toggle-doors doors (oneth-range max-n)))

(defn find-open-doors-for
  "Simulates the opening and closing of n-doors many doors, up to a maximum skip distance of n."
  [n-doors n]
  (let [doors (new-doors n-doors)
        toggled (toggle-doors-for doors n)]

    (-&gt; toggled
        (:open)
        (sort))))
My philosophy is "A fundamentally mutable problem requires a fundamentally mutable solution":

(def N 100)
(def bound (inc N))

(defn calc-doors []
  (verify (pos? N))
  (let [bound (inc N)
        doors (long-array bound 0) ]
    (doseq [step (range 1 bound)
            idx (range 0 bound step)]
      (aset-long doors idx
        (inc (aget doors idx))) )
     (vec doors)))

(dotest
  (let [doors (time (calc-doors))]
    (dotimes [i bound]
      (println (format "%5d %5d" i (nth doors i))))))


with result:

----------------------------------
   Clojure 1.9.0    Java 10.0.1
----------------------------------

Testing tst.demo.core
"Elapsed time: 0.498 msecs"

    0   100
    1     1
    2     2
    3     2
    4     3
    5     2
    6     4
    7     2
    8     4
    9     3
   10     4
   11     2
   12     6
   13     2
   14     4
   15     4
   16     5
   17     2
   18     6
   19     2
   20     6
   21     4
   22     4
   23     2
   24     8
   25     3
   26     4
   27     4
   28     6
   29     2
   30     8


Just noticed that you want the first N open doors:

(defn door-open?
  "Returns true if `door-idx` is open"
  [door-idx]
  (assert (pos? door-idx))
  (let [hits (atom 0)]
    (doseq [step (range 1 (inc door-idx))]
      (when (zero? (rem door-idx step))
        (swap! hits inc)))
    (odd? @hits)))

(defn first-n-open-doors
  "Return a vector of the first N open doors"
  [doors-wanted]
  (assert (pos? doors-wanted))
  (loop [idx       1
         open-idxs []]
    (let [next-idx       (inc idx)
          next-open-idxs (if (door-open? idx)
                           (conj open-idxs idx)
                           open-idxs)]
      (if (= doors-wanted (count next-open-idxs))
        next-open-idxs
        (recur next-idx next-open-idxs)))))


with result:

(first-n-open-doors 100) =&gt; [1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604 9801 10000]
"Elapsed time: 1279.926319 msecs"