Pete Corey Writing Work Contact

The Captain's Distance Request

This post is written as a set of Literate Commits. The goal of this style is to show you how this program came together from beginning to end. Each commit in the project is represented by a section of the article. Click each section’s header to see the commit on Github, or check out the repository and follow along.

Project Setup

Under the captain’s orders, we’ll be implementing a method that calculates the distance between two points on Earth given in degree/minute/second format.

As always, we’ll get started by creating a new project that uses Babel for ES6 transpilation and Mocha for all of our testing needs.

.babelrc

+{
+  "presets": ["es2015"]
+}

.gitignore

+node_modules/

package.json

+{
+  "main": "index.js",
+  "scripts": {
+    "test": "mocha ./test --compilers js:babel-register"
+  },
+  "dependencies": {
+    "babel-preset-es2015": "^6.9.0",
+    "babel-register": "^6.9.0",
+    "chai": "^3.5.0",
+    "lodash": "^4.12.0",
+    "mocha": "^2.4.5"
+  }
+}

test/index.js

+import { expect } from "chai";
+
+describe("index", function() {
+
+    it("works");
+
+});

The Simplest Test

To get started, we’ll write the simplest test we can think of. We would expect the distance between two identical coordinates to be zero kilometers:


expect(distance(
    "48° 12′ 30″ N, 16° 22′ 23″ E",
    "48° 12′ 30″ N, 16° 22′ 23″ E"
)).to.equal(0);

At first, our test suite does not run. distance is undefined. We can easily fix that by exporting distance from our main module and importing it into our test module.

Now the suite runs, but does not pass. It’s expecting undefined to equal 0. We can fix this by having our new distance function return 0.

index.js

+export function distance(coord1, coord2) {
+    return 0;
+}

test/index.js

 import { expect } from "chai";
+import { distance } from "../";
 
-describe("index", function() {
+describe("The captain's distance", function() {
 
-    it("works");
+    it("calculates the distance between two points", () => {
+        let coord1 = "48° 12′ 30″ N, 16° 22′ 23″ E";
+        let coord2 = "48° 12′ 30″ N, 16° 22′ 23″ E";
+
+        expect(distance(coord1, coord2)).to.equal(0);
+    });

Splitting on Lat/Lon

We can think of our solution as a series of transformations. The first transformation we need to do is splitting our comma separated lat/lon string into two separate strings. One that holds the latitude of our coordinate, and the other that holds the longitude.


expect(splitOnLatLon("48° 12′ 30″ N, 16° 22′ 23″ E")).to.deep.equal([
    "48° 12′ 30″ N",
    "16° 22′ 23″ E"
]);

We can test that a function called splitOnLatLon does just this.

Implementing splitOnLatLon is just a matter of stringing together a few Lodash function calls.

index.js

+import _ from "lodash";
+
+export function splitOnLatLon(coord) {
+    return _.chain(coord)
+        .split(",")
+        .map(_.trim)
+        .value();
+}
+
 export function distance(coord1, coord2) {

test/index.js

 import { expect } from "chai";
-import { distance } from "../";
+import {
+    distance,
+    splitOnLatLon
+} from "../";
 
 ...
 it("calculates the distance between two points", () => {
-        let coord1 = "48° 12′ 30″ N, 16° 22′ 23″ E";
-        let coord2 = "48° 12′ 30″ N, 16° 22′ 23″ E";
+        expect(distance(
+            "48° 12′ 30″ N, 16° 22′ 23″ E",
+            "48° 12′ 30″ N, 16° 22′ 23″ E"
+        )).to.equal(0);
+    });
 
-        expect(distance(coord1, coord2)).to.equal(0);
+    it("splits on lat/lon", () => {
+        expect(splitOnLatLon("48° 12′ 30″ N, 16° 22′ 23″ E")).to.deep.equal([
+            "48° 12′ 30″ N",
+            "16° 22′ 23″ E"
+        ]);
 });

DMS To Decimal

The next step in our transformation is converting our coordinates from their given degree, minute, second format into a decimal format that we can use to calculate distance.

We would expect our new toDecimal function to take in a DMS string and return a decimal interpretation of that lat/lon value.


expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001);

We can represent each DMS string as a regular expression and use ES6 destructuring to easily extract the values we care about:


let regex = /(\d+)° (\d+)′ (\d+)″ ((N)|(S)|(E)|(W))/;
let [_, degrees, minutes, seconds, __, N, S, E, W] = regex.exec(dms);

From there, we do some basic conversions and math to transform the DMS values into their decimal equivilants.

index.js

 ...
 
+export function toDecimal(dms) {
+    let regex = /(\d+)° (\d+)′ (\d+)″ ((N)|(S)|(E)|(W))/;
+    let [_, degrees, minutes, seconds, __, N, S, E, W] = regex.exec(dms);
+    let decimal = parseInt(degrees) +
+                 (parseInt(minutes) / 60) +
+                 (parseInt(seconds) / (60 * 60));
+    return decimal * (N || E ? 1 : -1);
+}
+
 export function distance(coord1, coord2) {

test/index.js

 ...
 distance,
-    splitOnLatLon
+    splitOnLatLon,
+    toDecimal
 } from "../";
 ...
 
+    it("converts dms to decimal format", () => {
+        expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001);
+        expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.2083, 0.001);
+        expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.3730, 0.001);
+        expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.3730, 0.001);
+    });
+
 });

The Haversine Formula

