Problem 8: 1000 digit number

18 10 2009

Find the largest product of 5 consecutive digits of a 1000 digit number

This can be solved very elegantly in Clojure, the 1000 digit number can be found here.

(def number-string "73167...")

(def digits (map #(- (int %) 48) number-string))

(apply max (map * digits (drop 1 digits) (drop 2 digits) (drop 3 digits) (drop 4 digits)))

number-string stores the 1000 digit number as a string

digits creates a list of digits from number-string, 48 is the ASCII value for the character ‘0’, 49 for ‘1’ and so on. Subtracting 48 from the character gives the digit value.

map runs only till one of the list arguments terminates so the last line is valid


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)

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]
	(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]
       	    (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)]
		(< 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

reverse-int takes an integer as argument and reverses it

(reverse-int 234)

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]
	    (= 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]
		(< 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)

(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 b]
	(+ a b)))

(add 1)

(add 1 2)

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

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]
	(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)

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]
	(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)

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]
	(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]
        (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]
	(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]
	        (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]
		(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)

“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))

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.