Resuelvo una prueba técnica para un puesto de 160.000$ anuales 🤑

Esta semana me he encontrado con un tweet que decía:

Hace un tiempo subí una prueba de código a twitter para unirse a mi equipo de desarrollo. Si conseguías pasarla, obtenías el email al que enviar el CV. El salario eran 160K, full-remote, libertad total. El lunes se incorpora una persona que la resolvió en 10 minutos

Aquí tienes el tweet

Me ha sido imposible no intentar resolver dicha prueba, y por eso este artículo.

La solución, que encontrarás al final del artículo está simpática, ya que al final de la misma te muestra el email para postular al trabajo.

Por cierto, el puesto ya no está disponible

La prueba

La prueba dice:

Encuentras un espejo raro que siempre muestra una mano en movimiento. La mano parece tener vida y después de muchas preguntas de "sí" o "no" consigues deducir que la mano está intentando darte un mensaje escrito en HPL (Hand Programming Language).

Este lenguaje funciona con una memoria indefinida de bytes y con todos los valores iniciados en 0. El lenguaje tiene 7 instrucciones:

👉 : mueve el puntero de memoria a la siguiente celda
👈 : mueve el puntero de memoria a la posición anterior
👆 : incrementa el valor de la celda de memoria en la que está
👇 : decrementa el valor de la celda de memoria en la que está
🤜 : si la celda en la que está el puntero tiene un valor de 0 salta a la siguiente celda después de su 🤛 correspondiente
🤛 : si la celda en la que está en puntero no vale 0, salta después de su correspondiente 🤜
👊 : Muestra el carácter representado por su código ASCII de la actual posición.

Nota:

Como cada celda de memoria es un byte, de 0 a 255, si decrementas 0 tu valor será 255, si incrementas 255 tu valor será 0.
Bucles de 🤜 y 🤛 pueden ser anidados.

Tests

Te dan dos pruebas para testear tu código además del problema real.

El siguiente programa mostrará "Hello"

👇🤜👇👇👇👇👇👇👇👉👆👈🤛👉👇👊👇🤜👇👉👆👆👆👆👆👈🤛👉👆👆👊👆👆👆👆👆👆👆👊👊👆👆👆👊

El siguiente programa con bucles anidados mostrará "Hello World"

👉👆👆👆👆👆👆👆👆🤜👇👈👆👆👆👆👆👆👆👆👆👉🤛👈👊👉👉👆👉👇🤜👆🤛👆👆👉👆👆👉👆👆👆🤜👉🤜👇👉👆👆👆👈👈👆👆👆👉🤛👈👈🤛👉👇👇👇👇👇👊👉👇👉👆👆👆👊👊👆👆👆👊👉👇👊👈👈👆🤜👉🤜👆👉👆🤛👉👉🤛👈👇👇👇👇👇👇👇👇👇👇👇👇👇👇👊👉👉👊👆👆👆👊👇👇👇👇👇👇👊👇👇👇👇👇👇👇👇👊👉👆👊👉👆👊

Encontrarás el problema original aquí

Solución

El problema parece fácil hasta que llegas al tema de los bucles anidados. Pero no nos agobiemos, vayamos por partes, comenzamos abordando el problema sin tener en cuenta el tema de bucles anidados, ya sabes, divide y vencerás 💪

Con el siguiente código pasamos el test1

            
  function loadInputFile(pathFile: string): string {
    return Deno.readTextFileSync(pathFile);
  }
  
  const problem = Array.from(loadInputFile("test1.txt"));
  const memory: number[] = [0]; //consideraremos un array como la memoria y cada posición del array puede almacenar y byte que en valor decimal va de 0 a 255
  
  let index = 0;
  let pointer = 0;
  
  let resultString = "";
  
  while (index < problem.length) {
    switch (problem[index]) {
      case "👉":
        pointer++;
        if (!memory[pointer]) memory.push(0);
        break;
      case "👈":
        pointer--;
        break;
      case "👆":
        memory[pointer] = checkValue(memory[pointer] + 1);
        break;
      case "👇":
        memory[pointer] = checkValue(memory[pointer] - 1);
        break;
      case "🤜":
        if (memory[pointer] === 0) index = problem.indexOf("🤛", index);
        break;
      case "🤛":
        if (memory[pointer] !== 0) index = problem.lastIndexOf("🤜", index);
        break;
      case "👊":
        resultString += String.fromCharCode(memory[pointer]);
        break;
      default:
        console.log("problema");
        break;
    }
    console.log({
      input: problem[index],
      index,
      memory:memory[pointer],
      resultString,
    });
    index++;
  }
  
  function checkValue(value: number): number {
    if (value < 0) return 255;
    if (value > 255) return 0;
    return value;
  }

