453 PurelyFunctional.tv Newlsetter

00 Backspace jam.md

Backspace jam

Let's say we have users typing keys on the keyboard. We capture the characters they represent in strings. However, sometimes the user hits the backspace key, which removes the previous character. We will represent a backspace key press with a # character. Write a function that applies the behavior of backspace to the string.

Examples

(apply-bs "abc#") ;=> "ab"
(apply-bs "abc###") ;=> ""
(apply-bs "###abc") ;=> "abc"
(apply-bs "there###eir") ;=> "their"

Thanks to this site for the problem idea, where it is rated Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn- conj-ch [chars ch]
  (if (= \# ch)
    (if (seq chars)
      (pop chars)
      chars)
    (conj chars ch)))

(defn apply-bs [s]
  (apply str (reduce conj-ch [] s)))

(defn apply-bs [s]
  (letfn [(pop' [stk] (if (empty? stk) stk (pop stk)))
          (rf [s c] (if (= \# c) (pop' s) (conj s c)))]
    (apply str (reduce rf [] s))))

(defn apply-bs [input]
  (loop [input (second (re-matches #"#*(.*)" input))
         result []]
    (if (empty? input)
      (apply str result)
      (let [[_ characters hashes remainder] (re-matches #"([^#]+)(#*)(.*)" input)]
        (recur remainder
               (drop-last (count hashes)
                          (concat result characters)))))))

(defn apply-bs [s]
  (reduce (fn [acc char]
           (if (= char "#")
            (subs acc 0 (dec (count acc)))
            (str acc char))) 
          "" s))

I always struggle with using seq in order to prevent an exception, as it can clutter a really short function.

Here is another version borrowing from fnil:

(defn fpred [f pred x]
  (fn [a & args]
    (apply f (if (pred a) x a) args)))

(def pop-always (fpred pop empty? [\#]))

(defn backspace [cs c] (when (#{\#} c) 
                         (pop-always cs)))

(defn apply-bs [typos]
  (->> typos (reduce (fn [tape c]
                       (or (backspace tape c)
                           (conj tape c)))
                     [])
       (apply str)))

(defn apply-bs [s] 
  (let [ s-fix (clojure.string/replace s #"^#+" "") ]   ; remove backspaces at the start
     (loop [curr-s s-fix] 
        (if (.contains curr-s "#")    ; if there are still backspaces left,
           (recur (clojure.string/replace curr-s #"\w#" ""))    ; remove a character next to a backspace
           curr-s)))) ; else, return the result

(defn apply-bs [input]
  (str (let [b (StringBuilder.)]
         (doseq [c input]
           (if (= c \#)
             (when-not (empty? b) (.deleteCharAt b (dec (.length b))))
             (.append b c))) b)))

(defn reducer [acc c]
  (if (= c \#) (into [] (drop-last acc)) (conj acc c)))

(defn apply-bs [s]
  (->> s
       (into [])
       (reduce reducer [])
       (apply str)))

Not pretty, but fast:

(defn apply-bs [^String s]
  (loop [sb (StringBuilder. s) octo (.indexOf s "#")]
    (cond (pos? octo) (let [sb (.delete sb (dec octo) (inc octo))]
                        (recur sb (.indexOf sb "#" (dec octo))))
          (neg? octo) (.toString sb)
          :else  (let [sb (.deleteCharAt sb 0)]
                   (recur sb (.indexOf sb "#"))))))