For fun and relaxation, I sometimes work on coding puzzles at sites like HackerRank (here’s a good summary of various coding challenge sites). Today I was working on what HackerRank calls “the staircase problem.” Basically, if you’re given some integer n, output a “staircase” of symbols that is n stair steps high. For example if n = 4, the staircase would look like:
# ## ### ####
For someone who’s been coding as long as I have, this is a trivially simple problem to solve using traditional imperative programming constructs, e.g.
function outputStaircaseOfSize(n) {
for (let i = 0; i < n; i += 1) {
let output = "";
for (let j = 0; j < n; j += 1) {
output += j < n - 1 - i ? " " : "#";
}
console.log(output);
}
}
outputStaircaseOfSize(4);
// #
// ##
// ###
// ####
However, of late I’ve been trying to break my old imperative habits, and instead replace them with functional programming practices. (I’ve probably been most influenced to follow this path by Eric Elliott.) For-loops are typically a big red flag that you are using imperative programming. I decided to see if I could write this code without loops.
Declarative Array Creation
Typically in JavaScript we declare an array just by putting the elements we want to be in the array within square brackets, like so:
let fruit = [ "apple", "banana", "pear" ]; // initialized with 3 values console.log(fruit.length); // 3 let output = []; // initialized as an empty array console.log(output.length); // 0
Indeed, the MDN documentation of the JavaScript Array class suggests that this is the most straightforward way to work with arrays. However, tucked within this page are the details of what happens if you want to use the Array() constructor function. To accomplish the exact same thing we did above using the constructor we would do:
let fruit = Array("apple", "banana", "pear"); // initialized with 3 values
console.log(fruit); // [ 'apple', 'banana', 'pear' ]
let output = Array(); // initialized as an empty array
console.log(output); // []
If the Array() constructor is called with only a single parameter, and that parameter is an integer, JavaScript will initialize an array with the specified number of empty slots. Assuming you’d like to fill those slots with some default content, you can use the Array.fill() function to do so. Array.fill() can even take an array as a parameter:
let a = Array(3);
console.log(a); // [ <3 empty items> ]
let b = Array(3).fill("#");
console.log(b); // [ '#', '#', '#' ]
let c = Array(3).fill(Array(3).fill("#"));
console.log(c); // [ [ '#', '#', '#' ], [ '#', '#', '#' ], [ '#', '#', '#' ] ]
This is interesting! Now we’ve got the first glimmer of how we might solve the staircase problem without using loops. As a first pass, we might try creating and then outputting a 2-dimensional array with the pre-specified # character:
function outputStaircaseOfSize(n) {
Array(n).fill(
Array(n).fill("#")
).map(x => console.log(x.join("")));
}
outputStaircaseOfSize(4);
// ####
// ####
// ####
// ####
Admittedly, this is more of a “wall” than a “staircase” but we seem to be on the right track. The problem seems to be that Array.fill() can only accept a static value. We don’t have any way to conditionally decide with which character to fill a certain array element.
Since Array.map() will apply a transformation function to each element of the array, and we can also access the index of each particular element, it seemed reasonable that we could do something like the following. In this case, I just want to conditionally fill the array with an X or an O depending on whether the array index is odd or even:
let a = Array(10); // creates an array with 10 empty slots
let b = a.map((x, i) => i % 2 === 0 ? "O" : "X");
console.log(b.join("")); // expected "XOXOXOXOXO"; got "undefined"
As it turns out even though Array(10) creates an array with 10 empty slots, “empty” is NOT the same thing as undefined, and as such, Array.map() doesn’t have any items over which to iterate. For the current example, we can fix this by simply filling the initial array with dummy data, e.g.
let a = Array(10).fill("#"); // creates an array with 10 slots filled with #
let b = a.map((x, i) => i % 2 === 0 ? "O" : "X");
console.log(b.join("")); // OXOXOXOXOX
While this works, it seems inefficient to fill an array with data only to immediately replace it with something else. As it turns out, I found out a way to iterate over an empty array by using a combination of array literal syntax and the spread operator:
let a = [...Array(10)].map((x, i) => i % 2 === 0 ? "O" : "X");
console.log(a.join("")); // OXOXOXOXOX
Enclosing the Array() constructor in square brackets (i.e. array literal notation) and using the spread operator makes an empty array iterable.
Putting It All Together
Now that we can declaratively create arrays of any dimensionality and conditionally fill them with whatever data we’d like, the non-looping answer to the staircase problem becomes:
function outputStaircaseOfSize(n) {
[...Array(n)].map(
(x, i) => [...Array(n)].map(
(y, j) => j < n - 1 - i ? " " : "#"
)
).map(x => console.log(x.join('')));
}
outputStaircaseOfSize(4);
// #
// ##
// ###
// ####
Neat!
Which Solution Is “Better”?
From a performance perspective, it seems to depend on how high your staircase is. I put together a performance test at JSPerf which seems to indicate that for shorter staircases (10 steps “high”) the imperative version of the code is about 15% faster. For taller staircases (1000 steps “high”) the declarative version seems about 25% faster.
From a readability/maintainability standpoint, I find the imperative syntax to be much easier to read. That’s probably because I’m more used to thinking about these problems from an imperative perspective.
Part of the problem of comparing these two approaches is that the problem itself is so seemingly unrealistic. One of the benefits of functional programming is supposed to be the ability to break down larger tasks into small, even minuscule, tasks and then compose the functions to make the whole thing easier to read, easier to test, easier to maintain. In this case, however, there doesn’t appear to be any opportunity to do this. The problem is that the inner Array.map() depends upon and uses variables from the outer Array.map(), i.e. i, and even from the context outside of that, i.e. n. Because of the coupling between the nested layers, there doesn’t appear to even be an opportunity to create partials that could be curried.
In the end, while I’m happy to have learned about this different way to declare and work with arrays, I’m not sure it makes a whole lot of sense in this particular case.