La última línea que vemos en consola es:

            
  { input: "👊", index: 43, memory: 111, resultString: "Hello" }

Vamos con el test2, y los bucles anidados

Al ver esto de los bucles anidados con las manitas he recordado el problema de algoritmia de crear una función para evaluar paréntesis válidos.

Es un ejercicio típico de pruebas técnicas, ya hice un artículo resolviéndolo, te lo dejo aquí

Para poder hacer un buena gestión de los bucles, haré uso de las estructuras de datos de pila (stack) y tabla de hash. La pila como estructura de datos te lo explico en el artículo de arriba (algoritmia de paréntesis válidos), de todas formas, de forma muy resumida, imagina la pila como una pila de platos, de forma que el último plato que dejas es el primero que coges.

Aquí está el punto clave, antes de nada recorreré todas las manitas y construiré una tabla de hash que relacione el puño de apertura (🤜) con el puño de cierre (🤛).

        
  const loops = new Map; //tabla de hash
  const stack:number[]=[] //pila LIFO
  instructions.forEach((instruction, index) => {
  if (instruction === "🤜") {
    stack.push(index);
  } else if (instruction === "🤛") {
    const loopStart = stack.pop() || 0;
    loops.set(loopStart,index);
    loops.set(index,loopStart);    
  }
  });

Si encontramos un puño hacia la derecha (🤜 puño de apertura) metemos su index en la pila.
Si encontramos un puño hacia la izquierda (🤛 puño de cierre) anoto en la tabla de hash el index de ese puño de cierre y lo relaciono con el último index almacenado en la pila que es el index de su puño de apertura y viceversa. De esta forma, cuando me encuentre con un puño de bucle, independientemente de si es de apertura o de cierre sabré dónde tengo que ir sin prácticamente ningún coste computacional y en un tiempo constante (cualidad de las tablas de hash).
Para obtener el último elemento de la pila uso el método pop().

Código de la solución

        
  function loadInputFile(pathFile: string): string {
    return Deno.readTextFileSync(pathFile);
  }
  
  const instructions = Array.from(loadInputFile("input.txt"));
  let cursor = 0;
  const data = [0];
  let pointer = 0;
  let resultString = "";

  const loops = new Map; //tabla de hash
  const stack:number[]=[] //pila LIFO
  instructions.forEach((instruction, index) => {
  if (instruction === "🤜") {
    stack.push(index);
  } else if (instruction === "🤛") {
    const loopStart = stack.pop() || 0;
    loops.set(loopStart,index);
    loops.set(index,loopStart);    
  }
  });
  
  while (cursor < instructions.length) {
    const instruction = instructions[cursor];
  
    switch (instruction) {
      case "👉":
        pointer += 1;
        if (pointer >= data.length) {
          data.push(0);
        }
        break;
      case "👈":
        pointer -= 1;
        break;
      case "👆":
        data[pointer] = checkValue(pointer) + 1;
        break;
      case "👇":
        data[pointer] = checkValue(pointer) - 1;
        break;
      case "👊":
        resultString += String.fromCharCode(data[pointer]);
        break;
      case "🤜":
        if (data[pointer] === 0) {
          cursor = loops.get(cursor);
        }
        break;
      case "🤛":
        if (data[pointer] !== 0) {
          cursor = loops.get(cursor);
        }
        break;
      default:
        console.log("ERROR");
        break;
    }
    cursor += 1;
  }
  
  console.log(resultString);

  function checkValue(value: number): number {
    if (value < 0) return 255;
    if (value > 255) return 0;
    return value;
  }