Classic "100 doors" simulation in Clojure

Question

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"
=> (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)]

    (->> toggled
         (map vector (oneth-range))
         (filter second)
         (map first))))

(ns irrelevant.hundred-doors-set)

(defrecord Doors [open n-doors])

(defn- new-doors [n-doors]
  (->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)]

    (-> toggled
        (:open)
        (sort))))

Alan Thompson · Accepted Answer · 2018-09-05 17:36:15Z

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) => [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"

I try to avoid mutation except where it's necessary or would be too difficult to do otherwise, but this would have been a good opportunity to practice using arrays. Thanks. — Carcigenicate
– Carcigenicate, Commented Sep 5, 2018 at 17:46
Re the "math method", notice that all of the open doors are perfect squares......! — Alan Thompson
– Alan Thompson, Commented Sep 5, 2018 at 18:03
Ya. That's too easy though. And it changes if the bound and N differ. — Carcigenicate
– Carcigenicate, Commented Sep 5, 2018 at 20:09

Thumbnail · Accepted Answer · 2018-09-23 21:34:14Z

Your implementations

Your toggle-doors functions are slower than they need be. Let's look at the first one:

(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))

This knocks on every one of the doors, flipping its state only if its number divides by every-n. So the toggle-doors-for function does max-n * max-n door knocks in all.

A better way to toggle-doors is to knock only on the doors that need toggling:

(defn toggle-doors [doors every-n]
  (reduce (fn [ds i] (assoc ds i (not (ds i))))
          doors
          (range (dec every-n) (count doors) every-n)))

(I've changed defn- to defn to be able to exercise the function from the REPL.)

This knocks on about 1 / every-n of the doors. So the number or knocks in toggle-doors-for is now roughly

max-n * (1 / 1 + 1 / 2 + ... 1 / max-n)

... which, according to this, is about

max-n * ln (max-n)

This is like the improvement from bubble-sort to quick-sort. On this basis, for a max-n of 100,

your version does 10,000 knocks;
mine does about 460 (482, in fact).

So mine is roughly 20 times as fast as yours.

My preferred approach

We are looking for the doors that are hit an odd number of times by an open/close event. We can find these as follows:

(defn hundred-doors []
  (let [steps (range 1 101)
        hits (fn [step] (range step 101 step))
        changes (mapcat hits steps)
        change-counts (frequencies changes)
        opens (filter (comp odd? val) change-counts)]
        (sort (map key opens))))

   (hundred-doors)       
=> (1 4 9 16 25 36 49 64 81 100)

Taking each line in turn ...

steps is the range of intervals for the passes through the doors;
hits returns the sequence of doors hit by the pass with the given step;
changes is the whole sequence of door hits;
change-counts maps each door to the number of hits it gets;
opens filters the map entries for oddness of number of hits.

The answer is the keys of the opens entries, sorted for display.

You can abbreviate this cascade of computations using the ->> threading macro:

(defn hundred-doors []
  (->> (range 1 101)
        (mapcat (fn [step] (range step 101 step)))
        (frequencies)
        (filter (comp odd? val))
        (map key)
        (sort)))

Despite appearances, this is not so different from your solution.

It turns the sequence of door hits into an explicit data structure.
A hit, instead of flipping the state of a door, increments its hit-count.

Stack Exchange Network

Classic "100 doors" simulation in Clojure

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Classic "100 doors" simulation in Clojure

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions