Skip to content

Instantly share code, notes, and snippets.

# ericnormand/00 Run-length encoding description.md Last active Mar 18, 2019

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.

https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-317-when-you-see-a-job-apply/

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 [uncompressed] (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 [compressed] (mapcat (fn [[count thing]] (repeat count thing)) compressed))
 (defn rle ([seq] (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 [coll] (loop [coll (reverse coll) result ()] (if (empty? coll) result (let [item (first coll) [head tail] (split-with (partial = item) coll) chunk [(count head) item]] (recur tail (cons chunk result)))))) (defn rld [coll] (->> (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)) rle-seq))
 (defn rle [c] ((fn encode [e c] (if (empty? c) e (let [p (first c) l (or (first (keep-indexed #(when (not= %2 p) %1) c)) (count c))] (encode (lazy-cat e [[l p]]) (drop l c))))) (lazy-seq) c)) (defn rld [e] (mapcat #(repeat (first %) (second %)) e))
 (defn rle ([coll] (rle [] coll)) ([result coll] (if (empty? coll) coll (lazy-seq (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) coll (lazy-seq (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] (map #(vector (count %) (first %)) (partition-by identity s))) (defn rld [l] (flatten (map #(repeat (first %) (second %)) l)))
 (defn run-len-encode [seq] (->> seq (partition-by identity) (map #(vector (count %) (first %))))) (defn run-len-decode [enc] (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] (lazy-seq (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] (lazy-seq (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)))))))))
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.