99 Clojure Problems – 16: Drop Every Nth Element of a List

Example:

(deftest p16-drop-every-nth
  (is (= '( a  b  d  e  g  h  j  k) (drop-every 3  '(a b c d e f g h i j k)))))

Solution:

I have two solutions to offer. The basic idea for both of them is to go through the input list and transform it to a result list, counting the elements as they are cons'ed to the result. But I would only do the cons'ing if the value of the counter was not a multiple of n thereby dropping every nth element as required.

The first one is a recursive solution. I used a let binding to define an inner function with the additional counter argument. Without any further precautions the function would be stack-consuming and a stack overflow would be due quite quickly (on my machine with a standard 'lein repl' it can handle 4221 elements). In order to prevent that I wrapped the meat of the function in a lazy-seq

 +--------+   +--------+  +--------+
 |LazySeq |   |LazySeq |  |LazySeq |
 |--------|   |--------|  |--------|
 |+--+---+|   |+--+---+|  |        |
 ||a | +----> ||b | +---> |(drop..)|
 |+--+---+|   |+--+---+|  |        |
 +--------+   +--------+  +--------+

lazy-seq is just a macro that turns the expressions it is given into a LazySeq object. If you followed the link and were surprised by Java code: LazySeq is part of the Java underpinnings of Clojure. The lazy part in lazy-seq means that it does not immediately realise the given expressions (and in our case use up all the stack through recursion). Instead it returns and does nothing until it is accessed as a sequence (that's the seq part). Once realised it caches its value. See my poor man's illustration above to find two realised seqs (a and b) and one that has not yet computed its value and still contains the function to produce it.

With this arrangement in place, the only limit is the size of your heap. At least if you prevent the garbage collector from freeing up memory by collecting the elements of the list we have already computed but won't need anymore. This will happen if you hold on to the head of the list somewhere.

Solution number two is based on the same idea but makes use of a built-in function called 'keep-indexed'. I discovered it a couple of days after my first implementation. It's a higher-order function that takes a decider as its first argument. The decider function gets called for every element in the input sequence. The decider itself takes two arguments the first being the zero-based index of the current item and the second being the item itself. The function is called 'keep-indexed' because it keeps every element for which the decider returns a non-nil value. Implementing drop-every-nth is thus reduced to a very simple anonymous function that does the division (as explained above)—we end up with a quite elegant one-liner.

Read more about this series.

99 Clojure Problems – 15: Duplicate the Elements of a List a Given Number of Times

Example:

(deftest p15-duplicate-n
  (is (= '(a a a b b b c c c c c c d d d) (duplicate-n 3 '(a b c c d)))))

Solution:

Again, the solution is just a slight variation on the solution to the previous problem. We are reducing the list into an accumulator as before, but this time we use Clojure's built-in 'repeat' to achieve the specified number of duplications per element. 'Repeat' is returning a list so we have to concat the accumulator with the repeated elements to get our results back.

This is a two star problem, meaning it should take an experienced programmer about 60-90 minutes to solve. Presumably this problem is much harder to solve in Prolog than in Clojure.

Read more about this series.

99 Clojure Problems – 14: Duplicate the Elements of a List

Example:

(deftest p14-duplicate
  (is (= '(a a b b c c c c d d) (duplicate '(a b c c d)))))

Solution:

A straightforward solution just uses reduce to conjoin the current element twice with an accumulator.

Read more about this series.

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

Example:

(deftest p13-decode
  (is (= '( a a a a b c c a a d e e e e) (decode '((4 a) (1 b) (2 c) (2 a) (1 d) (4 e))) )))

Solution:

Maybe I missed the point here, but my solution is identical to the solution of problem 10 after the substitution of pack with its body.

Read more about this series.

99 Clojure Problems – 12: Decode a Run-length Encoded List

Given a run-length code list generated as specified in problem P10, construct its uncompressed version.

Example:

(deftest p12-decode
  (is (= '( a a a a b c c a a d e e e e) (decode '((4 a) (1 b) (2 c) (2 a) (1 d) (4 e))) )))

