99 Clojure Problems – 60: Construct Height-balanced Binary Trees with a Given Number of Nodes.

"Construct height-balanced binary trees with a given number of nodes. Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain? Clearly, MaxN = 2H - 1.

However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a function min-hbal-nodes that takes a height and returns MinN.

On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?

Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes."

Example:

ninety-nine-clojure.bintrees> (min-hbal-nodes 4)
7
ninety-nine-clojure.bintrees> (all-hbal-trees 4 'x)
([x [x [x nil nil] nil] [x nil nil]] [x [x nil nil] [x [x nil nil] nil]] [x [x nil [x nil nil]] [x nil nil]] [x [x nil nil] [x nil [x nil nil]]])

Discussion

The solution to problem 60 builds upon the solution to problem 59, so if you have not done that one yet, now would be a good time.

As always I don't want to give away the solution in the blog post right away to give you a chance to try it yourself first. But if you get stuck, it is all on Github.

Approach

The question contains a hint towards a possible solution but it was not immediately clear to me how the minimum number of nodes at a given height MinN helps us in finding all height-balanced trees with a given number of nodes.

It helped me to explore the problem starting with the expected result and progressing to the intermediate computations mentioned in the problem description later: What do we want to achieve and which parts do we have already?

1. We have a method "height-balanced-trees" to calculate all height-balanced trees with a certain height from P59.
2. We could now just filter the result of calling this existing function, leaving those trees in the result that have the required number of nodes and have the desired solution to problem 60.
3. But at which height do we start generating trees and where do we stop? We cannot generate trees for all possible heights.
4. Working our way back towards the beginning of the question, we could use the maximum height H of a tree with a given number of nodes as the upper bound of the input to the "height-balanced-trees" function from problem 59.
5. That leaves us with the missing lower bound: What is the minimum height of a tree with a given number of nodes? We need another function to answer that question. Let's start with that one.

Minimum Height of a Tree with a Given Number of Nodes

If we recursively half the given number of nodes and keep track of how many times we did that we have the minimum height, because it is a height-balanced binary tree. But we could also exploit the fact that the height of a balanced binary tree of n nodes is log2 n + 1.

Maximum Height of a Tree with a Given Number of Nodes

Now this part is a bit trickier. We now need to know what the minimum number of nodes at a given height is, as indicated in the question. Why? Let's look at the number of nodes for all the trees at a given height:

H=3: (4 5 6 7)
H=4:       (7 8 9 10 11 12 13 14 15)
H=5:                   (12 13 14 15 16 17 18 19 20 ...

To pick an interesting example: A tree with seven nodes is at most four levels high. We know that because the minimum number of nodes at height five is greater than seven. If we look at all MinN for increasing heights and stop when MinN gets bigger then our N, we know that the previous height is the maximum height we are looking for.

Now how do we calculate the MinN? Interestingly the MinN(H) is always the MinN(H-1) + MinN(H-2) +1. A formula that seems like a twist on the Fibonacci sequence. I don't have a good intuition as to why this is, but you can just derive this rule by looking at trees with small Hs.

The mentioned formula translates nicely into a recursive function.

Solution and Outlook

Putting it all together is then relatively straight forward. So much so that I will share the code right here:

(defn all-hbal-trees
  "P60 (**)  ... Now, we can attack the main problem: construct all the
  height-balanced binary trees with a given nuber of nodes."
  [n v]
  (->>  (range (min-height-hbal n) (inc (max-height-hbal n)))
        (mapcat #(height-balanced-trees % v))
        (filter #(= n (num-nodes %)))))

Reusing the code from problem 59 is certainly nice but this solution seemed rather wasteful to me as we are throwing away many intermediate results in the filter step. Feeling a bit underwhelmed by my solution I started exploring the original Prolog solution to the problem and reimplemented it using David Nolen's core.logic library. We will cover this additional experiment in the next post.

Read more about this series.

99 Clojure Problems – 59: Construct Height-Balanced Binary Trees

"In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Write a method to construct height-balanced binary trees for a given height with a supplied value for the nodes. The function should generate all solutions."

Example

ninety-nine-clojure.bintrees> (height-balanced-trees 2 'x)
([x [x nil nil] [x nil nil]] [x [x nil nil] nil] [x nil [x nil nil]])

Discussion

To get some intuition for this problem we can distinguish tree cases:

1. The left subtree has the same length as the right subtree
2. The left subtree is shorter by one level
3. The right subtree is shorter by one level

If we combine all three cases via concat we have our solution. We generate the solutions by recursively calling the function with the heights h-1 and h-2. We don't have to generate the 'short' versions of the left and right subtrees separately. We can just create both combinations (left shorter/right shorter) with just one copy of the lower subtrees (h-2) and one copy of the higher subtrees (h-1). Still, there is some redundant computation going on as the h-1 contains also the h-2 subtrees. Memoization might help here.

The practical applicability of the function just created as described is somewhat limited as the number of height balanced binary trees grows exponentially. For our test case we therefore just look at trees up to five levels high.

Read more about this series.

99 Clojure Problems – 58: Generate-and-Test Paradigm

"Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.

How many such trees are there with 57 nodes? Investigate about how many solutions there are for a given number of nodes? What if the number is even? Write an appropriate function."

Example

>(symmetric-cbalanced-trees 5 'x)
([x [x nil [x nil nil]] [x [x nil nil] nil]] [x [x [x nil nil] nil] [x nil [x nil nil]]])

Discussion

A simple approach just filters the output of our existing function for completely balanced trees using the also existing symmetric? predicate.

A simple optimisation is to avoid the tree generation all together if the number of nodes requested is even, as there is no symmetric tree with an even number of nodes.

Solution on Github.

Read more about this series.

99 Clojure Problems – 56: Symmetric Binary Trees

"Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes."

Example/Test

(deftest p56-symmetric-binary-trees
  (is (= true (symmetric? [:a [:b nil nil] [:c nil nil]])))
  (is (= false (symmetric? [:a nil [:b nil nil]]))))

Discussion

This is a two star problem but once the implications of 'symmetry' in this case become clear, it is not hard at all to solve.

If we think about the tree it is obvious that we cannot establish the property of symmetry just by looking at the node count. Symmetry seems to be stricter in that it not only requires the same number of nodes in each subtree but they also have to be mirror images of each other. This is already implied in the hint given to us in the problem description.

Another way of putting it is that the leaves of the subtrees we compare have to be in the mirrored position respectively. One way to find that out is to recursively inspect both subtrees and make sure that there is a leaf in left tree when there is also a leaf in the right tree.

This led to this solution, which is incorrect.

Nil-Punned

The reason this first solution does not work as expected is that I have overloaded the meaning of nil. It represents the absence of a subtree and the empty tree. But I have also created the helper functions 'lefts' and 'rights' to extract the left or right subtrees respectively. As they rely on the seq abstraction through 'first', 'next' and 'last', nil now can be also the result of retrieving one of the subtrees.

There is no way to decide if the nil we get back means now 'there is no subtree' or 'there is no subtree because there is no tree in the first place'. But exactly this distinction is important when we want to determine the symmetry property of the data structure.

(Data) Structure

Pattern matching using core.match on the structure of the tree allows us to overcome this problem and distinguish the different cases more clearly. Nil as the empty tree never matches the pattern for a tree node. We do not need the different helper functions anymore as we are now working directly with the structure of our data.

You can find this amended solution on Github.

Read more about this series.

99 Clojure Problems – 57: Binary Search Trees

Write a function insert-val to add elements to a binary search tree. Then write a function to construct a binary search tree from a list of integer numbers. Then use this function to test the solution of the problem P56.

Example

>(->binary-search-tree 3 2 5 7 1)
[3 [2 [1 nil nil] nil] [5 nil [7 nil nil]]]
>(->binary-search-tree 5, 3, 18, 1, 4, 12, 21)
[5 [3 [1 nil nil] [4 nil nil]] [18 [12 nil nil] [21 nil nil]]]
> (symmetric? *1)
true

Discussion

I feel almost bad about the number of times I have resorted to core.match to solve these problems. Maybe I am just not thinking hard enough about alternative approaches. What it certainly tells us is that pattern matching seems to lend itself very well to this class of problems.

Pattern Match All The Things

Four match clauses seem to do the trick (number three is technically split into two) :

1. Adding nil to a tree is just the tree.
2. Adding a value to nil is a new tree of one node
3. Adding a non-nil value to a non-nil tree: Now it depends on the ordering of the values: is the value greater than the value at the current node: add it to the right subtree, else add it to the left subtree.

What about adding the same value twice? I do not think binary search trees are per se opinionated about how to handle duplicates. In my implementation duplicate values just end up to the right of the value they are identical with. I think it would also be very plausible to make insert-val a no-op if the value is already contained in the tree.

Putting it all together

Constructing the tree seems trivial using the insert-val function we have just constructed. Clojure's reduce is equivalent to a 'fold left' over the input collection. If we reduce the input values with insert-val using nil as the neutral element we get the desired result.

My solution can be found, as always, on Github.

Read more about this series.

99 Clojure Problems – 55: Construct Completely Balanced Binary Trees

"In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one."

Example

>(balanced-trees 3 'x)
([x [x nil nil] [x nil nil]])

Verification

(defspec balanced-trees-are-balanced
  20
  (prop/for-all [i gen/nat]
                (->> (balanced-trees i 'x)
                     (apply  breadth-first-traverse)
                     (map balanced?)
                     (reduce #(and %1 %2)))))

Discussion

The following observations lead to a possible solution:

1. We can enumerate all the trees by combining the root node with all its possible subtrees to the left and to the right which have in sum \(n-1\) nodes
2. We distinguish between even and odd values of n
3. Odd values of n give balanced trees as \(n-1\) is even and both subtrees will be of equal size
4. Even values of n give balanced trees if we return all combinations of left/right trees with \((n-1) / 2\) and \((n-1) / 2 + 1\) nodes. We are using integer division here, thereby effectively 'flooring' and 'ceiling'

Based on this understanding the implementation is fairly straightforward. We handle the base case of an empty tree separately and then the two cases for odd and even number of nodes.

There is a little bit of ceremony involved in order to create the combinations of subtrees in the case of odd-sized subtrees. You have to do a nested mapcat to get both variants with the longer subtree in left and right position respectively. Maybe there is room for improvement.

I found it instructive to look at the Haskell and Prolog solutions in order to get a better understanding. The latest version of my code tries to come close to the clarity of the Prolog solution.

Read more about this series.

99 Clojure Problems－54: Is This A Binary Tree?

"Write a predicate tree? that succeeds if and only if its argument is representing a binary tree."

Example/Test

(deftest nil-is-a-tree
  (is (= true (tree? nil))))

Discussion

This is an interesting problem because it allows us to touch the basic question of static vs. dynamic typing.

If we look at the Scala solution, we see that in a statically typed language this problem can be fully solved via the type system. Or as Phil Gold put it: "Score one for static typing."

I am not a zealot when it comes to static vs. dynamic typing. Both approaches have their merits. There are many ways to look at this (prototyping, easier code reuse vs. working with legacy code, catching errors early ...). Maybe it is a very narrow perspective but for me it is almost more of a social than a technical issue. I see how a team of developers with mixed skill levels in combination with a code base in various stages of decay can benefit from a compiler giving them more guidance along the way through the maze. On the other hand, I have never missed the absence of a strict type system in Clojure when quickly building prototypes or solving programming problems. While I am still on the fence about the general issue of static vs. dynamic type systems, let us look at the problem at hand: working with binary trees.

The Dynamic Approach

We can solve this problem in a "dynamic" fashion building upon what we have done so far in this series. We worked with trees before for problem 25 using a library called core.match, which gives us pattern matching in Clojure to implement all the tree operations.

With core.match we get the tree?-predicate with a simple three way pattern match: it is either a node consisting of a label and two subtrees or nil representing the empty tree. Everything else is not a tree. The only complication is that we need to apply the pattern match for the node recursively, because the left and right subtrees should also be proper trees. Luckily, core.match supports function application in match expressions since 0.3.0.

Have a look at the solution and the accompanying tests to the get the idea.

Best of Both Worlds?

In Clojure we have a second option because, while being dynamic as a language, it offers us optional static typing in the form of a library called core.typed. The library is the result of the work Ambrose Bonnaire-Sergeant did for his PhD dissertation.

It allows us to declare a type Node consisting of a label of any kind and two children that are trees themselves. A tree is now either an empty tree (represented by nil) or one of these nodes.

(t/ann-datatype Node [val :- Any
                      l   :- Tree
                      r   :- Tree])
(deftype Node [val l r])

(t/defalias Tree
  (t/Nilable Node))

To make this work, all you have to do is include core.typed as a library dependency in your project.clj (assuming you are using leiningen as your build tool). The type checking is not part of the compilation but an extra step you have to integrate into your workflow. Editor integrations for vim, Emacs and LightTable make it easier to construct your type system during development.

It helps to look at the core.typed example code (even if you are familiar with static typing) to work out how to apply the type annotations.

The Choice Is Yours

Clojure seems to give us the choice between both (optional) static and dynamic typing. If time allows, I will try to follow this dual path through all the binary tree problems to gain more insight into both approaches.

Read more about this series.

99 Clojure Problems－50: Huffman Code

Example

(deftest huffmann
  (is (= '([a "0"] [c "100"] [b "101"] [f "1100"] [e "1101"] [d "111"])
         (-> '([a 45] [b 13] [c 12] [d 16] [e 9] [f 5])
             build-huffman-tree
             map-symbols))))

Discussion

Huffman coding is a variable length coding based on the frequency of each possible source value. You might have a look at the wikipedia article (or a good book on discrete mathematics and/or algorithms as suggested on the original "99 problems" page) to get a basic understanding of what we are trying to do here.

I used a variation of the two queues method: one queue for the initial set of leaf nodes, the other for the aggregate or branch nodes. The queues have to be ordered by ascending frequency. If you can use a priority queue that does the ordering for you that's fine. You then dequeue the two items with the lowest frequency from each queue (or from just one queue if the other is empty) and combine the two leaves into a branch node. You continue with this procedure until there is only one node left, which is your Huffman tree.

Have a look at the code, but, as usual, first try it yourself. I'm not entirely happy with my solution, which seems to be correct, but some of its semantics are rather subtle. Did you spot that the check for an empty queue is implicit in the default value of Long/MAX_VALUE when accessing the next value polled from the queue? As always, I am happy to get feedback on the solutions presented.

This is the last post for 2014. I set out at the beginning of the year to solve all 99 problems in Clojure that were mentioned in the original 99 Prolog problems compilation. I managed to do the first 50 and I really enjoyed them. Nevertheless, when learning a new language, solving these kinds of nicely prepared educational problems takes you only half the way. I think that the next step should be to build an actual system in Clojure. I still found doing these exercises rewarding and useful, as they allow me to do some Clojure in the limited spare time I have. I am going to continue with the series next year hoping to solve the remaining problems.

99 Clojure Problems – 49: Gray Code

"An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example:

n = 1: C(1) = ("0", "1").
n = 2: C(2) = ("00", "01", "11", "10").
n = 3: C(3) = ("000", "001", "011", "010", "110", "111", "101", "100").

Find out the construction rules and write a function to generate Gray codes. See if you can use memoization to make the function more efficient."

Example/Test

deftest gray-2
  (is (= ["00" "01" "11" "10"] (gray 2))))

(deftest gray-3
  (is (= ["000" "001" "011" "010" "110" "111" "101" "100"] (gray 3))))

Discussion

I did not work out the construction rules myself but simply looked at Wikipedia. I recommend to read the relevant article yourself before continuing. Based on my reading I came up with two solutions.

The first solution follows the name giving generative principle of forming new lists of gray codes by reflecting existing sublists. Or more precisely from Wikipedia:

"The binary-reflected Gray code list for n bits can be generated recursively from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1"

This lead to an immediate translation into code based on strings as can be seen on Github.

Adding memoization as requested by the exercise is very easy in Clojure as there is a dedicated memoize function that returns a memoized version for a referentially transparent function.

Leaving aside the inefficiencies of this solution there is a more immediate problem with this implementation because it is not "stack safe". That means for every recursive step a new stack frame will be created and the code will only unwind the stack when it has reached the exit condition leading to a stack overflow for deep recursive calls. Using the gray code example, depending on your VM configuration and whether or not you are using memoization, you start running into trouble around 20 bits or so.

The second solution is based on the gray code conversion algorithm whereby you convert binary to gray code by xor'ing the binary number with itself right shifted by one. The only complication is that you have to calculate the range of possible numbers first. This is 2^n where n is the number of bits you want to support in your gray code encoding.

You calculate an exponent in Clojure by literally multiplying the number as many times as the exponent states:

(reduce * (repeat n 2))

or use a library like numeric-tower that features an exponent function. To create the identical output as the string based version I used the common lisp formatting build into clojure.pprint:

(cl-format nil (str "~" n "'0b") %)

This allows me to print the binary/gray code elegantly left padded with zeros. Alternatively you could use Java interop with String.format and Long.toBinaryString.

There is probably more to be said about gray code and there are more efficient solutions. The two main takeaways here on the language level are how easy it is in Clojure to create a memoized function and the possibility to use Common Lisp formatting instead of Java's if it seems more appropriate.

Read more about this series.

99 Clojure Problems – 48: Truth Tables for Logical Expressions (3)

Generalize problem 47 in such a way that the logical expression may contain any number of logical variables. Define table in a way that (table vector expr) prints the truth table for the expression expr, which contains the logical variables enumerated in vector.

Example

ninety-nine-clojure.logic> (table (i [a b c], (a and (b or c) equ a and b or a and c)))

|    :a |    :b |    :c | :result |
|-------+-------+-------+---------|
|  true |  true |  true |    true |
|  true |  true | false |    true |
|  true | false |  true |    true |
|  true | false | false |    true |
| false |  true |  true |    true |
| false |  true | false |    true |
| false | false |  true |    true |
| false | false | false |    true |

Discussion

This is more of a refactoring of the previous solution than anything else. I learned a bit more about how macros work in Clojure and discovered that some of the problems I solved last time were actually non-problems.

There are three places in our current code that prevent us from specifying expressions with arbitrary many logical variables: The input values were hard-coded to the four possible combinations of two boolean arguments. The header used when printing the truth table was hard-coded. Finally the macro that supported the defintion of a logical expresion in infix notation was limited to two arguments as well.

Possible input values

We want to create all possible ordered sets that can be created out of the n sets of input parameters for each logical variable. For two boolean parameters (that's what we had so far) it looks like this:

        +                             
        |  true         false         
+------------------------------------+
  true  | [true true]   [true false]  
        |                             
  false | [false true]  [false false] 
        +                             

I initially thought of this problem as a for comprehension in the form of

(for [x [true false] y [true false]] [x y])

To make that work for n arguments I would have to implement another macro to create a for comprehension with n generators. When I realised that the operation here is just an n-fold Cartesian product, I knew that this was not necessary. I decided to use clojure.math.combinatorics which was already a dependency of the project to calculate the Cartesian product of n sets of Boolean parameters instead.

Generating functions with a given arity

I had introduced the 'i' macro to have a simple and elegant way to express that its argument was to be interpreted as a logical expression in infix notation.

(i (a or b))

To support n logical variables we now need to move away from this succinct syntax a bit and specify the logical variables in use in a separate argument.

(i [a b c] (a and (b or c)))

Implementing this was way easier than I thought. It looks similar to this:

(defmacro [bindings & expr]
   `(fn ~bindings (infix ~expr)))

I also noticed that the deep code walking and code replacement I introduced last time, was completely unnecessary. I thought you need generated symbols, but that is only true if you want to use let inside a syntax quote, which I did not. I had probably stumbled over Clojure's quoting rules, which are one of the more complicated bits of the language.

This new argument was interesting in another respect: I wanted to use it to create a header for the truth table. But wanted to avoid this duplication:

(table [a b] (i [a b] (a or b)))

Extracting metadata from a function

A possible solution: Clojure functions have metadata about their arity which is exactly what we want and need to generate the header of the truth table. But the metadata is only present on functions created via defn. The one used here was anonymous. In addition you should be able to do

(table and)

That is not even a function. As we already know 'and' is a macro in Clojure but it has the necessary metadata. Even more than we need:

(:arglists (meta #'and))
([] [x] [x & next])

The hash-quote is a reader macro that translates to (var and) which resolves to the var object (as opposed to it's value) where the metadata is stored. The problem here: 'and' has more than one argument list and the relevant one in this context contains a var arg.

I ended up offering both APIs:

(table '[a b] and)
(table (i [a b] (a and b)))

The second variant uses the metadata to infer the header of the truth table while it's explicit in the first variant. I'm not entirely happy with that result as it seems a bit brittle: in the second variant it just uses the first argument list and falls flat on its face when the argument does not contain any metadata, which could well happen if you just specify an anonymous function yourself instead of using the 'i' macro.

Have a look at the complete code here on Github.

Read more about this series.

99 Clojure Problems – 47: Truth Tables for Logical Expressions (2)

"Continue problem P46 by defining and/2, or/2, etc as being operators. This allows to write the logical expression in the more natural way, as in the example: A and (A or not B). Define operator precedence as usual; i.e. as in Java."

If we want to have this 'natural way' of writing logical expressions we will have to introduce infix notation into Clojure's prefix world.

Example

ninety-nine-clojure.logic> (table (i (a and (a or not b))))

|    :a |    :b | :result |
|-------+-------+---------|
|  true |  true |    true |
|  true | false |    true |
| false |  true |   false |
| false | false |   false |
nil

Discussion

How do we get the desired syntax?

If you have read the previous article you know that we are deep in macro-land and there is no way back. This can be seen as a macro anti-pattern (See "Macros all the way down" in Clojure for the Brave and True).

We are already in a situation where our truth table function can only be a macro because we want to pass in unquoted macros as parameters. This is also true for the infix problem: What we need in a first step is a macro that allows us to write something like this:

(table #(infix (%1 and (%1 or not %2))))

Remember the truth table macro expects expressions that take two arguments. A first step towards that goal is to create an anonymous function with two arguments (%1, %2) and process our logical expression with a yet to write infix function or macro to turn it back into Clojure code. The infix notation is not easy to read due to the numbered arguments but we will work on that later.

Infix in Clojure

It is a well established exercise to implement infix operators in a Lisp. There is the exercise 2.58 in SICP for example that teaches us about the benefits of prefix notation over infix notation. The chapter 1.22 in the "Joy of Clojure" shows us in a similar fashion how we can avoid all the troubles in Clojure that usually come with the rules of operator precedence and still have some infix notation if we want it.

Now to get a basic infix notation we just need a rather simple macro that puts the operator into function position and adds parens around it.

([a op b]
     `(~op (infix ~a) (infix ~b)))

It recursively calls itself on the symbols 'a' and 'b', which can be composite expressions in parens like:

(a and b) 

or a simple boolean value. I came up with this to deal with both cases:

 ([x] (if (seq? x)
         `(infix ~@x)
         x))

It says: If the argument is a sub-expression in list form and therefore sequential apply the infix macro again otherwise return the value.

We have got all the binary operators covered assuming that they all have the same precedence. (Which they don't e.g. in Java which was mentioned in the original Prolog problem description). A bit trickier are now the unary operators like 'not'. If we use parens as in '(not a) and b)' it will work out of the box, as this negation of 'a' is already valid Clojure. I am supporting expressions like 'a and not b' with the following extension of my infix macro:

([a b c d]
     (if (unary? a)
       `(~c (~a (infix ~b)) (infix ~d) )
       `(~b (infix ~a) (~c (infix ~d)))))

The basic idea here is to take advantage of Clojure's support for multi-arity functions/macros and deal with a unary operator before the second value/sub-expression by interpreting any call with four arguments in that way. Now this falls obviously down as soon as we have something like 'not a and not b'. We will have to cover that case seperately.

Optional noise reduction

I already mentioned that the usage of the infix macros in combination with the truth tables leaves room for improvement:

(table #(infix (%1 and (%1 or not %2))))

The numbered arguments of the anonymous function are a bit ugly. We would rather have something like this:

(table (i (a and (a or not b))))

We imagine that 'i' is the macro that triggers the infix magic and the rest is an easy to read logical expression. We imagine further that 'i' is a macro that transform our expression into a function of two arguments 'a' and 'b'. The result of the transformation would be the following piece of Clojure code:

(fn [a b] (and a (or a (not b))))

[Update: As it turns out the symbol replacement described below is unnecessary. Stay tuned for problem 48 for more detail on this.]

The problem with that idea: Clojure won't allow you to introduce new bindings in a syntax quote (`) that might capture existing variables. The gensym mechanism is there for you to generate unique symbols to be used in a macro that won't accidentally hijack existing variables.

A post on Fogus' blog about deep code walking macros lead me to this implementation:

(defmacro i
  [& args]  
  (let [a (gensym)
        b (gensym)
        code (clojure.walk/postwalk-replace {'a a 'b b} args)]
    `(fn [~a ~b] (infix ~@code))))

It has its limitations: you can only use 'a' and 'b' as variables, as they are hard-coded. I then uses a deep code walking function to replace the 'a's and 'b's with generated symbols, which will also be used to generate a wrapper function around the logical expressions.

That was not very hard, but there would be a bit more work involved to get rid of the limitations. We will look at that when we tackle the next problem which will require us to support logical expressions of arbitrary arity. The source for my complete solution is as always on Github.

Read more about this series.

99 Clojure Problems – 46: Truth Tables For Logical Expressions

Define functions and, or, nand, nor, xor, impl, and equ (for logical equivalence) which return true or false according to the result of their respective operations; e.g. (and A B) is true if and only if both A and B are true.

A logical expression in two variables can then be written in prefix notation, as in the following example: (and (or A B) (nand A B)).

Now, write a predicate table which prints the truth table of a given logical expression in two variables.

Example

ninety-nine-clojure.logic> (table impl)

|    :a |    :b | :result |
|-------+-------+---------|
|  true |  true |    true |
|  true | false |   false |
| false |  true |    true |
| false | false |    true |

Discussion

This problem has three parts: Implementing the logical expressions as functions. Implementing the truth table function and finally—and this is Clojure specific—thinking about how to deal with the built-in logical expressions 'and' and 'or'.

Logical expressions in Clojure

Once you have implemented 'and', 'or' and 'not' you can implement all other logical expressions in terms of these three "primitives". In Clojure 'and' and 'or' are macros. I don't want to give an introduction to macros here (I recommend having a look at the most excellent Joy of Clojure or Clojure for the Brave and True) But I will say that much: As Clojure's code is just data, macros allow you to transform that data before compilation into other code/data.

Bearing that in mind and trying to understand clojure.core/and we hope to get an idea how to implement the most basic logical expressions for this problem ourselves. This is how the 'and' macro is implemented in Clojure:

(defmacro and
  ([] true)
  ([x] x)
  ([x & next]
   `(let [and# ~x]
      (if and# (and ~@next) and#))))

Even without understanding every last detail of this macro definition, we can see that Clojure's 'and' transforms the and-expression into a recursive series of if-expressions.

Filling in concrete values and using macroexpand makes things a bit clearer:

ninety-nine-clojure.logic> (macroexpand '(and true false))
(let* [and__3941__auto__ true] 
  (if and__3941__auto__ 
     (clojure.core/and false) 
     and__3941__auto__))

Expanded to the first level, we see how the and-expression is now an 'if' inside a 'let'. A recursive call to 'and' for the second argument is still unexpanded. This should give us enough inspiration to implement simple 'and' and 'or' functions of our own.

But we can also reuse the existing control structures Clojure offers right away to build the higher level expressions for 'nand', 'nor', 'equ', 'impl' and 'xor'.

Creating a truth table

The next step is to build the table function. I cheated a bit and used Clojure's print-table, hard-coding the possible inputs for a function with two boolean arguments. Print-table takes a sequence of maps for each row. To get the desired effect I interleaved a descriptive header with the result of evaluating the logical expressions and turned that into a sorted map. But it should not be too hard to built a simple printing function yourself.

Make it work with the built-in expressions

Now this last part is only relevant if you were lazy, as I was, and reused the existing Clojure expressions for 'and' and 'or'. Try to create a truth table for them and you will get a response similar to the following:

(table and)
CompilerException java.lang.RuntimeException: Can't take value of a macro: #'clojure.core/and, compiling:(NO_SOURCE_PATH:1:1) 

Now we already know that 'and' is implemented as a macro. Unless we are quoting we can't use it as a value:

(table 'and)

If we want to provide an API where the user does not need to know whether the argument to our table function is a macro and therefore has to be quoted, we have to write a macro ourselves.

Now this is a bit tricky and took a while. The hardest bit was was a helper macro I created to evaluate the logical expression (possibly a macro) for all input values, even though this is shamelessly taken from an answer on stackoverflow. The helper wraps the macro in a function where it is eval'd after making it referable by quoting it like so (with exemplary values added for clarity):

(list 'and true false)

I called it evaluator:

(defmacro evaluator [expr]
  `(fn [& args#]
     (eval `(~'~expr ~@args#))))

It uses two levels of syntax-quoting (`). The first to allow the introduction of the args-symbol and the second to allow the unquote-splicing (~@args#) of the args vector in the quoted function call (~'~expr) which we are building inside our evaluator function.

This kind of complexity is in my experience the exception and I am not even sure if there is not an easier solution to my problem than the one I found. But given the fact that the argument to our function is already a macro, I don't see a solution avoiding macros. Please let me know if you think I'm wrong. In the meantime have a look at the source code.

Read more about this series.

99 Clojure Problems: 41: A List Of Goldbach Compositions

"Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition."

Example

(print-goldbach (range 9 21))
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

"In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than, say, 50. Try to find out how many such cases there are in the range 2..3000.

Example (minimum value of 50 for the primes)":

(print-goldbach (range 2000) 50)
992 = 73 + 919
1382 = 61 + 1321
1856 = 67 + 1789
1928 = 61 + 1867

Discussion

A simple problem as we have already implemented all the bits that do most of the work. To create a list of Goldbach compositions we take the input range (note the range semantics in Clojure: the upper limit is exclusive) filter out the even numbers that are greater than 2 (as required by Goldbach's conjecture). We then map the Goldbach function over the range and apply the mimimum filter for the first prime in the results (see the second example above).

We format the result and println it, generating a new line for every Goldbach composition. Have a look at the source once you tried it yourself.

The interesting aspect of this problem is the use of doall, which we have to call at the very end. Why? The intermediate representation of the data is a lazy sequence. By mapping println over that sequence we declare that we want to trigger a side effect (the printing). But the effect does not occur, due to laziness, until we force it with doall.

Read more about this series.

99 Clojure Problems – 40: Goldbach's Conjecture

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers. Write a predicate to find the two prime numbers that sum up to a given even integer.

Test/Example

(deftest p40-goldbach
  (is (= [5 23] (goldbach 28))))

(def even-nats-greater-two (gen/such-that #(< 2 %) (gen/fmap #(* 2 %) gen/nat)))


(defspec goldbach-conjecture
  100
  (prop/for-all [i even-nats-greater-two]
                (let [res (goldbach i)]
                  (and
                   (= 2 (count res))
                   (every? prime? res)
                   (= i (reduce + res))))))

Discussion

A naive approach just looks at all prime numbers below the input value. We are then only interested in those primes that if subtracted from that input leave us with another prime number. Both numbers obtained by that method form the result. We already got a list of prime numbers, Clojure's take-while and filter do the rest. I expressed the fact that Goldbach's conjecture is only defined for even natural numbers greater than two with a precondition.

If you have been following this series you might have noticed that the example I give in the blog posts is almost always a unit test. I think this a quite succinct way to illustrate the intended behaviour of a function. But this time you will have noticed that there is something else.

I have added a dependency to clojure.test.check. Test.check is a QuickCheck inspired property-based testing library for Clojure. You can learn more about QuickCheck by having a look at the original paper.

Looking at the code above you will notice that a generative test consists of two parts. First a property (within the defspec). In this case I specified that for all even natural numbers greater than two the Goldbach function should return two prime numbers whose sum is equal to the input value. This property is an almost literal translation of Goldbach's conjecture.

Secondly you need to specify how to generate all possible input values that the test runner should use. Again: Instead of doing this explicitly for every single input value, as you would have to in a traditional exemplary unit test, you just define a generator. I used the built-in generator for natural numbers called nat. But in order to create only valid input values for the Goldbach function the generated values need to be greater than two and even. You can achieve this by using combinators on the original generator. A fmap * 2 shifts the domain of the generator into the even values. I then used the such-that combinator to filter out everything below two.

While writing these generative tests seems like more work at first sight you get back a more thorough verification of your program in return.

Property-based testing recognises the impossibility of coming up with test inputs that expose all edge cases. Instead it encourages you to define properties of your function that you expect to hold. The flip side of the coin is that property based tests won't contribute as much to the design of your APIs and your system as the traditional TDD approach did. But it is a very valuable attempt at automated verification.

Read more about this series.

99 Clojure Problems: 39 – A List Of Prime Numbers

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Example:

(deftest p39-primes-range
  (is (= '(7 11 13 17 19 23 29 31) (primes-range 7 31))))

Solution:

This is a quick one. As we have already defined a lazy seq of prime numbers to solve P35 we can reuse that. To produce the desired range drop from that sequence until we reach the lower bound and then take until we reach the upper bound. Have a look at the solution if this was too terse.

Read more about this series.

99 Clojure Problems – 37/38: Calculate Euler's Totient Function phi(m) (Improved)

See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: $$\varphi(m) = (p_1-1) p_1^{(m_1-1)} (p_2-1) p_2^{(m_2-1)} (p_3-1) p_3^{(m_3-1)} \ldots $$

I combined this with the next problem: P38 (*) Compare the two methods of calculating Euler's totient function. Use the solutions of problems P34 and P37 to compare the algorithms. Try to calculate phi(10090) as an example.

Example

(deftest p37-totient-improved
  (is (= 144 (fast-totient 315))))

The output of comparing the two functions using the criterium benchmarking library looks like this on my machine (running it in a REPL):

Benchmarking the original approach

Evaluation count : 13200 in 60 samples of 220 calls.
             Execution time mean : 4.661557 ms
    Execution time std-deviation : 111.338965 µs
   Execution time lower quantile : 4.577765 ms ( 2.5%)
   Execution time upper quantile : 4.905024 ms (97.5%)
                   Overhead used : 130.196103 ns

Found 5 outliers in 60 samples (8.3333 %)
 low-severe  2 (3.3333 %)
 low-mild  3 (5.0000 %)
 Variance from outliers : 11.0453 % Variance is moderately inflated by outliers

Benchmarking the product based algorithm

Evaluation count : 1510020 in 60 samples of 25167 calls.
             Execution time mean : 39.865790 µs
    Execution time std-deviation : 463.957713 ns
   Execution time lower quantile : 39.517915 µs ( 2.5%)
   Execution time upper quantile : 40.800218 µs (97.5%)
                   Overhead used : 130.196103 ns

Found 4 outliers in 60 samples (6.6667 %)
 low-severe  2 (3.3333 %)
 low-mild  2 (3.3333 %)
 Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Solution

The given formula follows from Euler's product formula. Translating the formula into Clojure is pretty straightforward. We can reuse the result from P36 and reduce the resulting map of prime numbers and their multiplicity by plugging in the product formula directly as the reducer function.

If you look at the code you will find that there is some additional "key/val-noise" due to the fact that we are getting a map back from the function calculating the multiplicities.

Running the benchmarks shows that this solution is about two orders of magnitude faster than the original solution based on the divisor sum and using Clojures ratio datatype.

There is a precondition though: The prime numbers have to be precalculated. If you have to calculate the prime numbers on the fly the product formula approach is only one order of magnitude faster:

Evaluation count : 259980 in 60 samples of 4333 calls.
             Execution time mean : 233.261376 µs
    Execution time std-deviation : 13.268456 µs
   Execution time lower quantile : 218.678716 µs ( 2.5%)
   Execution time upper quantile : 262.518850 µs (97.5%)
                   Overhead used : 131.115424 ns

Found 2 outliers in 60 samples (3.3333 %)
 low-severe  2 (3.3333 %)
 Variance from outliers : 41.8220 % Variance is moderately inflated by outliers

Read more about this series.

99 Clojure Problems – 36: Determine the Prime Factors of a Given Positive Integer (2)

Construct a list containing the prime factors and their multiplicity. Alternately, use a map for the result.

Example

(deftest p36-prime-factors-multiplicity
  (is (= {3 2, 5 1, 7 1} (prime-factors-multiplicity 315) )))

Solution

If you have been following this series this problem might sound familiar. In fact it is just a slight variation on the combination of Problem 35 (prime factors) and Problem 10 (run-length encoding). I followed Phil Gold in using a map as the output format to make the problem a bit more interesting.

While you could reimplement the solution from scratch, I think it is good practice to reuse existing code. In this case all we have to do is call prime-factors on the input, run-length encode, reverse the individual pairs of primes and their multiplicity as required by the problem description. Turning it into a map is then just a matter of flattening the result and applying the assoc function to an empty map and our intermediate result. Try it yourself before you look at the code.

Read more about this series.

99 Clojure Problems – 35: Determine the Prime Factors of a Given Positive Integer

Example

(deftest p35-prime-factors
  (is (= '(3 3 5 7) (prime-factors 315))))

Solution

If you have ever done the "Prime Factors Kata" the solution to this problem is probably already in your muscle memory. One reason why this problem works well as an exercise is that there exists a very simple solution to it. In fact the solution can be expressed in just a few lines of code (in almost any language).

This simplest approach is to do trial division with increasing positive integers. You don't even have to bother checking for primality as things just fall into place: dividing by two for example effectively "eliminates" all multiples of two, in the sense that the next successful division can only happen with a number that is not a multiple of two. You do quite a lot of unnecessary divisions in the process though.

In my Clojure solution I chose to calculate a lazy (memoized) sequence of primes first and then do trial division using primes only. This reduces the number of divisions you have to do, assuming the primes are already calculated.

As long as your number is divisible by one of the small primes and does not have too many digits, trial division might be sufficient. For anything else you have to start looking at things like the general number field sieve.

Read more about this series.

99 Clojure Problems – 34: Calculate Euler's Totient Function phi(m)

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r <= m) that are coprime to m.

Example

(deftest p34-totient
  (is (= 8 (totient-euler 20)))
  (is (= 4 (totient-euler 5))))

Solution

There are multiple ways of calculating the totient function. One pretty straightforward way is to check for every positive integer less than m whether it is coprime to m and count their number.

But when reading up on Wikipedia, Euler's classical formula struck me as a use case for Clojure's ratio data type.

It is defined as the sum over all positive devisors d of n: $$\sum_{d\mid n}\varphi(d)=n $$ One way of deriving that formula is to look at all the fractions between 0 and 1 with denominator n. For n = 10: $$\tfrac{1}{10} \tfrac{2}{10} \tfrac{3}{10} \tfrac{4}{10} \tfrac{5}{10} \tfrac{6}{10} \tfrac{7}{10} \tfrac{8}{10} \tfrac{9}{10} \tfrac{10}{10} $$

That is just mapping / over a range of numbers in Clojure.

Put them to lowest terms: $$\tfrac{1}{10} \tfrac{1}{5} \tfrac{3}{10} \tfrac{2}{5} \tfrac{1}{2} \tfrac{3}{5} \tfrac{7}{10} \tfrac{4}{5} \tfrac{9}{10} \tfrac{1}{1} $$ Clojure reduces it's ratios automatically to lowest terms.

We then look at the ratios that still have n as their denominator (here 10): $$\tfrac{1}{10} \tfrac{3}{10} \tfrac{7}{10} \tfrac{9}{10} $$ They turn out to be the ones whose nominators are coprimes of n and their number is the result of the totient function. In Clojure that is just a filter and a count over the result of the application of map.

This solution is probably not the fastest way of calculating the totient but it is faster than calculating coprimes based on the previous solution.

If I interpret the Criterium benchmark results correctly it is about 1.7x faster

ninety-nine-clojure.arithmetic> (bench (totient-euler 2000))
Evaluation count : 70320 in 60 samples of 1172 calls.
             Execution time mean : 867.964067 µs
    Execution time std-deviation : 14.561162 µs
   Execution time lower quantile : 859.192054 µs ( 2.5%)
   Execution time upper quantile : 901.487425 µs (97.5%)
                   Overhead used : 133.031916 ns

Found 7 outliers in 60 samples (11.6667 %)
 low-severe  7 (11.6667 %)
 Variance from outliers : 6.2554 % Variance is slightly inflated by outliers
nil
ninety-nine-clojure.arithmetic> (bench (totient 2000))
Evaluation count : 41400 in 60 samples of 690 calls.
             Execution time mean : 1.496732 ms
    Execution time std-deviation : 63.212003 µs
   Execution time lower quantile : 1.450532 ms ( 2.5%)
   Execution time upper quantile : 1.636526 ms (97.5%)
                   Overhead used : 133.031916 ns

Found 5 outliers in 60 samples (8.3333 %)
 low-severe  3 (5.0000 %)
 low-mild  2 (3.3333 %)
 Variance from outliers : 28.6860 % Variance is moderately inflated by outliers
nil

Read more about this series.

99 Clojure Problems – 33: Determine Whether Two Positive Integers Are Coprime

Example

(deftest p33-coprime-integers
  (is (coprime? 14 15))
  (is (not (coprime? 14 21))))

Solution

Two positive integers are coprime if the only positive integer that divides them both is 1. That is equivalent to their greatest common divisor being 1.

The solution is trivial building upon the solution to the last problem.

Read more about this series.