Callenge 2: Did you mean...?

Ver el enunciado original y descargar el archivo zip con los diccionarios

El objetivo del segundo problema del concurso, resumiendo el adornado enunciado del mismo, es dado un conjunto de caracteres (la palabra que requiere sugerencias) buscar todas las palabras de entre una lista de palabras dada en un fichero aparte (el diccionario) que se puedan construir con el conjunto de caracteres colocados en cualquier orden y, finalmente, ordenar estas palabras por orden alfabético.

Algunas veces me pregunto ¿por qué uso C++ en lugar de C cuando no uso objetos? Este programa me recuerda la respuesta: poder usar algunos objetos de clases ya programadas.

Una de ellas ya la empleé en el anterior problema, las clases de entrada y salida que me resultan más intuitivas que las funciones de entrada/salida de C. Para usarlas necesito incluir al principio, donde siempre detallo todos los ficheros de cabecera que empleo, la orden (la segunda es para acceder a un fichero del sistema de archivos):

#include <iostream>

#include <fstream>

El problema de emplear clases que no hemos programado nosotros es acceder a la documentación de la misma porque, al menos para mí, me resulta imposible recordar el nombre exacto de los métodos y propiedades que empleo ni el archivo de cabecera que debo añadir. Recuerdo, como mucho, el nombre de la clase por lo que constantemente tengo que acceder a la documentación. Aunque muchos de los IDE que se emplean para confeccionar programas (yo uso Anjuta en mi sistema Linux) te ayudan con los parámetros de las funciones, al final siempre tienes que buscar en la documentación. Yo empleo esta documentación on line que me resulta útil, cómoda y completa.

En este problema vamos a manejar cadenas de caracteres. Los arrays de char de C están bien pero tienen limitaciones, como tener que fijar su longitud máxima al definirlos, que hace que me incline a usar la clase string que tiene las ventajas de los anteriores pero soslayando sus inconvenientes. Obviamente no serán tan eficientes pero nos simplifican la vida. Así que incluyo el archivo de cabecera correspondiente:

#include <string.h>

Paso previo: representación por claves

Me he enrollado en generalidades inútiles y no me he centrado en el verdadero problema. ¡Vamos con él!

Al algoritmo a desarrollar le van a suministrar una palabra, iremos cambiando el orden de los caracteres de dicha palabra y, de las combinaciones que nos resulten seleccionaremos las que estén incluidas en el diccionario que nos propongan.

El algoritmo descrito en el párrafo anterior es lo que se suele llamar usar la fuerza bruta. Aunque generar todas las combinaciones no es un algoritmo difícil comprobar cada combinación contra todo el diccionario nos llevaría a un tiempo de ejecución inabordable.

Tiene que haber una solución mejor.

Como tenemos libertad para manipular los diccionarios mi propuesta es reordenar sus entradas guardando cada una de ellas por una clave por la que luego busquemos la palabra propuesta al algoritmo y, a ser posible, directamente obtengamos todas las combinaciones directamente.

¿Es posible esto? La respuesta es sí si obtenemos una representación para cada palabra que identifique a una palabra y a las diferentes combinaciones de sus letras por un mismo código. La representación más sencilla que se me ocurre es usar las mismas letras de la palabra pero ordenadas alfabéticamente. Así la palabra propuesta en el ejemplo de ejecución del enunciado (elvis), tendría como representación eilsv, que es la misma representación que tendrían las palabras soluciones lives y velis.

Resumiendo: procesamos el diccionario de tal forma que guardaremos las palabras lives y velis bajo la clave eislv. Cuando procesemos la palabra elvis la convertiremos a su representación (eislv) y con esa clave buscaremos en el diccionario modificado y directamente obtendremos las dos palabras guardadas con esa clave. Mucho más rápido que la fuerza bruta.

Ya tenemos por donde empezar, obtener la clave de una palabra. El algoritmo es sencillo aplicaremos a los caracteres que forman la palabra (tipo string) el conocido método de ordenación de la burbuja. No es muy eficiente para ordenar grandes conjuntos de datos pero es suficiente para el tamaño de las palabras que vamos a manejar.

