Adivina la palabra

Como estoy aburrido esperando a que se actualice el Champions Online (mucho tiempo libre y en algo hay que ocuparlo), aprovecharé para subir una cosilla que hice una noche estando, de nuevo, aburrido…

¿Nunca os habéis encontrado con esos programas a las tantas de la mañana, donde te piden que adivines una palabra o un nombre que contiene X letras?  Cuando uno no puede dormir, se encuentra con cosas de esas, pero también aparecen variantes del mismo juego en los periódicos, donde te dan una serie de palabras que eliminan letras para que, al final, te quedes con un número limitado de ellas y tengas que formar una palabra…

Bueno, pues como ejercicio de programación, no está del todo mal…

Problema: Formar todas las variantes

Supongamos el siguiente problema: tenemos una serie de caracteres y queremos formar todas las posibles combinaciones de ellos, sin repetir ningún carácter y estando todos ellos presentes (ejemplo: si tenemos como caracteres base “esto”, no podremos formar “esteo” ni tampoco “est” porque no cumplen con las restricciones). Tenemos diferentes alternativas:

  • La primera que se nos ocurre, sería utilizar una cadena fija e ir intercambiando la posición de un carácter con todos los demás, de tal forma que cada cambio que realicemos sería una palabra, y repetir dicho procedimiento con todos y cada uno de los caracteres de la cadena; volviendo al ejemplo anterior, intercambiaríamos la letra ‘e’ con la ‘s’ para obtener “seto”, posteriormente intercambiaríamos la letra ‘e’ en la primera posición con la ‘t’ en la tercera para obtener ‘tseo’, y así hasta completar toda la secuencia. Este enfoque, aunque correcto, presenta a mi juicio dos problemas: el primero, es la repetición de cadenas. Si intercambiamos la primera letra con la segunda, obtendremos la misma cadena que si intercambiamos la segunda posición con la primera, de tal forma que obtendremos cadenas duplicadas e, igualmente, trabajaremos el doble; el segundo problema, es que puede resultar algo confuso de implementar (al menos, para mí).
  • La segunda (y, para mí particularmente, la mejor alternativa) es emplear árboles. Veámoslo a continuación…

Solución con árboles

Antes de todo, si no sabes lo que es un árbol, mal vamos. Podríamos definir un árbol como un grafo acíclico no dirigido, y en tal caso posiblemente nos quedaríamos igual. Pero, resumiendo mal y pronto, diremos que un árbol es una estructura de datos jerárquica, constituida de distintas celdas a las que llamaremos ‘nodos’, las cuales ‘cuelgan’ de una celda única a la que llamaremos ‘nodo raíz’ o, sencillamente, ‘raíz’. La información la almacenaremos en dichos nodos, de los cuales a su vez pueden colgar otros nodos… para poner un ejemplo rápido, si alguna vez te fijaste en los emparejamientos de la final de ‘Karate Kid’, eso es un árbol, donde los participantes en la primera ronda son los ‘nodos hojas’ (nodos finales), y el campeón es el nodo raíz.

 

Y si aún no te quedó claro, tranquilo, porque más adelante veremos un esquema… ¡qué digo más adelante! ¡Ahora mismo!

Ejemplo de un árbol

Mi solución, basada en árboles

Tomando como ejemplo la palabra ‘esto’, queremos formar todas las posibles variables existentes. Para ello, crearemos un árbol, y en el primer nivel introduciremos una letra por cada nodo, teniendo un nodo ‘e’, un nodo ‘s’, un nodo ‘t’ y un nodo ‘o’. Después, el siguiente nivel de cada letra, serán las letras que faltan, salvo la letra inmediatamente superior (como podemos apreciar, el siguiente nivel después de ‘e’  está constituido por los nodos ‘s’, ‘t’ y ‘o’). La definición es recursiva, hasta llegar a los últimos nodos. Si realizamos un recorrido por ramas, podremos formar todas las variantes existentes (nota, los puntos indican que los árboles que cuelgan de ‘s’, ‘t’ y ‘o’ en el primer nivel, siguen el mismo esquema que el árbol que cuelga de ‘e’).

Bien, y ahora, ¿qué?

Pues ahora toca el código fuente…

 

Lo primero que tenemos que hacer, es crear una clase Arbol que nos permita trabajar como hemos especificado. Para ello, antes, debemos de definir también una clase Celda que nos haga la labor de nodo. La clase Arbol contendrá el primer nivel de nuestros árboles, actuando como si fuera nuestro nodo raíz (aunque no es lo más flexible del mundo, nos servirá para lo que queremos hacer). Para poder almacenar los niveles, utilizaremos un QList (o un vector de la STL, si no empleas Qt).

[cce lang=”cpp-qt” file=”arbolt.txt”]

[/cce]

 

Cosas que pueden parecer extrañas: he creado la clase Celda dentro de la definición de ArbolT. Para que no se vea demasiado extraño, está en la parte pública, aunque bien podría haberla creado dentro de la parte privada de la clase ArbolT, pues es sólo de uso interno… desde luego, esto afecta a como se definen los métodos de la clase Celda en su implementación, que en vez de ser…

[cce lang=”cpp-qt”]

Celda::Celda(QChar etiqueta)

{

this->etiqueta=etiqueta;

}

[/cce]

… se convierten en …

[cce lang=”cpp-qt”]

ArbolT::Celda::Celda(QChar etiqueta)

{

this->etiqueta=etiqueta;

}

[/cce]

 

Y aquí tenemos el código fuente

[cce lang=”cpp-qt” file=”arbolt_fuente.txt”]

[/cce]

Como se puede apreciar, los métodos son recursivos. Cuando necesito generar un nuevo nivel, debo de copiar la cadena anterior, y eliminar el elemento que está presente en el nodo actual; y el recorrido para obtener las cadenas, es también recursivo: buscamos hasta el final de la rama del árbol, y una vez allí devolvemos el valor almacenado como una nueva cadena; a esa cadena, en el siguiente nodo, se le añadirá al principio el carácter almacenado en el nodo, y se almacenará en una lista donde se almacenan las palabras devueltas por los demás nodos del nivel.  No, repito, no es un recorrido por niveles ni tampoco un recorrido prefijo o postfijo. Es necesario hacerlo así porque, de lo contrario, te comes palabras.

 

Mas cosillas: es evidente que, para ciertas cadenas, se van a producir valores repetidos: por ejemplo, una cadena base donde existan dos consonantes iguales, o dos vocales iguales, como por ejemplo “este”. Para eliminar esas repeticiones, empleamos algo muy sucio como es almacenar los valores devueltos en un QSet, el cual sólo admite valores no duplicados, y que él se encargue del trabajo sucio. No obstante, hay que hacerlo al final, cuando nos ha devuelto todas las cadenas, ya que podemos encontrarnos con secciones repetidas que, al diferir en la última letra, serían válidas. Si realizamos el descarte durante el procesado del árbol, perderíamos información.

 

Y ya, por último, las ordenamos utilizando el algoritmo quicksort, el cual está presente dentro de las librerias Qt, dentro de QtAlgorithms. Se puede emplear con prácticamente todos los contenedores Qt (se me ocurre como excepción un QHash, que de por sí no admite que los elementos se ordenen).

 

Y ya, con eso, doy por concluida la entrada. ¡Pasadlo bien!

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s