¡Ya ha comenzado! Por fin, tras un arranque movidito debido a la altísima demanda que ni el propio autor ha podido prever, el advent of code 2020 está en marcha.

En esta ocasión, después de 5 años seguidos salvando la Navidad has decidido marcharte a una isla tropical a pasar las fiestas en un resort. Pero por supuesto, los elfos (tocapelotas) y en concreto los de administración (doblemente tocapelotas) quieren que dejes tu hoja de gastos cuadrada antes de marcharte.

El trabajo en la comunidad advent of code es increible…..video creado por ManicD7

Parte 1

En la primera parte del puzzle del día 1 nos piden encontrar, dentro de nuestra lista de gastos, los dos importes que sumados den la cifra 2020. Como entrada disponemos de una lista de números que vamos a trasformar a un array para poder utilizarlos cómodamente y como solución al problema debemos dar la multiplicación de ambos.

No se trata de una tarea complicada y dado que la lista de numeros solo tiene 200 posiciones vamos a usar la fuerza bruta para hallar la respuesta correcta: seleccionamos un numero y lo sumamos a cada uno de los demás en el array buscando los que den como solución 2020.

  public findCosts = (): number[] => {
    console.time("findCost");

    // Ordenamos los numeros
    this.expenses = this.expenses.sort((a, b) => a - b);

    const costs: number[] = [];
    for (let index1 = 0; index1 < this.expenses.length && costs.length == 0; index1++)
      for (
        let index2 = index1 + 1;
        index2 < this.expenses.length &&
        costs.length == 0 && //no continuar iterando si hemos hallado la respuesta
        this.expenses[index1] + this.expenses[index2] < 2021; // no continuar iterando si las suma supera los 2020
        index2++
      )
        if (this.expenses[index1] + this.expenses[index2] === 2020)
          costs.push(this.expenses[index1], this.expenses[index2]);

    console.timeEnd("findCost");

    return costs;
  };
}

La función devolverá los dos números del juego de datos de entrada que sumen 2020. Antes de optar por esta solución había contemplado hacerlo las iteraciones utilizando la función forEach, pero hay que tener en cuenta que esta función no puede interrumpirse, con lo que una vez encontrada la solución seguiría ejecutándose hasta calcular todas las combinaciones posibles de números, por lo que he desechado esta opción.

A pesar de tener una solución sencilla, como corresponde al primer día, no deja de tener sus trucos:

  • El más obvio: si hemos calculado la suma de los números a + b, no es necesario calcular la de b + a. El bucle interno siempre empieza desde la siguiente posición al bucle externo.
  • El segundo más obvio: una vez encontrada la solución no hay que seguir computando combinaciones. Esto lo logramos con la condición de salida costs.length==0 en ambos bucles.
  • Uno menos obvio: si analizamos los datos de entrada veremos que pocos números son inferiores a 1010, la mitad de la solución buscada. Uno de los dos números de la solución tiene que pertenecer a ese conjunto, por lo que si ordenamos el array de entrada en orden ascendente nos aseguramos de que vamos a realizar muchas menos ejecuciones del bucle exterior. Puede comprobarse que con la entrada ordenada el bucle se ejecuta 9 veces, mientras que con ella desordenada se ejecuta 132.
  • Uno de optimización: puesto que hemos ordenado la entrada sabemos que si en cualquier momento la suma supera 2020 no hace falta seguir computando, ya que las siguientes combinaciones serán también superiores a esa cifra. La condición this.expenses[index1] + this.expenses[index2] < 2021 en el bucle interno nos asegura esa optimización.

Con todo ello logramos un tiempo de ejecución en mi máquina de 0.230 milisegundos. Este año prestaré especial atención a toda posible optimización que se pueda realizar al código para arañar milisegundos. En este puzzle del día 1 no ha sido determinante, pero sin duda lo será mas adelante.

Actualización

A pesar de todo lo dicho en la anterior solución, esta no deja de tener una complejidad O(N2). Existe una solución con complejidad O(N) muy sencilla si ordenamos la lista: recorrer el array desde los extremos hasta dar con la solución:

 public findCostsN = (): number[] => {
    console.time("findCostN");

    // Ordenamos los numeros
    this.expenses = this.expenses.sort();
    let start = 0,
      end = this.expenses.length - 1;
    // Ajustar los indices teniendo en cuenta la ordenacion

    while (this.expenses[start] + this.expenses[end] !== 2020)
      if (this.expenses[start] + this.expenses[end] > 2020) end--;
      else start++;

    console.timeEnd("findCostN");
    return [this.expenses[start], this.expenses[end]];
  };
}

Con esta solución el tiempo de ejecución baja a 0.040 ms, seis veces menos que en la anterior propuesta.

Parte 2

Los elfos de administración siguen tocando las bolas y ahora quieren los tres números que cumplan el criterio anterior. Teniendo en cuenta el código desarrollado anteriormente opto por hacerle una modificación de manera que, si la suma de los dos primeros números es inferior a 2020, busco un tercero que los complemente:

public findCosts = (): number[] => {
    console.time("findCost");
    // Ordenamos los numeros
    this.expenses = this.expenses.sort();
    const costs: number[] = [];
    for (let index1 = 0; index1 < this.expenses.length && costs.length == 0; index1++)
      for (
        let index2 = index1 + 1;
        index2 < this.expenses.length &&
        costs.length == 0 &&
        this.expenses[index1] + this.expenses[index2] < 2020; //no iterar en combinaciones de numeros que sumen mas de 2019, no existe un tercer numero en ese caso
        index2++
      ) {
        //Buscar el indice del  numero que sumado a los otros 2 nos de 2020
        const index3 = this.expenses.findIndex(
          (n) => n === 2020 - (this.expenses[index1] + this.expenses[index2]) && n != index1 && n != index2
        );
        if (index3 > -1) costs.push(this.expenses[index1], this.expenses[index2], this.expenses[index3]);
      }

    console.timeEnd("findCost");

    return costs;
  };

Esto implica:

  • Modificar la condición del bucle interior para que se ejecute si la suma es menor de 2020, utilizando la condición this.expenses[index1] + this.expenses[index2] < 2020
  • Incluir una búsqueda del índice de un tercer número que complete la suma hasta 2020. En este caso hago uso de la función findIndex para localizarlo, asegurándome de que ese numero no es ninguno de los dos que ya tengo seleccionados anteriormente.

La ejecución de la función con el mismo juego de datos de entrada tarda 0.350 ms.

Y así acaba el primer día de este advent of code 2020. ¿Tienes una solución mejor? ¡ Déjame un comentario!

Puedes descargar el código completo de este ejemplo desde GitHub: oddbytes.net/adventofcode

100.000 personas han resuelto el día 1

A 4 de Diciembre se ha batido la marca de 100.000 personas que han resuelto el día 1 de Advent Of Code 2020. Impresionante, ¡felicidades Eric Wastl!

Free WordPress Themes, Free Android Games