Resolver una sopa de letras con python [algoritmo]

Buen día.

Hoy nos pondremos un poco mas "rudos", pero solo un poco; nos plantearemos el hecho de hacer un programa que pueda resolver sopas de letras, tendremos que examinar bien el funcionamiento y tratar de recrearlo en nuestro lenguaje de programación preferido, como ya lo saben, pueden leer la descripción del reto y detenerse allí,  pues hay ciertas personas que prefieren afrontar el reto desde cero y de ser así  nos pueden enviar sus respectivas soluciones alternas. Esperamos que les guste y ya saben, cualquier comentario, sugerencia, correcion o lo que sea, lo pueden comentar y les sera respondido con el mejor de los gustos.

Descripción Sopa_de_Letras :

Realizar un programa que resuelva una Sopa de Letras de tamaño MxN, lo que implicaría poder encontrar en dicha Sopa de Letras todas las palabras que están contenidas en una lista P de tamaño cualquiera; Además de encontrar las palabras, el programa debe definir la posición y dirección de la palabra encontrada en la Sopa de Letras.

Datos de Entrada:

1.       Sopa de letras de MxN.

2.       Lista P de palabras clave.

Datos de Salida:

1.       Un mensaje indicando la palabra encontrada, la posición y la dirección.

Ejemplo de uso:

Datos de Entrada:

1. Sopa de letras:
                          

    VVCKRXDWIJ

    ZANOAMIGGF

    MLADDLNQHQ

    OBAOAIRMFP

    ACOCKCOAWO

    SRUCUNSCEG

    ERALJAEABI

    MHOATRPSQP

    IFAUFOVOFS

    DADIRUGESE

2. Lista P de palabras a buscar:

    SEGURIDAD
    HACKING
    WEB
    OCULTO
    SCADA

Datos de Salida:

1.       La palabra SEGURIDAD está ubicada partiendo de la posición (10,9) hacia la izquierda.

2.       La palabra HACKING está ubicada partiendo de la posición (8,2) en forma de diagonal superior derecha.

3.       La palabra WEB está ubicada partiendo de la posición (5,9) hacia abajo

4.       La palabra OCULTO está ubicada partiendo de la posición (4,1) en forma de diagonal inferior derecha.

5.       La palabra SCADA está ubicada partiendo de la posición (6,1) en forma de diagonal superior derecha.

 -----------------------------------------------------------------------------------------------------------------

Ahora que ya tenemos la descripción del reto que debemos afrontar, tendremos que suponer que iniciaremos desde cero para hacer nuestro programa, esto con el ánimo de que pensemos diferentes métodos para poder atacarlo así que no se asusten, vamos a retomar el análisis desde cero y así verán que un reto de programación es 80% análisis 20% programación, también conviene decir que si aún no has intentado realizar este reto, puedes detenerte aquí e intentar realizarlo, y si así lo quieres, tú solución podrá ser publicada en este post.

Bueno, para poder ver más gráficamente este problema, vamos a construir una sopa de letras (la del ejemplo) de la manera más común como nos la muestran, en este caso una tabla. 

¿Pero de que nos ayuda ver la sopa de letras de esta manera?, En principio muchos pueden decir que esta manera gráfica nos complica las cosas, pero no es así, dado que de esta manera, podemos ver todo el sistema como una gran matriz de MxN y con esto, podemos acceder a cada uno de las letras, especificando el número de la fila y el número de la columna donde se encuentra dicha letra (Esto se explica mucho mejor en el post de “camino corto”).  Un ejemplo de esto, es que si pedimos la letra que se encuentra en la posición (1,1) tendremos que en dicha posición se encuentra la letra V, y si pedimos la letra que está en la posición (6,6) y la letra en la posición (10,10) obtendremos respectivamente N y E, así que con esta información, ya sabemos que podemos definir toda nuestra sopa de letras como array bidimensional o como una lista bidimensional, y solo basta con ir accediendo a cada posición que deseemos, primero especificando la fila y luego la columna donde se encuentra (dado que solo utilizamos dos coordenadas filas y columnas, podemos ver esto más gráficamente como un plano cartesiano, con x,y), teniendo esto claro, ya hemos definido nuestro sistema de trabajo.

Como ya definimos nuestro sistema de trabajo, ahora vamos a recordar un poco nuestra infancia, y si tenemos buena memoria, podremos recordar que en una sopa de letras hay varias maneras de encontrar una palabra o de buscarla, por ejemplo, mi táctica era buscar no la palabra completa sino solo buscar su letra inicial, y una vez la encontraba miraba a su alrededor haber si las demás coincidían con toda la palabra que yo buscaba, de no ser así, simplemente seguía recorriendo la sopa de letras hasta encontrar otra vez la letra inicial de la palabra que estaba buscando, y repetía esto hasta revisar  toda la sopa de letras o gran parte de ella; Mis compañeros hacían lo mismo pero no solo con la primera letra, sino también con la última, dado que una palabra podría estar tanto al derecho como al revés, otros  recorrían toda la sopa de letras primero mirando fila por fila, o columna por columna; Bueno creo que esas son todas las tácticas que utilice en mi infancia, así que no menosprecien la curiosidad de un niño, ps todas esas tácticas son 100% viables para poder resolver una sopa de letras, lo que haremos será simular cada uno de esos pasos, y como utilizaremos una computadora, realizaremos la misma cantidad de pasos, solo que en un tiempo record.

