Coding Katas

What coding katas are about

Japanese culture influenced a lot of software and project management fields. Concepts like Lean, Kata, etc has come from Japan. And we should admit, that they have improved the existing processes, increasing efficiency and satisfaction overall — apiumhub.com

With the materials in this repository, you'll learn TDD by practicing so-called coding katas:

A kata is an exercise in karate where you repeat a form many, many times, making little improvements in each. The intent behind code kata is similar — codekata.com

Generally speaking, each kata tries to target one or more skills, and this collection is no exception to that general rule. As the saying goes, practice makes perfect, and the same holds for (coding) katas: preferably you make them your own by repeating them time and again.

And although the saying goes that practice makes perfect, the reality is that code almost never reaches a perfect state: you can always find ways to further improve your code and your skill(s). There are always new ways to become more proficient and faster. Luckily, it turns out that mastery is one of the three primary drivers that keep us motivated. Moreover, the payoff of mastering TDD is much higher than the investments that you'll put in.

After spending a certain time with TDD, people claim that there is no other way to develop software. It is almost a learning to type with ten fingers: once you master the skill, you wonder how you ever managed without it.

Katas using backtracking algorithms

For a couple of katas such as the Sudoku solver, we need to implement a backtracking algorithm. So let's elaborate a bit on this topic.

A simple backtracking example in Clojure

This section is based on the Sudoku exercise that is part of the Clojure course taught at the computer science department of the University of Helsinki.

Subset sum is a classic problem. You are given a set of numbers, such as the set #{1 2 10 5 7} and another number, let's say 23.

The puzzle is to find out if there is some subset of the original set that has a sum that is equal to the target number.

Let's see how we may solve this by implementing a brute-force approach based on a backtracking search.

Here’s one possible way to implement it:

(defn sum [a-seq]
  (reduce + a-seq))

(defn subset-sum-helper [a-set current-set target]
  (if (= (sum current-set) target)
    [current-set]
    (let [remaining (clojure.set/difference a-set current-set)]
      (for [elem remaining
            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]
        solution))))

(defn subset-sum [a-set target]
  (subset-sum-helper a-set #{} target))

So the main thing that happens inside subset-sum-helper. First of all, always check if we have found a valid solution. Here it’s checked with

  (if (= (sum current-set) target)
    [current-set]

If we have found a valid solution, return it in a vector (we’ll see soon why in a vector). Okay, so if we’re not done yet, what are our options? Well, we need to try adding some element of a-set into current-set and try again. What are the possible elements for this? They are those that are not yet in current-set. Those are bound to the name remaining here:

    (let [remaining (clojure.set/difference a-set current-set)]

What’s left is to actually try calling subset-sum-helper with each new set obtainable in this way:

      (for [elem remaining
            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]
        solution))))

Here first elem gets bound to the elements of remaining one at a time. For each elem, solution gets bound to each element of the recursive call

            solution (subset-sum-helper a-set
                                        (conj current-set elem)
                                        target)]

And this is the reason we returned a vector in the base case so that we can use for in this way. Finally, we return each such solution in a sequence.

So let’s try this out:

    (subset-sum #{1 3 4 10 9 23} 20)
;=> (#{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10} #{1 9 10})

Okay, so the above example is not exactly optimal. It forms each set many times. Since we were only interested in one solution, however, we can just add first to the call if the helper:

(defn subset-sum [a-set target]
  (first (subset-sum-helper a-set #{} target)))

And due to the way Clojure uses laziness, this actually cuts the computation after a solution is found (well, to be exact, after 32 solutions have been found due to the way Clojure chunks lazy sequences).