JS Algoritmos y estructuras de datos II: Resolución de problemas. Patrón Frequency Counter

Antes de empezar a ver algoritmos complejos o las estructuras de datos entremos un poco en el área de la resolución de problemas que, aunque no te lo creas, existen algunos patrones típicos que podemos usar para resolver problemas y que pueden ser bastante útiles en nuestro dia a dia o por lo menos a la hora de hacer entrevistas. Aquí veremos algunos de estos patrones para que nos hagamos una idea y luego simplemente sería ir buscando más. Empecemos.

Resolución de problemas

Antes de entrar a ver patrones, vamos a comentar un poco algunos conceptos importantes.
Empecemos por preguntarnos, ¿qué es un algoritmo?... Por ponerlo simple podemos definirlo como un proceso o serie de pasos que tenemos que seguir para completar una tarea específica o para resolver un problema (algo así podría valer ¿no?).
Y esto ¿por qué es importante?... si lo pensamos detenidamente los desarrolladores realmente lo que hacemos es resolver problemas (muchos de estos los generamos nosotros mismos pero eso es otro tema) y aunque en nuestro día a día realmente puede que no necesitemos usar procesos complejos para nuestro trabajo, siempre estamos haciendo uso de algoritmos y como casi siempre en programación, alguien ya se ha encontrado con el problema que tenemos actualmente y puede ser que exista una manera mejor o más eficiente para resolver un problema en el que, por ejemplo, estemos usando bucles anidados o cosas similares (ya hemos visto que eso es kaka). Básicamente podemos entender que los algoritmos son como nuestras bases para ser mejores programadores y resolutores de problemas. También que aunque en vuestro dia a dia al final no hagáis uso de esto, siempre os podrá venir bien para las entrevistas o para las pruebas técnicas, que ahora cada vez más están recurriendo a este tipo de pruebas y muchas contienen problemas que podéis resolver con este tipo de patrones.

Best Practices

Como en la mayoría de entornos a la hora de resolver problemas tenemos unas best practices reconocidas (que realmente no usamos) y que podemos usarlas en última instancia si no somos capaces de resolver el problema que tenemos entre manos. Esto sería lo que llamaríamos Idear un plan de resolución de problemas, luego tenemos la otra opción que es dominar los patrones de resolución de problemas y aplicarlos directamente (ya llegaremos a esto demomoento empecemos con nuestro plan).

Pasos básicos para resolver un problema

Estos serían los pasos básicos que podemos seguir para resolver un problema:
1. Entender realmente el problema
2. Revisar ejemplos concretos de este problema
3. Descomponer el problema en problemas más pequeños y asumibles
4. Resolver o simplificar
5. Revisar y refactorizar

1. Entender el problema
Para ver si realmente entendemos el problema podemos hacernos algunas preguntas básicas:
* ¿Puedo replantear el problema con mis propias palabras?
* ¿Cuáles son realmente los inputs?
* ¿Cuáles son los outputs que debería devolver la solución del problema?
* ¿La salida puede ser determinada con los elementos que recibe el problema?¿Tenemos toda la información que necesitamos para resolver el problema?
* ¿Como debo identificar los datos importantes que son parte del problema?

Lo primero seria resolver preguntas de este tipo para poder hacernos una idea de lo que necesitamos y donde tenemos las mayores dificultades con este problema.

2. Buscar ejemplos
Si no tenemos ejemplos con la entrada y los resultados que deberíamos obtener, podemos tener tests o historias de usuario, pero al final, necesitamos algún tipo de pista de que es lo que necesitamos conseguir.
A continuación podemos plantearnos empezar creando nosotros mismos ejemplos simples (podemos incluso simplificar un poco el problema ignorando algunas de sus condiciones) e ir avanzando añadiendo dificultad hasta tener toda la complejidad que el problema realmente tiene. OJO no se nos pueden olvidar ejemplos con entras vacías o erroneas.

3. Descomponer el problema
En este punto debemos escribir los pasos que necesitamos tomar para resolver el problema, y sí escribir aunque parezca una tontería esto nos ayuda a plantear la resolución del problema correctamente viendo posibles fallos en nuestro planteamiento antes de escribir una sola línea de código. Al escribir los pasos, los estamos descomponiendo en otros más pequeños que son más sencillos de enfrentar.