Y haciéndole honor a nuestra querida infancia, vamos a utilizar dichas tácticas para nuestro programa, pero primero debemos descomponerlas de una manera más concisa y fiable, por ejemplo, primero miremos las posibles maneras de encontrar una palabra, en este caso tenemos 8 posibilidades maneras. 

1. Al derecho (normal)

2. Al revés

3. Hacia arriba

4. Hacia abajo

5. Diagonal Superior Izquierda

6. Diagonal Inferior Izquierda

7. Diagonal Superior Derecha

8. Diagonal Inferior Derecha

Como podemos ver, si nos situamos en alguna letra, solo tendremos que verificar esas 8 posibles maneras, y en alguna de ellas tendrá que estar la palabra que buscamos, y de no ser así, simplemente cambiamos de L, ósea de letra y repetimos el proceso. Bueno, entonces si recapitulamos nuevamente todo lo que llevamos:

1. Recorrer toda la sopa de letras

                1. Si la letra, coincide con el primer carácter de la palabra a buscar

                               1. verificamos las 8 posibles maneras de encontrar la palabra

                2. si la letra, NO coincide con el primer carácter de la palabra a buscar

                               1. seguimos recorriendo la sopa de letras hasta encontrar una que coincida

Un buen refrán que me gusta a la hora de programar es ese que dice: “Divide y vencerás”,  así que siempre trato de estructurar todo el código tratando dividir todo el procedimiento en funciones, por ejemplo,  en este caso he divido todo lo que vamos a hacer en 4 funciones:

1. Matriz_y_palabras ()
2. Posicion_inicial (b_palabra,matriz,M,N)
3. Ocho_posibilidades (matriz,i,j,b_palabra)
4. Verificando (op,i,j,matriz,palabra)

Iremos explicando el funcionamiento de cada función en particular, dado que como ya lo dijimos, tenemos claro cómo funciona todo el sistema general; En principio, no quiero que piensen que este código fue el primero o el que se realizo sin mayor apuro pues la realidad es distinta, se hicieron tres códigos diferentes pero el que expondremos aquí, fue el más “elegante” y por ende el mas  entendible para poderlo explicar en su totalidad.

##<CODIGO>##

Ver codigo en Pastebin[0]

##</CODIGO>##


1.       Matriz_y_palabras()

Bueno, para hacer que el programa sea un poco mas ordenado y mas utilizable, definimos que todos los datos de entrada estarán contenidos en un archivo .txt, y es con esta función con la cual sacaremos los datos que en este caso, nos retornara la dimensión de la sopa de letras, también nos retornara la sopa de letras y la lista de palabras a buscar; esto lo hacemos suponiendo que el archivo .txt tiene los datos organizados de cierta manera, así al momento de sacar los mismos, no nos generara ningún tipo de error.

En principio lo que hacemos es algo básico de manejo de archivos, en este caso, abrimos el archivo en modo lectura (read), y con la función de archivo.redlines() obtenemos los datos del archivo en forma de lista y separado por cada renglón (\n), una vez tenemos esto, según la estructura del archivo .txt, sabemos que en la primera línea ira la dimensión de la sopa de letras MxN, pero para poderla sacar, es necesario quitar el carácter “\n” así que esto lo hacemos con datos[0].replace(“\n”,””) y también sabemos que la dimensión M y N está separada por un espacio, así que con el método datos[0].split(“ ”) retornamos y guardamos la dimensión en las variables M y N; Ahora crearemos la matriz bidimensional que va a simular la sopa de letras, así que teniendo la dimensión MxN recorreremos los datos hasta allí y los almacenaremos primero en una lista llamada columna y después almacenaremos a columna en la variable matriz, con lo cual crearemos la simulación de lista bidimensional [[columna]] o matriz.

Ahora solo nos falta sacar la lista de palabras a buscar, pero como ya sabemos la estructura del archivo .txt, sabemos que las palabras están en la ultima línea, por eso siempre estarán en datos[-1], pero como las delimitamos con una coma (,) entonces tendremos que separarlas con el método datos[-1].split(“,”) y así obtendremos un lista con todas las palabras, que almacenaremos en la variable palabras. Y una vez esto, ya tenemos todos los datos que nos proporciona tanto el archivo como la sopa de letras.

