Solución a “Counting Valleys”, explicada

Contando valles es un problema de nivel de entrada en el sitio Hackerrank.com. Aquí presento una explicación y un enfoque de solución, para principiantes en problemas de estructuras de datos y algoritmos.

Puedes encontrar la descripción del sitio en Hackerrank.com, aquí comienzo con un enfoque comprensivo.

Descripción

Imagina una línea recta, el nivel del mar.
Si subimos, estamos sobre el nivel del mar, en una colina.
Estando allí, si bajamos, volvemos a subir al nivel del mar.
Si volvemos a bajar, estamos por debajo del nivel del mar, en un valle.
Si volvemos a subir, volvemos a estar al nivel del mar.

This image has an empty alt attribute; its file name is image.png
Figura 1. Colinas y valles.

El problema es el siguiente: Dada una serie de movimientos, representados por una cuerda, en los que “U” significa “Arriba” y “D” significa “Abajo”, cuenta todas las veces que estamos por debajo del nivel del mar, en un valle.

Por ejemplo: DUDDUUUD
Significado: Abajo, Arriba, Abajo, Abajo, Arriba, Arriba, Arriba, Abajo

This image has an empty alt attribute; its file name is image-1.png
Figura 2. Número de Valles.

Solución

Estructura de datos

Lo primero es determinar qué estructura de datos necesitamos. Como vemos en la representación gráfica, podemos contar los valles de forma lineal, mediante una iteración de cada comando (Arriba o Abajo). Entonces, la estructura de datos que necesitamos es una matriz. Una cadena es una matriz de caracteres.

This image has an empty alt attribute; its file name is image-2.png
Figura 3. Estructura de datos ‘Arreglo’

Algoritmo

A continuación, se definen los pasos que vamos a realizar.

  • Para resolver el problema, necesitamos saber cuándo estamos en el nivel del mar y cuándo volvemos a alcanzar el nivel del mar.
  • La forma más sencilla es asignar un valor a los altibajos, 1 y -1, y sumarlos en cada iteración.
  • Si la suma es menor que 0 (negativo), estamos en un valle.
  • Debemos contar el valle una vez que alcancemos el nivel del mar nuevamente, cuando la suma sea igual a cero una vez más.

Diagrama

PlantUML Diagram
Figura 4. Diagrama de flujo.

Prueba de Escritorio

Ahora, probemos nuestro algoritmo, para cada iteración vamos a calcular:

  • La carta que estamos recibiendo.
  • El valor de esa carta.
  • Si ‘U’, es 1.
  • Si ‘D’, es -1.
  • La suma acumulada de los valores.
  • Si estamos en un valle (suma negativa).
  • El recuento de valor acumulado.

Por ejemplo, para la primera iteración, la letra es ‘D’, lo que significa un valor de -1, ya que comenzamos a agregar valor, la suma acumulada es -1, y como actualmente estamos en un número negativo, estamos en un valle, y como no hemos superado el valle, tenemos un recuento de valles de cero.

Y así sucesivamente, realizamos los cálculos para cada letra.

LetraValorSumaEn un valleConteo de Valles
D-1-1Yes0
U10No1
D-1-1Yes1
D-1-2Yes1
U1-1Yes1
U10No2
U11No2
D-10No2
Tabla de prueba de escritorio.

Código

Una vez que nuestro algoritmo está validado, podemos codificarlo con confianza. El lenguaje utilizado aquí es JavaScript.
Las buenas prácticas son escribir el algoritmo en los comentarios para describir lo que está haciendo el programa. Podemos seguir fácilmente el código comentado para revisar el algoritmo.

Firma (Signature)

Lo primero que tenemos que hacer es obtener la firma correcta, lo que significa que los parámetros y la salida están configurados correctamente.

/**
 * We receive a number of steps
 * and a string representing a path
 */
function countingValleys(steps, path) {
    
    //  we return a number of valleys
    return valleys;
} // end function counting valleys

Declaración de variables

Como comenzamos con algoritmos y estructuras de datos, una buena práctica es declarar todas las variables que vamos a necesitar y darles nombres descriptivos. Además, será más fácil para la persona que lee el código seguir el algoritmo.

    //  to store the amount of valleys
    let valleys = 0;
    
    //  to sum the value of every step
    let sum = 0;
    
    //  to know if we're on a valley
    let inValley = 0;

Notas

Ahora implementamos el algoritmo validado. El código puede ser bastante corto y conciso, sin embargo, el ejemplo aquí es detallado para fines de aclaración.
La legibilidad y la claridad son fundamentales siempre que aprende o revisa un fragmento de código. Siempre puede refactorizarlo para que sea ordenado y simple.

Ciclo

Repasemos el proceso del ciclo.
Para cada paso (letra) del camino (la cadena), debemos realizar el algoritmo descrito.

    //  loop the steps
    for (let step of path) {
        
        // here we code
        // the algorithm

    } // end for each step

Dentro del bucle

Lo primero que necesitaremos es determinar el movimiento.
Si es “Arriba”, agregue una unidad a la suma total; de lo contrario (es “Abajo”), reste una unidad.

        //  add the step value
        if (step == 'U') {
            //  if up, positive
            sum++;
        } else {
            //  if down, negative
            sum--;
        } // end if step is 'U'

El siguiente paso es buscar si debemos agregar valles.
Para hacer esto, aplique la condición:

  • Si estuviéramos en un valle, y ahora estamos de nuevo al nivel del mar, agregue un valle al conteo.
  • Al llegar al nivel del mar, ahora no estamos en un valle, para nuestra referencia.
        //  if we were on a valley
        //  and reach sea level
        if (inValley && sum == 0) {

            //  value counter increase
            valleys++;

            //  we're not
            //  in a valley anymore
            inValley = 0;
        } // end if we were in a valley

Por último, si la suma total de valores para las posiciones (arriba y abajo) es negativa, estamos en un valle.

        //  if the sum is negative
        if (sum < 0) {
            //  we're below
            //  sea level
            //  in a valley
            inValley = 1;
        } // end if sum < 0

Y con esto terminamos de implementar el algoritmo para la iteración.
Una vez finalizado el ciclo, el programa vuelve al contador de valles.

Veamos cómo se ve el código completo:

/**
 * We receive a number of steps
 * and a string representing a path
 */
function countingValleys(steps, path) {
    
    //  to store the amount of valleys
    let valleys = 0;
    
    //  to sum the value of every step
    let sum = 0;
    
    //  to know if we're on a valley
    let inValley = 0;
    
    //  loop the steps
    for (let step of path) {
        
        //  add the step value
        if (step == 'U') {
            //  if up, positive
            sum++;
        } else {
            //  if down, negative
            sum--;
        } // end if step is 'U'
        
        //  if we were on a valley and reach sea level
        if (inValley && sum == 0) {
            //  value counter increase
            valleys++;
            //  we're not in a valley anymore
            inValley = 0;
        } // end if we were in a valley
        
        //  if the sum is negative
        if (sum < 0) {
            //  we're below sea level, in a valley
            inValley = 1;
        } // end if sum < 0
    } // end for each step
    
    //  we return a number of valleys
    return valleys;
} // end function counting valleys

Complejidad de tiempo y espacio

  • Como solo necesitamos hacer un bucle en la matriz una vez, la complejidad del tiempo es O (n).
  • Como no necesitamos copiar la matriz, la complejidad del espacio también es O (n).
  • Este es un algoritmo eficiente.
This image has an empty alt attribute; its file name is image-3.png
Figura 5. Complejidad de espacio y tiempo.

Probar la solución

Nuestro algoritmo debe poder ejecutarse para una variedad de casos:

  • Casos sencillos, rectos y felices.
  • Casos de borde (muy cortos o muy grandes).
  • Vacío de casos nulos (qué pasa si no se proporciona ninguna entrada).
  • Tiempo de ejecución y asignación de memoria.
  • Debe rendir en poco tiempo y con la menor cantidad de recursos posible.

Necesitamos conocer la respuesta de antemano para poder probarla.
Hay una gran cantidad de herramientas de prueba, o podemos codificar simplemente una función de prueba que evalúa el código y lo coteja con una respuesta predefinida.

Quédate con esto, es clave

  • Comprende y crea una imagen clara del problema en tu mente.
  • Dibujarlo ayuda mucho.
  • Determinar la estructura de datos a utilizar es resolver la mitad del problema.
  • Escribe los pasos del algoritmo y realiaz una prueba de escritorio para validarlo antes de escribir el código.
  • Escriba código claro y legible, con comentarios sobre lo que está haciendo el programa.
  • Realice pruebas para las principales categorías de problemas, casos especiales cortos, largos, sencillos.

Gracias por leer 🙂