4. Resolver el problema/Simplificando el problema
Ahora llega el punto de realmente resolver el problema. A la hora de intentar resolverlo nos daremos cuenta donde realmente estará el núcleo de la difilcutad que tenemos para llegar a revolver el problema. En este punto lo que debemos hacer es ignorar esa dificultad, es decir, simplificamos el problema y lo resolvemos de esta manera. Una vez que esté resuelto volvemos a incorporar esa dificultad a nuestra solución.
Aunque no lo parezca, este proceso ayuda muchas veces a resolver nuestro problema.

5. Revisar y refactorizar
En este punto lo que tendríamos que hacer sería comprobar, lo primero, si nuestra solución realmente funciona en todos los casos y luego ya hacernos preguntas de este estilo:
- ¿Podemos llegar a la misma solución de otra manera?
- ¿Podemos usar este algoritmo para resolver otros problemas?
- ¿Podemos mejorar el rendimiento de nuestra solución?
- ¿Cómo han resuelto el problema otros desarrolladores?

Con un plan o estrategia similar a estos 5 puntos podemos acercarnos más a una solución a nuestro problema.

Y a continuación esta estrategia la complementaremos con nuestro conocimiento en algunos patrones típicos de resolución de problemas.

Common problem solving patterns

Existen multitud de patrones de resolución de problemas:
- Frequency Counter
- Multiple Pointers
- Sliding Window
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- ....

Aquí comentaremos algunos que están en el nivel correcto sencillez/utilidad pero en esta página GeeksForGeeks tenemos todos los patrones o algoritmos que podamos necesitar (es muy completa).

Vamos a empezar viendo el que se conoce como Frequency Counter

Patrón FREQUENCY COUNTER

Este patrón es relativamente sencillo y tiene una función muy específica "Contar las veces que algo se repite o aparece". En un primer momento podemos pensar en la utilidad de esto, veamoslo con un ejemplo.

Queremos un método que compruebe si un string es un anagrama de otro, es decir, queremos saber si ambos strings se pueden formar con las mismas letras. Una forma fácil es contar las veces que existe cada letra en ambos strings y comparar, veremos dos acercamientos posibles de este patrón

function validAnagram(string1, string2){
    
    //Comprobamos si el tamaño es el mismo,si no, terminamos antes de empezar
    if (string1.length !== string2.length){
        return false;
    }
    
    const frequency1 = {};
    const frequency2 = {};
    //Recorremos ambos strings y guardamos en un objeto siendo la letra la key y el valor el número de veces que aparece
    for (let char of string1){
        frequency1[char] = ++frequency1[char] || 1;
    }
    
    for (let char of string2){
        frequency2[char] = ++frequency2[char] || 1;
    }

    //Recorremos y comprobamos. Si en algún caso las cantidades no coinciden entonces no es un anagrama uno de otro
    for (let char in frequency1){
        
        if(frequency1[char] !== frequency2[char]){
            return false;
        }
    }
    return true;
  }

Esta es una solución válida, que excepto que tenemos 3 búcles for, no está mal. Veamos otro posible acercamiento en este caso son solo 2 búcles

function validAnagram(string1, string2){
    //Comprobamos si el tamaño es el mismo,si no, terminamos antes de empezar
    if (string1.length !== string2.length){
        return false;
    }
    const letters = {};
    
    for (let i = 0; i < string1.length; i++){
        letters[string1[i]] = ++letters[string1[i]] || 1;
    }
    
    for (let i = 0; i < string2.length; i++){
    //Si es 0 o no existe no es un anagrama.
        if(!letters[string2[i]]){
            return false;
        } else {
            letters[string2[i]] -= 1;
        }
    }
    return true;
}

En este caso tenemos otra solución que tiene un búcle for menos y también nos funciona. Por si a alguien no le queda claro lo que estamos haciendo es restando las coincidencias del segundo string con el primero dentro de nuestro objeto letters y en el caso de que intentemos acceder a un valor que ya es 0 o que no exista es señal de que no es un anagrama.

Bueno y hasta aquí el patrón de Frequency Count, básicamente contamos dentro de un objeto CLAVE-VALOR los elementos que nos interesen, sencillo ¿verdad?

Nos vemos en el siguiente, un abrazooooooorrrrrrrr.