Friday, February 28, 2014

99 Clojure Problems – 24: Draw N Different Random Numbers From The Set 1...M

Example:

(deftest p24-lotto
  (let [draw (lotto 6 49)]
    (is (= 6 (count draw)))
    (is (>= 49 (apply max draw)))))

Solution

This is simple if you solved the previous problem. Just reuse random-select to select n numbers from the set 1...m which you pass in as the second argument.

Read more about this series.

Saturday, February 22, 2014

99 Clojure Problems – 23: Extract a Given Number of Randomly Selected Elements From a List

Example:

(deftest p23-random-select
  (is (= 3 (count (random-select 3 '(1 2 3 4 5 6))) )))

Solution:

There is a simple and idiomatic solution to this problem based on shuffle (which delegates to java.util.Collections#shuffle).

I did another implementation based on recursive loop'ing and the Clojure's rand function (which delegates to java.lang.Math#random). The basic idea is to remove a randomly selected element (reusing remove-at from problem 20) and repeat the process n times. The recipe is fairly simple: use a loop binding with the function parameters and an aggregator. Remove the random element. Then destructure the result, cons'ing the removed element onto the result aggregator and passing the remaining elements into the recur call. Decrement n with each recursion. Exit at (= 0 n).

Read more about this series.

Monday, February 17, 2014

99 Clojure Problems – 22: Create a List Containing All Integers Within a Given Range

Example:

(deftest p22-range
  (is (= '(4 5 6 7 8 9) (my-range 4 9))))

Solution:

There is a function in clojure.core called 'range' that does the job.

My solution is fairly simple compared to the built-in. It uses a lazy-seq, Clojure's alternative to streams. In the body of the lazy-seq we 'cons' the start element onto either an empty list or onto ourselves via a recursive call. We decide which alternative we choose by comparing the start element with the specified end element. If they are equal we have generated all the values we need and end the recursion.

Delayed computation is the necessary precondition for solving the range problem for arbitrarily large ranges of numbers. Delaying the computation allows us to compute the next value in the range only in the very moment we need it and once we continue with our computation it can be thrown away and the memory it consumed can be freed. In our case, on the JVM, the garbage collector will take care of the last part, unless you hold onto the head of your range somewhere.

I have mentioned lazy-seqs before. But a much better introduction with motivating examples can be found as always in SICP. Rich Hickey did not seem to like the stream approach. What he did like were the benefits of delayed computation. If you compare Clojure's form of laziness to the SICP examples you will find that in SICP a completely separate stream API has been established to allow delayed computation. Clojure's lazy-seq keeps compatibility with the existing higher order functions like map, filter and reduce while offering the same degree of laziness.

Read more about this series.

Thursday, February 13, 2014

99 Clojure Problems – 21: Insert an Element at a given Position into a List

Example:

(deftest p21-insert-at
  (is (= '(1 new 2 3 4) (insert-at 'new 1 '(1 2 3 4)))))

Solution:

My solution to this problem is based on the same idea as the previous one: Reuse split from problem 17 to cut the input sequence into two parts. Then concatenate the parts, cons'ing the element to insert to the tail before doing so.

Read more about this series.

Tuesday, February 11, 2014

99 Clojure Problems – 20: Remove the Kth Element from a List

Return the list and the removed element in a tuple. Elements are numbered from 0.

Example:

(deftest p20-remove-at
  (is (= '((a c d) b) (remove-at 1 '(a b c d)))))

Solution:

A quick one: Reuse split from problem 17 to cut the input sequence into two parts. I called them head and tail, which is not quite accurate as head usually refers to the first element of a sequence only. You can then concatenate the head part and the tail part again into a single sequence. Calling rest on the tail before concatenating removes the right element. Calling first on the tail allows you to return the removed element as required (Source).

Read more about this series.

Saturday, February 08, 2014

99 Clojure Problems – 19: Rotate a List N Places to the Left

Example:

(deftest p19-rotate
  (is (= '(d e f g h i j k a b c) (rotate 3 '(a b c d e f g h i j k))))
  (is (= '(j k a b c d e f g h i) (rotate -2 '(a b c d e f g h i j k)))))

Solution:

The examples illustrate that the sign of the first parameter determines the direction of rotation. A positive integer is meant to indicate that we want to rotate N places to left counting from the beginning of the input sequence. A negative integer means start counting from the end of the input sequence.

My solution calculates the split point accordingly and reuses the solution to problem 17 to split the input sequence. All of this happens in an initial let binding, thus we can use destructuring to bind the result of the split operation to two symbols. I called the second sublist "newhead" and the first sublist "newtail". We can then simple concatenate the two parts in the order indicated by the symbol names to create the rotated list.

Read more about this series.

Friday, February 07, 2014

99 Clojure Problems – 18: 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.

Example

(deftest p18-slice
  (is (= '(d e f g) (slice 3 7 '(a b c d e f g h i j k)))))

Solution

If we drop the first I elements we get a lazy sequence starting with the Ith element (because we count starting with 0). If we then take the difference between K and I and remove as many elements from our sequence we obtain the desired slice (Source).

Read more about this series.

Tuesday, February 04, 2014

99 Clojure Problems – 17: Split a List into Two Parts

The length of the first part is given. Use a tuple for your result.

Example:

(deftest p17-split
  (is (= ['(a b c) '(d e f g h i j k)]) (split 3 '(a b c d e f g h i j k))))

Solution:

There is a nice, functional, built-in solution in Clojure. I wanted to do it anyway.

My solution uses a nested, recursive function. Strictly speaking you cannot nest function definitions in Clojure in the same way as you can e.g. in Scala. But what you can do is to define a binding via let pointing to a function within another function. Since writing the solution I have learned that you can use letfn for this purpose.

The local function itself is fairly simple. It returns a vector (the tuple if you will) of the two lists and takes the length n of the first list, the list to break apart and the the initially empty result accumulator. We then "recur" by decrementing n, conjoining the first element to the result and passing on the rest of the sequence. When n becomes zero or we don't have anything left to split, we return the result.

Read more about this series.