Solution:

Again, the solution to this problem is fairly straightforward: We map the encoded list over a function that applies Clojure's built-in repeat to each sublist's second element (the character) as many times as the first element of the sublist specifies. This leaves us with a list of lists, each containing the repeating elements. We obtain the final result by flattening the nested structure in to a single list.

Read more about this series.

99 Clojure Problems – 11: Modified Run-length Encoding

Example:

(deftest p10-encode-modified
  (is (= '((4 a)  b  (2 c)  (2 a)  d  (4 e)) (encode-modified '( a a a a b c c a a d e e e e)))))

Solution:

Source. A simple map over the result of P10 leads to the desired result.

Read more about this series.

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

Example

(deftest p10-encode
  (is (= '((4 a) (1 b) (2 c) (2 a) (1 d) (4 e)) (encode '( a a a a b c c a a d e e e e) ))))

Solution:

My simple solution maps over the result of problem 9 using a mapping function that replaces each sublist with a tuple consisting of the length of the sublist and the element.

Read more about this series.

99 Clojure Problems – 9: Pack Consecutive Duplicates of List Elements into Sublists

Example:

(deftest p09-pack
  (is (= '( ( a a a a) ( b) ( c c) ( a a) ( d) ( e e e e)) (pack  '( a a a a b c c a a d e e e e)))))

Solution:

The key to the solution was the partition-by function. I believe I first learnt about it when looking at other people's solutions to a previous problem (While I find it helpful and enlightening to look at other people's code, I am quite strict about not peeking at solutions to problems I have not solved myself yet.)

Partition-by is a higher-order function that takes a grouping function as it's first argument. It pipes all values through that function and lumps the values together in a subsequence (read sublist) until the grouping functions returns a new value—which marks the start of the next subsequence.

By choosing the identity as our grouping function we get exactly the desired result.

Read more about this series.

99 Clojure Problems – 8: Eliminate Consecutive Duplicates of List Elements

Example:

(deftest p08-compress
  (is (= '[a b c a d e]  (compress  '[a a a a b c c a a d e e e e]))))

Solution:

Source

A simple reduce that only conjoins the current element to the result if it is not identical to its predecessor. It uses last to find out who that predecessor was. This is not the most efficient way to solve the problem, as we know from problem 1, last has linear time complexity.

Read more about this series.

99 Clojure Problems – 7: Flatten a Nested List Structure

Example:

(deftest p07-flatten
  (is (= '(1 1 2 3 5 8) (flatten (list (list 1 1) 2 (list 3 (list 5 8)))))))

Solution:

This was the first problem that forced me think a bit harder. It is marked with two asterisks in the original prolog version of the "challenge", meaning a skilled programmer should be able to solve the problem in 30-90 minutes.

It is also the first problem where I'm not happy with my solution. It feels quite imperative too me and its nested if-structures are not exactly easy on the eyes. I used a multiple arity function, which means the function accepts two (or more) different parameter lists. I did this to supply an initial value for an accumulator. Thinking about it now it seems cleaner to me to hide these implementation details completely from the user. This could be achieved by using a let binding or something similar inside the function without polluting the API. The following first "if" checks whether we are dealing with a sequence at all. If not we are just conjoining this non-sequential element with the accumulator. If the input is a sequence we need another "if" to check for an empty sequence which is used as the escape hatch in the recursion that follows: We thread the accumulator through two recursive calls of the function one for the head of the sequence, one for the rest.

Feeling a bit unsatisfied with what I had come up with I went looking for other people's solutions, again, something I had not done before. I found rodnaph github repo with a rather elegant solution based on reduce (I have included it with minor modifications in my code for easy comparison). Reduce saves one noisy if and leaves us with just one check to decide whether an element is a sequence or not. If it is we call the function recursively. But instead of joining individual elements as I did he just concats the resulting flattened sublist onto the accumulator.

Finally I had a quick look at Clojure's built-in flatten. It interprets the nested lists as a tree and uses its tree-seq function to turn this tree into a lazy sequence of its elements. Tree-seq is a higher-order function that takes a branch detector function as its first argument to decide when to descent into the depths of the given data structure. By using sequential? as the branch detector we follow the nested lists as we walk the tree. Tree-seq then conses all nodes together in a lazy sequence. We are not quite done with the resulting sequence because it contains lots of "duplicates" as each branch node also contains in our case all of its children—the root node of our tree for example is the whole nested input list. Therefore we have to filter out all sequences in the result thereby removing the branching nodes. We return the remaining leaves—our flattened list.

Read more about this series.

99 Clojure Problems – 6: Find Out Whether a List Is a Palindrome

Example:

(deftest p06-test
  (is (= true (palindrome? '(1 2 3 3 2 1))))
  (is (= false (palindrome? '(1 2 3)))))

Solution:

One definition of a palindrome is "a sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction" [Wikipedia]. The definition contains already a possible solution. To test whether a given sequence of elements is a palindrome we can compare it with the same sequence in reverse order. We can reuse the reverse function defined to solve the last problem.

Read more about this series.

99 Clojure Problems – 5: Reverse a List

Example:

(deftest p05-reverse
  (is (= '(3 2 1) (my-reverse '(1 2 3)))))

Solution:

Now this might be a bit disappointing but my two solutions to this problem are structurally very similar to the solutions to problem no. 4. One way of reversing a list is to recursively call reverse with the tail of the list until all that is left is an empty list. We cons the head of the current list to the result on the way and return the reversed result when we hit the base case.

Another solution could use reduce to cons the elements together in a similar fashion. The val parameter initialised with an empty list is used again as an accumulator to build up the result.

Finally there is, of course, also the built-in reverse.

Read more about this series.

99 Clojure Problems – 4: Find the Number of Elements of a List

Example:

(deftest p04-test
  (is (= 3 (my-count (list 1 2 3)))))

Solution

There is the built-in count that solves this problem.

I implemented two possible solutions for this problem:

Source 1. This is again a variation on the theme of using the loop/recur construct (that I also used in the previous problems) with an additional parameter binding aka accumulator to keep track of the state—in this case the number of elements encountered so far.

Source 2 I'm not entirely sure if this was really my own idea or if I saw it or something similar somewhere—I should have made a note. This solution uses reduce, a standard higher-order function found in most functional languages. Clojure's implementation allows for a val argument that we use to accumulate the count by incrementing by one for each element in the collection passed as the third argument.

Read more about this series.

99 Clojure Problems – 3: Find the Kth Element of a List

Example:

(deftest p03-kth
  (is (= 3 (kth 2 (list 1 2 3 4)))))

Solution

There is a built-in function called nth that solves this problem.

Source

A relatively straightforward recursive solution uses recur on the function itself while decrementing the k and dropping the first element on each recursive call until we reach k = 0 at which point we return the first element. Strictly speaking this is a linear iterative process and not a recursive one as all the state of the process is in its parameter bindings and not in the results of the stack of recursive calls.

Read more about this series.

Ninety Nine Clojure Problems

My New Year's resolution for 2014: I am going to solve 99 Clojure problems inspired by "S-99: Ninety Nine Scala Problems" and "P-99: Ninety Nine Prolog Problems". It might be a bit ambitious, but we will see.

I thought it would be a good idea to cover each problem and its solution in a short blog post. I will try to do it in a format that does not reveal the solution right away (there will be a link to the solution in each post).

Another word of warning: I am really just starting my Clojure adventure and the code presented here does not claim to be correct or idiomatic Clojure. I hope to see continuous improvement throughout the process though. If you have suggestions or more elegant solutions to one of the problems, please let me know.

The classification of the problems works as follows: * means easy, ** means 60-90 minutes if you are a skilled programmer, *** means difficult. The levels of difficulty are not based on my own experience but taken from the original Prolog problems.

Lists

• P01 (*): Find the last element of a list
• P02 (*): Find the penultimate element of a list
• P03 (*): Find the kth element of a list
• P04 (*): Find the number of elements of a list
• P05 (*): Reverse a list
• P06 (*): Find out whether a list is a palindrome
• P07 (**): Flatten a nested list structure
• P08 (**): Eliminate consecutive duplicates of list elements
• P09 (**): Pack consecutive duplicates of list elements into sublists
• P10 (*): Run-length encoding of a list
• P11 (*): Modified run-length encoding
• P12 (**): Decode a run-length encode list
• P13 (**): Run-length encoding of a list (direct solution)
• P14 (*): Duplicate the elements of a list
• P15 (**): Duplicate the elements of a list a given number of times
• P16 (**): Drop every nth element of a list
• P17 (*): Split a list into two parts
• P18 (**): Extract a slice from a list
• P19 (**): Rotate a list N places to the left
• P20 (*): Remove the Kth element from a list
• P21 (*) Insert an element at a given position into a list.
• P22 (*): Create a list containing all integers within a given range
• P23 (**): Extract a given number of randomly selected elements from a list
• P24 (*): Lotto: Draw N different random numbers from the set 1...M
• P25 (*): Generate a random permutation of the elements of a list
• P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list
• P27 (**) Group the elements of a set into disjoint subsets
• P28 (**) Sorting a list of lists according to length of sublists

Arithmetic

• P31 (**) Determine wether a given number is prime
• P32 (**) Determine the greatest common divisor of two positive integers
• P33 (*) Determine whether two positive integer numbers are coprime.
• P34 (**) Calculate Euler's totient function phi(m)
• P35 (**) Determine the prime factors of a given positive integer
• P36 (**) Determine the prime factors of a given positive integer (2)
• P37 (**) Calculate Euler's totient function phi(m) (improved)
• P38 (*) Compare the two methods of calculating Euler's totient function
• P39 (*) A list of prime numbers
• P40 (**) Goldbach's conjecture
• P41 (**) A list of Goldbach compositions

Logic and Codes

• P46 (**) Truth tables for logical expressions
• P47 (**) Truth tables for logical expressions (2)
• P48 (**) Truth tables for logical expressions (3)
• P49 (**) Gray code
• P50 (***) Huffman Code

Binary Trees

• P54 (*) Is this a binary tree?
• P55 (**) Construct completely balanced binary trees
• P56 (**) Symmetric binary trees
• P57 (**) Binary search trees
• P58 (**) Generate-and-test paradigm
• P59 (**) Construct height-balanced binary trees
• P60 (**) Construct height-balanced binary trees with a given number of nodes
• P60 (Alternative Solution) Construct height-balanced binary trees with a given number of nodes
• P61 (*) Count the leaves of a binary tree
• P61A (*) Collect the leaves of a binary tree in a list
• P62 (*) Collect the internal nodes of a binary tree in a list.
• P62A (*) Collect the nodes at a given level in a list
• P63 (**) Construct a complete binary tree

99 Clojure Problems – 2: Find the Penultimate Element of a List

Example:

(deftest p02-penultimate
  (is (= 2 (penultimate (list 1 2 3)))))

Solution

Source

There are multiple ways of solving this problem. I used a variation of the solution to the first problem. Instead of recurring on the function itself, I added an additional loop form, which allowed me to keep track of the first element in each of the sublists. Once the evaluation reaches the sublist of the last two elements, the first element of this list is also the element we are looking for.

I also added a precondition to the function to ensure the parameter is a Sequence.

Read more about this series.

99 Clojure Problems – 1: Find the Last Element of a List

Example:

(deftest p01-last
    (is (= 3 (last (list 1 2 3)))))

Solution:

There is a built-in function that does just that.

Source.

If you don't want to use the built-in, one possible approach with linear time complexity is to check if there is a next element in the list after the head. If there is one, use the special form recur to recursively apply the function again to the tail of the list until there is no "next" element. Then return the first element, which is also the last. Using "recur" has the added benefit of being non-stack-consuming.

Read more about this series.