Solving CodinGame: The Descent

A screenshot of the game.

There’s a website, called CodinGame, with several programming challenges. One of the easiest ones is The Descent:

The goal is to, iteratively in an infinite loop, output the index of the highest number from the input (lines of numbers). I’m providing three solutions implemented in Javascript.

Imperative programming

If you’re only used to C like programming languages, probably you immediately something like this:

let highestHeight = 0;
let selectedId = 0;
for (let id = 0; id < 8; ++id) {
    const height = parseInt(readline());
    if (height > highestHeight) {
        highestHeight = height;
        selectedId = id;
    }
}

That’s an imperative approach. The state, (two variables: highestHeight and selectedId), is frequently changed according to some rules, which describe, step by step, how to solve the problem. Those variables only have the final correct values when the loop iterations are finished. They have initial values (zero), but most probably they’ll be replaced.

Functional programming

Following a functional approach, the state is not changed, requiring more abstract thinking. For instance, instead of thinking about how two variables are updated step by step, we may think like this:

To solve the problem, we need to find the index related to the highest, then:

1. Find the highest height.
2. Find the index related to the highest height.

const heights = Array.from(
    {length: 8},
    () => parseInt(readline())
);
const selectedId = heights.indexOf(
    Math.max(...heights)
);

1. Math.max(...heights) finds the highest height.
2. height.indexOf(highestHeight) finds the index related to the highest height.

Reducer function

It’s possible to avoid auxiliary constants and use a single function to find the index related to the highest value in an array: using a reducer function.

const selectedId = Array.from(
        {length: 8},
        () => parseInt(readline())
    ).reduce((highestMountainId, height, index, heights) => 
        height > heights[highestMountainId]
            ? index
            : highestMountainId,
        0
    );

In that code, the reduce function receives an array of heights and reduces it to a value: the index related to the highest height. That function has two arguments:

• A function is used to update the accumulator. In this case, the accumulator is highestMountainId and the function returns the highest height found: height > heights[highestMountainId] ? index : highestMountainId. It describes what is wanted (the index related to the highest value), instead of how to achieve it.
• The initial value of the accumulator. In this case, it’s the number zero.

Conclusion

The code with Math.max is the fastest to write, and also the most readable if you understand each function and language feature. But, in practice, the array is transversed at least twice times.

A reducer function is a functional alternative to “for” loops if it’s used to transverse an entire array and return a value. It doesn’t require several variables that are changed. In this case, it’s not faster than the code with less code. Probably because an anonymous function is called iteratively several times and the Math.max and Array.indexOf are built-in functions.

Benchmark at: https://jsbench.me/n8kqtpq5yn/1

The imperative approach, in principle, is the fastest to process and requires the least memory. It doesn’t require an array initialization, and the values are evaluated while they’re read from some source (ex: a file). It’s not necessarily worse when it’s not the most readable code. It’s still simple. It follows a usual recognizable pattern. And it can be encapsulated inside a function.

That doesn’t mean an imperative programming style is always good. Readability is valuable, and it’s helpful to know several approaches and tools to solve problems.