Delete Occurrences of an Element

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 11, 2016.

Laying the Groundwork

Today we’ll be tackling a code kata called “Delete occurrences of an element if it occurs more than n times” (what a catchy name!). The goal of this kata is to implement a function called deleteNth. The function accepts a list of numbers as its first parameter and another number, N, as its second parameter. deleteNth should iterate over each number in the provided list, and remove and numbers that have appeared more than N times before returning the resulting list.

While this is a fairly simple problem, we’re going to solve it in a very deliberate way in order to practice building better software.

This first commit lays the groundwork for our future work. We’ve set up a simple Node.js project that uses Babel for ES6 support and Mocha/Chai for testing.

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

Take What We’re Given

One of the challenges of real-world problems is teasing out the best interface for a given task. Code katas are different from real-world problems in that we’re usually given the interface we’re supposed to implement upfront.

In this case, we know that we need to implement a function called deleteNth which accepts an array of numbers as its first argument (arr), and a number, N, as its second parameter (x).

Eventually, deleteNth will return an array of numbers, but we need to take this one step at a time.

index.js

+function deleteNth(arr,x){ + // ... +}

Our First Test

Writing self-testing code is a powerful tool for building robust and maintainable software. While there are many ways of writing test code, I enjoy using Test Driven Development for solving problems like this.

Following the ideas of TDD, we’ll write the simplest test we can that results in failure. We expect deleteNth([], 0) to return an empty array. After writing this test and running our test suite, the test fails:


deleteNth is not defined

We need to export deleteNth from our module under test and import it into our test file. After making those changes, the test suite is still failing:


expected undefined to deeply equal []

Because our deleteNth method isn’t returning anything our assertion that it should return [] is failing. A quick way to bring our test suite into a passing state is to have deleteNth return [].

index.js

-function deleteNth(arr,x){ - // ... +export function deleteNth(arr,x){ + return [];

test/index.js

+import { deleteNth } from "../"; ... -describe("index", function() { +describe("deleteNth", function() { ... - it("works"); + it("deletes occurrences of an element if it occurs more than n times", function () { + expect(deleteNth([], 0)).to.deep.equal([]); + });

Keep it Simple

Interestingly, our incredibly simple and incredibly incorrect initial solution for deleteNth holds up under additional base case tests. Any calls to deleteNth with a zero value for N will result in an empty array.

test/index.js

... + expect(deleteNth([1, 2], 0)).to.deep.equal([]);

Forging Ahead

As we add more test cases, things begin to get more complicated. In our next test we assert that deleteNth([1, 2], 1) should equal [1, 2]. Unfortunately, our initial solution of always returning an empty array failed in this case.


expected [] to deeply equal [ 1, 2 ]

We know that all calls to deleteNth where x is zero should result in an empty array, so lets add a guard that checks for that case.

If x is not zero, we know that our test expects us to return [1, 2] which is being passed in through arr. Knowing that, we can bring our tests back into a green state by just returning arr.

index.js

... - return []; + if (x == 0) { + return []; + } + return arr;

test/index.js

... + + expect(deleteNth([1, 2], 1)).to.deep.equal([1, 2]);

Getting Real

We added a new test case, and things suddenly became very real. Our new test expects deleteNth([1, 1, 2], 1) to return [1, 2]. This means that the second 1 in the input array should be removed in the result. After adding this test, our test suite groans and slips into a red state.

It seems that we have to finally begin implementing a “real” solution for this problem.

Because we want to conditionally remove elements from an array, my mind initially gravitates to using filter. We replace our final return statement with a block that looks like this:


return arr.filter((num) => {
  return seenNum <= x;
});

Our filter function will only pass through values of arr that we’ve seen (seenNum) no more than x times. After making this change our test suite expectedly complains about seenNum not being defined. Let’s fix that.

To know how many times we’ve seen a number, we need to keep track of each number we see as we move through arr. My first instinct is to do this with a simple object acting as a map from the number we seen to the number of times we’ve seen it:


let seen = {};

Because seen[num] will initially be undefined we need to give it a default value of 0:


seen[num] = (seen[num] || 0) + 1;

Our test suite seems happy with this solution and flips back into a green state.

index.js

... - return arr; + let seen = {}; + return arr.filter((num) => { + seen[num] = (seen[num] || 0) + 1; + let seenNum = seen[num]; + return seenNum <= x; + });

test/index.js

... + expect(deleteNth([1, 1, 2], 1)).to.deep.equal([1, 2]);

Simplifying the Filter

After getting to a green state, we notice that we can refactor our filter and remove some duplication.

The seenNum variable is unnecessary at this point. Its short existence helped us think through our filter solution, but it can easily be replaced with seen[num].

index.js

... - let seenNum = seen[num]; - return seenNum <= x; + return seen[num] <= x;

Removing the Base Case

While we’re on a refactoring kick, we also notice that the entire zero base case is no longer necessary. If N (x) is zero, our filter function will happily drop every number in arr, resulting in an empty array.

We can remove the entire if block at the head of our deleteNth function.

index.js

... - if (x == 0) { - return []; - }

Final Tests

At this point, I think this solution solves the problem at hand for any given inputs. As a final test, I add the two test cases provided in the kata description.

Both of these tests pass. Victory!

test/index.js

... + + expect(deleteNth([20, 37, 20, 21], 1)).to.deep.equal([20, 37, 21]); + expect(deleteNth([1, 1, 3, 3, 7, 2, 2, 2, 2], 3)).to.deep.equal([1, 1, 3, 3, 7, 2, 2, 2]);

Final Refactoring

Now that our tests are green and we’re satisfied with the overall shape of our final solution, we can do some final refactoring.

Using the underrated tilde operator, we can simplify our seen increment step and merge it onto the same line as the comparison against x. Next, we can leverage some ES6 syntax sugar to consolidate our filter lambda onto a single line.

index.js

... - return arr.filter((num) => { - seen[num] = (seen[num] || 0) + 1; - return seen[num] <= x; - }); + return arr.filter((num) => (seen[num] = ~~seen[num] + 1) <= x);

Wrap-up

This was an excellent demonstration of how following test-driven development ideas can give you supreme confidence when refactoring your code. We were able to gut entire sections out of our solution and then completely transform it with zero trepidation.

Overall, our solution looks very similar to the other submitted solutions for this kata.

My one regret with this solution is using the double tilde operator (~~). While it does make our final solution quite a bit shorter, it adds confusion to the solution if you’re not familiar with how ~~ works.

Be sure to check out the final project on Github!

Winston and Meteor 1.3

Written by Pete Corey on Jul 4, 2016.

Logging is a very important part of any production application. Quality logging provides invaluable, irreplaceable information about the inner workings of your application as it runs.

Winston is a great tool for providing a unified logging interface for a variety of log transports (the console, rotating files, third party services, etc…).

Unfortunately, some of the intricacies of Meteor’s isomorphic build system make using Winston more difficult that it would seem at first glance.

Setting Up Winston

In Meteor 1.3, adding Winston to your project is as simple as installing the NPM package:


meteor npm install winston

Thanks to its stellar documentation, setting up Winston as an ES6 module in your Meteor project is fairly straight forward too:


import winston from "winston";

let console = new winston.transports.Console({
    name: "console",
    timestamp: true
});

export const logger = new winston.Logger({
    transports: [
        console
    ]
});

Now that logger is being exported by our new module, it can be imported anywhere else in the project and used to log vital information:


import { logger } from "/imports/logger";

logger.info("Party time! 🎉");

While this works beautifully on the server, we’ll quickly run into issues when we start up our application and try to do some logging from the client.

Troubles on the Client

After starting up the application, you may see an error like the following in your browser console:


TypeError: fs.readdirSync is not a function

If you spend some time Googling this obtuse error, you’ll eventually land on this open Github issue which explains that Winston currently doesn’t support in-browser logging.

This unfortunate information leaves us with two options. We can either restrict imports of our logger module to only server-side components, or we can wrap our import winston and export logger statements in a Meteor.isServer guard.

Because the first option would be difficult to manage and would be a constant source of bugs, a reasonable solution would be to choose the second option:


import { Meteor } from "meteor/meteor";

if (Meteor.isServer) {

    import winston from "winston";

    let console = new winston.transports.Console({
        name: "console",
        timestamp: true
    });

    export const logger = new winston.Logger({
        transports: [
            console
        ]
    });
    
}

Now that Winston is confined to the server, our client is happy.

A Tale of Two Loggers

Unfortunately, this solutions leaves us in an awkward position. On the server, we can import and use our new logger, but on the client we’re forced to continue using console for all of our logging needs.

Isomorphic code, or code that runs on both the server and the client, amplifies the awkwardness of this situation.

Imagine that a collection has a helper method which can be called from both the client and the server. How would we log an error in that helper? If we’re on the client, we’d have to use console.log or console.error, but if we’re on the server we would want to use logger.error:


Collection.helpers({
    foo() {
        return something()
        .catch((e) => {
            if (Meteor.isServer) {
                logger.error(e);
            }
            else {
                console.error(e);
            }
        });
    }
});

This is far from an ideal situation. Ideally, we’d like to be able to use logger across the board, regardless of if we’re on the client or server.

Creating a Faux-Logger

Thankfully, we can make this ideal situation a reality.

Back in our logger module, we can detect if we’re being imported on the client and, if we are, export an object that looks like a Winston logger, but is actually console.


if (Meteor.isServer) {
    …
}
else {
    export const logger = console;
}

On Chrome this works just as we would expect. If we import logger on the client we can use logger.info, logger.warn, and logger.error because Chrome implements all of these methods (info, warn, and error) in its built-in console object.

However, if you want to target other browsers or environments that don’t natively implement all of these logging methods, we’ll have to implement them in our faux-logger ourselves:


if (Meteor.isServer) {
    …
}
else {
    export const logger = {
        info: console.log,
        warn: console.log,
        error: console.log
    };
}

We can even take this solution to the next level by decorating our calls to console.log and prepending whatever information we need:


function prepend(argument) {
    return function() and{
        let args = [].slice.call(arguments);
        args.unshift(argument);
        console.log.apply(console, args);
    }
}

export const logger = {
    info: console.log,
    warn: prepend("⚠️"),
    error: prepend("☠️")
};

Now our logger module can be imported and used as expected throughout our entire code base.

The browser’s underlying logging framework will be used on the client, and Winston will be used on the server. While the underlying logging changes depending on context, our developer experience does not.

A New Look For East5th

Written by Pete Corey on Jun 27, 2016.

Things may look a bit different around here. I’m excited and relieved to finally release a design overhaul that I’ve been working on for the past several weeks.

The main goal of this redesign is to bring all things East5th under a single roof. No longer are things haphazardly scattered between three different subdomains and a variety of hosting services. Everything we have to offer can now be found at www.east5th.co.

All of our old blog content is still alive and well and can now be found at www.east5th.co/blog/. Be sure to check out our newly unified services page, and our brand new collection of case-studies.


When we get down to the nitty gritty details, things are still fundamentally the same. Now, the entire site is a collection of static pages built and generated with Jekyll.

Keeping things simple, we’re still relying on Github Pages for hosting, and using our previously described Zapier setup to schedule and release future blog posts.

Scheduling Posts With Jekyll, Github Pages & Zapier
Zapier Named Variables - Scheduling Posts Part 2

Last, but not least, we’re using a slightly modified Prism for all of our inline and block syntax highlighting needs.


This redesign is just the beginning on a larger set of infrastructure changes planned for East5th.

One of these upcoming changes will involve building out a Meteor backend application that communicates with a Serverless microservice. I’m planning on documenting and publishing the entire process behind building this service.

Stay tuned!