Clojure Manhattan Distance & Path

Foreword

This tutorial explains what a Manhattan Distance is and how to calculate it in Clojure. It also shows how to generate the Manhattan Path in a functional style by combining a few basic Clojure functions together.

The Euclidean Distance

The common way to calculate the distance between two points is by using the Euclidean Distance.

Here is how it looks for the Points (2, 3) and (5, 6):

How to calculate it:

We can calculate the Euclidean Distance between two points by using the formula

sqrt( (x1-x2)² + (y1-y2)² )

Note: sqrt means Squre Root.

In our example this would be:

Distance between (2, 3) and (5, 6):



sqrt( (2-5)² + (3-6)²)

= sqrt( (-3)² + (-3)² )

= sqrt( 9 + 9 )

= sqrt(18)

= 4.24

The Manhattan Distance

Now let's assume we are driving a taxi through a city like Manhattan, where the streets are in a certain grid layout like this:

And we want to know the distance between the two points. Now the Euclidean Distance (red line) isn't useful here because we can't drive directly through all the buildings. We will have to drive on the street along the grid (green line):

This is what's called the Manhattan Distance. It's important to understand that the blue line in the following picture has exactly the same Manhattan Distance as the green line:

And since we love the simple stuff, we will always use the blue line for our computations.

Here is the formula for the Manhattan Distance:

abs(x1-x2) + abs(y1-y2)

And in our example this would be:

Distance between (2, 3) and (5, 6):



abs(2-5) + abs(3-6)

= abs(-3) + abs(-3)

= 3 + 3

= 6

Manhattan Distance in Clojure

Now let's calculate the Manhattan Distance in Clojure. The function expects two points u and v, it then zips together the x and the y components to [[x1 x2] [y1 y2]], afterwards it subtracts them from each other, makes them absolute with Math/abs and then sums up the results.

The Function:

; (manh-dist [2 3] [5 6]) => 6

(defn manh-dist [u v]

  (reduce +

    (map (fn [[a b]] (Math/abs (- a b)))

         (zip u v))))

Here is the calculation from inside to outside:

; zip x's and y's together:

(zip [2 3] [5 6])

=> ([2 5] [3 6])



; subtract them from each other, make them absolute:

(map (fn [[a b]] (Math/abs (- a b))) [[2 5] [3 6]])

=> (3 3)



; sum of the results

(reduce + [3 3]) => 6

As we can see, it does exactly the same that we did manually before. It even returns the same result.

The Manhattan Path

So far so good. Let's say we are making a simple pixelated 2D game, which means that our game world contains coordinates like (1, 2) or (3, 4) but never (1.56, 6.78). Or in other words: we have our grid again, just like Manhattan.

So if we want to generate a path between two points (shown in green), it will have to look like this:

Manhattan Path in Clojure

If we think about our Manhattan Path, it's really just this:

And this:

Combined to this:

Now that looks a lot like something that we all saw in Clojure before: the range function!

Okay so we'll start by defining a function that takes two points as parameters:

(defn manh-path-px [p1 p2]

  ...

But wait, we want the x and y coordinates of the two points so we might as well use Destructuring again:

(defn manh-path-px [[x1 y1] [x2 y2]]

  ...

We can generate the horizontal points like this:

; for a list of x coordinates it generates points like

; [0, y1]

; [1, y1]

; [2, y1]

; ...

(map (fn [x] [x y1]) (range x1 x2))

Uah wait no!
Range expects the parameters to be from small to high, like (range -3 5). But if we do (range 5 -3) this would be a problem. So let's sort the parameters first:

(apply range (sort [x1 x2]))



; example:

;  for x1=-1 and x2= 3 it calculates (range -1 3) => (-1 0 1 2)

;  for x1= 3 and x2=-1 it calculates (range -1 3) => (-1 0 1 2)

Alright so this is how we generate the horizontal and the vertical points:

; horizontal:

(map (fn [x] [x y1]) (apply range (sort [x1 x2])))



; vertical:

(map (fn [y] [x2 y]) (apply range (sort [y1 y2])))

Now all we have to do is put them together:

(concat

  (map (fn [x] [x y1]) (apply range (sort [x1 x2])))

  (map (fn [y] [x2 y]) (apply range (sort [y1 y2]))))

To avoid weird cases with duplicates, we will just make it a set:

; (manh-path-px [2 3] [5 6])

;  => #{[4 3] [5 4] [3 3] [5 5] [2 3] [5 3]}

(defn manh-path-px [[x1 y1] [x2 y2]]

  (set 

    (concat

      (map (fn [x] [x y1]) (apply range (sort [x1 x2])))

      (map (fn [y] [x2 y]) (apply range (sort [y1 y2]))))))

Summary

The above functions are functional programming at its finest. Instead of writing everything from scratch we simply combined a few very basic Clojure functions, which makes everything much easier to read.

Its important to understand that functions like map, range, concat and set were used in production for several years by thousands of people already. Reusing them is always a good idea and keeps the bugs away!