# Playing with Algorithms (#1)

This is a new series that I thought I’d start purely for my own enjoyment to explore various algorithmic solutions to problems that one may encounter when writing code all while using varying paradigms (like functional, imperative, etc.). The intent is to describe a problem, and then walk through various implementations. I make no promises that the implementations will be comprehensive or that the most efficient implementation will be covered. This is purely for fun… if you like that sort of thing!

Note: All these examples will be using modern JavaScript. If you aren’t comfortable with reading code using modern JavaScript, you should still be able to follow along, and I’ve tried to provide some equivalents. For the rest of the examples, you may need to do some more research in order to follow what’s going on.

#### Problem: Find the largest item in a list

You’re provided a list of items. The list may contain arrays, in which case, you need to consider all the items inside each array, no matter how deep (within reason, of course). The function will be called with a variable number of arguments and should return the largest item. If there is no largest item (e.g., if given an empty list), the result should be `undefined`.

Things to consider:

• The list will probably be numbers. But it might contain strings. We’ll define “largest” as being consistent with the JavaScript greater-than operator and all of the type coercion that implies to keep things simple.
• Using `Math.max` is cheating, and yields incorrect results anyway, since it can’t process arbitrary strings.

Example:

Given the list `1, 10, [5, 9], [12, [900], [34, 56, 7600]], 34` the implementation should return `7600`. Or, given the list `'hello', 'world', 'strings', ['are', 'fun']`, the implementation should return `'world'`.

#### The Boilerplate

All functions will be wrapped as follows:

`function findMax(...args) {    /* algorithm */}`

If you’re not familiar with modern JavaScript, that `...` might look a little odd. All it’s doing is collecting all the arguments passed to `findMax` and putting them in an array named `args`.

#### The imperative way (no recursion)

JavaScript is often written using functional style today, but it’s adept at imperative style as well. So let’s start there — and hopefully you’ll start to see the expressive benefits of using the functional style.

First, I’ve made the problem more difficult than your typical “find the largest number” problem. The catch in our case is that there may be nested arrays, and they may be nested arbitrarily deep. That means we can’t just iterate over the array, pluck out the largest item, and return it. We have to be able to process an arbitrarily deep tree instead.

Normally we’d use recursion, but let’s keep recursion out of the equation for the moment. That means we’re going to have to keep track of the values we need to process ourselves… a stack sounds about right. We’re also going to have to keep track of the largest value we’ve found thus far.

`let largest;const stack = args;`
`/* algorithm here */`
`return largest;`

Next, we need to iterate over the stack. But, since it’s a stack, we shouldn’t use a regular `for` loop — no, we need to loop while there are items still on the stack. The best candidate for that is a `while` loop:

`while (stack.length > 0) {    const candidate = stack.pop();    /* algorithm here */}`

Once we pop off a candidate item off the stack, we need to decide what to do with it. If it’s an array, our lack of recursion is not a huge obstacle — just put the items inside the array back on the stack (this is easy using `...`):

`if (Array.isArray(candidate)) {    stack.push(...candidate);}`
Did you know that `Array#push` can accept more than one parameter? Yep, it’s capable of pushing multiple items on a stack at once. 🎉

If the candidate isn’t an array, then we just need to compare it to our current largest item:

`else if (largest === undefined || candidate > largest) {    largest = candidate;}`

Et voilà! We now have a method that returns the largest item in a list without recursion.

Full code:

`function findMax(...args) {    let largest;    const stack = args;    while (stack.length > 0) {        const candidate = stack.pop();        if (Array.isArray(candidate)) {            stack.push(...candidate);        } else if (largest === undefined || candidate > largest) {            largest = candidate;        }        }    return largest;}`

#### Imperative Recursion

Using recursion isn’t that different from the above implementation beyond being a little easier to read. In this implementation we don’t need a stack — the call tree will take the place of that, so we only need one variable to track the currently known largest item:

`let largest;`
`/* algorithm here */`
`return largest;`

Since we’re going to use recursion, we can safely loop over each item in the list with a `for...of` loop (a `for` loop would work just as well, of course):

`for (let candidate of args) {    /* algorithm here */}`

Inside the `for...of` loop, we need to decide what to do with the candidate item. If it’s an array we need to determine the largest item inside the array… hey — sound familiar? We’re already doing that! So…

`if (Array.isArray(candidate)) {    candidate = findMax(...candidate);}`

If you’re not familiar with recursion, the above invokes our `findMax` function again, just with the items in the candidate array, not with the original arguments. If another candidate is discovered to be an array, it will invoke `findMax` again, and so on, until something is discovered that isn’t an array. This should sound pretty similar to the stack we were using in the last section.

But so far we’ve not done any checks to see if a candidate is larger than our currently known largest value. That’s up next:

`if (largest === undefined || candidate > largest) {    largest = candidate;}`

With this we will compare the candidate to the largest known value whether or not it is an array or not.

Full Code:

`function findMax(...args) {    let largest;    for (let candidate of args) {        if (Array.isArray(candidate)) {            candidate = findMax(...candidate);        }        if (largest === undefined || candidate > largest) {            largest = candidate;        }    }    return largest;}`

#### Using Functional Style

So far we’ve used imperative programming. Let’s switch gears and do something functional.

First, we’re going to need a function that can flatten a list so that there are no arrays in it. Instead the items inside any arrays are spread into the list itself.

That’s not too hard:

`function flatten(...args) {    return args.reduce((acc, item) => [        ...acc, ...(Array.isArray(item) ? flatten(...item)                                         : [item])    ], []);}`

Oh, wait, who am I kidding? 😱 If you aren’t familiar with the syntax or `Array#reduce`, that looks like a nightmare. So, let’s add some comments:

`function flatten(...args) {    return args.reduce(        /* acc is short for "accumulator" here */        (acc, item) => [            ...acc, // spread the accumulator out            /* we'll spread the item out into multiple arguments */            ...(Array.isArray(item)                /* If the item is an array...                 * we need to use recursion, so spread the array out                 * and call ourselves again. */                ? flatten(...item)                /* Otherwise, return array containing a single item                 * so that spread can still work */                : [item])        ],        /* Make the starting point for Array#reduce an array with no         * items. This will be returned if there is nothing to          * flatten, but also serves as the initial value to `acc`          * above (the accumulator) */        []    );}`

To be honest, I’m not sure if that’s any better with the comments… Maybe syntax highlighting will help:

Oh well… once you get used to functional programming, it makes a lot of sense… trust me… 🐍… (Oh, come on… Disney’s Jungle Book! The first one… Am I the only one that finds that a little bit funny…? 😢)

When done we’ll have a flat array with no nesting. Once we have that, we can just `reduce` the array down to the largest value:

`const largest = (a, b) => (    [a = b, b = a] = [a, b],    a > b ? a : b);return flatten(args).reduce(largest, undefined);`

Wait… whaaaat? How in the world does that work? 😲 Time for more comments!

`const largest = (a, b) => (    // This is "array destructuring"; it lets us extract    // values out of arrays based on their position.    // here, we are extracting `a` and `b` from the RHS    // (right hand side), and then assigning those    // to the variables in the LHS.    // But what about those "=" assignments? Those are    // the defaults that get assigned if the destructured    // item happens to be undefined. So, if `a` is undefined,    // `a` will be given the value of `b` (and vice versa).    // In terms of comparing largest, that's OK, since if both    // `a` and `b` are equal, it doesn't matter which we    // return as the largest, but ultimately this lets us    // ensure we aren't comparing undefined to anything other    // than undefined.    [a = b, b = a] = [a, b],        // and now that we have two values, we can safely compare    // them and get a useful result.    // note: comma returns the last expression evaluated,    // but evaluates all the expressions in the list.    a > b ? a : b);`
`// So how does the above work with Array#reduce?// The first parameter to the reduce callback (`a` above)// is still technically acting as an accumulator, only// it's not accumulating an array of items -- it's just// holding the largest value we've encountered thus far.return flatten(args).reduce(largest, undefined);`

Okay… am I being too clever by half there? This works just as well:

`const largest = (a, b) =>     (a === undefined) ? b     : (b === undefined) ? a      : (a > b) ? a      : b;return flatten(args).reduce(largest, undefined);`

😠 Dang it… I’m an arrow function and ternary operator addict. Let’s try that again:

`function largest(a, b) {    if (a === undefined) return b;    if (b === undefined) return a;    if (a > b) return a;    return b;}return flatten(args).reduce(largest, undefined);`
Note: I’m not going to list the entire code snippets again — you’ve just seen it all!

#### Functional Sort

When thinking about the largest of anything, sorting quickly comes to mind. After all, it’s easy to think of flattening the list, sort it in ascending order, and then return the last item in the list. That will always be the largest value. (Or, do the reverse: sort it in descending order and return the first item.)

But first, a disclaimer: Array sorts in JavaScript are not pure; they mutate the original array. That is:

`const arr = [3, 2, 1];arr.sort();console.log(arr); // [1, 2, 3]`

However, knowing that, we can use it in a way that does remain pure, since we’ll have to flatten the incoming list anyway. So even though we’ll be mutating an array, it’ll only be a temporary scratch array.

So, first, we define a sorting function — here we’ll just use ascending order:

`const ascendingOrder = (a, b) => a < b ? -1 : a > b ? 1 : 0;`

There I go again with arrow functions and ternary operators. 💥

That said, the above is a pretty typical construct when it comes to sorting, but just in case your eyes want to wiggle out of their sockets looking at that (assuming they haven’t already), here’s the equivalent without either array functions or ternary operators:

`function ascendingOrder(a, b) {    if (a < b) return -1;    if (a > b) return 1;    return 0;}`

Next, we need to flatten the incoming arguments:

`return flatten(args)`

then sort them (note, this technically mutates the previous result, but it’s a scratch result, so it’s not a problem):

`.sort(ascendingOrder)`

… and then get the last value in the array:

`.pop();`

#### Whew!

Wow… that was a lot to take in, wasn’t it? But now we have several implementations that all solve the problem using different programming styles and algorithms, each with varying levels of performance and memory use. Can you pick out which implementations have better performance? Which one do you prefer reading? Which one do you prefer writing? Can you think of other ways to solve the problem?

No one style or algorithm is necessarily right all the time. Maintainability and readability is as important (if not moreso) than clever code. Performance may be even more important, if you’re dealing with large lists, or need to execute the algorithm many times in succession. On the other hand, if you’re in a memory-constrained environment, then you need a solution that works with the least amount of memory overhead. Ultimately, you need to choose a style and algorithm that works for your specific needs.

Oh, and if you want to play with the various implementations or build your own, check out the related playground. If you want a test harness in which to play around, I made one just for you!

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.