Problem 6: Sums of Squares of Sums

14 10 2009

Difference between sum of squares and square of sums

Find the difference between the sum of squares and the square of the sum of the integers 1 to 100

Using the functions map and reduce, this becomes trivial to implement

(defn sqr [x]
    (* x x))

(let [terms (range 1 101)]
    (- (reduce + (map sqr terms)) (sqr (reduce + terms))))

map takes a function and 1 or more lists and generates a new list of terms which are a result of the application of the function on each of the terms in the list/lists

(map + '(1 2 3) '(1 2 3))
=> (2 4 6)
Advertisements




Problem 5: Lowest Common Multiple

14 10 2009

Find the smallest number divisible by each of the numbers 1 to 20

The requirement is to find the Lowest Common Multiple (LCM)of the numbers 1 to 20

We can very easily find the LCM using the  Greatest Common Divisor (GCD) using the formula

lcm(x, y) = (x * y) / gcd(x, y)

A very fast method to calculate GCD is using Euclid’s algorithm

gcd(x, y) = gcd(y, x mod y)

Implementing this in Clojure

(defn gcd [x y]
    (cond
	(zero? x) y
	(zero? y) x
	:else (recur y (mod x y))))

(defn lcm [x y]
    (/ (* x y) (gcd x y)))

(reduce lcm (range 1 21))

gcd calculates the greatest common divisor of 2 integers

(gcd 6 8 )
=> 2

lcm calculates the lowest common multiple of 2 integers

(lcm 6 8 )
=> 24




Problem 4: Numeric Palindromes

14 10 2009

Find the largest palindrome which is the product of 2, 3 digit numbers

The challenge is to find a numeric palindrome which is the product of 2 numbers, both from 100 to 999.

(defn reverse-int [n]
    (loop [m n acc 0]
	(cond
       	    (zero? ) acc
	    :else (recur (quot m 10) (+ (* acc 10) (mod m 1))))))

(defn palindrome? [n]
    (= n (reverse-int n)))

(defn euler-4 [lower-limit upper-limit]
    (loop [p upper-limit q upper-limit largest 0]
	(let [candidate (* p q)]
    	    (cond
		(< p lower-limit) largest
		(< candidate largest) largest
		(< lower-limit q) (recur (dec p) (dec p) largest)
                (palindrome? candidate)
  	  	    (if (> candidate largest)
			(recur p (dec q) candidate))
		:else (recur p (dec q) largest)))))

(euler-4 100 999)

let like loop, forms a dynamic binding between the odd and even terms in the argument list for the expression in the body of the let.

(let [a 3 b 4]
    (+ a b))
=> 4

if takes 2 – 3 expressions as arguments, if the first one evaluates to be True, then the second (then) is evaluated, else the third (else) is evaluated. In this case there is no else clause, the control breaks out of the if statement

(if (< 2 3)
    4
    5)
=> 4

reverse-int takes an integer as argument and reverses it

(reverse-int 234)
=>432

palindrome? is a predicate which checks if an integer is a palindrome

(palindrome? 121)
=> True

There are 2 optimizations in this solution

1> Any 2 numbers are multiplied only once
2> If the largest palindrome found so far is larger than the current (* p q), return it





Problem 3: Prime Factor

13 10 2009

Find the largest prime factor of a composite number

The brute force method would be to find all the prime factors and choose the largest, a better algorithm is this one.

(defn divides? [n x]
    (zero? (mod n x)))

(defn largest-prime-divisor [n]
    (loop [x 2 m n]
	(cond
	    (= x m) x
	    (divides? m x) (recur x (/ m x))
	    :else (recur (inc x) m))))

Clojure’s syntax takes a while getting used to but now I find it quite easy to express an algorithm in it. Lets trace what happens with a small value

(largest-prime-divisor 100)
(loop 2 100)
(loop 2 50)
(loop 2 25)
(loop 3 25)
(loop 4 25)
(loop 5 25)
(loop 5 5)
=> 5




Problem 2: Fibonacci

13 10 2009

Find the sum of all even fibonacci numbers not greater than 4000000

The fibonacci series has a simple recursive definition, just like factorial

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

As before, the Clojure solution is a simple application

(defn euler-2 [n]
    (loop [a 0 b 1 acc 0]
	(cond
		(< n b) acc
		(even? b) (recur b (+ a b) (+ acc b))
		:else (recur b (+ a b) acc))))

(euler-2 4000000)

This works, but this is not a very reusable solution. Having to rewrite the same function each time for a specific case is not something you should be doing.

Storing a list of fibonacci terms is a great way to encapsulate them. Assume we already have this list, then the same problem can be very simply solved.

