Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
453 Newlsetter

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.


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

Copy link

KingCode commented Dec 12, 2021

(defn apply-bs [typos]
  (->> typos (reduce (fn [tape c]
                       (if (#{\#} c)
                         ((comp pop #(if (seq %) % [\#])) tape)
                         (conj tape c)))
       (apply str)))

Copy link

led commented Dec 13, 2021

(defn apply-bs [ss]
  (reduce str
            (fn [a s]
              (if (= s "#")
                (if (seq a) (pop a) a)
                (conj a s)))
            [] ss)))

Copy link

steffan-westcott commented Dec 13, 2021

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

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

Copy link

mchampine commented Dec 13, 2021

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

Copy link

adamdavislee commented Dec 13, 2021

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

Copy link

ndonolli commented Dec 13, 2021

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

Copy link

KingCode commented Dec 14, 2021

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

Copy link

kvn-prhn commented Dec 14, 2021

(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

Copy link

jonasseglare commented Dec 14, 2021

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

Copy link

ZaymonFC commented Dec 15, 2021

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

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

Copy link

miner commented Dec 16, 2021

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 "#"))))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment