My Clojure explained solutions to the s99 problems 14 to 20
28/08/2010 1 Comment
Duplicate the elements of a list.
user> (duplicate ‘(\a, \b, \c, \c, \d))
(\a, \a, \b, \b, \c, \c, \c, \c, \d, \d)
(defn duplicate-s99 "P14" [xs] (reverse (reduce #(cons %2 (cons %2 %1)) '() xs)))
The reduction function would start with an empty list, prepending every item of the xs list two times.
Duplicate the elements of a list a given number of times.
user> (duplicate-n 3, ‘(\a, \b, \c, \c, \d))
(\a, \a, \a, \b, \b, \b, \c, \c, \c, \c, \c, \c, \d, \d, \d)
I’ll cheat a little bit here by using the repeat function from clojure’s api which returns a list (a sequence actually) by repeating an item n times:
(defn duplicate-n "P15" [n xs] (reduce concat (map (partial repeat n) xs)))
I started by repeating evey item of the xs list n times using a combination of the map and repeat functions. Normally, I would have written this transformation this way:
(defn duplicate-n "P15" [n xs] (map #(repeat n %) xs))
But in this case, I used the partial function which given a function f and a number of args returns a new function that takes the remaining args and calls the original function f with all the arguments.
After this step, we end up with a list of lists, as evey item of the xs list was mapped to a list. I flattened this using concat as a reduction function.
Drop every Nth element from a list.
user> (drop-s99 3 ‘(\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k))
(\a, \b, \d, \e, \g, \h, \j, \k)
(defn mul? [m n] (and (not (zero? m)) (zero? (mod m n)))) (defn drop-s99 "P16" [n xs] (keep-indexed #(if (mul? (inc %1) n) nil %2) xs))
This solution relies on the keep-indexed function added in the recently released clojure 1.2. I’m not going to duplicate its documentation here as the official docs already do a great job of explaining it.
I’ve also defined a function mul? which for two arguments m and n returns true if m > 0 and n divides m.
For evey item of the xs list plus its index (0 based), my solution will check if the latter plus one (1 based) is a multiplier of n, returning nil (which will be eliminated by keep-indexed) if this is the case, or the item itself (which will be kept) otherwise.
Split a list into two parts.
The length of the first part is given. Use a Tuple for your result.
user> (split-s99 3 ‘(\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k))
((\a, \b, \c), (\d, \e, \f, \g, \h, \i, \j, \k))
(defn split-s99 "P17" [n xs] (reduce #(if (< (count (first %1)) n) (list (concat (first %1) [%2]) '()) (list (first %1) (concat (last %1) [%2]))) '(() ()) xs) )
A verbose solution, but it is very simple actually: I applied a reduction function on the xs list that starts with an empty solution (a list of two empty lists). For every item of the xs list, if the length of the first list of the solution is less than n, add that item to the first list, otherwise add it to the second list.
As a side note, we could have used clojure’s split-at function, but that would take the fun off solving these problems wouldn’t it ?
Extract a slice from a list.
Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.
user> (slice 3 7 (\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k))
(\d, \e, \f, \g)
(defn slice "P18" [i k xs] (first (split-s99 (- k i) (last (split-s99 i xs)))))
The hard part was already done in the previous problem: the solution uses split-s99 to split the xs list with the i arg, then splits the second part with k-i and returns the first part:
- split (\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k) at 3 and take the second part => (\d, \e, \f, \g, \h, \i, \j, \k)
- split the result of the first step (\d, \e, \f, \g, \h, \i, \j, \k) at 7-3=4 and keep the first part => (\d, \e, \f, \g)
Rotate a list N places to the left.
user> (rotate 3 ‘(\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k))
(\d, \e, \f, \g, \h, \i, \j, \k, \a, \b, \c)
user> (rotate -2 ‘(\a, \b, \c, \d, \e, \f, \g, \h, \i, \j, \k))
(\j, \k, \a, \b, \c, \d, \e, \f, \g, \h, \i)
(defn rotate "P19" [n xs] (let [m (if (neg? n) (+ (count xs) n) n) s (split-s99 m xs)] (concat (last s) (first s))))
Again, the hard part was already done in the P17 problem where a split function was defined. What I did here was to split the xs list at a position depending on n: if n is positive, the split occurs at n, otherwise it occurs at xs’s length minus n. I then return the list obtained by concatting the second segment with the first, in this order.
Remove the Kth element from a list.
Return the list and the removed element in a Tuple. Elements are numbered from 0.
user> (remove-at 1 ‘(\a \b \c \d))
((\a \c \d) \b)
(defn remove-at "P20" [k xs] (let [s (split-s99 (inc k) xs)] (list (concat (butlast (first s)) (last s)) (last (first s)))) )
- I start by splitting xs (\a \b \c \d) at k+1 (2) => ((\a \b) (\c \d))
- return a list with 2 items:
- concatenate the first segment without its last element (\a) with the second segment (\c \d) => (\a \c \d)
- the last element of the first segment (\a \b) => \b
=> ((\a \c \d) \b)