Hi
On 28 August 2010 02:25, neveu <[email protected]> wrote:
> I implemented the "Flavius Josephus" algorithm from Programming Praxis
> in Clojure using loop/recur. My first version looked like this:
>
> (defn rotate-left
> ([ln n m]
> (take n (drop (dec m) (cycle ln))))
> ([ln m] (rotate-left ln (count ln) m)))
>
> (defn josephus3 [N M] ;; execute every mth soldier
> (loop [soldiers (range N)
> m M
> deceased '()]
> (let [n (count soldiers)]
> (cond
> (zero? n) deceased
> true (let [r (rotate-left soldiers n m)
> dead (cons (first r) deceased)
> survivors (rest r)]
> (recur survivors m dead))))))
>
> This works fine, but I don't really need to count the soldiers every
> pass, it always decreases by 1. So I wrote this version in which n is
> one of the loop parameters:
>
> (defn josephus4 [N M] ;; execute every mth soldier
> (loop [soldiers (range N)
> n N
> m M
> deceased '()]
> (cond
> (zero? n) deceased
> true (let [r (rotate-left soldiers n m)
> dead (cons (first r) deceased)
> survivors (rest r)]
> (recur survivors (dec n) m dead)))))
>
> Both work for small N (e.g. 41) but the second one fails for large
> (41000) N with a stack overflow.
> What am I missing here?
It seems to be the lazyness of rotate-left that causes it. Not sure
why it doesn't affect josephus3, but breaks josephus4, though.
I tried starting java with a 60k thread stack size to make it easier
to see the problem:
java -Xss60k ...
Then this fails with an n as low as 100:
(defn josephus5 [N M] ;; execute every mth soldier
(loop [soldiers (range N)
n N
m M
deceased []]
(cond
(zero? n) deceased
:else (let [r (rotate-left soldiers n m)
dead (conj deceased (first r))
survivors (rest r)]
(recur survivors (dec n) m dead)))))
but this works (obviously with the wrong results):
(defn josephus6 [N M] ;; execute every mth soldier
(loop [soldiers (range N)
n N
m M
deceased []]
(cond
(zero? n) deceased
:else (let [r soldiers
dead (conj deceased (first r))
survivors (rest r)]
(recur survivors (dec n) m dead)))))
I then changed rotate-left and updated josephus as follows:
(defn rotate-left2
([ln n m]
(doall (take n (drop (dec m) (cycle ln)))))
([ln m] (rotate-left ln (count ln) m)))
(defn josephus7 [N M] ;; execute every mth soldier
(loop [soldiers (range N)
n N
m M
deceased []]
(cond
(zero? n) deceased
:else (let [r (rotate-left2 soldiers n m)
dead (conj deceased (first r))
survivors (rest r)]
(recur survivors (dec n) m dead)))))
and that seems to work.
--
Michael Wood <[email protected]>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
