Month: June 2010

Posted on

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]
  (list
    (concat
      (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]
  (concat
    (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) 
      output 
      (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.

Posted on

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 '()] 
              (if 
                (= (count output) n) 
                output 
                (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) 
      (if 
        (= 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 [c 0
         [head & tail] 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)))))
Posted on

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
  end
end

n = 2
arr = []

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

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.

Posted on

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]
  (map
    (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 '()]
                (if
                  (= curr n)
                  output
                  (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.

Posted on

99 Clojure Problems (7-10)

This is where things got both fun and difficult. These problems aren’t too difficult in F# and scala, but flatten especially confused me. Luckily, I found an example of LISP that used the mapcat function, and it basically wrote the flatten function for me. Map maps a function to a list, but mapcat assumes that the function applied to the list turns each element into a list, and then concatenates all of the items into a new list. It was confusing to say the least, but I am starting to see the power of it peeking around the corner.

; P07 (**) Flatten a nested list structure.
(defn flatten [l]
  (if (list? l)
    (mapcat flatten l)
    (list l)))

; P08 (**) Eliminate consecutive duplicates of list elements.
(comment "If a list contains repeated elements they should be 
replaced with a single copy of the element. 
The order of the elements should not be changed.")
(defn compress [l]
  (loop [current '()
         remaining l]
    (if (nil? (first remaining))
      (reverse current)
      (recur 
        (if (= (first current) (first remaining)) current (cons (first remaining) current)) 
        (rest remaining)))))

; P09 (**) Pack consecutive duplicates of list elements into sublists.
; If a list contains repeated elements they should be placed in separate sublists.
(defn pack [l] 
  (loop [output '()
         remaining l
         last-seen-list nil]
    (let [head (first remaining)
          tail (rest remaining)
          last-seen (first last-seen-list)]
    (if 
      (nil? head) 
      (reverse (cons last-seen-list output))
      (if (= last-seen head) 
        (recur output tail (cons head last-seen-list)) 
        (recur (if (nil? last-seen-list) output (cons last-seen-list output)) tail (list head)))))))

; P10 (*) Run-length encoding of a list.
; Use the result of problem P09 to implement the so-called run-length encoding 
; data compression method. Consecutive duplicates of elements are encoded as 
; tuples (N, E) where N is the number of duplicates of the element E.
(defn encode [l] 
  (map 
    (fn [a] (list (count a) (first a))) 
    (pack l)))

Unlike my first pass in scala, I’m actually doing these as they’re intended. I’m using the results of P09 to implement P10. In my scala run, I wrote each one from scratch.

Posted on

99 Clojure Problems (5-6)

Clojure’s been strange so far. After tinkering in F# for the last couple months, it seems like functional programming should be easier by now.

Reverse and palindrome were easy enough, though.

; P05 (*) Reverse a list.
; clojure already has a (reverse l)
(defn s99_reverse [l]
  (loop [remain l
         curr '()] 
    (let [head (first remain)
         tail (rest remain)]
      (if (nil? head) curr (recur tail (cons head curr)))))

; P06 (*) Find out whether a list is a palindrome.
(defn isPalindrome [l] (= l (reverse l)))

I’m slowly getting my brain around the lisp like syntax, but it appears that some of the idioms are different. I’ll discuss this more when I get to the next set.

Posted on

99 Clojure Problems (1-4)

I’ve been learning new languages lately, and I’ve been using the 99 scala problems to help me learn important features of the languages.

I’m going to blog about my experiences with clojure.

Once I got through the hoops of starting with clojure (just download the eclipse plugin and go!), it was smooth sailing for the first four problems.

(ns s99)
;; P01 (*) Find the last element of a list.
; Basically, this replicates the (last n) functionality already in clojure
(defn s99_last [input]
  (loop [i input]
    (let [a (first i)
          b (first (rest i))]
      (if (= b nil) a (recur (rest i))))))

; P02 (*) Find the last but one element of a list.
(defn penultimate [input] 
  (loop [i input]
	  (let [a (first i) 
	        b (first (rest i))
	        c (first (rest (rest i)))] 
	    (if (nil? c) a (recur (rest i))))))

; P03 (*) Find the Kth element of a list.
; By convention, the first element in the list is element 0.
; in clojure, nth already exists (nth n l)
(defn s99_nth [n input]
  (loop [c 0
         i input]
    (if (= c n) (first i) (recur (inc c) (rest i)))))

; P04 (*) Find the number of elements of a list.
; This is the same functionality as clojure's (count l) function
(defn length [input]
  (loop [c 0 
         i input]
    (if (nil? (first i)) c (recur (inc c) (rest i)))))

So far, the lack of pattern matching makes things a little more difficult than scala or f#, but once I got a hang of the sea of parenthesis, it was easy to remember my college work with xquery.

jon.com.org.net is using WP-Gravatar