Header photo by Matthew Sleeper
Setting the backdrop
I've been using Clojure for a little over three years and I finally made it to my first Clojure coding dojo at the London ThoughtWorks office a few weeks ago. I've wanted to attend one of these events for a while, but living outside of London has prevented me from doing so until now.
I enjoyed the evening. If you haven't attended one of these events yet either, I would highly recommend trying to go to one. You can find out more about the London Clojurians meetup group here.
I'd also like to make special mention of ClojureBridge which "aims to increase diversity within the Clojure community by offering free, beginner-friendly Clojure programming workshops for underrepresented groups in tech." If you're in the London area and want to get involved, either as a student or as a coach, please checkout ClojureBridge London.
Dojo structure
There is a lot of literature on the internet about running your own coding dojo so I won't go into detail here. The basic idea is to suggest a few problems to work on, vote on those to narrow the final selection, and then to split into smaller groups and work on a problem together. The final 30 minutes can be used for the groups to share what they may have learned during the session.
The challenge
I was in a group of three and we chose to work on solving the Codewars snail kata. When given an n x n array, your code has to return the array elements arranged from outermost elements to the centre element, traveling in a clockwise direction.
The code
The code that follows is what I implemented at home in the days after the dojo. It was based on my memories of what we attempted on the night. There may be some subtle differences, but the essence should be the same. You can checkout the code for this post at https://github.com/yogidevbear/clojure-playground/tree/master/snailsort.
We start by creating a new Clojure project using Leiningen. From the terminal, run:
lein new snailsort
This creates a new project folder called snailsort with the following directory structure:
snailsort/
src/
snailsort/
core.clj
test/
snailsort/
core_test.clj
project.clj
Next, we change into the snailsort directory and start the tests using lein test-refresh.
cd snailsort
lein test-refresh
This should start running the code tests in the terminal. Every time we save any file in the test or src folders, the tests will be re-run automatically for us.
We want to adhere to TDD. Using your editor of choice, open test/snailsort/core_test.clj. The snailsort.core-test namespace requires the snailsort.core namespace found in src/snailsort/core.clj. Update the require on lines 2-3 to alias snailsort.core as snail.
test/snailsort/core_test.clj:
(ns snailsort.core-test
(:require [clojure.test :refer :all]
[snailsort.core :as snail]))
This allows us to call functions within snailsort.core using syntax like (snail/some-function-name args).
We decided on the evening that we would make use of array coordinates to reference positions within the array we were trying to sort. Let's define a 3x3 grid that we want to sort (as well as adding a commented out matrix to help us conceptualise the relative x+y coordinates while we work on the solution).
test/snailsort/core_test.clj:
; Reference coordinates
; x y
; [[0 0] [0 1] [0 2]
; [1 0] [1 1] [1 2]
; [2 0] [2 1] [2 2]]
(def grid
[[1 2 3]
[8 9 4]
[7 6 5]])
The initial path we took was to figure out how to traverse the grid. The first solution is sub-optimal, but I will run through it here first and then show a different approach towards the end which should illustrate what I mean.
We have our grid above and we want to know how to find the next appropriate adjacent coordinate in our spiral sequence. We will define a next-coordinate function which will take a direction keyword and a current coordinate position. If we look at our commented reference grid above, we can see that our first coordinate on the top left is [0 0] and the next position to the :right will be [0 1]. Using this logic we can start off by writing our first test with a few different assertions.
test/snailsort/core_test.clj:
(deftest next-coordinate
(testing "Test retrieving next coordinate"
(is (= [0 1] (snail/next-coordinate :right [0 0])))
(is (= [2 1] (snail/next-coordinate :left [2 2])))
(is (= [2 2] (snail/next-coordinate :down [1 2])))
(is (= [1 0] (snail/next-coordinate :up [2 0])))))
Now we can add some code to our core namespace.
src/snailsort/core.clj:
(def directions
{:right #(update-in % [1] inc)
:down #(update-in % [0] inc)
:left #(update-in % [1] dec)
:up #(update-in % [0] dec)})
(defn next-coordinate
"I return the next grid coordinate based on current position and direction"
[direction current]
((directions direction) current))
When you save these changes, you should see the tests refresh in your terminal, with an output similar to:
*********************************************
*************** Running tests ***************
:reloading (snailsort.core snailsort.core-test)
Testing snailsort.core-test
Ran 1 tests containing 4 assertions.
0 failures, 0 errors.
Passed all tests
I won't mention the test output again. The main point I'm hoping to illustrate is the quick feedback loop that you get from following this approach. Now back to the actual code above.
The first thing we did, was define a Clojure map call directions. This will map each of the four direction keywords to a relative function for updating the [x y] coordinates that we're trying to keep track of as we step through solving the grid path.
In the example of calling (next-coordinate :right [0 0]), this will resolve to ((directions :right) [0 0]) which will ultimately resolve to (#(update-in % [1] inc) [0 0]), which will return [0 1].
I'm sure by now, you're already noting that we need to check that the coordinate we're returning is actually valid. We don't want to get into a situation where we're going outside the possible confines of our grid.
Let's go back and write our next test to check if an [x y] coordinate is valid.
test/snailsort/core_test.clj:
(deftest is-valid?
(testing "Test if next coordinate is valid"
(is (= true (snail/is-valid? grid [0 2])))
(is (= true (snail/is-valid? grid [1 1])))
(is (= false (snail/is-valid? grid [0 3])))
(is (= false (snail/is-valid? grid [0 3])))))
We are testing two positions that we know will be valid and two which won't be. Next we can switch to our core namespace and write the function to pass the test.
src/snailsort/core.clj:
(defn is-valid?
"I return a boolean if a coordinate is valid or not"
[grid coordinate]
(some? (get-in grid coordinate)))
This function is pretty straightforward. We're just checking if we can return a value from our grid by using get-in with our [x y] coordinate.
We have a way to get an adjacent position and a way to test for valid positions. Next, we need a way to determine our next clockwise direction for when we need to switch things up. Here is the test:
test/snailsort/core_test.clj:
(deftest next-direction
(testing "Test next-direction for clockwise rotation"
(is (= :down (snail/next-direction :right)))
(is (= :left (snail/next-direction :down)))
(is (= :up (snail/next-direction :left)))
(is (= :right (snail/next-direction :up)))))
And the code to solve it (note that we need a map to help with the clockwise step):
src/snailsort/core.clj:
(def clockwise-direction
{:right :down
:down :left
:left :up
:up :right})
(defn next-direction
"I return the next clockwise direction"
[direction]
(direction clockwise-direction))
Our next logical step is to check that we haven't visited a position before. We can write a function that takes a set of previously visited positions and the coordinate we want to test and return true if it isn't found in the set.
test/snailsort/core_test.clj:
(deftest first-visit?
(testing "Test if coordinate is being visited for the first time"
(is (= true (snail/first-visit? #{} [0 0])))
(is (= false (snail/first-visit? #{[0 0]} [0 0])))
(is (= true (snail/first-visit? #{[0 0] [0 1]} [0 2])))
(is (= false (snail/first-visit? #{[0 0] [0 1] [0 2]} [0 2])))))
src/snailsort/core.clj:
(defn first-visit?
"I check if a grid cell is being checked for the first time"
[checked current]
(nil? ((set checked) current)))
We also want to know if we've completed traversing the grid.
test/snailsort/core_test.clj:
(deftest all-visits?
(testing "Test if visited set size matches grid size"
(is (= false (snail/all-visits? grid #{[0 0]})))
(is (= false (snail/all-visits? grid #{[0 0] [0 1]})))
(is (= true (snail/all-visits? grid #{[0 0] [0 1] [0 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2]})))
(is (= true (snail/all-visits? grid #{[0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0] [1 0] [1 1]})))))
src/snailsort/core.clj:
(defn all-visits?
"I check if all grid cells have been checked"
[grid checked]
(= (count (flatten grid))
(count checked)))
The above few functions give us most of the pieces we need for validation purposes. Let's switch things up and start working towards solving the path we want to traverse.
NOTE:
It was at this point where I was working at home on the remainder of the solution by myself. At the time, I was wondering whether there was a more idiomatic solution that could be used instead. Although the code we have so far is well tested and makes a lot of sense, it is also growing a little unwieldy. For the purposes of this article though, I'll continue with the current solution and come back to a more succinct solution at the end.
The next logical step in the current approach is to figure out which is the next valid position to traverse. We need to know if we can keep going in the current direction or whether we need to turn clockwise, etc. There are a few test assertions we can use here to cover all our bases.
test/snailsort/core_test.clj:
(deftest next-valid-coordinate
(testing "Test next valid position in grid"
(is (= {:direction :right :next-coordinate [0 1]} (snail/next-valid-coordinate grid [0 0] :right #{[0 0]})))
(is (= {:direction :left :next-coordinate [2 1]} (snail/next-valid-coordinate grid [2 2] :down #{[0 0] [0 1] [0 2] [1 2] [2 2]})))
(is (= {:direction :up :next-coordinate [1 0]} (snail/next-valid-coordinate grid [2 0] :left #{[0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0]})))
(is (= {:direction :right :next-coordinate [1 1]} (snail/next-valid-coordinate grid [1 0] :up #{[0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0] [1 0]})))
(is (= nil (snail/next-valid-coordinate grid [1 1] :down #{[0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0] [1 0] [1 1]})))))
src/snailsort/core.clj:
(defn next-valid-coordinate
"I return the next valid coordinate or nil if none exists"
[grid current direction checked]
(let [next-pos (next-coordinate direction current)
new-direction (next-direction direction)
rotated-pos (next-coordinate new-direction current)]
(if (and (is-valid? grid next-pos)
(first-visit? checked next-pos))
{:direction direction :next-coordinate next-pos}
(if (and (is-valid? grid rotated-pos)
(first-visit? checked rotated-pos))
{:direction new-direction :next-coordinate rotated-pos}
nil))))
The idea of next-valid-coordinate is to return a map of the next position, as well as the direction for the next test. We need to return the direction in the result as we need to be made aware of any potential change in direction.
One thing we haven't covered yet, and is a requirement for the kata, is to validate that the grid being supplied is actually a valid square.
We want to test a variety of valid grid sizes, so lets start with a function in our test file to generate grids of any specified length.
test/snailsort/ore_test.clj:
(defn generate-grid
"Generates a random n x n grid"
[n]
(if (< n 1)
[[]]
(let [row (fn [] (take n (repeatedly #(rand-int 10))))]
(into [] (take n (repeatedly #(into [] (row))))))))
Now we can define our test and function to check if a grid is a valid square.
test/snailsort/ore_test.clj:
(deftest is-valid-grid?
(testing "Test if grid supplied is valid n x n square"
(is (= false (snail/is-valid-grid? [])))
(is (= false (snail/is-valid-grid? [1 2 3])))
(is (= false (snail/is-valid-grid? [[1 2 3] [4 5 6]])))
(is (= false (snail/is-valid-grid? [[1 2 3] [4 5] [6 7 8 9]])))
(is (= true (snail/is-valid-grid? grid)))
(is (= true (snail/is-valid-grid? (generate-grid 0))))
(is (= true (snail/is-valid-grid? (generate-grid 3))))
(is (= true (snail/is-valid-grid? (generate-grid 9))))
(is (= true (snail/is-valid-grid? (generate-grid 100))))
(is (= true (snail/is-valid-grid? (generate-grid 1000))))))
src/snailsort/core.clj:
(defn is-valid-grid?
"I check if a supplied grid is a valid n x n grid"
[grid]
(if (= grid [[]])
true
(let [height (count grid)]
(if (> height 0)
(every? #{true}
(map #(and (= (type %) (type []))
(= height (count %)))
grid))
false))))
We have most of the parts we need for a final solution. The approach that I initially went for was to work out the sequence as a list of cooridates and then use that sequence to fetch the individual position values. First we need the function to work out the sequence. For this, we can also add a couple of other variations of grids to test, followed by the sequence function test.
test/snailsort/ore_test.clj:
(def grid-alt-1
[[1 2]
[4 3]])
(def grid-alt-2
[[1 2 3 4 5]
[16 17 18 19 6]
[15 24 25 20 7]
[14 23 22 21 8]
[13 12 11 10 9]])
(deftest sequence-path
(testing "Test if sequence-path returns the correct vector sequence of coordinate points of snailsort"
(is (= [[0 0] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0] [1 0] [1 1]] (snail/sequence-path grid)))
(is (= [[0 0] [0 1] [1 1] [1 0]] (snail/sequence-path grid-alt-1)))
(is (= [[0 0] [0 1] [0 2] [0 3] [0 4] [1 4] [2 4] [3 4] [4 4] [4 3] [4 2] [4 1] [4 0] [3 0] [2 0] [1 0] [1 1] [1 2] [1 3] [2 3] [3 3] [3 2] [3 1] [2 1] [2 2]] (snail/sequence-path grid-alt-2)))))
src/snailsort/core.clj:
(defn sequence-path
"I return a vector of the spiral path"
([grid]
(sequence-path grid [] [0 0] :right))
([grid res current direction]
(let [res (conj res current)]
(if (< (count res) (count (flatten grid)))
(let [next-valid (next-valid-coordinate grid current direction res)]
(recur grid res (:next-coordinate next-valid) (:direction next-valid)))
res))))
I've used a 2-arity function definition here so that we can simply pass in the grid and let the known defaults initialise the main recursive functionality. With each iteration, we conjoin the current position to the result. We then check if the result has the same number of coordinates as positions in the main grid. If it is smaller, we recall (recur) the function with the result and the next coorditate. If the result is the same size as the grid, then we can return the result.
We have everything we need now, so let's implement the main snailsort function.
test/snailsort/ore_test.clj:
(deftest snailsort
(testing "Test snailsort function"
(is (= [] (snail/snailsort [[]])))
(is (= (mapv inc (range 9)) (snail/snailsort grid)))
(is (= (mapv inc (range 4)) (snail/snailsort grid-alt-1)))
(is (= (mapv inc (range 25)) (snail/snailsort grid-alt-2)))
(is (= [1 2 3 6 9 8 7 4 5] (snail/snailsort [[1 2 3] [4 5 6] [7 8 9]])))))
src/snailsort/core.clj:
(defn snailsort
"I sort an n x n grid in a clockwise spiral pattern"
[grid]
(if (is-valid-grid? grid)
(if (= grid [[]])
[]
(let [spiral-path (sequence-path grid)]
(mapv #(get-in grid %) spiral-path)))
nil))
And there you have it. A snailsort function that we can call with a grid which will return the expected result for a valid grid or nil for a bogus grid.
Improving the solution
As you can see, the solution works, but is rather lengthly. I was chatting to a friend who's work colleague, Corneliu Hoffmann, created a solution using the concept of rotating the grid as opposed to trying to walk the grid sequentially. I spent a bit of time thinking about this and decided to try my own implementation using this concept.
Understanding the rotation
Assume we have the following grid:
[[1 2 3]
[4 5 6]
[7 8 9]]
I want to be able to have a result of [1 2 3 6 9 8 7 4 5] for my sorted result. I can take the first row (i.e. [1 2 3]) in order to start my result. This will leave me with the rest.
[[4 5 6]
[7 8 9]]
Now for the rotation, we want to convert the above into a new structure, namely:
[[6 9]
[5 8]
[4 7]]
Then I can take the first row from that (i.e. [6 9]) and join it to my current result (i.e. [1 2 3 6 9]) which will leave me with the rest.
[[5 8]
[4 7]]
And then we repeat the process until there is nothing left. At that point, we can return our result.
What does it look like?
Here is my attempt at this solution.
src/snailsort/core.clj:
(defn rotation-sort
"An alternative solution to snailsort."
[grid]
(when (is-valid-grid? grid)
(loop [acc []
coll grid]
(if (empty? coll)
(flatten acc)
(recur (conj acc (first coll))
(partition (count (rest coll))
(apply interleave
(map reverse (rest coll)))))))))
I think this solution is really interesting. We can get rid of most of the functions we wrote previously. The only two functions we need are the one above, and is-valid-grid? because we still want to validate our input before attempting to sort it. This example shows how a change in perspective can have a significant impact on the approach we end up taking.
Conclusion
I hope you enjoyed reading this post. Hopefully you learned something new along the way. I learned a few things by attending the Clojure coding dojo and working through this solution at home afterwards. I would like to encourage anyone reading this to attend a coding dojo in whichever programming language(s) you're interested in. It's a great way to meet like-minded people and learn new things. I'll definitely be attending more of them myself in the near future.
Top comments (0)