manhattan-distance

The Manhattan distance kata

In this kata, you will learn about another important TDD principle, namely the 1-2-N princple, also known as three strikes and you refactor. This means that before you implement a generic case (N = n), you first implement the case for N = 1, then the case for N = 2, and finally generalize it to N = n.

In this kata, you will first calculate the Manhattan distance between two points in a one-dimensional space (i.e. on a line), and then two points in a plane. Next, you'll be able to generalize it to points located in N-dimensional spaces.

The Manhattan distance

Figure 1: The Manhattan distance is independent of the chosen route and is defined as the sum of the absolute differences in both the x and y coordinates between both points.

The Manhattan distance is the distance between two points in a grid (like the grid-like street geography of the New York borough of Manhattan) calculated by only taking a vertical and/or horizontal path.

The distance only depends on the absolute difference in the x and y coordinates. It does not depend on a particular route that is taken.

You are going to write a function int manhattanDistance(Point, Point) that returns the Manhattan Distance between the two points. From the beginning, it will be our intention to generalize the distance to N dimensions.

Rules

It is extremely important to "play" this kata by the rules, as it also aims to show how to avoid exposing state of a class and instead, implement behavior that logically belongs to this state in that same class (remember: object = state + behavior + identity, also known as tell don't ask principle).

So summarizing, the following rules need to be applied:

• The class Point is immutable (its state cannot be changed after instantiation)
• The class Point has no getters for the coordinates
• The class Point has no public properties (i.e. the internal state cannot be read nor modified from outside the class).

Optional extensions

Determine all shortest paths

For those that are up to a more challenging extension: determine the number of possible shortest paths when the points are two-dimensional (see this web page for a nice graphical representation when the horizontal and vertical distances are equal).

A somewhat more complex extension would be to output all paths explicitly in a sequence of steps, where u is up, d is down, l is left, and r is right. A typical output for two points separated 3 blocks horizontally and 2 vertically would then look something like

llluu
lluul
luull 
uulll
llulu
lullu 
ulllu
lulul 
ullul
ulull