Skip to content

Instantly share code, notes, and snippets.

Last active March 18, 2019 11:26
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ericnormand/a17f3a0cfed0d978c5525e8277f751d4 to your computer and use it in GitHub Desktop.

Run-length encode a sequence

Run-length encoding is a way to represent a sequence in a more compact form. Instead of saying :p :p :p, you say “3 :ps”. Write a function that takes a sequence and returns that sequence with run-length encoding.

For example:

(rle [:a :a :a :b :c :d :d :d :d])
;=> ([3 :a] [1 :b] [1 :c] [4 :d])

Then, write a function to decode the run-length representation.

(rld '([3 :a] [1 :b] [1 :c] [4 :d]))
;=> (:a :a :a :b :c :d :d :d :d)

That’s two functions: one to encode, and one to decode. Bonus points for laziness, concision, and efficiency.

Note: These solutions are untested. Testing them is left as an exercise for you.

(defn rle [v]
(->> v
(partition-by identity)
(map #(vector (count %) (first %)))))
(defn rld [l]
(mapcat #(repeat (first %) (second %)) l))
(defn rle [values]
(map #(vector (count %) (first %)) (partition-by identity values)))
(defn rld [values]
(flatten (map #(repeat (first %) (second %)) values)))
(defn rle
(if (= uncompressed [])
(loop [items uncompressed
curcount {(first items) 0}
retseq ()]
(let [item (first items)]
(if (nil? item)
(->> (conj retseq curcount) (mapcat vec) (map reverse) (map vec) reverse) ;; there has to be a better way
(if (nil? (get curcount item))
(recur (rest items) {item 1} (conj retseq curcount))
(recur (rest items) (update curcount item inc) retseq)))))))
(defn rld
(mapcat (fn [[count thing]] (repeat count thing)) compressed))
(defn rle
(if (empty? seq) '() (rle (rest seq) [1 (first seq)])))
([seq [quantity value]]
(if (= value (first seq))
(rle (rest seq) [(inc quantity) value])
(lazy-cat (list [quantity value]) (rle seq))
(defn rld
[[[quantity value] & rest]]
(if (= quantity 0)
(if (= rest nil) [] (rld rest))
(lazy-seq (cons value (rld (cons [(dec quantity) value] rest))))
(defn encode [xs]
(->> xs
(partition-by identity)
(map (juxt count first))))
(defn decode [xs]
(->> xs
(mapcat (fn [[n x]] (repeat n x)))))
(defn rle [s] (map (juxt count first) (partition-by identity s)))
(defn rld [s] (mapcat (fn [[ct k]] (repeat ct k)) s))
(let [s [:a :a :a :b :c :d :d :d :d]] (= s (rld (rle s)))) ;==> true
(defn rle
(loop [coll (reverse coll)
result ()]
(if (empty? coll)
(let [item (first coll)
[head tail] (split-with (partial = item) coll)
chunk [(count head) item]]
(recur tail (cons chunk result))))))
(defn rld
(->> (reverse coll)
(reduce (fn [acc [times key]]
(into acc (repeat times key)))
(defn rle-encode [coll]
(let [to-rle (fn [coll] [(count coll) (first coll)])]
(map to-rle
(partition-by identity coll))))
(defn rle-decode [rle-seq]
(mapcat (fn [[n x]] (repeat n x))
(defn rle
((fn encode [e c]
(if (empty? c)
(let [p (first c)
l (or (first (keep-indexed #(when (not= %2 p) %1) c)) (count c))]
(lazy-cat e [[l p]])
(drop l c)))))
(lazy-seq) c))
(defn rld [e]
(mapcat #(repeat (first %) (second %)) e))
(defn rle
(rle [] coll))
([result coll]
(if (empty? coll)
(let [current (first coll)
n (count (take-while #(= % current) coll))]
(cons [n current] (rle result (drop n coll))))))))
(defn rld
([coll] (rld [] coll))
([result coll]
(if (empty? coll)
(let [[n x] (first coll)
remainder (if (= 1 n)
(rest coll)
(cons [(dec n) x] (rest coll)))]
(cons x (rld result remainder)))))))
(defn rle [s]
#(vector (count %) (first %))
(partition-by identity s)))
(defn rld [l]
#(repeat (first %) (second %))
(defn run-len-encode
(->> seq
(partition-by identity)
(map #(vector (count %) (first %)))))
(defn run-len-decode
(mapcat (fn [[n k]] (repeat n k)) enc))
(defn rle
([] (comp (partition-by identity) (map (juxt count peek))))
([coll] (sequence (rle) coll)))
(defn rld
([] (mapcat #(apply repeat %)))
([runs] (sequence (rld) runs)))
(defn rle [xs]
(for [part (partition-by identity xs)]
[(count part) (first part)]))
(defn rld [pairs]
(mapcat (fn [[n v]] (repeat n v)) pairs))
(defn rle [coll]
(when-let [s (seq coll)]
(let [sym (first s)
same-symbol-run (take-while #(= % sym) s)]
(cons [(count same-symbol-run) sym] (rld-lazy (drop (count same-symbol-run) s)))))))
(defn rld [runs]
(when-let [s (seq runs)]
(let [[run-length run-symbol] (first runs)
run-done? (= 0 (dec run-length))]
(cons run-symbol
(rld (if run-done?
(rest runs)
(cons [(dec run-length) run-symbol] (rest runs)))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment