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.

Written by Pete Corey on Aug 10, 2016.

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!

Module Import Organization

Written by Pete Corey on Aug 8, 2016.

In our last post discussing the benefits of moving your methods, publications, and templates into modules, we mentioned that all of this Meteor-specific functionality relied on modifying global state.

This means that our modules didn’t need to export anything. However, they do need to be imported at least once by your main Meteor application.

Importing these modules executes your calls to Meteor.methods(...), Meteor.publish(...), etc… and makes them accessible to the rest of your application.

Depending on how you structure your imports, this kind of upfront importing can quickly get out of hand.

The Problem With Direct Imports

Imagine we have an /imports/lib folder in our project. Within that folder we break up our application’s functionality into distinct components, like foo and bar. Each component has it’s own set of Meteor methods defined in a methods.js file:


.
└── imports
    └── lib
        ├── bar
        │   └── methods.js
        └── foo
            └── methods.js

To make sure these methods are registered when our application starts, we’ll need to update both our /client/mains.js and our /server/main.js to import these method files:


import "/imports/lib/foo/methods";
import "/imports/lib/bar/methods";

This import structure seems to make sense so far.

It might get more difficult to deal with if we start to aggressively break up our methods, but we’ll put that out of our minds for now.


When we begin adding template modules, our /imports folder structure will quickly begin to balloon in size:


.
└── imports
    ├── client
    │   ├── bar
    │   │   ├── template-1
    │   │   │   ├── template-1.js
    │   │   │   └── template-2.html
    │   │   └── template-2
    │   │       └── ...
    │   └── foo
    │       ├── template-3
    │       │   ├── template-3.js
    │       │   └── template-3.html
    │       └── template-4
    │           └── ...
    └── lib
        ├── bar
        │   └── methods.js
        └── foo
            └── methods.js

Now we’ll have to update our /client/main.js to pull in each of these templates:


import "/imports/lib/foo/methods";
import "/imports/lib/bar/methods";

import "/imports/client/bar/template-1/template-1";
import "/imports/client/bar/template-2/template-2";
import "/imports/client/foo/template-3/template-3";
import "/imports/client/foo/template-4/template-4";

Our /client/main.js file has to keep up with every defined method and template in the system. Similarly, our /server/main.js will have to keep up with ever method definition and publication definition (and potentially every template definition, if we’re using SSR).

This breaks the clean modularity of our system. Our main.js files need to be intimately aware of the structure and implementation of all of our component pieces.

Index Files to the Rescue

Thankfully, index files can lead us out of this increasingly hairy situation.

When an index.js file is present in a directory, attempting to import that directory will cause the index.js file to be imported on its behalf. For example, consider this folder structure:


.
└── baz
    └── index.js

If we import "baz" (import "./baz"), index.js will be imported instead.

We can leverage this to organize our /imports structure and clean up our main.js files. Let’s start by adding an index.js file to each method and template “component”:


.
└── imports
    ├── client
    │   ├── bar
    │   │   ├── template-1
    │   │   │   ├── index.js
    │   │   │   ├── template-1.js
    │   │   │   └── template-2.html
    │   │   └── template-2
    │   │       └── ...
    │   └── foo
    │       └── ...
    └── lib
        ├── bar
        │   │── index.js
        │   └── methods.js
        └── foo
            └── ...

Our /imports/client/bar/template-1/index.js file only needs to be concerned about importing the files related to the template-1 component:


import "./template-1";

Similarly, our /imports/lib/bar/index.js file only needs to be concerned about importing the method and other server-side functionality related to the bar component:


import "./methods.js";

Fantastic. Now, let’s move up in our folder tree, adding index.js files at each step along the way until we hit our client, lib, or server folders:


.
└── imports
    ├── client
    │   ├── index.js
    │   ├── bar
    │   │   ├── index.js
    │   │   ├── template-1
    │   │   │   ├── index.js
    │   │   │   ├── template-1.js
    │   │   │   └── template-2.html
    │   │   └── template-2
    │   │       └── ...
    │   └── foo
    │       └── ...
    └── lib
        ├── index.js
        ├── bar
        │   │── index.js
        │   └── methods.js
        └── foo
            └── ...

Our newly created /imports/client/bar/index.js file is concerned about importing all of the templates and functionality related to the bar component:


import "./template-1";
import "./template-2";

We can finish up our import chain on the client by updating our new /imports/client/index.js file to import the foo and bar client-side components:


import "./bar";
import "./foo";

We can do the same thing in our /imports/lib folder by updating our new /imports/server/index.js file:


import "./bar";
import "./foo";

Finally, we can drastically simplify our /client/main.js and /server/main.js files to only pull in what we need at a very high level.

On the client (/client/main.js), we’ll just want to import client-only and shared components:


import "/imports/lib";
import "/imports/client";

And on the server (/server/main.js), we (currently) only want to import the shared components:


import "/imports/lib";

If we had a set of server-only components we could easily include it there as well.

Reaping the Benefits

I’m a big fan of this structure.

Each level of our dependency tree only has to concern itself with the next level. Our client folder only has to know that it wants to pull in the foo and bar components. It doesn’t need to know which templates those components use. The foo and bar components manage the importing of their templates themselves!

If you wanted to add a new template to the bar component, you’d simply add the template folder into /imports/client/bar/, with an index file that pulls in the required files. Lastly, you’d update /imports/client/bar/index.js to import that new template.

Removing a template is as simple as deleting its folder and removing the import reference from its parent’s index.js file.

Nesting Structure Comparison

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.

Written by Pete Corey on Aug 3, 2016.

Project Setup

The goal of this code kata is to implement a method on the Array prototype that determines when the current array and another array provided as input have the same nested structure.

To get a better idea of what we mean by “nested structure”, these calls to sameStructureAs would return true:


[ 1, 1, 1 ].sameStructureAs( [ 2, 2, 2 ] );
[ 1, [ 1, 1 ] ].sameStructureAs( [ 2, [ 2, 2 ] ] );

And these would return false:


[ 1, [ 1, 1 ] ].sameStructureAs( [ [ 2, 2 ], 2 ] );
[ 1, [ 1, 1 ] ].sameStructureAs( [ [ 2 ], 2 ] );

We’ll start by initializing our project with a basic Babel and Mocha setup.

.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"); + +});

Extending Array

The simplest test we can write to get going is to compare the structure of an empty array to another empty array:


expect([].sameStructureAs([])).to.be.true;

After writing this test, our test suite fails. A naively simple way to get our suite back into the green is to define a very simple sameStructureAs function on the Array prototype that always returns true.

index.js

+Array.prototype.sameStructureAs = function(other) { + return true; +}

test/index.js

+import "../"; import { expect } from "chai"; -describe("index", function() { +describe("sameStructureAs", function() { - it("works"); + it("works", () => { + expect([].sameStructureAs([])).to.be.true; + });

Comparing Types

Next, we’ll add our first real test. We expect an array who’s first element is a Number to have a different structure than an array who’s first element is an Array:


expect([1].sameStructureAs([[]])).to.be.false;

The most obvious way to make this test pass is to check the types of the first element of each array. If both first elements are arrays, or both are not arrays, we’ll return true. Otherwise, we’ll return false.

index.js

+import _ from "lodash"; + Array.prototype.sameStructureAs = function(other) { - return true; + if (_.isArray(this[0]) && _.isArray(other[0])) { + return true; + } + else if (!_.isArray(this[0]) && !_.isArray(other[0])) { + return true; + } + return false; }

test/index.js

... expect([].sameStructureAs([])).to.be.true; + expect([1].sameStructureAs([[]])).to.be.false; });

Generalizing

Now that we have our base case figured out, it’s time to generalize and check the structure of arrays of any length.

To guide us on this process, we added two new tests:


expect([[], []].sameStructureAs([[], []])).to.be.true;
expect([[], 1].sameStructureAs([[], []])).to.be.false;

The general idea is that we’ll want to compare each element of this and other using the same kind of structural comparison we previously wrote. Lodash’s _.zipWith function is a great way of comparing array elements like this:


let comparisons = _.zipWith(this, other, (a, b) => {
    ...
});

Now, comparisons will hold a list of true/false values representing whether the values at that position shared the same structure.

We can use _.every to return true if all comparisons are true, or false otherwise.

During this process, we also did some refactoring of our comparison code, just to clean things up a bit:


let bothArrays = _.isArray(a) && _.isArray(b);
let bothNot = !_.isArray(a) && !_.isArray(b);
return bothArrays || bothNot;

index.js

... Array.prototype.sameStructureAs = function(other) { - if (_.isArray(this[0]) && _.isArray(other[0])) { - return true; - } - else if (!_.isArray(this[0]) && !_.isArray(other[0])) { - return true; - } - return false; + let comparisons = _.zipWith(this, other, (a, b) => { + let bothArrays = _.isArray(a) && _.isArray(b); + let bothNot = !_.isArray(a) && !_.isArray(b); + return bothArrays || bothNot; + }); + return _.every(comparisons); }

test/index.js

... expect([1].sameStructureAs([[]])).to.be.false; + expect([[], []].sameStructureAs([[], []])).to.be.true; + expect([[], 1].sameStructureAs([[], []])).to.be.false; });

