Problem 1: Fizzbuzz

13 10 2009

Find the sum of all numbers less than 1000 which are divisible by 3 or 5

This sum reminds  me of “fizzbuzz”, the “Hello World!” of loops in a language. Before I give the Clojure solution, i’ll explain how to loop in Lisp.

Looping in Lisp is a little different from most other languages you might be familiar with like C or Python. A looping construct (like “for” or “while”) is not required to execute a loop. A simple example is the implementation of the factorial function. The factorial function is defined recursively as

factorial(0) = 1
factorial(n) = n * factorial(n-1)

Implementing the factorial function in Clojure

(defn factorial [n]
    (cond
	(zero? n) 1
	:else (* n (factorial (dec n)))))

“cond” takes an even number of arguments which alternate between clauses and values. In this case the clauses are zero? and :else.

Predicates (functions which return either True of False) are usually terminated by a “?”. This is not a rule but a naming convention.

If a clause, taken from left to right, evaluates to True; the corresponding value (immediately to the right) is returned. In this case if (zero? n) 1 is returned.

What’s interesting is if (zero? n) is false, the product of n and (factorial (dec n)) is returned. This concept is known as recursion. [dec, decrements its argument by 1]

Tracing the factorial function for a small value 5 we get

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
=>120

Notice the Triangular structure, this is recursive growth. The number of lines can be taken as the time and the horizontal growth is the space required. Both time and space in this case are linear functions of n so we can say that the “Time Complexity” is of O(n) (read as Order n) and the “Space Complexity” is also of O(n).

Another solution, very similar to the first

(defn factorial [n acc]
    (cond
	(zero? n) acc
	:else (factorial (dec n) (* n acc))))

This factorial takes 2 arguments n and acc. Lets see the trace of this version.

(factorial 5 1)
(factorial 4 5)
(factorial 3 20)
(factorial 2 60)
(factorial 1 120)
(factorial 0 120)
=>120

See the difference? There is no horizontal growth. While this function is still of O(n) time complexity, the space complexity is a constant O(1). This is far more efficient than the previous solution. The variable “acc” is required to store and carry forward the product so far in each step.

This feature is automatic in some implementations of Lisp. Since Clojure runs on the Java Virtual machine however the second function is as inefficient as the first. This is because every nested function call in Clojure/Java is pushed on the stack.

There is a special construct in Clojure which comes to the rescue and that is “recur”

(defn factorial [n acc]
    (cond
	(zero? n) acc
	:else (recur (dec n) (* n acc))))

Replacing the call to factorial with recur we get the same effect as we would have in Lisp. One condition is that recur has to be at the “Tail” position, that means there should be no need to return from it.

This is not valid

(defn factorial [n]
    (cond
        (zero? n) 1
        :else (* n (recur (dec n)))))

So lets implement an iterative solution to the 1st euler problem

(defn divides? [p q]
    (zero? (mod p q)))

(defn euler-1 [n acc]
    (cond
	(zero? n) acc
	(or (divides? n 3) (divides? n 5)) (recur (dec n) (+ n acc))
	:else (recur (dec n) acc)))

(euler-1 999 0)

The mod function takes 2 arguments, p and q, and returns the remainder of p/q. “or” takes an arbitrary number of arguments and returns True if any one of them is True.

This is a good iterative solution but is it really necessary  to supply the acc variable each time? This leaves room for errors. We could solve this by defining a nested function (a function defined in a function)

(defn defn ">euler-1 [n]
    (defn iter [i acc]
	(cond
	        (zero? i) acc
		(or (divides? i 3) (divides? i 5)) (recur (dec i) (+ i acc))
		:else (recur (dec i) acc)))
    (iter n 0))

(euler-1 999)

This hides the implementation detail from the user of your function and is less error prone. There is an alternative to defining a nested function, especially in cases where you only require it once. Clojure provides a loop construct which can be used instead.

(defn euler-1 [n]
    (loop [i n acc 0]
	(cond
		(zero? i) acc
		(or (divides? i 3) (divides? i 5)) (recur (dec i) (+ i acc))
		:else (recur (dec i) acc))))

(euler-1 999)

The loop construct takes as arguments an even number of terms, just like cond. The 2nd expression is assigned to the 1st term, the 4th to the  3rd and so on. In this case n gets assigned to i and 0 to acc.

The loop construct also uses recur to return to the beginning of the loop. Sometimes it seems right to use loop and at other times a function, there is no real difference so chalk it up to better readability r personal taste.

Now onto some different solutions, these can be hard to understand initially but this is a style encouraged by Clojure.

(reduce + (filter #(or (divides? % 3) (divides? % 5)) (range 1000)))

“range” defines a sequence of numbers starting from 0 up to n-1.

(range 5)
=>(0 1 2 3 4)

“filter” applies a filter function on a sequence removing the terms which do not satisfy the filter.

(filter even? (range 10))
=>(0 2 4 6 8 )

#() creates and anonymous function (a function with no name) % stands for the first argument and can also be written as %1. Successive arguments are %2, %3…

(#(+ %1 %2) 2 3)
=>5

“reduce” is a powerful construct which combines the elements in a sequence with the provided function. It takes the terms 2 at a time, that is the first 2 are combined to produce a new term which is then combined with the 3rd term.

(reduce + (range 5))
=>10

A solution in a single line, pretty incredible.

Here’s another interesting solution

(+ (reduce + (range 0 1000 3))
   (reduce + (range 0 1000 5))
   (reduce - (range 0 1000 15)))

The range function can take a maximum of 3 arguments (range [start] [end] [step])

(range 0 10 2)
=>(0 2 4 6 8 )

This solution sums up the numbers divisible by 3 or 5 and subtracts the intersection.

Whew, that covered a lot of matter, and lots more to come. Comments are welcome, would be interested to know if anyone is following a similar approach to learning Clojure/Lisp.

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: