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!