loading...
Cover image for The challenge to make a shape area calculation in CodeSignal

The challenge to make a shape area calculation in CodeSignal

equiman profile image Camilo Martinez Updated on ・3 min read

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.

Shape Area
Image taken from CodeSignal

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");
  }
};
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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 nondesired 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 🖖

Buy me a cofee

Discussion

pic
Editor guide
Collapse
_bigblind profile image
Frederik 👨‍💻➡️🌐 Creemers

I think think there's an even easier solution:

shapeArea = function(n){
    return 1 + (n-1)*4
}

Enter fullscreen mode Exit fullscreen mode
Collapse
xerghos profile image
Xerghos

I think this is more appropriate:

function shapeArea(n) {
return (1 + (n-1)*n) *2 - 1
}

Collapse
trungsusi97 profile image
TrungSuSi97

Why do you think that formula ?

Thread Thread
axelespinosadev profile image
Axel Espinosa

Did you solve it?

Collapse
axelespinosadev profile image
Axel Espinosa

Hey buddy, can you explain your solution?

Collapse
equiman profile image
Camilo Martinez Author

Yeah, that's exactly the beauty that I talk about code fights. You can learn from other solution.

Collapse
larawho profile image
Lara Potjewyd

Hi! Would it be possible for someone to explain what's happening in the code? I'm a beginner to both code and maths. Any resources and tutorials would be appreciated too :)

Collapse
equiman profile image
Camilo Martinez Author

There is no tutorial about this specific ploblem. You need learn other concepts like recursion and loops.

This function shapeArea is not important. It's used to measure the amount of time.

Relevant things on this exercise is x.loopShapeArea, x.recursionShapeArea and x.mathShapeArea. Three of them solves the problem, but math is more efficient than others.

Collapse
stxenhammer profile image
stxenhammer

But where did you get the 4 from & multiplying it ?

For example when I can recite something for 60 times in a min so if i recite for 100 mins i just do 60 * 100 to find out how many times I recite a line.
What was ur reasoning behind using the number 4 ? I am not clear on how I would go on solving this on my own. @

Thread Thread
equiman profile image
Camilo Martinez Author

I'm using a technic learned in a subject Numerical Methods. You need reproduce step by steep and try to find something familiar between each interaction.

Explained

A square have 4 sides, that's why you need multiply the value by four.

But each side merge a point with other in the other side (red circle), you can't count both. That's why yo need subtract 4, one for each corner.

That's how I found this formula: n * 4 - 4

On first and second iteration is difficult to see it... but next iterations can give you an idea about the solution.

Hope it helps.

Collapse
ericcurtin profile image
Eric Curtin

It's more like:

int shapeArea(int n) {
  int area = 1;
  while (n > 1) {
    area += (n-- - 1) * 4;
  }
  return area;
}
Collapse
akshayd20187103 profile image
Akshay Dalvi

return n*n + (n-1)*(n-1);

Collapse
cayalav profile image
Carlos Ayala

n*(n*2*-1)-int((n*2-1/2)