Supongo que es conocido, pero para los que no trato de explicarlo en unas pocas palabras: Se trata de ir comparando todos los elementos con el primero y cada vez que se encuentra uno que debe ir antes en el orden se cambian entre sí los dos elementos. Al final de las comparaciones el elemento con el orden más bajo se habrá quedado en el primer lugar. Repetimos con el segundo elemento, comenzando a comparar con el tercero para conseguir que el segundo elemento quede en su sitio. Así sucesivamente hasta llegar al penúltimo lugar que se comparará, evidentemente, sólo con el último.

Nos vamos a aprovechar de la posibilidad de manejar las variables string como arrays de char con lo que el método queda tan sencillo como:

string calcKey(string word)

{

for (int i=0; i<word.size(); i++)

for (int j=i+1; j<word.size(); j++)

{

if (word[i]>word[j])

{

char c=word[i];

word[i]=word[j];

word[j]=c;

}

}

return word;

}

Le pasamos como parámetro un string, dentro del método se le aplica el método de la burbuja a sus letras quedando éstas ordenadas alfabéticamente y devolvemos como retorno de la función el string alterado.

Esta función falla si mezclamos mayúsculas con minúsculas en una palabra puesto que la representación de los caracteres minúsculos en el tipo char está antes que los minúsculos, de tal forma que se cumple 'Z' < 'a'.  Por ello, pese a que aparentemente todas las palabras, tanto de los diccionarios como las entradas al programa, están en minúsculas, como no nos lo especifica que tenga que ser así el enunciado vamos a programar un método que convierta todos los caracteres de una palabra a minúscula. Podría ser algo así:

void toLower(string& word)

{

for (int i=0; i<word.size(); i++)

if ((word[i]>='A') && (word[i]<='Z'))

word[i]=word[i]-'A'+'a';

}

El algoritmo es muy simple: si una letra está en el rango de las mayúsculas le sumamos la cantidad necesaria para convertirla a minúsculas.

Quiero hacer resaltar una diferencia en la implementación de ambos métodos. Ambos métodos trabajan directamente sobre la variable que representa al argumento pasado a la función, sin embargo en el primer caso devolvemos el valor de esta variable al final de la rutina con una instrucción return mientras que en el segundo no. ¿Por qué esta diferencia?

La respuesta está en la forma en que se pasa el argumento a la función. En el primer caso se trata de una variable, es decir de un valor (de hecho a esta forma de pasar argumentos se llama por valor) mientras que en el segundo caso estamos pasando no el valor de la variable sino la dirección de la variable que contiene el valor (eso significa el & detrás del tipo). En el primer caso si llamamos al método pasando como argumento una variable de tipo word lo que hará el programa es extraer el valor de esta variable y pasar el valor como argumento que se almacena en una variable interna del método (se dice que su alcance se limita al método y fuera de él no existe) lo que significa que el valor de la variable que se ha pasado como argumento en la llamada no se modifica. En el segundo caso lo que almacena la variable interna del método no es el valor sino la dirección de la variable que se pasa como argumento (esta forma de pasar argumento se llama por referencia) por lo que las modificaciones que hacemos en el interior del método se realizan directamente sobre la variable original. Por ello en el primer caso tenemos que devolver el valor final mientras que en el segundo no, aunque podríamos hacerlo por redundancia. Cuando luego usemos estas funciones veremos cómo este funcionamiento diferente nos permite hacer cosas diferentes con los parámetros de llamada.

También se puede definir un parámetro por referencia empleando la definición de puntero a tipo normal (string* en este caso). El funcionamiento es idéntico pero dificulta la legibilidad del código porque nos obliga a usar el operador dirección (&) al llamar a la función y el operador apunta a (*) en el interior del método. Realmente con la notación usada este trabajo lo realiza el compilador, de forma transparente, por nosotros.

Guardar el diccionario en memoria. std::multimap