(reduce + (take-while #(< % 4000000) fibonacci-list))

take-while is a variation of the take function, take takes the first n terms in a list.

(take 3 (range 100))
=>(0 1 2)

take-while takes a predicate function and a list and returns a list of successive terms satisfying the function

(take-while #(< % 5) (range 100))
=>(0 1 2 3 4)

See how much simpler that is to understand and read. The problem is that the fibonacci series in an infinite series. You could  create a really large list but its impossible to know just how big is big enough. Fortunately Clojure has built in support for lazy-sequences.

Lazy-sequences are infinite lists which only generate terms when required. Clojure has a set of functions which can be used to create lazy-sequences, functions like repeat, cycle and iterate all generate lazy sequences.

warning: Do not evaluate an infinite sequence at the REPL as this will result in an infinite loop.

repeat is used to create finite or infinite sequences of the same term

(repeat 5 "F")
=>("F" "F" "F" "F" "F")

(repeat "F")
=>("F" "F" "F" ...)

cycle takes a list as argument an returns an infinite sequence of the list repeated.

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

iterate takes a function and value and returns a lazy sequence of x, (f x) (f  (f x)) …

(iterate inc 0)
=>(0 1 2 3 4 5 ...)

where inc is the increment function

Now onto something a little more basic. In Clojure lists are evaluated, that is, the first term is taken as a function and is applied to the remaining terms in the list.

There are times when you just want a list of terms without evaluation. This is what the quote function is for.

(+ 1 2 3)
=>6

(quote (+ 1 2 3))
=>(+ 1 2 3)

quote can also be written as the symbol ‘ before the start of the list.

'(1 2 3)
=>(1 2 3)

The concat function concatenates  its arguments which are lists

(concat '(1 2 3) '(4 5 6))
=>(1 2 3 4 5 6)

lazy-cat can be used to concatenate infinite lists

(lazy-cat '(0 1) (iterate inc 2))
=>(0 1 2 3 4 ...)

One more feature of Clojure to go before we implement the lazy fibonacci sequence

In Clojure, a function can take a variable number of arguments and also dispatch differently on the number of arguments called, this is known as polymorphism

(defn add
    ([a]
	a)
    ([a b]
	(+ a b)))

(add 1)
=>1

(add 1 2)
=>3

add if called with 1 argument returns the argument itself and if called with 2 returns the sum of the 2 terms.

Now onto the infinite fibonacci

(defn create-fibonacci-list
    ([]
	(create-fibonacci-list 0 1))
    ([a b]
	(lazy-cat (list a b) (create-fibonacci-list b (+ a b)))))
(def fibonacci-list
    (create-fibonacci-list))

The list function takes an arbitrary number of terms and creates a list out of them

(list 1 2 3 4)
=>(1 2 3 4)
(take 10 fibonacci-list)
=>(0 1 1 2 3 5 8 13 21 34)




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.





An introduction to Clojure

11 10 2009

I’ve started solving Project Euler problems to learn Clojure, a new language on the Java Virtual Machine

Before going into the problem solutions, i’ll give a brief introduction to Clojure

Clojure (pronounced like closure) is a dialect of the Lisp programming language. It is a general-purpose language supporting interactive development. (from Wikipedia)

The Lisp programming is one of the oldest programming languages still in use today, in fact it’s the second oldest, beaten only by Fortran.

One of the defining properties of Lisp is that its homoiconic, that is, the code of Lisp is written in lists.

Clojure is also a Lisp and has similar syntax. One of the properties of Clojure and other lisps is the interactive nature. Instead of a Code -> Compile -> Run cycle, there is a Code -> Evaluate cycle. Pieces of the code can be dynamically added to the running program image.

When you start Clojure, you will be handed a prompt which looks like this

>

Similar to a prompt, this is a REPL (Read Eval Print Loop) . You can type Clojure code here and immideately define functions and evaluate expressions.

Lets evaluate some basic expressions

> 5
5

> "Hello"
"Hello"

Whenever you type anything into the REPL it is code, what gets displayed is Clojure’s representation of that code as data. So in the case of typing 5, Clojure evaluates it as 5.

Similarly with “Hello” which is a String, Clojure create a String with a value “Hello”. Clojure can do floating point arithmetic just as easily so typing 5.5 wil give you 5.5.

Now onto an expression.

> (+ 2 3)
5

Clojure and other Lisps use the prefix notation, that is the operator first followed by the remaining operands. This could get some getting used to but stick to it and you’ll be prefixing in no time. This is a simple expression, the function ‘+’ followed by 2 and 3. This evaluates to 5.

One of the advantages of prefix notation is the ability to have arbitrary lists of operands so (+ 2 3 4) is just as easily understandable.

> (def a 5)
#'user/a

> a
5

> (* 2 a)
10

def associates a symbol with a value, as shown above a is defined with a value of 5. Now for all purposes a is 5. You can even asign an expression to a like (+ 2 3), this will be evaluated and the value assigned to a.

Don’t worry about the #’user/a, this just means that the symbol a has now been defined. the ‘user’ refers to the current namespace. You can have multiple namespaces with the same symbol associated with different values.

> (defn add [x y]
	(+ x y))
#'user/add

> (add 10 12)
22

defn defines a function the square brackets [] are the argument list to the function, in this case the function add takes 2 arguments x and y. The sum of the 2 arguments is returned as the result.

This should give you a basic idea about Clojure and enough to be able to understand the project euler solutions in the next couple of posts.