Molecule to Atoms

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 Jul 27, 2016.

Project Setup

Today we’re going to be tackling the Molecule to Atom kata. The goal of this kata is to parse a string representation of a molecule into its component elements, or atoms.

As always, the first step is to get our project set up. We’ll be using Mocha as our test runner and Babel for ES6 support.

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

Laying the Groundwork

The best place to start is at the beginning. We’ll begin solving this kata by writing the most basic test we can think of. We expect an empty string to be parsed into an empty object:


expect(parseMolecule("")).to.deep.equal({});

After writing this test, it fails. parseMolecule is not defined. We can quickly remedy this by importing parseMolecule into our test file and then exporting it from our main module.

Lastly, we need parseMolecule to return an empty object. Just like that, our tests are green.

index.js

+export function parseMolecule(formula) { + return {}; +}

test/index.js

import { expect } from "chai"; +import { parseMolecule } from "../index"; -describe("index", function() { +describe("Molecule to Atoms", function() { - it("works"); + it("it parses a molecule", () => { + expect(parseMolecule("")).to.deep.equal({}); + });

Introducing Our Abstractions

Knowing this solution is going to get complex fairly quickly, we’d like to leverage some abstractions to make it more testable and maintainable.

The most obvious abstraction we can think of is a molecule. We create a molecule by passing in a formula. From there, we can call parse to get an object-based representation of the molecule.

We can rewrite our parseMolecule function to use molecule in a clean way.

index.js

+export function molecule(formula) { + function parse() { + return {}; + } + + return { + parse + }; +} + export function parseMolecule(formula) { - return {}; + return molecule(formula).parse(); }

Testing Hydrogen

Let’s add a new test case:


expect(parseMolecule("H")).to.deep.equal({ H: 1 });

This test fails. It’s expecting {} to equal { H: 1 }.

The fastest way we can get ourselves to green is to return an object that maps the provided formula to 1.


return {
    [formula]: 1
};

After making this change, our first test fails. We now need to explicitly handle this base case:


if (!formula) {
    return {};
}

And now we’re back to green again.

index.js

... function parse() { - return {}; + if (!formula) { + return {}; + } + return { + [formula]: 1 + }; }

test/index.js

... expect(parseMolecule("")).to.deep.equal({}); + expect(parseMolecule("H")).to.deep.equal({ H: 1 }); });

Multiple Elements

Next we’ll move onto parsing a molecule with multiple types of elements. Let’s try to parse "HMg":


expect(parseMolecule("HMg")).to.deep.equal({ H: 1, Mg: 1 });

As expected, this test fails. parse is returning { HMg: 1 }, rather than correctly splitting "H" and "Mg".

To fix this, we’ll need to implement a new method on molecule that will split a formula into a number of parts. We’ll start things off by splitting formulas into its component elements:


formula.match(/[A-Z][a-z]*/g) || [];

The || [] default is required to keep our base case of parsing "" happy.

After rewriting parse to use this new parts method to assemble the molecule object, our tests flip back to green.

index.js

export function molecule(formula) { + function parts() { + return formula.match(/[A-Z][a-z]*/g) || []; + } + function parse() { - if (!formula) { - return {}; - } - return { - [formula]: 1 - }; + return parts().reduce((result, part) => { + result[part] = 1; + return result; + }, {}); } ... return { - parse + parse, + parts };

test/index.js

import { expect } from "chai"; -import { parseMolecule } from "../index"; +import { parseMolecule, molecule } from "../index"; ... expect(parseMolecule("H")).to.deep.equal({ H: 1 }); + expect(parseMolecule("HMg")).to.deep.equal({ H: 1, Mg: 1 }); + }); + + describe("molecule", () => { + it("splits a formula into parts", () => { + expect(molecule("HMg").parts()).to.deep.equal(["H", "Mg"]); + }); });

Compiling Parts

Things are getting more complicated. Instead of just breaking apart our formula and looking for elements, we need to look for pairs of elements and their corresponding count, or ratio in the molecule.

A nice way to do this is using regular expression match groups and ES6 pattern matching. We can define our regex, and wrap the element and optional count in match groups:


let regex = /([A-Z][a-z]*)(\d*)/g;

As we iterate over our regex matches, we can destructure the result into its corresponding element and count pair.

Finally, we refactored parts to return an object with part and count keys to keep things explicit. Thinking ahead, I think this might come in handy when we need to deal with nested expressions.

index.js

... function parts() { - return formula.match(/[A-Z][a-z]*/g) || []; + let parts, results = []; + let regex = /([A-Z][a-z]*)(\d*)/g; + while (parts = regex.exec(formula)) { + let [_, part, count] = parts; + results.push({ + part, + count: parseInt(count) || 1 + }); + } + return results; } ... function parse() { - return parts().reduce((result, part) => { - result[part] = 1; + return parts().reduce((result, {part, count}) => { + result[part] = count; return result;

test/index.js

... expect(parseMolecule("HMg")).to.deep.equal({ H: 1, Mg: 1 }); + expect(parseMolecule("H2Mg")).to.deep.equal({ H: 2, Mg: 1 }); }); ... it("splits a formula into parts", () => { - expect(molecule("HMg").parts()).to.deep.equal(["H", "Mg"]); + expect(molecule("HMg").parts()).to.deep.equal([ + { part: "H", count: 1 }, + { part: "Mg", count: 1 }, + ]); });

Fixing an Edge Case

One thing I noticed while looking over our solution is that it did not support multiple instances of the same element in a molecule. For example, with "HMgH", the last "H" element would override the previous.

I added a test to confirm my suspicions, and quickly fixed the problem. Instead of overriding the element in the result object with count, increment it (if it exists) by count:


result[part] = ~~result[part] + count;

The ~~ operator is rarely seen, but it’s an incredibly useful operator. In this case, if result[part] is undefined, it will be converted to 0, preventing a NaN result from our addition.

index.js

... return parts().reduce((result, {part, count}) => { - result[part] = count; + result[part] = ~~result[part] + count; return result;

test/index.js

... expect(parseMolecule("H2Mg")).to.deep.equal({ H: 2, Mg: 1 }); + expect(parseMolecule("H2MgH")).to.deep.equal({ H: 3, Mg: 1 }); });

Beginning Nested Expressions

Next up on our feature todo list is adding support for nested expressions. A simple nested expressions to get us going could be "[H]Mg". Let’s set our expectations with a test:


expect(parseMolecule("[H]Mg")).to.deep.equal({ H: 1, Mg: 1 });

Now each “part” in our parts method could be either an element, or a nested expressions within square brackets. Let’s update our regular expression to reflect that:


let regex = /(\[(.*)\]|([A-Z][a-z]*))(\d*)/g;

Thanks to the magic of match groups and destructing, we can assign the nested expression (if it exists) to square:


let [_, __, square, part, count] = parts;

Finally, if square exists, let’s recursively process the nested expression and append its parts onto our list of results.

With those changes, our tests flip back to green. Beautiful.

index.js

... let parts, results = []; - let regex = /([A-Z][a-z]*)(\d*)/g; + let regex = /(\[(.*)\]|([A-Z][a-z]*))(\d*)/g; while (parts = regex.exec(formula)) { - let [_, part, count] = parts; - results.push({ - part, - count: parseInt(count) || 1 - }); + let [_, __, square, part, count] = parts; + if (square) { + let nested = molecule(square).parts(); + results = results.concat(nested); + } + else { + results.push({ + part, + count: parseInt(count) || 1 + }); + } }

test/index.js

... expect(parseMolecule("H2MgH")).to.deep.equal({ H: 3, Mg: 1 }); + expect(parseMolecule("[H]Mg")).to.deep.equal({ H: 1, Mg: 1 }); });

Refactoring

Looking forward, the next feature we’ll want to support is using ratios, or count on nested expressions. This means that we’ll need some notion of “multiplying” molecules by some count.

I imagine calling molcule(...).multiply(2) would return a new molecule. This means that multiply will need access to our parsed interpretation of the formula.

We could have multiply call parts, multiply each element by count, serialize the result back into a formula and then create and return a new molecule, but that’s a very roundabout way of doing things.

Instead, let’s define an internal _parts list that’s created every time a molecule is created. The parts method will simply return _parts, and multiply will be able to modify _parts directly.

After doing our refactoring, all of our tests are still passing. We’re safe.

index.js

export function molecule(formula) { - function parts() { - let parts, results = []; - let regex = /(\[(.*)\]|([A-Z][a-z]*))(\d*)/g; - while (parts = regex.exec(formula)) { - let [_, __, square, part, count] = parts; - if (square) { - let nested = molecule(square).parts(); - results = results.concat(nested); - } - else { - results.push({ - part, - count: parseInt(count) || 1 - }); - } + let _parts = []; + + let matches; + let regex = /(\[(.*)\]|([A-Z][a-z]*))(\d*)/g; + while (matches = regex.exec(formula)) { + let [_, __, square, part, count] = matches; + if (square) { + let nested = molecule(square).parts(); + _parts = _parts.concat(nested); + } + else { + _parts.push({ + part, + count: parseInt(count) || 1 + }); } - return results; + } + + function parts() { + return _parts; }

Multiplying Nested Expressions

With that refactor out of the way, we can easily implement multiply. To give ourselves an explicit objective, let’s write a test first:


expect(molecule("H").multiply(2).parse()).to.deep.equal({ H: 2 });

Implementing multiply is straight forward. We just loop over each of the _parts of the molecule, multiplying its count by the provided count. Finally, we return this, so calls to molecule methods can be chained together.

Next, let’s write a test for handling ratios on nested expressions:


expect(parseMolecule("[HO]2Mg")).to.deep.equal({ H: 2, O: 2, Mg: 1 });

This test fails, as expected, but it’s not difficult to get our suite back to green. We just need to build our nested molecule, multiply is by its corresponding count, and finally append its parts onto our results array.

index.js

... let [_, __, square, part, count] = matches; + count = parseInt(count) || 1; if (square) { - let nested = molecule(square).parts(); - _parts = _parts.concat(nested); + let nested = molecule(square).multiply(count); + _parts = _parts.concat(nested.parts()); } ... part, - count: parseInt(count) || 1 + count }); ... + function multiply(count) { + _parts.forEach((part) => { + part.count *= count; + }); + return this; + } + function parts() { ... parse, - parts + parts, + multiply };

test/index.js

... expect(parseMolecule("[H]Mg")).to.deep.equal({ H: 1, Mg: 1 }); + expect(parseMolecule("[HO]2Mg")).to.deep.equal({ H: 2, O: 2, Mg: 1 }); }); ... }); + it("multiplies an object", () => { + expect(molecule("H").multiply(2).parse()).to.deep.equal({ H: 2 }); + }); });

Regex Woes

Unfortunately, there’s a big problem with our solution. Our regex (\[.*\]) is looking for opening and closing brackets and assuming that everything within them are a nested expression.

This assumption breaks down when we have two nested expressions in the same formula, like "[H]O[H]". Our regex will match on the first and very last square brackets, returning "H]O[H" as the nested expression. We can write this as a test to see the failure in action:


expect(molecule("[H]2O[H]").parts()).to.deep.equal([
    { part: "H", count: 2 },
    { part: "O", count: 1 },
    { part: "H", count: 1 }
]);

Switching to a non-greedy regex (\[.*?\]) would still fail, but this time on nested subexpressions, like "[H[O]]".

We need a better way to parse out our formula parts.

Our new solution uses a regex to match on all opening brackets, closing brackets, and elements with a trailing count:


let regex = /((\[)|(\])|([A-Z][a-z]*))(\d*)/g;

Every time we encounter an opening bracket, we push a new formula onto our new stack:


if (open) {
    stack.push({
        formula: ""
    });
}

A non-empty stack means that we’re collecting the pieces of a nested expression. That means we should just append any elements and counts we find to that sub-expression’s formula:


else if (stack.length) {
    stack[stack.length - 1].formula += part + count;
}

Finally, whenever we encounter a closing bracket, we want to create a new molecule out of the nested expression we just collected, and appends its parts onto our list of parts:


else if (close) {
    let nested = molecule(stack.pop().formula).multiply(count);
    _parts = _parts.concat(nested.parts());
}

Now we’re properly processing sub-expressions and our tests return to green.

index.js

... let matches; - let regex = /(\[(.*)\]|([A-Z][a-z]*))(\d*)/g; + let stack = []; + let regex = /((\[)|(\])|([A-Z][a-z]*))(\d*)/g; while (matches = regex.exec(formula)) { - let [_, __, square, part, count] = matches; + let [_, __, open, close, part, count] = matches; count = parseInt(count) || 1; - if (square) { - let nested = molecule(square).multiply(count); + if (open) { + stack.push({ + formula: "" + }); + } + else if (close) { + let nested = molecule(stack.pop().formula).multiply(count); _parts = _parts.concat(nested.parts()); } + else if (stack.length) { + stack[stack.length - 1].formula += part + count; + } else {

test/index.js

... ]); + expect(molecule("[H]2O[H]").parts()).to.deep.equal([ + { part: "H", count: 2 }, + { part: "O", count: 1 }, + { part: "H", count: 1 } + ]); });

Alternate Groupings and Bug Fixes

Last up on our feature list is the ability to use parentheses and curly brackets in addition to square brackets as sub-expression dividers.

We can add a test for this:


expect(parseMolecule("K4{ON(SO3)2}2")).to.deep.equal({K: 4, O: 14, N: 2, S: 4});

The most straight-forward way to accomplish this is to just replace all "{" and "(" characters with "[", and "}" and ")" characters with "]" in our formula:


formula.replace(/[{(]/g, "[").replace(/[})]/g, "]");

Unfortunately, this test also exposed another bug in our solution. it looks like counts on sub-expressions aren’t being applied to other nested expressions.

We can fix this by giving our stack a bit more state. In addition to building up our current expressions’s formula as we go, we also want to keep track of any nested molecules we encounter, so we can multiply them by our count.

After making this change, all of our tests pass.

index.js

... + formula = formula.replace(/[{(]/g, "[").replace(/[})]/g, "]"); + let matches; ... stack.push({ - formula: "" + formula: "", + molecules: [] }); ... else if (close) { - let nested = molecule(stack.pop().formula).multiply(count); - _parts = _parts.concat(nested.parts()); + let popped = stack.pop(); + popped.molecules.push(molecule(popped.formula)); + popped.molecules.forEach((molecule) => { + molecule.multiply(count); + }); + if (!stack.length) { + popped.molecules.forEach((molecule) => { + _parts = _parts.concat(molecule.parts()); + }); + } + else { + let last = stack[stack.length - 1]; + last.molecules = last.molecules.concat(popped.molecules); + } }

test/index.js

... expect(parseMolecule("[HO]2Mg")).to.deep.equal({ H: 2, O: 2, Mg: 1 }); + expect(parseMolecule("K4{ON(SO3)2}2")).to.deep.equal({K: 4, O: 14, N: 2, S: 4}); + expect(parseMolecule("{[Co(NH3)4(OH)2]3Co}(SO4)3")).to.deep.equal({ + Co: 4, + N: 12, + H: 42, + O: 18, + S: 3 + }); });

Final Thoughts

This was a doozy of a kata.

All in all, there are a lot of ideas flying around here and I fear I didn’t explain myself as well as I could have. Balancing trying to keep things as concise, while staying true to the intent of explaining every change is definitely a challenge.

The limitations of regular expressions are explored in this problem was well. Initially, a totally regex based solution seemed like a good approach, but the nested structure of our data made regexes difficult to use.

When using regexes, it’s always important to keep in mind that there are entire classes of problem where they’re simply not suitable.

