Especialmente si eres un usuario habitual en Twitter, es muy probable que hayas oído hablar de Wordle. Este juego mental que está tan de moda tiene un mecanismo muy complejo, seguramente te interese saber cómo funciona Wordle a nivel lógico, te lo explicamos.
Entendamos los problemas NP-complejos para explicar cómo funciona Wordle
Es posible que no te conste lo que es un "problema NP-complejo" o NP-hard en inglés. Pues es un concepto muy importante para comprender cómo se plantea el funcionamiento de este rompecabezas desde un punto de vista lógico/computacional.
Los problemas pueden ser caracterizados por su dificultad. Es decir, por el tiempo que se necesita para resolverlo a medida que aumentamos el tamaño del problema.
Algunos problemas son etiquetados como sencillos por que el tiempo que tardan en resolverse no varía demasiado en conjunción a su tamaño. Otros, por el contrario, son considerados difíciles.
Un ejemplo bastante clarificante es el de las ciudades y el camino. Imagina que tenemos 10 ciudades y queremos buscar un camino que pase por todas ellas y que tenga menos de X kilómetros.
Tendremos que comprobar todas las formas diferentes de movernos entre las ciudades hasta encontrar una posible solución. Puede que con 10 no sea complejo, pero si aumentamos el número a 300 la cosa cambia.
Un problema NP-complejo es aquel que es difícil de resolver pero cuya solución es fácil de verificar. NP es el acrónimo de "polinomio no determinista", en español.
Por ende, para saber cómo funciona Wordle es interesante tener claro que es un problema que se resuelve en un tiempo polinomial complejo (alto).
Algunos detalles sobre el algoritmo de Wordle
Consideremos las siguientes variables de entrada: ℓ, D. La primera es el número de intentos de adivinar que tiene el usuario y la segunda es el el conjunto de palabras de igual longitud a 'w', la palabra secreta.
En el pseudocódigo de arriba podemos diferenciar dos partes. Por un lado tenemos dos casos base, que serán las dos primeras sentencias if (líneas 1.1 a 1.4). Estas acaban decidiendo cuándo el jugador ha ganado o no.
Por otro lado tenemos el bloque recursivo, desde la línea 1.5 al final. En este lo que se hace es ir comprobando la validez de cada palabra 'p' que introducimos como intento de adivinar la palabra secreta 'w'.
Cada vez que se envía una palabra 'p', la variable ℓ se decrementa en una unidad. El juego se acaba si dicha variable ha llegado a 0, o bien si el jugador ha acertado la palabra p = w.
Todos los detalles sobre la complejidad de este juego están recopilados en este estudio.
Vía i-programmer
