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

Desde la universidad, no me había metido en retos se programación hasta que recibí una invitación a CodeSignal una pagina donde puedes "competir" contra tus amigos resolviendo algoritmos.

Lo que más me ha gustado de esta plataforma con respecto a las otras de retos como CodeWars es que esta muy bien segmentadas y los retos van subiendo progresivamente de nivel.

El problema

Cuando alcancé el segundo nivel del modo arcade, me encontré con un ejercicio sobre el cálculo del área de una figura geométrica y como es debido antes de sentarme a tirar código, había que pensar antes una solución. Trate de hacer memoria de lo que vi en la universidad y me di cuenta de que habían al menos 3 formas de resolverlo: ciclos, recursión y matemáticamente.

Abajo vamos a definir un polígono de tamaño n. Tu misión es encontrar el área del polígono dada una n.

Un polígono de tamaño 1 es solo un cuadro con una longitud lateral de 1. Un polígono de tamaño n se obtiene tomando el tamaño n - 1 y adicionando 1 hasta el borde en cada uno de los lados. En la siguiente imágen vas a encontrar polígonos de tamaño 1, 2, 3 y 4.

Ejemplo:

Para n = 2, la respuesta debería ser: shapeArea(n) = 5.
Para n = 3, la respuesta debería ser: shapeArea(n) = 13.

Solución

Como reto personal decidí resolverlo por las 3 formas que se me ocurrieron y adicionalmente ver entre ellos cual era el mas eficiente.

Pude resolver en el mismo día hacerlo con ciclos y usando recursividad, pero la solución matemática me tomó más de un día y hasta tuve que ir a mirar los apuntes de la materia de Métodos Numéricos, que ya había visto varios años atrás.

Ciclos

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

Recursividad

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

Matemática

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

Ésta es la más corta pero también la más críptica y para no dejar la intriga, trataré de explicar el proceso de cómo encontré la formula.

Use una técnica de métodos numéricos que consiste en solucionar paso a paso cada iteración y luego tratar de encontrar algo común o familiar.

Un cuadrado tiene 4 lados, por eso es que necesitamos multiplicar el valor por n * 4. A partir de la tercera interaction se hace visible que cada lado tiene un punto de intersección donde se unen (color rojo) por eso no podemos contar esos puntos y es el motivo por el cual debemos restar 4 al resultado total, 1 por cada esquinas.

Así fue como encontré la formula: n * 4 - 4 que para mi sorpresa se parecía a la de solución recursiva. Le aplique un poco de álgebra de secundaria y terminó en un bonito n^2 + (n - 1)^2.

Midiendo el rendimiento

Todo muy bonito, ya tenemos 3 soluciones al mismo problema, pero entonces ¿cuál de ellos usar?.

Al mejor estilo de los Juegos Olímpicos, vamos a poner en una carrera los 3 métodos y descubrir cuál se lleva la medalla de oro.

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");
  }
};

Resultado

En CodeSignal van a encontrar que varios de los ejercicios no solo te piden resolverlos, sino que adicionalmente también lo hagas en un límite de tiempo, para este caso nos dan 4000ms, asi que despues de todo es buena idea medir su ejecución.

¿Cuál crees que va ganar la medalla de oro? para descubrirlo solo debes ejecutar esta solución.

let n = 9; //Cambia este valor
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);

Conclusión

Me di cuenta que si uno no repasa las habilidades aprendidas fácilmente se van olvidando y por eso me costó más resolver la opción matemática. Por eso es que trato de resolver al menos un reto cada semana para así mantenerme en forma.

Lo mejor de CodeSignal es que una vez resuelves el problema tienes acceso a la lista de todas las respuestas ordenadas por las más votadas. Te vas a dar cuenta que a veces elaboramos soluciones demasiado complicadas y ellxs lo hacen de una forma tan estúpidamente sencilla.

¿maldita sea porque no pensé en eso antes?

Vas a decir eso una y otra vez, pero no tiene nada de malo, al contrario va expandir tu capacidad para resolver problemas y aprender de cómo los resuelven los otros.

Pero además CodeSignal no está limitado a un solo lenguaje de programación, nos reta a lxs de habla hispana a enfrentarnos al inglés, nos hace una acercamiento al tema de pruebas unitarias y también a tener en cuenta que el rendimiento es una métrica importante. Hasta tiene retos creados por las empresas top de desarrollo como preparación para las entrevistas de trabajo.

A mi este ejercicio en especial, me regresó a la época de los retos con mis compañerxs de la universidad y me picó de nuevo el gusto por resolver retos de programación que no fueran los del trabajo.

¿Qué esperas? unete a CodeSignal y disfruta haciendo lo que nos encanta... tirar código!

Extra

La primera vez que ejecute estas pruebas, inyecte sin querer un error al incluir unos console.log entre hrstart y hrstart lo que causaba que la impresión en consola fuera contabilizada. El resultado era tan dudoso que daba como ganador el método de recursión sobre el matemático.

Una vez elimine los console.log pude ver el verdadero resultado. Asi que, eviten adiciona cualquier operación que interactúe con la pantalla cuando vayan a realizar mediciones de rendimiento.

That’s All Folks!
Happy Coding 🖖