Skip to content

Instantly share code, notes, and snippets.

Created December 6, 2021 15:44
Show Gist options
  • Save ericnormand/576b85aadf1d003c09919841ce6cb2fd to your computer and use it in GitHub Desktop.
Save ericnormand/576b85aadf1d003c09919841ce6cb2fd to your computer and use it in GitHub Desktop.
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

(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

(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

(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

(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

(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

(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

(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