Languages: [🇪🇸] Español - [🇺🇸] English

Since college, I was not encouraged to do programming challenges, until I got the invitation to CodeSignal a page where you can "play" against several friends or companies about solving algorithms.

I found on the second introduction level an exercise to make a shape area calculation that calls all my attention and before starting to develop it I thought of at least three ways to solve it: loops, recursion and mathematically … too late, now I'm infected with development fever.

The Problem

Below we will define an n-interesting polygon. Your task is to find the area of a polygon for a given n.

A 1-interesting polygon is just a square with a side of length 1. An n-interesting polygon is obtained by taking the n - 1-interesting polygon and appending 1-interesting polygons to its rim, side by side. You can see the 1-, 2-, 3- and 4-interesting polygons in the picture below.

Sample

For n = 2, the output should be: shapeArea(n) = 5.
For n = 3, the output should be: shapeArea(n) = 13.

My Solution

I decided to give myself the task of solving it in the 3 methods with node.js. I solved loops and recursion the same day, but the mathematical solution took me more than expected because I had to review my notes about Numerical Methods viewed years ago in college.

const x = {};
x.loopShapeArea = (n) => {
  let area = 1;
  for (let i = 1; i <= n; i++) {
    area += i * 4 - 4;
  }
  return area;
};

x.recursionShapeArea = (n) => {
  if (n === 1) {
    return 1;
  } else {
    return n * 4 - 4 + x.recursionShapeArea(n - 1);
  }
};

x.mathShapeArea = (n) => {
  return Math.pow(n, 2) + Math.pow(n - 1, 2);
};

const shapeArea = (n) => {
  let solution = {};
  if (0 < n && n <= Math.pow(n, 4)) {
    let obj = {
      0: "loopShapeArea",
      1: "recursionShapeArea",
      2: "mathShapeArea"
    };
    for (let item in obj) {
      let fx = obj[item];
      solution[fx] = {};
      solution[fx].result = {};
      let hrstart = process.hrtime();
      for (let i = 1; i <= n; i++) {
        let result = x[fx](i);
        solution[fx].result[i] = result;
      }
      let hrend = process.hrtime(hrstart);
      solution[fx].execution = {};
      solution[fx].execution.s = hrend[0];
      solution[fx].execution.ms = hrend[1] / 1000000;
    }
    return solution;
  } else {
    return Error("Not a valid number");
  }
};

Result

This exercise has a timeout condition of 4000ms, so it's good to add a way to measure the runtime. From the beginning, I thought that the most optimal solution was going to be mathematics. What do you think? Which one is faster?

let n = 9; //Change this value
const result = shapeArea(n);
for (let item in result) {
  console.log(`${item} -> Execution time (hr): ${result[item].execution.s}s ${result[item].execution.ms}ms.`
  );
}
console.log(result);

Why I love CodeSignal? because sometimes you figured a complicated and elaborated answer and when you can see other solutions found a ridiculous and simple way to solve it. Dam it … why did not I think of that before?

Join us on CodeSignal and enjoy making all that we love… code!

Bonus Track

The first time that I made this code, inject non-desired mistake adding console.log between hrstart and hrstart and this print time was charged to the solution. When I saw the results seem to me estrange that recursion was the winner over math solution.

But once I removed console.log from there saw the true result. So, avoid the additional operation or screen interaction if you want to have a real metric of time spent.

That’s All Folks!
Happy Coding 🖖