Archive for May, 2012

Project Euler in Clojure – Problem 4

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 3 can be found here.

Problem 4 of Project Euler is described as:

Find the largest palindrome made from the product of two 3-digit numbers.

The solution I came up with is:

(ns project-euler.core
  (:require [clojure.string :as string]))

(defn is-palindrome? [s]
 (= (str s) (string/join (reverse (str s)))))

(defn problem4 []
 (apply max (filter is-palindrome? (for [x (range 100 1000) y (range 100 1000)] (* x y)))))

As I want to use the join function in the clojure.string namespace, I added the :require keyword and aliased clojure.string as string using the :as keyword from the namespace macro.

The function is-palindrome? converts the value into a string, reverses the stream of characters in the string and then joins them back together and then compares it with the value as a string.

As defined problem4 does the meat of the work, by using a for loop over the set of of values from 100 to 999 for the binding of x and y, and multiplies x and y for each combination. This set is then filtered against the is-palindrome function, and the filtered sequence is then passed to the max function via apply.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 5 has been posted here.

–Proctor

Advertisements

, ,

5 Comments

Project Euler in Clojure – Problem 3

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 2 can be found here.

Problem 3 of Project Euler is described as:

What is the largest prime factor of the number 600851475143 ?

For this problem, I needed to generate the prime factors of a number. In order to generate the prime factors, I decided to pul out the Uncle Bob’s (found here, here, here, and here) Prime Factors Kata and apply it to Clojure. By doing this kata, I test drove the result, and decided I would give Brian Marick’s Midje a shot and play with that some as well. The resulting tests are as follows.

(ns project-euler.prime-factors-test
  (:use clojure.test
        midje.sweet
        project-euler.core))

(defn mersenne [n]
  (int (dec (Math/pow 2 n))))

(fact
  (prime-factors-of 1) => []
  (prime-factors-of 2) => [2]
  (prime-factors-of 3) => [3]
  (prime-factors-of 4) => [2 2]
  (prime-factors-of 5) => [5]
  (prime-factors-of 6) => [2 3]
  (prime-factors-of 7) => [7]
  (prime-factors-of 8) => [2 2 2]
  (prime-factors-of 9) => [3 3]
  (prime-factors-of 10) => [2 5]
  (prime-factors-of 11) => [11]
  (prime-factors-of 12) => [2 2 3]
  (prime-factors-of 16) => [2 2 2 2]
  (prime-factors-of 25) => [5 5]
  (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37]
  (prime-factors-of (mersenne 17)) => [(mersenne 17)])

The total solution to problem 3 is as follows, with the test driven function for generating the prime factors, is:

(defn factors-starting-at [f n]
  (cond (= n 1) []
        (zero? (rem n f)) (cons f (factors-starting-at f (/ n f)))
        :else (recur (inc f) n)))

(defn prime-factors-of [n]
  (factors-starting-at 2 n))

(defn problem3 []
  (reduce max (prime-factors-of 600851475143)))

The resulting function for prime-factors-of calls the recursive function factors-starting-at with the first factor of 2, and the number itself. The factors-starting-at returns an empty vector when n is one. When the factor is actually a factor of the number (zero? (rem n f)) the returned result is the factor cons’ed onto the result of calling factors-starting-at again with the same factor, and the number divided by that factor. Otherwise, we return the result of recur-ing with the same number and the factor incremented again.

The solution to problem 3 is actually very simple in Clojure after one generates the prime factors for a number. All that one has to do is reduce the sequence of prime factors with the function max to find the largest prime factor for the number 600851475143.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 4 in Clojure.

–Proctor

, ,

6 Comments

Project Euler in Clojure – Problem 2

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 1 can be found here.

Problem 2 of Project Euler is described as:

By considering the terms in the Fibonacci sequence whose values do
not exceed four million, find the sum of the even-valued terms.

The solution I came up with is:

(defn skip-n [n s]
  (cond
    (<= n 0) s
    :else (recur (dec n) (rest s))))

(defn fib
  ([] (concat [0N 1N] (fib 0N 1N)))
  ([a b] (let [c (+ a b)]
          (lazy-seq
            (cons c (fib b c))))))

(defn problem2 []
  (reduce + (filter #(even? %) (take-while #(< % 4000000N) (skip-n 2 (fib))))))

As a didn’t see a skip function, which would keep a sequence, but skip over a given number of inputs, I created the function skip-n. The skip function calls the function rest on the sequence n number of times by using recur, and decrementing n.

The function fib generates the Fibonacci sequence lazily by using the function lazy-seq to create a lazily evaluated sequence, as I want the numbers generated until the time that I decide I do not need them anymore. Instead of trying to determine how many that will be before I generate them, I just decided to make them generated lazily.

The previous two functions were a helper function, and the function to generate the Fibonacci sequence (huh, sequence is even in the name). The work to determine the results of the problem are found in the function problem2. This function uses the skip-n function to skip the first two results, as Project Euler shows the Fibonacci sequence starting as 1, 2, 3, … instead of the starting as 0, 1, 1, 2, 3, … so I skip the first two in the sequence. I then use the take-while function to take only those items which are less than 4 million, which I then feed to the filter function to take only those items from the Fibonacci sequence that are even. The last step is to use the reduce function to sum all of those items together to get the final result.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 3 in Clojure.

–Proctor

, ,

5 Comments

Project Euler in Clojure – Problem 1

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.

Problem 1 of Project Euler is described as:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

The solution I came up with is:

(defn problem1 []
  (reduce + (filter #(or (zero? (rem % 3)) (zero? (rem % 5))) (range 1000))))

I take the range of all numbers from 1 to 999, filter out those numbers evenly divisible by 3 or 5, and then reduce/apply the addition operator to that sequence of numbers.

I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Updated**
Here is my approach to Problem 2 in Clojure.

–Proctor

, ,

2 Comments