99 Clojure Problems (39-41)

Only three problems this update, since we’re coming to the end of the arithmetic section of the problems. The Goldbach Conjecture is fun to say, and fairly easy to solve. Unfortunately, I think I misunderstood the “secondary” problem of P41. I returned all even numbers that can be expressed as the sum of two primes that are over 50. The solution in the scala version of the problems seems to find the first possible pair of primes that equal a prime, and then find which “initial” pair of primes is over 50.

(defn prime? [n prime-cache] 
  (= 0 (count (filter zero? (map (fn [e] (mod n e)) prime-cache)))))

(defn primes-upto [n]
  (loop [possible 3
         primes '()]
	    (< n 2) primes
	    (= n 2) '(2)
	    (>= possible n) (reverse primes)
	    (prime? possible primes) (recur (+ 2 possible) (conj primes possible))
	    :else (recur (+ 2 possible) primes))))

; P39 (*) A list of prime numbers.
(comment "Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.")
(defn prime-list [start end]
  (drop-while (fn [e] (< e start)) (primes-upto end)))

; P40 (**) Goldbach's conjecture.
(comment "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 (much larger than we can go with our Prolog system). Write a predicate to find the two prime numbers that sum up to a given even integer.") 
(defn goldbach [n]
  (let [primes (primes-upto n)]
    (loop [[head & tail] primes] 
    (let [match (first (filter #(= % (- n head)) primes))]
        (nil? head) nil
        (nil? match) (recur tail)
        :else (list head match)

(defn limited-goldbach [n limit]
  (let [primes (primes-upto n)]
    (loop [[head & tail] primes] 
    (let [match (first (filter #(= % (- n head)) primes))]
        (nil? head) nil
        (> head (/ n 2)) nil
        (nil? match) (recur tail)
        (< head limit) (recur tail)
        :else (list head match)

(comment "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.")
(defn print-goldbach-list-limited [a end limit] 
  (loop [start a] 
      (> start end) nil
      (< start limit) (recur (inc start))
      (zero? (rem start 2)) (do
                              (let [gbp (limited-goldbach start limit)]
                                (if (nil? gbp) nil 
                                    (let [[a b] gbp] (println start "=" a "+" b )))) 
                              (recur (inc start)))
      :else (recur (inc start)))))

; P41 (**) A list of Goldbach compositions.
(comment "Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.") 
(defn print-goldbach-list [a end] 
  (print-goldbach-list-limited a end 0))

So yeah, some extra work… oh well! I learned about the “do” function today, which allows me to do something in addition to “recur”.

99 Clojure Problems (35-38)

Once again, a lot of the familiar faces from Project Euler show up to give us a hand. And then, in problem 36, we actually go back and use that list encoding work we did earlier in problem 10. Most of my learning moments this set were in problem 38, where I struggled a little to abstract the timing harness enough. Defining my own operator was cool too, but not as fancy looking as scala, ruby, or python.

; P35 (**) Determine the prime factors of a given positive integer.
(comment "Construct a flat list containing the prime factors in ascending order.")
(defn prime-factors [n]
  (loop [number n
         curr 2
         output '()]
      (= 1 number) (reverse output)
      (evenly-divisible number curr) (recur (/ number curr) curr (conj output curr))
      :else (recur number (inc curr) output))))

; P36 (**) Determine the prime factors of a given positive integer (2).
(comment "Construct a list containing the prime factors and their multiplicity.") 
(defn prime-factors-mult [n] (encode (prime-factors n)))

; stolen from http://rosettacode.org/wiki/Exponentiation_operator#Clojure
(defn ** [x n] (if (zero? n) 1 (reduce * (repeat n x))))

; P37 (**) Calculate Euler's totient function phi(m) (improved).
(comment "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:") 
(defn totient2 [n] 
  (let [pfs (prime-factors-mult n)]
    (reduce * (map (fn [[m p]] (* (dec p) (** p (dec m)))) pfs))))

; P38 (*) Compare the two methods of calculating Euler's totient function.
(comment "Use the solutions of problems P34 and P37 to compare the algorithms. Try to calculate phi(10090) as an example.")
(defn timer [which function n]
  (let [start (System/currentTimeMillis)
        answer (function n)
        end (- (System/currentTimeMillis) start)]
  (println which "{" answer "} takes" end "ms")))

(defn benchmark [n] 
  (doseq [i (range 1 11)]
	  (println "Run" i)
	  (timer "p34" totient n)
	  (timer "p37" totient2 n)
	  (println "------\n")))

(benchmark 10090)

99 Clojure Problems (31-34)

I wanted to complete problems 27 and 28, but it just wasn’t working out. I’ll come back to them later, but for now, here’s numbers 31 through 34.

Since I’m working through Project Euler as a sort of algorithmic kata to stretch my legs in new languages, these prime based problems were a snap.

; A utility method that helps keep things readable.
(defn evenly-divisible [n d] (zero? (mod n d)))

; P31 (**) Determine whether a given integer number is prime.
(defn prime? [n] 
    (if (> (* c c) n) 
      (if (evenly-divisible n c)
        (recur (inc c))))))

; P32 (**) Determine the greatest common divisor of two positive integer numbers.
(comment "Use Euclid's algorithm.")
; my first attempt...
(defn gcd_a [n k] 
  (loop [a (if (< n k) n k)
         b (if (< n k) k n)
         c 2
         o 1] 
      (< a c) o
      (and (evenly-divisible a c) (evenly-divisible b c)) (recur (/ a c) (/ b c) c (* o c))
      :else (recur a b (inc c) o))))

(comment "using euclid's algorithm, which I thought I knew, but I was apparently misremembering")
(defn gcd [m n] 
  (if (zero? n) 
    (recur n (mod m n))))

; P33 (*) Determine whether two positive integer numbers are coprime.
(comment "Two numbers are coprime if their greatest common divisor equals 1.")
(defn coprime? [n k] (= 1 (gcd n k)))

; P34 (**) Calculate Euler's totient function phi(m).
(comment "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.") 
(defn totient [n] 
      (fn [e] (coprime? e n)) 
      (range 1 n))))

Not only was Project Euler helpful, the fact that these solutions so nicely build upon each other helped speed these through. I think I made the right choice skipping 27-28. The forward momentum has rekindled my interest in learning more about clojure.

Ruby Koans

Ben sent me a link to Ruby Koans today. These “Koans” are a kind of learn-by-doing approach to learning ruby.

Each problem is set up as part of a test-driven framework that requires you to make the tests pass by filling in the answers.

An example:

def test_combining_hashes
  hash = { "jim" => 53, "amy" => 20, "dan" => 23 }
  new_hash = hash.merge({ "jim" => 54, "jenny" => 26 })

  assert_not_equal hash, new_hash
  expected = { "jim" => __, "amy" => 20, "dan" => 23, "jenny" => __ }
  assert_equal expected, new_hash

This was a great way to spend a couple of hours and learn some of the deeper secrets of the ruby language.

Oh, and if you have a problem running the problems in 1.9.1, specifically the following:

(in C:/ruby_koans)
cd koans
C:/Ruby19/bin/ruby.exe path_to_enlightenment.rb
C:/ruby_koans/koans/edgecase.rb:33:in `<class:Sensei>': uninitialized constant T
est::Unit::AssertionFailedError (NameError)
        from C:/ruby_koans/koans/edgecase.rb:30:in `<module:EdgeCase>'
        from C:/ruby_koans/koans/edgecase.rb:29:in `<top (required)>'
        from C:/ruby_koans/koans/about_asserts.rb:4:in `require'
        from C:/ruby_koans/koans/about_asserts.rb:4:in `<top (required)>'
        from path_to_enlightenment.rb:3:in `require'
        from path_to_enlightenment.rb:3:in `<main>'
rake aborted!
Command failed with status (1): [C:/Ruby19/bin/ruby.exe path_to_enlightenme...]

(See full trace by running task with --trace)

You need to run:

gem install test-unit

The test-unit gem is no longer included in the Ruby installer.

Euler Problem 17 in Ruby

After hearing about Ben’s motivation trouble with problem 17, I realized that I only had fun on that problem because I saw a rather fun algorithm. Since I’m rather proud of it, I’m going to show off the code here.

ones = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"]
tens = ["", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"]
hundred = "hundred"
and_ = "and"
thousand = "thousand"

sum = ""
1.upto(1000) do |i|
  curr = i
  out = ""
  if (curr > 999) then
    out += ones[curr/1000] + thousand
    curr = curr%1000
  if (curr > 99) then
    out += ones[curr/100] + hundred
    curr = curr%100
    out += and_ if curr != 0
  if (curr >= 20) then
    out += tens[curr/10]
    curr = curr%10
    out += ones[curr]
    out += ones[curr]
  sum += out
puts sum.length

# Over 50 trials:
# Mean:	17.3689 ms
# Median: 16.5885 ms

I’m particularly proud of this code because I don’t have to convert the numbers into an array, and it’s blazing fast, even in ruby.

99 Clojure Problems (23-26)

This is the first set that I’m not a 100% proud of. After being stuck on P26 for days, I just stole the code from clojure.contrib.combinatorics. At least I learned a few things! (defn-) creates a generator! Now I can create infinite sequences! Also, there is a better example of the #(%) syntax. The (cond …) syntax also looks useful, as now I can replicate JSP’s choose/when/otherwise.

; P23 (**) Extract a given number of randomly selected elements from a list.
(defn rnd_select [n input] 
  (if (> n 0) 
    (loop  (remove_at (rand-int (count input)) input)] 
      (if (> c 0) 
        (recur (dec c) (cons x output) (remove_at (rand-int (count r)) r)) 
        output)) nil)

; P24 (*) Lotto: Draw N different random numbers from the set 1..M.
; The selected numbers shall be put into a result list.
(defn lotto [n m] (rnd_select n (s99_range 1 m)))

; P25 (*) Generate a random permutation of the elements of a list.
(defn randomPermute [input] 
  (loop  (remove_at (rand-int (count input)) input)]
      (if (> c 1) 
        (recur (dec c) (cons x output) (remove_at (rand-int (count r)) r)) 
        (cons x output))))

; P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.
(comment "In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.")
(defn- index-combinations
  [n cnt]
   (let  (+ j cnt (- (inc n)))))),
   (fn iter-comb 
     (if (> j n) nil
     (if (< (c j) j) 
           (if (= j 1) 
         (recur (assoc c (dec j) (dec (c j))) (dec j)))))))),
   (fn step 
     (cons (rseq (subvec c 1 (inc n)))
     (lazy-seq (let [next-step (iter-comb c j)]
           (when next-step (step (next-step 0) (next-step 1)))))))]
     (step c 1))))

(defn combinations
  "All the unique ways of taking n different elements from items"
  [n items]      
  (let [v-items (vec (reverse items))]
    (if (zero? n) (list ())
      (let [cnt (count items)]
         (> n cnt) nil
         (= n cnt) (list (seq items))
         :else (map #(map v-items %) (index-combinations n cnt)))))))

99 Clojure Problems (19-22)

First off, thanks to all the commenters that have been contributing advice and corrections! It’s definitely helping, and I think I’m making some good progress on my quest.

Here’s another set of simple problems:

; P19 (**) Rotate a list N places to the left.
(defn rotate [n input]
  (let [amount (if (< n 0) (+ n (count input)) n)]
    (concat (drop amount input) (slice 0 amount input))))

; P20 (*) Remove the K'th element from a list.
(defn remove_at [k input]
      (slice 0 k input)
      (slice (inc k) (count input) input))
    (nth input k)))

; P21 (*) Insert an element at a given position into a list.
(defn insert_at [k value input]
    (slice 0  k input)
    (list value)
    (slice k (count input) input)))

; P22 (*) Create a list containing all integers within a given range.
(comment "clojure already has a (range a b), but it is [a,b), not [a,b]")
(defn s99_range [s e]
  (loop [output (list s)
         curr (inc s)]
    (if (> curr e)
      (reverse output)
      (recur (cons curr output) (inc curr)))))

Taking some comments to heart, I came up with an alternate P22. I’m not sure, though whether it’s better or worse than my original. I’m pretty sure that there’s a pretty big difference between the two, but I don’t know enough to say what’s what.

; P22 (*) Create a list containing all integers within a given range.
; clojure already has a (range a b), but it is [a,b), not [a,b]
(defn s99_range_v [s e] 
  (loop [output [s] 
         curr (inc s)] 
    (if (> curr e) 
      (recur (conj output curr) (inc curr)))))

The next block may take a while. I’m encountering some real difficulty with P26, but I don’t think I’m ready to start “cheating” and looking for other people’s solutions yet.

99 Clojure Problems (15-18)

Not much to say about this batch. I burned through these too fast to learn a lot. I guess I did learn about clojure’s drop function, but most of the rest of these are just tweaks of earlier problems.

; P15 (**) Duplicate the elements of a list a given number of times.
(defn duplicateN [n l] 
  (mapcat (fn [a] 
            (loop [output '()] 
                (= (count output) n) 
                (recur (cons a output))))) l))

; P16 (**) Drop every Nth element from a list.
(comment "clojure's (drop n list) throws away the first n items in a list and returns the list")
(defn s99_drop [n l] 
  (loop [[head & tail] l
         c 1 
         output '()] 
    (if (nil? head) 
      (reverse output) 
        (= c n) 
        (recur tail 1 output) 
        (recur tail (inc c) (cons head output))))))

; P17 (*) Split a list into two parts; the length of the first part is given.
(defn split [n l] 
  (loop  l
         output '()]
      (if (< c (dec n))
        (recur (inc c) tail (cons head output))
        (list (reverse (cons head output)) tail))))

; P18 (**) Extract a slice from a list.
(comment "Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.")
(defn slice [i k l] 
  (loop [remaining (drop i l)
         current i
         output '()] 
    (if (= current k) 
      (reverse output) 
      (recur (rest remaining) (inc current) (cons (first remaining) output)))))

Code Club: Ruby Week 1

So my coworker Ben and I keep trying to keep people interested in learning and tinkering with languages.  So far we’ve explored python, scala, and f#.  Scala and F# seemed to have scared off most of our attendees, so we’re trying to reign it back into the mainstream by exploring Ruby.  For this first week, attendees are to do whatever Euler problems they are comfortable doing, as long as they do them in Euler.

Since I’ve done the first 20 or so Euler problems in all of the above languages, I was able to power through the first ten problems in Ruby pretty quickly.  I also used the opportunity to mess around with mercurial.  I originally wanted to use git and github, but the windows version of git is fairly opaque to me.  I set up an online repository for my Ruby exploration on intuxication. You can peer through the repository here: http://mercurial.intuxication.org/hg/rubyeuler/

I can’t wait until Wednesday to share how clever I feel, so I’m going to share a couple snippets that I feel especially pleased about.

maxprod = 0
999.downto(100) {|i| 
  999.downto(100) {|j|
    maxprod = [i * j, maxprod].max if ((i * j).to_s == (i * j).to_s.reverse)
puts maxprod

The whole creating an array of two items to grab the maximum is cool, but the if statement negating the previous expression makes things simultaneously easier to read and confusing to my traditional Java brain.

class Array
  def prod
    inject do |prod,x| prod ? prod * x : x end

n = 2
arr = []

while (n <= 20)
  currn = n
  arr.each {|i| currn /= i if currn % i == 0}
  arr << currn

puts arr.prod

The real “wow” moment I had here was the fact that you could extend existing classes without actually creating a whole new class. “Redefining” a class just adds/overwrites the things that you put in your newly written class definition. Totally blew my mind.

99 Clojure Problems (11 – 14)

So thanks to two great comments (Jake McCrary on let/loop and Zac on the & symbol), I’ve been refactoring my solutions a little. I’m only going to update my previous posts with my first revelation on the loop, as I figure the bad example of what I was doing before probably outweighs being able to see how I’m learning clojure.

So anyway, once I grokked the (loop [] expr) syntax, things became worlds easier. I don’t know if it’s because I’m getting used to clojure, or just the idea of functional programming.

; P11 (*) Modified run-length encoding.
(comment "Modify the result of problem P10 in such a way that if an element has no  duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms.")
(defn encodeModified [l]
    (fn [a] (if (= (first a) 1) (last a) a))
    (encode l)))

; P12 (**) Decode a run-length encoded list.
(comment "Given a run-length code list generated as specified in problem P10, construct its uncompressed version.")
(defn decode [l]
  (mapcat (fn [a]
            (let [n (first a)
                  value (last a)]
              (loop [curr 0
                     output '()]
                  (= curr n)
                  (recur (inc curr) (cons value output)))))) l))

; P13 (**) Run-length encoding of a list (direct solution).
(comment "Implement the so-called run-length encoding data compression method directly."
(comment "I.e. don't use other methods you've written (like P09's pack);  do all the work directly.")
(defn encodeDirect [l]
  (loop [output '()
         [head & tail] l
         last-seen nil
         n 0]
     (if (nil? head)
      (reverse output)
      (if (= last-seen head)
        (recur output tail last-seen (inc n))
        (recur (if (nil? last-seen) output (cons (list n last-seen) output)) tail head 1)))))

; P14 (*) Duplicate the elements of a list.
(defn duplicate [l]  (mapcat (fn [a] (list a a)) l))

Now that I think things are relatively under control, I’m steaming along nicely into what I think is the end of my “beginner” stage in clojure.