Getting Recursive

So far we’ve only handled a single layer of structure. However, the goal of sameStructureAs is to compare the nested structures of our inputs. Consider these examples:


expect([[], [1]].sameStructureAs([[], [1]])).to.be.true;
expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false;

While at first glance this seems to add a lot of complexity, there’s actually a very elegant solution to this problem. When we find two matching arrays in our inputs, all we need to do is ensure that the contents of those arrays have the same structure:


return (bothArrays && a.sameStructureAs(b)) || bothNot;

This recursive call into sameStructureAs will handle any nested depths that we can throw at it (as long as we don’t blow our stack).

index.js

... let bothNot = !_.isArray(a) && !_.isArray(b); - return bothArrays || bothNot; + return (bothArrays && a.sameStructureAs(b)) || bothNot; });

test/index.js

... expect([[], 1].sameStructureAs([[], []])).to.be.false; + expect([[], [1]].sameStructureAs([[], [1]])).to.be.true; + expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false; });

Bug Fixes

Submitting our solution revealed a few bugs in our solution. The first bug can be pointed out with this failing test:


expect([].sameStructureAs(1)).to.be.false;

We were assuming that other would be an array. Unfortunately in this case, other is 1, which causes _.zipWith to return an empty array.

We can fix this bug by adding an upfront check asserting that other is an Array.

After fixing that issue, another bug reared its ugly head:


expect([1].sameStructureAs([1, 2])).to.be.false;

In the last iteration of _.zipWith, a was undefined and b was 2. While checking if both of these values were not arrays returned true, we didn’t check if both values actually existed.

The fix for this bug is to check that both a and b are not undefined:


let bothDefined = !_.isUndefined(a) && !_.isUndefined(b);
let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b);

With those fixes, out suite flips back to green!

index.js

... Array.prototype.sameStructureAs = function(other) { + if (!_.isArray(other)) { + return false; + } let comparisons = _.zipWith(this, other, (a, b) => { let bothArrays = _.isArray(a) && _.isArray(b); - let bothNot = !_.isArray(a) && !_.isArray(b); + let bothDefined = !_.isUndefined(a) && !_.isUndefined(b); + let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b); return (bothArrays && a.sameStructureAs(b)) || bothNot;

test/index.js

... expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false; + expect([].sameStructureAs(1)).to.be.false; + expect([1].sameStructureAs([1, 2])).to.be.false; });

Final Refactor

To make things a little more readable, I decided to move the undefined check into a guard, rather than including it withing the comparison logic of our zipWith function.

After implementing this refactor, our tests still pass.

index.js

... let comparisons = _.zipWith(this, other, (a, b) => { + if (_.isUndefined(a) || _.isUndefined(b)) { + return false; + } let bothArrays = _.isArray(a) && _.isArray(b); - let bothDefined = !_.isUndefined(a) && !_.isUndefined(b); - let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b); + let bothNot = !_.isArray(a) && !_.isArray(b); return (bothArrays && a.sameStructureAs(b)) || bothNot;

Final Thoughts

Looking at the other submitted solutions to this kata, I realize that it’s a fairly interesting problem with lots of possible solutions. There are shorter solutions out there, but I like ours for its readability.

Brevity doesn’t always lead to better code. This is an important lesson that has taken me many years to fully appreciate.

Be sure to check out the final solution on GitHub. If you spot a bug or see a place ripe for improvement, be sure to submit a pull request!