The next step in our transformation is using the two sets of latidudes and longitudes we’ve constructured to calculate the distance between our two points.

We would expect the same two points to have zero distance between them:


expect(haversine(
    48.2083, 16.3730,
    48.2083, 16.3730,
    6371
)).to.be.closeTo(0, 0.001);

And we would expect another set of points to have a resonable amount of distance between them:


expect(haversine(
    48.2083, 16.3730,
    16.3730, 48.2083,
    6371
)).to.be.closeTo(3133.445, 0.001);

The haversize function is a fairly uninteresting implementation of the Haversine Formula. After implementing this formula, our tests pass!

index.js

 ...
 
+export function haversine(lat1, lon1, lat2, lon2, R) {
+    let dlon = lon2 - lon1;
+    let dlat = lat2 - lat1;
+    let a = Math.pow(Math.sin(dlat/2), 2) +
+            Math.cos(lat1) *
+            Math.cos(lat2) *
+            Math.pow(Math.sin(dlon/2), 2);
+    let c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
+    return R * c;
+}
+
 export function distance(coord1, coord2) {

test/index.js

 ...
 splitOnLatLon,
-    toDecimal
+    toDecimal,
+    haversine
 } from "../";
 ...
 it("converts dms to decimal format", () => {
-        expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.2083, 0.001);
-        expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.2083, 0.001);
-        expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.3730, 0.001);
-        expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.3730, 0.001);
+        expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.208, 0.001);
+        expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.208, 0.001);
+        expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.373, 0.001);
+        expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.373, 0.001);
+    });
+
+    it("calculates distance using the haversine formula", () => {
+        expect(haversine(
+            48.2083, 16.3730,
+            48.2083, 16.3730,
+            6371
+        )).to.be.closeTo(0, 0.001);
+
+        expect(haversine(
+            48.2083, 16.3730,
+            16.3730, 48.2083,
+            6371
+        )).to.be.closeTo(3133.445, 0.001);
 });

Finishing the Transformation

Now that we have all of the finished pieces of our transformation we can refactor our distance function.

The basic idea is that we want to split out the lat/lon of each coordinate, convert the DMS coordinates into decimal format, pass the resulting coordinates into haversine and finally round the result.

After doing this refactoring, our tests still pass!

index.js

 ...
 export function distance(coord1, coord2) {
-    return 0;
+    return _.chain([coord1, coord2])
+        .map(splitOnLatLon)
+        .flatten()
+        .map(toDecimal)
+        .thru(([lat1, lon1, lat2, lon2]) => haversine(lat1, lon1, lat2, lon2, 6371))
+        .divide(10)
+        .floor()
+        .multiply(10)
+        .value();
 }

Final Tests and Bug Fixes

After adding in the remaining given tests in the code kata, I noticed I was getting incorrect results form my distance function. After looking at my code, I noticed an obvious error.

My toDecimal function was returning coordinates in degrees, but the haversine function was expecting the coordinates to be in radians.

The fix to our toDecimal function was simply to convert the result to radians by multipling by Math.PI / 180:


return decimal * (N || E ? 1 : -1) * (Math.PI / 180);

After making this change and refactoring our toDecimal tests, all of our tests passed.

index.js

 ...
              (parseInt(seconds) / (60 * 60));
-    return decimal * (N || E ? 1 : -1);
+    return decimal * (N || E ? 1 : -1) * (Math.PI / 180);
 }

test/index.js

 ...
     )).to.equal(0);
+
+        expect(distance(
+            "48° 12′ 30″ N, 16° 22′ 23″ E",
+            "23° 33′ 0″ S, 46° 38′ 0″ W"
+        )).to.equal(10130);
+
+        expect(distance(
+            "48° 12′ 30″ N, 16° 22′ 23″ E",
+            "58° 18′ 0″ N, 134° 25′ 0″ W"
+        )).to.equal(7870);
 });
 ...
 it("converts dms to decimal format", () => {
-        expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(48.208, 0.001);
-        expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-48.208, 0.001);
-        expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(16.373, 0.001);
-        expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-16.373, 0.001);
+        expect(toDecimal("48° 12′ 30″ N")).to.be.closeTo(0.841, 0.001);
+        expect(toDecimal("48° 12′ 30″ S")).to.be.closeTo(-0.841, 0.001);
+        expect(toDecimal("16° 22′ 23″ E")).to.be.closeTo(0.285, 0.001);
+        expect(toDecimal("16° 22′ 23″ W")).to.be.closeTo(-0.285, 0.001);
 });

Final Thoughts

Lately, we’ve been playing around with functional programming and languages like Elixir. Functional languages encourage you to express your programs as a series of pure transformations of your data.

This practice problem definitely shows some influences from that style of thinking. We leaned heavily on Lodash and wrote most of our functions as neatly chained transformations of their arguments.

While Javascript may not be the best language for writing code in this style, I’m a big fan of these kind of functional transformation pipelines. I feel like they produce very clear, very easily to follow functions and programs.

Be sure to check out the Github repo if you want to see the final source for this project!

This article was published on August 10, 2016 under the CodewarsJavascriptLiterate Commits tags. For more articles, visit the archives. Also check out the work I do, and reach out if you’re interested in working together.

– Now that Meteor supports native modules, imports, and exports... Where do we put everything?

– Part one of our Meteor in Front, Phoenix in Back series. Let's put our mad scientist hats on and transplant a Meteor front-end into a Phoenix application!