2.       Posicion_inicial (b_palabra,matriz,M,N)

Como ya hemos  planteamos nuestra estrategia desde el principio, esta función será la encargada de buscar en la matriz las letras que coincidan con el primer carácter de la palabra a buscar, y en caso de que sea encontrada, posteriormente se intentara probar las ocho posibles maneras de encontrar una palabra.

Como tenemos la dimensión de la sopa de letras (MxN), crearemos dos bucles for uno contenido dentro del otro, y donde el primero partirá de desde 0 hasta M y el segundo partirá desde el 0 hasta el N; Esto lo hacemos con el fin de poder recorrer toda la sopa de letras, dado que con M recorremos las i filas y con N recorremos las j columnas, entonces realizamos una verificación donde especificamos que si la letra contenida en la posición (i,j) es igual a la primera letra de la palabra[0] a buscar, entonces tendremos que verificar las ocho posibles formas de encontrar dicha palabra, pero en caso de que no se cumpla esta igualdad, simplemente seguimos recorriendo la sopa de letras hasta encontrar otra letra que coincida con el primer carácter de la palabra a buscar y posteriormente llamamos a la función que nos dice si se halla la palabra en alguna de las 8 maneras posibles. Esto es un proceso simple y repetitivo, es cuestión de tener clara la forma general de cómo va a ser nuestra estrategia general.

3.       Ocho_posibilidades (matriz,i,j,b_palabra)

Bueno, esta función es fácil de entender, lo primero que hacemos es eliminar la primera letra de la palabra que estamos buscando, dado que como ya pasamos el filtro de la función Posicion_inicial(), quiere decir que ya estamos parados en la primera letra de la palabra que buscamos así que no es necesario seguirla buscando en alguna de las ocho posibles maneras; también tenemos un bucle FOR que va desde 1 hasta 9 (sin incluirlo), el cual representa que cada vez que complete un ciclo, quiere decir que ya probamos la forma 1, la forma 2, la forma3… de cómo hallar la posible palabra y para esto llamamos la función verificando() con un x variante según el bucle FOR.

4.       Verificando (op,i,j,matriz,palabra)

En realidad esta función es la parte “elegante” de todo el código y se podría decir que la más importante del mismo; en principio para entender su funcionamiento, tendremos que tener presente que para encontrar una palabra en la sopa de letras, cada letra de dicha palabra va a estar en una posición (i,j) diferente de las demás, por ejemplo, las ocho maneras de hallar la palabra oculto son estas:  

Como podemos observar, cada letra de la palabra (OCULTO), tiene una posición (i,j) diferente lo que quiere decir que para poder verificar si una palabra completa esta dentro de la sopa de letras, tendremos que asignar cada letra a un (i,j); por ejemplo, si partimos desde el centro O para poder verificar si la palabra completa esta en alguna de las ocho posibilidades, podemos observar que si queremos realizar un movimiento en la forma 1, solo tendremos que alterar las columnas, sumándole 1, quedando así la nueva posición (i,j+1). Y en general las ocho posibles maneras de encontrar la palabra quedan resumidas en estas ocho posibles maneras de movimiento, una para cada una.

Teniendo esto claro, podemos observar que en la función verificando(), hemos definido ocho sentencias IF y ELIF, los cuales van a resultar verdaderos solo según la forma en que se esté buscando dicha palabra (1,2,3,4,5,6,7,8), dado que cada una de las posibles formas implica un tipo especial de movimiento, y esto lo vemos reflejado, alterando el valor de la variable i y la variable j, según la forma que estemos probando.

Bueno, lo que hace especial a esta función es que utiliza la recursividad de una manera muy creativa, en principio la función verificando() se llama a si misma dentro de ella pero cambiando los parámetros que se le pasan; Tenemos que siempre se escoge el primer carácter de la palabra a buscar, y en cada nueva llamada a si misma, vamos recortando la palabra carácter por carácter, y si cada carácter coincide con las letras en la sopa de letras, quiere decir que al final la palabra a buscar será de un carácter, y en dicho caso, la función no se volverá a llamar a si misma, sino que retornara TRUE, indicando que hemos encontrado toda la palabra y que ya podemos pasar a buscar la siguiente.  

Si, sé que esto es algo confuso de explicar pero pueden ver el código dado que está documentado, y así podrán entender bien el funcionamiento de la misma. 

Bueno, ahora solo nos queda hacer la demostracion de su funcionamiento, para eso utilizaremos la sopa de letras que esta en el primer ejemplo, y veremos como es el formato en que creamos nuestro archivo.txt y la salida del mismo.

Formato:

Salida:

Espero que haya sido de su agrado, se muy bien que me complico en muchas explicaciones, pero igualmente cualquier duda o mal entendido, puede ser reportado y sera debidamente atendido.