Cuando necesito guardar datos en la memoria me alegro de haber cambiado de C a C++ gracias a algunas de las clases definidas en la enorme cantidad de clases definidas en el espacio de nombre std.

Estas clases son un conjunto de clases que permiten almacenar datos de cualquier tipo según cómo los vayamos a necesitar emplear. Unas clases los guardarán como vectores que, a diferencia de los arrays, pueden crecer o disminuir, otras como listas enlazadas (cada elemento guarda un puntero al elemento anterior o posterior en el orden), etc.

En nuestro caso necesitamos guardar un dato junto con una clave que lo representa y por el que lo buscaremos entre todos los datos guardados. Este tipo de almacenamiento lo implementa las clases map. Como en nuestro caso necesitamos almacenar varios elementos diferentes con la misma clave la clase que necesitamos es la clase multimap.

Para que estas clases puedan manejar cualquier tipo de dato el lenguaje C++ permite definir clases por plantillas. Más o menos es implementar una clase donde los datos con los que se trabaja son genéricos, es decir, pueden ser cualesquiera. En el momento de instanciar un objeto de esta clase, además del nombre de la clase como se especifica en las clases normales, definiremos una serie de tipos que serán con los que en concreto trabaje la instancia de la clase que definimos. Estos tipos se encierran entre signos menor/mayor a la derecha del nombre de la clase para especificar el tipo completo del objeto. Como esta declaración puede resultar larga y farragosa es preferible usar typedef para llamarla de una forma más amistosa. Así, por ejemplo, la clase que almacenará las palabras del diccionario será:

typedef multimap<string,string> strMap;

El primer tipo (string) es el tipo del dato que usamos como clave y el segundo (también string) es el tipo del dato en sí. En nuestro programa strMap va a ser el mismo tipo que multimap<strin,string>.

instanciamos un objeto de esta clase para guardar las palabras del diccionario. Lo vamos a definir fuera de todos los métodos del programa para que sea una variable global que podamos emplear en cualquier parte del programa:

strMap dict;

Los elementos que se guardan en este diccionario son pares de valores de los tipos que hemos establecido. Tenemos definida una clase que encapsula esta pareja de valores que también vamos a renombrar en otro typedef:

typedef pair<string,string> mapValue;

Estos tipos de almacenes de datos necesitan un tipo de datos que permita recorrerlos. Es decir, una tipo que nos permita definir una variable que guarda la posición de un dato de los del diccionario. Tiene la forma:

typedef multimap<string,string>::iterator itrMap;

Finalmente cuando busquemos entre los datos guardados en el diccionario lo haremos por su clave y la clase nos devolverá una pareja de valores del tipo anterior que apuntan al primer y al último valor del diccionario con esa clave. Como es una pareja de valores usará la clase pair así:

typedef pair<itrMap,itrMap> rangeMap;

Con todo esto ya tenemos la artillería necesaria para guardar las palabras de un diccionario con un índice que nos va a permitir recuperarlas en la forma deseada.
Vamos a programar un método al que pasaremos como argumento el nombre del fichero con la lista de palabras del diccionario.
El método abrirá el archivo usando una variable de la clase ifstream y leerá las palabras que contiene a una variable de tipo string llamada word.
Para cada palabra llamaremos al método toLower, programado con anterioridad, para asegurarnos que sus letras sean minúsculas. Después llamaremos al método calcKey para que nos devuelva la clave que representa a esta palabra. Con la clave y la propia palabra instanciaremos un objeto de la clase mapValue que guardaremos en la variable dict mediante su método insert (que almacena pares de valores clave-valor en su interior).
En lenguaje C++:

void readDictionary(const char* dictName)
{
string word;
ifstream fileDict;
fileDict.open(dictName, ios::in);
while (true)
{
fileDict >> word;
if (fileDict.eof()) break;
if (word.size()>0)
{
toLower(word);
dict.insert(mapValue(calcKey(word), word));
}
}
}

Observemos que construimos el objeto mapValue directamente en la llamada al método insert y que el primer parámetro en el constructor es el resultado de la llamada al método calcKey y que el segundo es la misma variable word aprovechándonos del hecho de que no se modifica al ser pasada por valor al método anterior.

