Learning Clojure

first.md

layout	title	date	categories	crossposted
post	How I learned Clojure while solving easy coding challenges	2015-08-03	coding	logdown

I decided to learn Clojure (and therefore ClojureScript, since the two intersect significantly) by doing. Who'd ever blame me with that?

I chose HackerRank as a platform for practice. There are other choices, of course, but I love HackerRank for two reasons:

• it offers a REPL-style flow: I write code, run it against some tests, get results instantly,
• before the code is submitted, I can test it against whatever cases I may imagine for as many times I need.

So I started from Introduction section within Functional Programming domain.

The first thing I encountered was that I didn't exactly know how to read from STDIN in Clojure. I also didn't know how to parse input string or stream, pass it into a function and split into substrings in particular.

The solution to this simple problem is, well, simple:

(let [in (slurp *in*)]
    (println (clojure.string/split in #"\s")))

For input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

it returns

[2 4 3 -1 -3 4 2 4 2 0 -1 2 1]

which means pretty much what I need.

Or, in a less readable and more laconic form,

(let [in (clojure.string/split (slurp *in*) #"\s")]
    (println in))

Typical challenge on HackerRank defines a sequence that, in its head, has a number that represents the number of test cases (in aforementioned example, there are 2 test cases). Knowing that, it's typically useful to extract this value into a separate variable. Good thing let evaluates its first parameter sequentially, so this is valid code:

(let
    [in (clojure.string/split (slurp *in*) #"\s")
    tests (first in)
    input-data (rest in)]
    (print tests input-data))

It now outputs

2 (4 3 -1 -3 4 2 4 2 0 -1 2 1)

HackerRank challenges

So here go some interesting (at the beginner level) challenges that I'd been puzzling over for relative long time, mostly because of lack of knowledge of clojure.core API.

List replication

The problem is to output values from the input list N times each, N given as the first element of the input:

Given a list repeat each element of the list n times. The input and output portions will be handled automatically by the grader. You need to write a function with the recommended method signature.

Sample input:

3
1
2
3
4

and sample output:

1
1
1
2
2
2
3
3
3
4
4
4

The most dumb problem in the world. And I've spent about 40 minutes on it.

The final code was

(fn [num lst]
    (loop [head (first lst) tail (rest lst)]
        (if-not (nil? head)
            (do
                (dotimes [i num] (println head))
                (recur (first tail) (rest tail))))))

It didn't look clear or beautiful to me but I just couldn't do it better. Hopefully, things will change over time, positively.

Filter array

The approach was very similar to the previous problem. This one is defined as:

Filter a given array of integers and leave only that values which are less than a specified value X. The integers in the output should be in the same sequence as they were in the input. You need to write a function with the recommended method signature for the languages mentioned below. For rest of language you have to write complete code.

Sample input:

3
10
9
8
2
7
5
1
3
0

and sample expected output:

2
1
0

So, the problem can be decomposed into simple tasks:

• loop through the whole list lst and by the way
• check if current element is less than delim,
• and if true, print it,
• then recur with the rest of the list lst.

The code:

(fn [delim lst]
    (loop [head (first lst) tail (rest lst)]
        (if-not (nil? head)
            (do
                (if (< head delim)
                    (println head))
                (recur (first tail) (rest tail))))))

Filter positions in a list

The problem is simple, the program should filter out every second item of the list (one with an odd index):

For a given list with N integers, return a new list removing the elements at odd positions.

Sample input:

2
5
3
4
6
7
9
8

and output:

5
4
7
8

The code:

(fn [lst]
    (loop [odd false lst lst]
        (if-not (nil? (first lst))
            (do
                (if odd (println (first lst)))
                (recur (not odd) (rest lst))))))

For this problem, it took me about 5 minutes to reach the working solution. However, I was feeling that not using let makes the code a lot less comprehensible than it could be.

Reverse a list

This one happened to be tricky for me, since I don't know much of Clojure's standard library. The clojure.string namespace seems to be deprecated for HackerRank FP challenges so I had to implement my own join, too.

The problem is to reverse a list without using reverse function, and then print it out each element on a new line.

Sample input:

19
22
3
28
26
17
18
4
28
0

and output:

0
28
4
18
17
26
28
3
22
19

Now, my solution is a lot like freshman's would look like, but considering I'm a Clojure novice, I don't feel bad about it (maybe about 1/4 of bad):

(fn [lst]
    (loop [in lst out (list)]
        (if (seq in)
            (recur (rest in) (conj out (first in)))
            (print
                (reduce str
                    (interpose "\n" out))))))

Sum of odd elements

The challenge was simply to return the sum of all elements of an input list that are odd. The solution is so short I felt proud of myself. However, thanks to Clojure by Example reference:

(fn [lst] 
    (reduce + (filter odd? lst)))

List Length

The challenge was to calculate the length of a list the hard way. Simple reduce got the job done:

(fn [lst]
    (reduce (fn [n t] (inc n)) 0 lst))

Update List

The caption isn't very clear, the problem statement is:

Update the values of a list with their absolute values.

Sample input:

2
-4
3
-1
23
-4
-54

and output:

2
4
3
1
23
4
54

At first, I thought of Math.abs. So I tried

(fn [lst]
    (map Math/abs lst))

but that threw with

Exception in thread "main" java.lang.RuntimeException: Unable to find static field: abs in class java.lang.Math

I'm not exactly sure why this happened, but, in a short search, I discovered the solution:

(fn [lst]
    (map #(Math/abs %) lst))

upd: it was FIXME but then I found an explanation

Evaluating e^x

There's a function e^x that is defined as a series:

e^x = x^0 + x^1/1! + x^2/2! + x^3/3! + ... + x^n/n!

The goal is to find a sum of first 10 elements of e^x.

The problem perfectly decomposes into a set of simply solvable tasks:

• factorial of n,
• x to the power of n, and
• sum of series, actually of a fixed number of elements.

At first, it was a bit difficult for me to get away from for-loop imperative approach and rather switch to more mathematical methods. So I googled a bit and found great solution for both factorial:

(defn factorial [n]
    (reduce * (range 1 (inc n))))

and exponentiation:

(defn exp [x n]
    (reduce * (repeat n x)))

Next, the sum of the series is also a simple reduce. So the overall solution looks like this:

(let
    [in (clojure.string/split (slurp *in*) #"\s")
    tests (read-string (first in))
    input-data (rest in)]
    (loop [input-data input-data]
        (when (not-empty input-data)
            (println 
                (reduce +
                    (map
                        (fn [l r]
                            (/
                                (reduce * (repeat r l))
                                (reduce * (range 1 (inc r)))))
                        (repeat 10 (read-string (first input-data)))
                        (iterate inc 0))))
            (recur (rest input-data)))))

It was accepted by HackerRank and got 100% score (20.00 pts), although its run-time is a bit too long for such a simple solution.

By the way, there are really great solutions submitted by other participants, one in Scala and one in Clojure, the latter deserves its place here:

(doseq [i (range (Integer/parseInt (read-line)))]
  (println
    ((fn [x]
      (reduce +
        (map first
          (take 10
            (iterate (fn [[r k]] [(/ (* r x) k) (inc k)]) [1.0 1])))))
              (Double/parseDouble (read-line)))))

Area Under Curves and Volume of Revolving a Curve

The problem was, given a function, to calculate its definite integral.

For this problem, few links to related information were provided:

• the limit definition of a definite integral, although a bit more mathematical and less computational,
• areas and volume computation, and an integral, in context of this problem, is a computation of an area.

However, I found more, and those were more useful:

• formulating abstractions with higher-order functions, a bit of useful Clojure-related info on integrals,
• numerical integration, a very good guide on different computational maths regarding to function integrals, with some visual perks,
• a bit more comprehensible explanation of integrating circles formed by rotation,
• and even Wolfram|Alpha's area calculator.

So, it took me 2 pomodoros to do research and reach a half-working solution:

(defn exp [x e]
    (reduce * (repeat e x)))

(defn build-function [multipliers powers]
    (fn [x]
        (reduce +
            (map
                #(* %1 (exp x %2))
                multipliers
                powers))))

(defn sum [term a next-term b]
    (if (> a b)
        0
        (+
            (term a)
            (sum term (next-term a) next-term b))))

(defn integral [f a b dx]
    (defn +dx [x] (+ x dx))
    (*
        (sum f (+ a (/ dx 2)) +dx b)
        dx))

(defn solve-flat [multipliers powers a b]
    (integral
        (build-function multipliers powers)
        a
        b
        0.001))

(let
    [multipliers
        (vec (map read-string (clojure.string/split (read-line) #"\s")))
    powers (vec (map read-string (clojure.string/split (read-line) #"\s")))
    ab (vec (map read-string (clojure.string/split (read-line) #"\s")))
    a (nth ab 0)
    b (nth ab 1)]
    (println
        (solve-flat multipliers powers a b)))

For the sample input

1 2
0 1
2 20

it has output

413.99999999997846

which was close to the answer, but only for the first part of two. Because the problem was:

The first Line will contain the area between the curve and the x-axis, bound between the specified limits. The second Line will contain the volume of the solid obtained by rotating the curve around the x-axis, between the specified limits.

So, the expected output was:

414.0
36024.1

However, this code was unstable, too, because for

1 2 3 4 5
6 7 8 9 10
1 4  

it returned

2432035.87874474

instead of expected

2435300.3

So I had to add volume calculation. A very brief googling got me to the calculus explanation of calculation of the volume of a shape formed by rotation of a given function around x-axis.

The code then was:

(defn exp [x e]
    (reduce * (repeat e x)))

(defn build-function [multipliers powers]
    (fn [x]
        (reduce +
            (map
                #(* %1 (exp x %2))
                multipliers
                powers))))

(defn build-circle-area-function [f]
    (fn [x]
        (*
            Math/PI
            (exp
                (f x)
                2))))

(defn sum [term a next-term b]
    (if (> a b)
        0
        (+
            (term a)
            (sum term (next-term a) next-term b))))

(defn integral [f a b dx]
    (defn +dx [x] (+ x dx))
    (*
        (sum f (+ a (/ dx 2)) +dx b)
        dx))

(defn solve-flat [multipliers powers a b]
    (integral
        (build-function multipliers powers)
        a
        b
        0.001))

(defn solve-volume [multipliers powers a b]
    (integral
        (build-circle-area-function (build-function multipliers powers))
        a
        b
        0.001))

(let
    [multipliers
        (vec (map read-string (clojure.string/split (read-line) #"\s")))
    powers (vec (map read-string (clojure.string/split (read-line) #"\s")))
    ab (vec (map read-string (clojure.string/split (read-line) #"\s")))
    a (nth ab 0)
    b (nth ab 1)]
    (println
        (solve-flat multipliers powers a b)
        (solve-volume multipliers powers a b)))

But it got me only 18 points out of possible 30. Kinda sad. 2 out of 5 tests failed.

It's a shame that I haven't come up with the right conclusion so I bought input and output samples for one of the tests, however only input was enough. The point was, I made up exponentiation function for only positive powers, e.g. x^e for e >= 0. So the next step was to enhance the exponentiation function to allow it calculate values for negative powers:

(defn exp [x e]
    (if (> e 0)
        (reduce * (repeat e x))
        (reduce / 1 (repeat (- e) x))))

This worked perfectly. 20 out of 20 points.

second.md

layout	title	date	categories
post	How I learned Clojure while solving easy coding challenges, part 2	2015-08-20	coding

[Previously]({% post_url 2015-08-03-learning-clojure %}) I made a little note about several things I've learned about Clojure while solving easy tasks. Later, I set my hands to the next subset of FP problems on HackerRank.

The subdomain is called “Recursion”, so it's expected that one employs recursive calls and, possibly, higher-order functions.

Computing the GCD

The problem statement is simple: given two numbers, find their GCD using Euclidean algorithm. The code is simple, too.

(defn gcd [a b]
    (if (= b 0)
        a
        (recur b (mod a b))))

(let [f (fn [a b] (gcd a b) ) [m n] (map read-string (re-seq #"\d+" (read-line)))] (println (f m  n)))

I'm not quite sure if recur or function name at the tail of the function body makes any difference. There's also an explanation of recur and loop and why those form recursion, not just a traditional imperative loop.

Fibonacci Numbers

This one was interesting. Simple recursion caused TLE, termination due to too long execution.

(defn fib [n]
    (if (#{0 1 2} n)
        (max 0 (- n 1))
        (+
            (fib (- n 1))
            (fib (- n 2)))))

(let [n (Integer/parseInt (read-line))]
    (print (fib n)))

It's because the complexity of this solution is O(N!), the worst ever imaginable.

The good thing is that Clojure provides memoization technique implementation out of the box with memoize function that returns a memoized function:

(def fib
    (memoize
        (fn [n]
            (case n
                0 0
                1 0
                2 1
                (+ (fib (- n 1))
                    (fib (- n 2)))))))

(let [n (Integer/parseInt (read-line))]
    (print (fib n)))

This solution was far more efficient and faster at run-time.

Pascal's Triangle

I've [explained this problem in detail earlier]({% post_url 2015-08-18-pascal-triangle %}) so I won't make a stop here.

String Mingling

The problem statement is complicated, however the extract it is simple: given two strings, interleave them. But the first solution I made had, too, terminated due to timeout:

(let [fst (read-line) snd (read-line)]
    (print
        (reduce str
            (map str fst snd))))

On the discussion forum, somebody asked if anybody else experienced problem with higher-order functions. I got the idea and replaced reduce with simple loop:

(loop [fst (read-line) snd (read-line)]
    (when (first fst)
        (print (str (first fst) (first snd)))
        (recur (rest fst) (rest snd))))

It worked, and again, in shorter time than at the first take.

String-o-Permute

Again, very simple problem. Given a string, swap each pair of its elements. The funny thing was that, at the third time, my solution at first had TLE:

(loop [tests (read-string (read-line))]
    (when (> tests 0)
        (let [input (read-line)]
            (println
                (reduce str
                    (map
                        #(clojure.string/join (reverse %))
                        (partition 2 2 input)))))
        (recur (- tests 1))))

Seemed like partition was too slow so I had to implement its alternative, narrower and faster in execution:

(defn swap-pairs
    ([input] (swap-pairs input []))
    ([input result]
        (if (empty? input)
            result
            (swap-pairs
                (drop 2 input) 
                (conj result (second input) (first input))))))

(loop [tests (read-string (read-line))]
    (when (> tests 0)
        (let [input (read-line)]
            (println
                (clojure.string/join "" (swap-pairs input))))
        (recur (- tests 1))))

Done.

By the way, that was the first time I've employed multi-arity function in Clojure. Due to my previous experience both with Java and then Javascript, I missed this feature in the latter. The syntax in Clojure is pretty clean:

(defn function-name
    ([param1] ...)
    ([param1 param2] ...))

The number of overloads and the number of params in each may vary.

String Compression

Classical problem when you have to somehow change the input “in stream way”, which means you don't have to return back thus getting it done in O(N). My problem here was, however, that the code was ugly:

(defn truthy? [exp]
    (if (and exp (pos? exp) (> exp 1))
        exp
        nil))

(defn compress
    ([input] (compress input "" nil 1))
    ([input result last-char last-count]
        (if (empty? input)
            (str result last-char (truthy? last-count))
            (if (= (first input) last-char)
                (compress
                    (rest input)
                    result
                    last-char
                    (+ last-count 1))
                (compress
                    (rest input)
                    (str result last-char (truthy? last-count))
                    (first input)
                    1)))))

(println (compress (read-line)))

Will think about its improvement later, though. I'm sure there's a better, better readable and cleaner solution.

Prefix Compression

Given two strings, find common prefix (from 0th element), cut it away from both strings and output all the three, provided with each one's length.

(defn cut-prefix
    ([left right] (cut-prefix left right ""))
    ([left right prefix]
        (let [l (first left) r (first right)]
            (if (and l r (= l r))
                (cut-prefix (rest left) (rest right) (str prefix l))
                [prefix (clojure.string/join left) (clojure.string/join right)]))))

(defn output [[prefix left right]]
    (println (count prefix) prefix)
    (println (count left) left)
    (println (count right) right))

(let [left (read-line) right (read-line)]
    (output (cut-prefix left right)))

Ugly, but works.

String Reductions

Given a string, reduce number of each unique character to one occurence. Nothing could be simpler than this because strings are sequences, and there's a function that extracts unique elements from a list into a (shorter) list.

(let [input (read-line)]
    (println
        (clojure.string/join
            (distinct input))))

It was so simple that, at first, I thought the TLE would happen again. It wouldn't.

Filter Elements

This task is marked as easy but I'm sure it's a bit harder than other easy problems. So, given a list, output a (shorter) list of distinct elements such that those occur in original list no less that N times, order preserved. For example, given

5 4 3 2 1 1 2 3 4 5

and for N equal to 2, the expected output is

5 4 3 2 1

The first thing, and very straightforward solution was to apply hash-maps, keys are elements in the list, and values are number of occurrences.

Hence the code

(defn pass-when-enough
    ([threshold lst] (pass-when-enough (count lst) threshold lst))
    ([elements-count threshold lst] (pass-when-enough elements-count threshold lst {}))
    ([elements-count threshold lst result]
        (if (zero? elements-count)
            (map first
                (filter
                    #(>= (second %) threshold)
                    result))
            (pass-when-enough
                (- elements-count 1)
                threshold
                (rest lst)
                (merge-with + result {(first lst) 1})))))

But it didn't work at some of the tests. I've spent about 20 minutes on hunting for the explanation and found out a very important thing: hash-maps don't preserve order when merged! Thus, the original list must be preserved. Thus, I've rewritten the solution, although no less ugly:

(defn pass-when-enough
    ([lst] (pass-when-enough (first lst) (second lst) (drop 2 lst)))
    ([threshold lst] (pass-when-enough (count lst) threshold lst))
    ([elements-count threshold lst] (pass-when-enough elements-count threshold lst {} []))
    ([elements-count threshold lst result-map result-lst]
        (if (zero? elements-count)
            (distinct
                (filter
                    (into {}
                        (filter #(>= (second %) threshold) result-map))
                    result-lst))
            (pass-when-enough
                (- elements-count 1)
                threshold
                (rest lst)
                (merge-with + result-map {(first lst) 1})
                (conj result-lst (first lst))))))

And it worked. There has to be a shorter and more comprehensible solution, though. But since I'm at the “learning by doing” phase, it doesn't matter now.

---

Learning a new language by solving series of simple tasks is great. However, it doesn't give any industry-level experience. But what I'm completely certain about is that one doesn't simply learn a new thing by either reading or doing, but rather by moving in both directions simultaneously. It takes a lot more time but it pays.