Wednesday 14 November 2012

Just the Squares Continued

Yes, putting that function together in a different way:-

(def just-squares
  (fn [s]
    (let [split-string (fn [s] (clojure.string/split s #",")),
      join-strings (fn [ss] (clojure.string/join "," ss)),
      square? (fn [n] (let [root (int (. Math sqrt n))] (= (* root root) n))),
      filter-squares (fn [ns] (filter square? ns)),
      strs->ints (fn [ss] (map #(. Integer parseInt %) ss)),
      ints->strs (fn [ns] (map str ns))]
      (-> s split-string strs->ints filter-squares ints->strs join-strings))))


Tuesday 13 November 2012

Just the Squares

Today's exercise is to take a string that contains numbers separated by commas, like this:

"3,4,5,6,7,8,9"

and return the same except containing only the numbers that are perfect squares, which in this case would be

"4,9"

So the first step is to break up that string into the individual numbers.  In the Clojure String library we get the split function, which takes your string and a regular expression that determines what part of the string is to be used to split.  We're using just about the simplest possible option, just chopping through the commas.  A function to do this would look so:

(defn split-string [s]
  (clojure.string/split s #","))


This gives us a sequence of the separated strings:-

user=> (split-string "4,5,45,6,7,67")
["4" "5" "45" "6" "7" "67"]


When we want to join these back again to restore the single string we have split's partner join, so:-

(defn join-string [ss]
  (clojure.string/join "," ss))


We just specify the string "," to be added between the strings in our sequence.

user=> (join-string ["4" "5" "45" "6" "7" "67"])
"4,5,45,6,7,67"


Now we will want to get the integer values of these strings.  So we dip into the Java class Integer and bring back the method parseInt.  I love it when you can step between languages and they play nicely together.  In the system I use professionally I can step from C to assembler and back again. It's similar in that Clojure has Java hiding inside and C has assembler hiding inside. Anyway to change a string to an integer I can summon the Integer class and call the parseInt method on it, like this:-

user=> (. Integer parseInt "123")
123


That's a macro but it can become a function quite easily:-

user=> (#(. Integer parseInt %) "123")
123


And we will want to convert these integers back into strings: the Clojure function str will do this:-

user=> (str 3)
"3"


We will want a filter function that will decide whether a number is a square.  For this let's dip into Java again and get the square root method from the Math class:-

user=> (. Math sqrt 2.0)
1.4142135623730951


So if I take the integer part of the square root (the Clojure function int will give this) and square this and compare with the original number that indicates whether it is was a square number. Along these lines:-

(defn is-square [n]
  (let [root (int (. Math sqrt n))]
    (= (* root root) n)))


user=> (is-square 100)
true
user=> (is-square 101)
false
user=> (is-square 99)
false


OK so putting the parts together.  The first version of my function just-squares will open up the string into the individual numbers and then put them together again:-

(def just-squares
  (fn [s]
    (join-string (split-string s))))


user=> (def s "4,5,6,7,8,9")
#'user/s
user=> (just-squares s)
"4,5,6,7,8,9"


So far so good.  Now convert them to integers and back again.

(def just-squares
  (fn [s]
    (join-string
      (map str
        (map #(. Integer parseInt %) (split-string s))))))


user=> (just-squares s)
"4,5,6,7,8,9"


Still works.  Now add that filter to allow only the square ones:-

(def just-squares
  (fn [s]
    (join-string
      (map str
        (filter (fn [n] (let [root (int (. Math sqrt n))](= (* root root) n)))
          (map #(. Integer parseInt %) (split-string s)))))))


user=> (just-squares s)
"4,9"


Ok so this works.  Now to make this code complete in itself I should fill in the definitions of those functions split-string and join-string, so we get this:-

(def just-squares
  (fn [s]
    (#(clojure.string/join "," %)
      (map str
        (filter (fn [n] (let [root (int (. Math sqrt n))](= (* root root) n)))
          (map #(. Integer parseInt %) (clojure.string/split s #",")))))))


Hmm.  Well, that works on the 4Clojure page but I don't like it.  Maybe there's scope to use the -> macro to link the sections together instead of nesting them. Or use more lets to give the sections some names.

Also a more idiomatic name for is-square would have been square?.

Wednesday 7 November 2012

Reverse Interleave

Today's example is a reverse interleave - - that is, instead of taking two or more sequences and blending them together, we take one sequence and split it down into two or more by adding elements from the original sequence to the new sequences in rotation.

For example we want the function f that does this:-

(f '(1 2 3 4 5 6) 2) => ((1 3 5) (2 4 6)) ; split into two
(f '(1 2 3 4 5 6) 3) => ((1 4) (2 5) (3 6)) ; split into three

OK, so I expect I will want code to get every nth element from a sequence - every 2nd, every 3rd one etc. The built-in function partition-all splits a sequence into sequences of a nominated length: so all I want from this is the first element of every sub-sequence.  I map first onto the sequence of sequences returned by partition-all:-

user=> (def t '(1 2 3 4 5 6))
#'user/t
user=> t
(1 2 3 4 5 6)
user=> (partition-all 2 t)
((1 2) (3 4) (5 6))
user=> (partition-all 3 t)
((1 2 3) (4 5 6))
user=> (map first (partition-all 2 t))
(1 3 5)
user=> (map first (partition-all 3 t))
(1 4)


Then moving on I will want to get every nth element but not starting at the beginning, starting at some i-th element in.  So I have to drop some elements before the rest of the function gets it - something like this:-

defn every-nth-from-i
  "return every nth item from sequence s starting from element i (counting from zero)"
  [n s i]
  (map first (partition-all n (drop i s))))


user=> (every-nth-from-i 3 t 0)
(1 4)
user=> (every-nth-from-i 3 t 1)
(2 5)
user=> (every-nth-from-i 3 t 2)
(3 6)


Now the result I want is a sequence of all the sequences generated by this code, for each value of i up to the length of the sub-sequences I want to generate. Well, one less.  That's ok, given n I want to map the numbers in (range n) to the every-nth code.

(def reverse-interleave
  (fn [n s]
    (map
      (fn [i] (map first (partition-all n (drop i s))))
      (range 0 n))))


I don't need to explicitly pass n and s to the internal function because it executes in the environment where they are already available.

Does this work?

user=> (reverse-interleave 2 t)
((1 3 5) (2 4 6))
user=> (reverse-interleave 3 t)
((1 4) (2 5) (3 6))


Actually that turned out simpler than I expected.

Friday 2 November 2012

Rotate Sequence

Today, for exercise No. 44 Rotate Sequence we write code to rotate a sequence in either direction - determined by the sign of the first parameter.

To rotate the first element of a list to the end we make a list of the first element and concatenate the rest of the list onto it, like this:

#(concat (rest %) (list (first %)))

For example:

user=> (#(concat (rest %) (list (first %))) '(1 2 3 4 5))
(2 3 4 5 1)


To rotate the other way we could use last to get the end element and butlast to get the others and then swap these around in the same way:

user=> (#(concat (list (last %)) (butlast %)) '(1 2 3 4 5))
(5 1 2 3 4)


This just moves one element - to move more I can make the function recursive.  As the function is recursive anyway I can implement the reverse rotation for negative counts by reversing the original list, rotating it forwards, then reversing the result.  The call to the negative version only happens once - the forward rotation call that does the work is still tail recursive.

You can make an anonymous function recursive by adding a label (in this case this) between the keyword fn and the parameter list. The base case is when the number of rotations left to do is zero: then of course we just return the list. On that basis then we get this:-

(def my-rotate
  (fn this [n xs]
    (if (= 0 n)
        xs
        (if (> n 0) ; n is +ve
          (this (dec n) (concat (rest xs) (list (first xs))))
          (reverse (this (- 0 n) (reverse xs)))))))


How does this look?

user=> (my-rotate 2 [1 2 3 4 5])
(3 4 5 1 2)
user=> (my-rotate -2 [1 2 3 4 5])
(4 5 1 2 3)
user=> (my-rotate 6 [1 2 3 4 5])
(2 3 4 5 1)
user=> (my-rotate 1 '(:a :b :c))
(:b :c :a)
user=> (my-rotate -4 '(:a :b :c))
(:c :a :b)


Thursday 1 November 2012

Flipping Out Continued

And to test the flip-out function I needed a function that takes three parameters where the order matters.  So I added this:

(defn drop-take
  "Drop i elements from the sequence s and then take j of what's left"
  [i j s]
  (take j (drop i s)))


Then to test:

user=> (drop-take 10 5 (range))
(10 11 12 13 14)


user=> ((flip-out drop-take) 5 10 (range))
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:494)


Ha - pay attention - arguments in the reverse order, remember?

user=> ((flip-out drop-take) (range) 5 10)
(10 11 12 13 14)


That's more like it.

I'm puzzled that I had to rebuild the parameter list by writing

([x y & more] (apply f (reverse (cons x (cons y more)))))

I thought this might work:

([x y & more :as s] (apply f (reverse (s)))

But no, more research required...