Algoritmo principal

Ya casi tenemos todo hecho. Sólo nos falta leer los datos con el formato que nos van a ir llegando por el canal de entrada, procesarlos y escribir el resultado en la salida.

Vayamos por partes.

En primer lugar nos indican que en la entrada nos llegarán líneas que comienzan por el carácter # que son comentarios, por lo que su contenido debe ser ignorado por nuestro programa. Aunque parece que nos van a llegar sólo tres comentarios en donde nos marca el ejemplo vamos a hacer nuestro programa como si en cualquier parte de los datos nos pudiera llegar un comentario.

Vamos a escribir un par de métodos para saltarnos los comentarios. Los llamaremos (llamaremos, en realidad a uno de ellos y éste llamará al otro si es necesario) antes de leer un dato de la entrada. Usaremos el método peek de la clase cin (entrada estandar) que nos devuelve el siguiente carácter de la entrada pero sin eliminarlo, es decir que se devolverá también en la siguiente lectura, para averiguar si es el carácter #. En caso afirmativo se llamará al segundo método que, en un bucle, leerá caracteres de la entrada, usando el método get, hasta que se devuelva e carácter que representa el final de la línea.

El resultado puede ser:

void jumpEol()

{

while (cin.get()!='\n');

}

void jumpComment()

{

while (cin.peek()=='#')

jumpEol();

}

Cada vez que necesitemos leer un dato de la entrada llamaremos al primer método, que se saltará las líneas que sean comentarios, luego leeremos el dato y finalmente llamaremos al segundo método por si en alguna línea hay más datos (aunque en la especificación se nos indique que sólo hay un dato por línea) y, sobre todo, para asegurarnos que leemos el final de línea y nos quedamos posicionados en el comienzo de la siguiente.

Leemos el primer dato, que es el nombre del archivo que vamos a usar como diccionario y llamamos al método que lee el archivo y lo almacena en nuestra variable multimap.

El segundo dato es un entero que nos marca la cantidad de palabras a procesar. Lo guardamos y lo usamos como límite de un bucle.

Para cada palabra la leeremos del canal de entrada. Extraeremos la clave que corresponde a esta palabra y con ella buscamos en la variable dict. Nos devolverá dos punteros a las palabras primera y última del diccionario con esa clave.

Las variables de tipo puntero en estos contenedores funcionan pueden funcionar como índices en un bucle y, con el operador ->, funcionan como punteros al tipo guardado en el diccionario (string en nuestro caso).

Usaremos los punteros devueltos como límites de un bucle que extraerá los datos string que serán las palabras que sugeriremos.

Como tenemos que ordenarlos alfabéticamente usamos un segundo contenedor más sencillo pensado para guadar datos ordenados. Es la clase set para tipo de datos string. En este contenedor iremos añadiendo las palabras que sacamos del diccionario pero ya ordenadas, por lo que emplearemos un bucle.

Cuando acabe el primer bucle escribiremos las palabras de este contenedor set recorriéndolo con un último bucle y escribiendo su contenido en la salida.

Es más claro si lo expresamos con instrucciones de C++:

int main()

{

set<string> sugg;

string word;

jumpComment(); cin >> word; jumpEol();

readDictionary(word.c_str());

int N;

jumpComment(); cin >> N; jumpEol();

for (int i=0; i<N; i++)

{

jumpComment(); cin >> word ; jumpEol();

cout << word << " ->";

toLower(word);

rangeMap range=dict.equal_range(calcKey(word));

sugg.clear();

for (itrMap it=range.first; it!=range.second; ++it)

{

if (it->second.compare(word)!=0)

sugg.insert(it->second);

}

for (set<string>::iterator it=sugg.begin(); it!=sugg.end(); ++it)

cout << " " << *it;

cout << endl;

}

return 0;

}

En contra de lo dicho al principio no he usado sinónimos para los tipos derivados de set. Ha sido por pura vagancia.

Y como siempre aquí se puede ver el resultado final al completo.