My Clojure explained solutions to the s99 problems 8 to 13
09/08/2010 1 Comment
Eliminate consecutive duplicates of list elements.
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
user> (compress ‘(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e))
(\a, \b, \c, \a, \d, \e)
(defn compress "P08" [xs] (reduce #(if (= (last %1) %2) %1 (concat %1 (list %2))) '() xs))
The reduction function would check if the last element of its first argument equals its second argument, which would be the element of xs being processed. It the they are equal, it would just return the first argument as is, otherwise it would add the xs element to the end of the first argument list and return it.
Here’s how it would work on the characters list shown above:
(‘() \a)=>(\a) because \a and (last ‘()) which is nil are not equal
((\a) \a)=>(\a) because (last (\a)) which is \a is equal to the second argument \a
((\a) \b)=>(\a \b) because \a and \b are not equal
((\a \b \c \a \d) \e)=>(\a \b \c \a \d \e)
Pack consecutive duplicates of list elements into sublists.
If a list contains repeated elements they should be placed in separate sublists.
user> pack(‘(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e))
(\a, \a, \a, \a), (\b), (\c, \c), (\a, \a), (\d), (\e, \e, \e, \e))
(defn pack "P09" [xs] (reverse (reduce #(if (= (ffirst %1) %2) (cons (cons %2 (first %1)) (rest %1)) (cons (list %2) %1 )) '() xs)))
Run-length encoding of a list.
Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
user> (encode ‘(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e))
((4,\a), (1,\b), (2,\c), (2,\a), (1,\d), (4,\e))
(defn encode "P10" [xs] (map #(list (first %) (count %)) (pack xs)))
This solution reutilizes the pack function defined in the previous problem. Once the list of items is packed, we map every element (which is a list) to a pair defined by any item of the list, the first for instance and the list’s length.
Modified run-length encoding.
Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms.
user> (encode-modified ‘(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e))
((4,\a), \b, (2,\c), (2,\a), \d, (4,\e))
(defn encode-modified "P11" [xs] (map #(if (= 1 (last %)) (first %) %) (encode xs)))
We rely on the encode function we defined in the tenth problem to do the actual work, and then we apply a mapping function on the result that for the pairs (count, item) with a count of one returns only the item, leaving the others as is.
Decode a run-length encoded list.
Given a run-length code list generated as specified in problem P10, construct its uncompressed version.
user> (decode ‘((4, \a), (1, \b), (2, \c), (2, \a), (1, \d), (4, \e)))
(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e)
(defn decode "P12" [xs] (reduce concat (map #(repeat (first %) (last %)) xs)))
We start by unpacking the encoded list elements by using the repeat function which given a count and an element, it yields a list of count elements.
Afterwards, it’s simply a matter of concatenating the lists elements using the concat function (which concatenates two lists).
Run-length encoding of a list (direct solution).
Implement the so-called run-length encoding data compression method directly. I.e. don’t use other methods you’ve written (like P09′s pack); do all the work directly.
user> (encode-direct ‘(\a, \a, \a, \a, \b, \c, \c, \a, \a, \d, \e, \e, \e, \e))
((4,\a), (1,\b), (2,\c), (2,\a), (1,\d), (4,\e))
(defn encode-direct "P13" [xs] (reverse (reduce (fn [res x] (let [pair (first res) count (first pair) e (last pair)] (if (= x e) (cons (list (inc count) x) (rest res)) (cons (list 1 x) res)))) '() xs)))
Basically what I’ve done here is combine the pack and encode functions. This solution starts by applying the following reduction function:
Given the current result res (which starts as an empty list) and an item x from the list to encode:
- Initialize the following locals:
- pair: represents the current pair (count, item) of the encoded result list. To simplify matters, I’ll store the pairs in the result list in reverse order
- count: the first element of pair
- e: the encoded item which is stored as the second element of the pair
- If the current list element is equal the the current pair element, increment the latter’s count. We do this by creating a new result list with the pair (e or x, count+1) as it’s head and the rest of the old result list as it’s tail.
- Else, add a new pair to the result with a count of 1 and x as it’s element
- In both cases, I use cons to construct the result list, which explains why I’m constructing the result in a reverse order
It remains to reverse the result to get the expected result.