Finally, my final solution isn’t as clean and clear as I would have liked. By the time I landed on a working solution, I feared that more refactor commits would have muddied the water. In future problems, I need to focus on refactoring sooner and more often.

Mocha's Grep Flag

Written by Pete Corey on Jul 25, 2016.

Mocha’s grep flag (-g, or --grep) is amazing. I very recently learned about this helpful tool, and it’s significantly improved my testing workflow.

The grep flag gives you the ability to focus on specific tests with zero code changes, even if the set of tests you want to run are spread across separate describe blocks!

I recently found myself in a situation where an ugly, manual process of zeroing in on tests was drastically simplified with the grep flag.

The Situation

One of my client projects has a very large, very complicated Mocha test suite. Many of the tests in this suite are generated programmatically (whether or not this is a good idea is a topic for another day…).

One of the motivations for generating tests dynamically is that we have multiple “transports” (Twilio SMS, Facebook Messenger, web chat, etc…) for communicating with users. On each of these transports, we want to run through a set of test scenarios and ensure that they all behave as expected:


[
    "twilio",
    "facebook",
    "web"
].forEach((transport) => {
    describe(`Scenarios for ${transport}:`, function() {
        it("sends a message", function() {
            ...
        });
        ...
    });
});

Sometimes, it’s helpful to see just the output of these transport scenario tests instead of the output of the entire test suite.

My initial instinct for zeroing in on these transport scenario tests is to change describe to describe.only. Unfortunately, if Mocha finds multiple describe.only calls, it will only run the tests in the last describe.only block it encounters. This means that only my "web" transport tests would run.

To see the results of all three transport tests, I’d have to run my tests in three passes, once for each transport:


[
    "twilio",
    // "facebook",
    // "web"
].forEach((transport) => {
    describe.only(...

[
    // "twilio",
    "facebook",
    // "web"
].forEach((transport) => {
    describe.only(...

[
    // "twilio",
    // "facebook",
    "web"
].forEach((transport) => {
    describe.only(...

This is not a good solution.

This kind of code juggling opens the doors for bugs to be introduced into my test suite and makes it impossible to watch all three transport tests at once.

Mocha Grep

It turns out that Mocha already has a solution to my problem.

If you read through the Mocha documentation, you may notice a section on the “grep flag” (-g, or --grep):

-g, –grep <pattern> only run tests matching <pattern>

When using this flag, Mocha will search through your tests and only run tests whose descriptions match the provided pattern. This means we can run our whole test suite and grep for "Scenarios" tests:


mocha -g "Scenarios for"

And just like that, our "twilio", "facebook", and "web" transport scenarios are detected and run by Mocha.

We can get more complex with our search. Let’s run just the "twilio" and "web" scenarios:


mocha -g "Scenarios for twilio|Scenarios for web"

We can even use the watch flag (-w, or --watch) to watch the results of our test search for changes:


mocha -w -g "Scenarios for twilio|Scenarios for web"

Final Thoughts

It’s always a good idea to thoroughly read the documentation of all of the tools you use on a regular basis.

You may be surprised to find that they’re much more powerful than you first realized.

TL;DR: RTFM.

Point in Polygon

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 Jul 20, 2016.

Project Setup

The goal of today’s kata is to implement a function called pointInPoly. pointInPoly is called with a polygon represented as a series of points as the first argument, and a single point at the second argument. Each point is represented as a set of [x, y] coordinates, where both x and y are numbers. pointInPoly should return true if the point is within the defined polygon, and false if it is not.

The kata description points out several assumptions we can make about the inputs: 1) The polygon will be a valid simple polygon. That is, it will have at least three points, none of its edges will cross each other, and exactly two edges will meet at each vertex. 2) In the tests, the point will never fall exactly on an edge of the polygon.

And lastly, although the description never explicitly says so, we’re assuming that the points in the polygon are given in order; each point shares an edge with the next.

This initial commit sets up our initial project.

.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", function() { + expect(2+2).to.equal(4); + }); + +});

The Simplest Test

The first thing we do when we’re solving a problem like this is to write a test. Because we’re implementing a function given to us, we already know what our final interface will look like (pointInPoly), so we can immediately write a test for it.

Our first test asserts that a point at the origin ([0, 0]) is within a simple triangle with points at [-1, -1], [1, -1], and [0, 1].

After writing this test, our test suite complains that pointInPoly is not defined. This is quickly fixed by importing pointInPoly into our test file and then exporting it from index.js.

After exporting the empty pointInPoly function, the test suite shouts that it expected undefined to be true. To bring us back to green we change our new pointInPoly function to return true.

index.js

+export function pointInPoly(poly, point) { + return true; +}

test/index.js

import { expect } from "chai"; +import { pointInPoly } from "../"; -describe("index", function() { +describe("pointInPoly", function() { - it("works", function() { - expect(2+2).to.equal(4); + it("detects a point in a triangle", function() { + let poly = [[-1, -1], [1, -1], [0, 1]]; + expect(pointInPoly(poly, [0, 0])).to.be.true; });

Fleshing Out a Strategy

We knew that our initial pointInPoly solution was incomplete. Returning true for all cases obviously wasn’t going to work. But what do we do instead? How do we even begin to tackle this problem?

Thankfully, from my days of video game programming I know that a simple test for checking if a point lies within a polygon is to send a ray outward from that point. If the ray intersects with the lines of the polygon an odd number of times, the point lies within the polygon. Otherwise, it’s outside.

Since we’re in a green state, we can do a little refactoring and implement a high level version of this solution. We want to count the number of intersections between our imaginary ray and our polygon:


let intersections = countIntersections(poly, point);

And then return true if that count is odd, or false if it’s even:


return !!(intersections % 2);

After making these changes, our test suite complains that countIntersections does not exist, so let’s quickly define it and have it return 1 to bring us back to green.

index.js

+function countIntersections(poly, point) { + return 1; +} + export function pointInPoly(poly, point) { - return true; + let intersections = countIntersections(poly, point); + return !!(intersections % 2); }

Rethinking Our Interfaces

After some soul-searching, I decided I wasn’t happy with where we were going with our previous solution. countIntersections was really an “internal method”. Outside of the context of our point-in-polygon problem, a function called countIntersections that takes in a poly and a point really just doesn’t make any sense.

Because it was an internal method, I was hesitant to write tests for it. These tests would be too closely coupled with our implementation, and would make refactoring difficult. Additionally, countIntersections would most likely call other methods would be even more contextually dependant and awkward to test.

We needed a cleaner solution.

After reconsidering the problem, it’s clear that we’re dealing with a few really solid abstractions. The most apparent is a polygon. If we implement a generic polygon, we’d be able to cleanly specify what we want from our pointInPoly method:


function pointInPoly(poly, point) {
    return polygon(poly).surrounds(point);
}

Additionally, by breaking polygon out into a new abstraction, we can freely build and test its interface to our heart’s content.

With this in mind, we wrote a new set of tests that describe polygon. The first tests looks nearly identical to our pointInPoly tests and checks if a polygon surrounds a point.

Our dummy implementation of polygon.surrounds simply returns true.

polygon.js

+export function polygon(_points) { + + let surrounds = (point) => true; + + return { + surrounds + }; +}

test/polygon.js

+import { expect } from "chai"; +import { polygon } from "../polygon"; + +describe("polygon", function() { + + it("checks if a polygon surrounds a point", function() { + let poly = polygon([[-1, -1], [1, -1], [0, 1]]); + expect(poly.surrounds([0, 0])).to.be.true; + }); + +});

Restating Point-in-Polygon

Now that we’ve defined our polygon, we can restate our implementation of surrounds. We want to translate our polygon so that the point we’ve been given can be treated as the origin. Next we want to count the number of intersections that an arbitrary ray ([0, 1]) makes with the newly translated polygon:


let intersections = translate([-x, -y]).intersections([0, 1]);

Lastly we want to return true from surrounds if intersections is odd:


return !!(intersections % 2);

After making these changes, our test suite complains about translate and intersections not being defined.

The fastest way to get us back to green is to have translate return a new polygon, and have intersections return 1.

polygon.js

... - let surrounds = (point) => true; + let surrounds = ([x, y]) => { + let intersections = translate([-x, -y]).intersections([0, 1]); + return !!(intersections % 2); + }; + + let translate = ([x, y]) => { + return polygon(_points); + }; + + let intersections = (ray) => 1; return { - surrounds + surrounds, + translate, + intersections };

Translate Base Case

Now we can start testing the component pieces of our surrounds function.

First up, let’s write a test for translate. A straight-forward base case for translate asserts that calling translate on an empty polygon ([[]]) should return an empty polygon.

After writing this test, I realized that I needed a function to return the points from a polygon. Thus, points was born.


let points = () => _points;

Suprisingly, our naive solution also works for all calls to translate where x and y are zero.

polygon.js

... + let points = () => _points; + return { ... translate, - intersections + intersections, + points };

test/polygon.js

... + it("translates a polygon", function() { + expect(polygon([]).translate([0, 0]).points()).to.deep.equal([]); + }); + });

Finishing Translate

Adding a more complicated test of translate shows that we need a better solution. Thankfully, it isn’t a huge leap to come up with the final form of the function.

The translate function returns a new polygon where every point in the polygon has been incremented by the provided x and y values.

polygon.js

... let translate = ([x, y]) => { - return polygon(_points); + return polygon(_points.map(p => [p[0] + x, p[1] + y])); };

test/polygon.js

... expect(polygon([]).translate([0, 0]).points()).to.deep.equal([]); + expect(polygon([ + [0, 0], [5, -5] + ]).translate([1, 1]).points()).to.deep.equal([ + [1, 1], [6, -4] + ]); });

Line Abstraction

Now we turn out attention to the intersections function. This still seems like a daunting piece of functionality, and we should break it down into simpler pieces, if possible.

If we’re not afraid of making use of another abstraction (line), a simple implementation of intersections could be written like this:


return lines().filter(line => line.intersects(ray)).length;

In plain english, this reads as “return the number of lines in this polygon that intersect the given ray”.

This is a nice solution. To make it a reality, let’s create a new set of tests for our new line abstraction and a dummy implementation of line and line.intersects.

line.js

+export function line(a, b) { + + let intersects = (ray) => true; + + return { + intersects + }; +}

test/line.js

+import { expect } from "chai"; +import { line } from "../line"; + +describe("line", function() { + + it("checks if the line intersects a ray", function() { + expect(line([0, 1], [1, 0]).intersects([1, 1])).to.be.true; + }); + +});

Finishing Line

Adding another test against line.intersects shows that we need a better solution.

Determining if a line intersects with a ray is a well-documented problem. I used this blog post as a guide for implementing my solution. Be sure to check it out for details on the math being used here.

line.js

... - let intersects = (ray) => true; + function cross(v1, v2) { + return (v1[0] * v2[1]) - (v1[1]*v2[0]); + } + + function dot(v1, v2) { + return v1[0] * v2[0] + v1[1] + v2[1]; + } + + let intersects = (ray) => { + let v1 = [-a[0], -a[1]]; + let v2 = [b[0] - a[0], b[1] - a[1]]; + let v3 = [-ray[1], ray[0]]; + + let t1 = cross(v2, v1) / (dot(v2, v3)); + let t2 = (dot(v1, v3)) / (dot(v2, v3)); + + return t1 >= 0 && (t2 >= 0 && t2 <= 1); + };

test/line.js

... expect(line([0, 1], [1, 0]).intersects([1, 1])).to.be.true; + expect(line([0, 1], [1, 0]).intersects([-1, -1])).to.be.false; });

Finishing Intersections

Now that line and line.intersects exist, we can implement our polygon.intersections method.

As usual, we start by adding a test for intersections, and then we make our test suite happy by importing line, and creating the polygon.lines function.

polygon.js

+import { line } from "./line"; + export function polygon(_points) { ... - let intersections = (ray) => 1; + let intersections = (ray) => { + return lines().filter(line => line.intersects(ray)).length; + }; ... + let lines = () => { + return [line([-1, 1], [1, 1])]; + } + return { ... intersections, - points + points, + lines };

test/polygon.js

... + it("counts intersections with a ray", function() { + let poly = polygon([[-1, -1], [1, -1], [0, 1]]); + expect(polygon([ + [-1, -1], [1, -1], [0, 1] + ]).intersections([0, 1])).to.equal(1); + }); + });

Constructing Lines

Finally, all we need to do to complete our solution is to build our polygon.lines function. This function should transform the set of _points that were used to define our polygon into a set of line objects.

We implement a test for polygon.lines and use it to drive the creation of our solution. Don’t forget that the last point in the polygon must connect back to the first!

line.js

... + let points = () => [a, b]; + return { - intersects + intersects, + points };

polygon.js

... let lines = () => { - return [line([-1, 1], [1, 1])]; + if ((!_points) || !_points.length) { + return []; + } + + let last = _points[0]; + let pairs = _points.slice(1).map((point) => { + let segment = line(last, point); + last = point; + return segment; + }); + pairs.push(line(_points[_points.length - 1], _points[0])); + + return pairs; }

test/polygon.js

... + it("creates lines for a polygon", function() { + let lines = polygon([ + [-1, -1], [1, -1], [0, 1] + ]).lines(); + expect(lines.map((line) => line.points())).to.deep.equal([ + [[-1, -1], [1, -1]], + [[1, -1], [0, 1]], + [[0, 1], [-1, -1]] + ]); + }); + });

Pull it all Together

Now that all of our building blocks are finalized, we can come back to our original pointInPoly method and rewrite it exactly how we had imagined:


return polygon(poly).surrounds(point);

After making this change, our test suite is still green. Everything is working as expected.

index.js

-function countIntersections(poly, point) { - return 1; -} +import { polygon } from "./polygon"; export function pointInPoly(poly, point) { - let intersections = countIntersections(poly, point); - return !!(intersections % 2); + return polygon(poly).surrounds(point); }

Final Test & Bug Fix

At this point, our solution should be finished. However, when we feed in the tests provided by the kata, we notice a failure.

After digging into what’s happening, we notice that the system was claiming that a line, line([4, -6], [4, 4]), was intersecting with a ray, [0, 1]. Clearly, this is incorrect.

To find out what was causing this, we write a new test against the line.intersects function:


expect(line([4, -6], [4, 4]).intersects([0, 1])).to.be.false;

As expected, this test fails.

After some poking, prodding, and comparing against reference equations, we notice a typo in the dot function. After fixing the dot production calculation, our entire test suite shifts back to a passing state.

Success!

line.js

... function dot(v1, v2) { - return v1[0] * v2[0] + v1[1] + v2[1]; + return v1[0] * v2[0] + v1[1] * v2[1]; }

test/index.js

... + it("detects a point in a square", function() { + var poly = [ + [-5, -5], [5, -5], + [5, 5], [-5, 5] + ]; + + expect(pointInPoly(poly, [-6, 0])).to.be.false; + expect(pointInPoly(poly, [1, 1])).to.be.true; + }); + });

test/line.js

... expect(line([0, 1], [1, 0]).intersects([-1, -1])).to.be.false; + expect(line([4, -6], [4, 4]).intersects([0, 1])).to.be.false; });

Wrap-up

When you compare our solution with other submitted solutions, you’ll notice that ours is longer. Our solution probably took much longer to write as well. However, our solution was a fantastic exercise in deliberate practice.

By consciously focusing on writing robust and maintainable code, we had a few introspective moments about our process and our technique.

The first major insight that we had came when we realized we were going down a bad road with the countIntersections method. By creating additional abstractions, we ended up with more testable, maintainable and re-usable code.

At the very end of the process we found a bug in the solution. Thanks to our test suite we were able to almost immediately find the source of the bug and fix it.

Be sure to check out the full project, complete with detail commit messages on GitHub.