4
\$\begingroup\$

I have a piece of Clojure code that reverses a string recursively. It is working but too slow (because I got the problem from Codewars and I cannot validate it before it timeouts).

The algorithm is :

  • take a string ex. "abc" and reverse it (r "abc") -> "cba"
  • take the first position and reverse from there "c" + (r "ba") -> "cab"
  • take the second position and reverse from there "ca" + (r "b") -> "cab" and so on..

First iteration :

(defn reverse-fun [s]
  (loop [r s p 0]
    (if (= p (count s))
      r
      (let [[b e] (split-at p r)
            e     (reverse e)]
        (recur (apply str (concat b e)) (inc p))))))

However it was too slow. I pass about 31 tests with this one before the timeout. Here is the fastest I have for now :

(defn reverse-fun [s]
  (apply str (loop [r (vec s) p 0]
               (if (= p (count r))
                 r
                 (let [b (subvec r 0 p)
                       e (rseq (subvec r p (count r)))]
                   (recur (into [] (concat b e)) (inc p)))))))

This code passes about 72 tests before there is a timeout. How can I make this code faster ?

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ – Phrancis Mar 19 '16 at 16:21
2
\$\begingroup\$

The intermediate reversals seem like a bit of a trick question and are not really necessary to solve this problem. They are a complicated way to describe reordering a sequence indexed
0 ... n by taking items n, 0, n-1, 1, n-2, 2 ...
alternating from which end you take each time.

If you abandon the idea of creating the intermediate strings described it becomes more about how to select the right character from the input string for each position :

(ns reversefun.core)

(defn reverse-fun [s]
  (->> (interleave (reverse s) s)
       (take (count s))
       (apply str)))
\$\endgroup\$
  • \$\begingroup\$ Got it, thanks :) You could replace join by apply str. Otherwise it could be written : (defn reverse-fun [s] (->> (interleave (reverse s) s) (take (count s)) (apply str))). Would you like me to edit your answer with that ? \$\endgroup\$ – nha Mar 20 '16 at 12:22
  • 1
    \$\begingroup\$ Yeah, that is basically the alternate I was talking around so go for it. \$\endgroup\$ – Magos Mar 20 '16 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.