hangmanADT - Parcial 2C2016

[mariu23]

Hola, les mando mi solucion al ejercicio de hangmanADT (pasa el test).

hangmanADT.c

#include <stdio.h>
#include "hangmanADT.h"
#include <time.h>
#include <stdlib.h>

struct elem{
    char ** vec;
    int wordCount;
};

typedef struct hangmanCDT{
    int maxLevel;
    struct elem * vec;

} hangmanCDT;

/* Crea la estructura que dará soporte al almacenamiento y selección de palabras
** maxLevel: la cantidad máxima de niveles de dificultad que soportará (como mínimo 1)
** Los niveles válidos serán de 1 a maxLevel inclusive
 */
hangmanADT newHangman(unsigned int maxLevel){
    hangmanADT new = malloc(sizeof(hangmanCDT));
    new->maxLevel = maxLevel;
    new->vec = malloc(maxLevel*sizeof(struct elem));
    for(int i = 0 ; i < maxLevel ; i++){
        new->vec[i].vec = NULL;
        new->vec[i].wordCount = 0;
    }
    srand(time(NULL));
    return new;
}

/* Agrega un conjunto de palabras asociadas a un nivel de dificultad.
** El arreglo words[] está finalizado en NULL
** Si alguna de las palabras de words[] ya existe en el hangmanADT para ese nivel de dificultad
** se ignora.
** No se realiza una copia local de cada palabra sino únicamente los punteros recibidos
** Retorna cuántas palabras se agregaron al nivel
*/
#define BLOCK 10

int addWords(hangmanADT h, char * words[], unsigned int level){
    if(h->maxLevel < level){
        return -1;
    }
    int cantAdded = 0;
    for(int i = 0 ; words[i] ; i++){
        if(h->vec[level-1].wordCount % BLOCK == 0){ 
            h->vec[level-1].vec = realloc(h->vec[level-1].vec, sizeof(char *) * (h->vec[level-1].wordCount + BLOCK));
        }
        int flag = 0;
        for(int j = 0 ; j <  h->vec[level-1].wordCount ; j++){
            if(h->vec[level-1].vec[j] == words[i]){
                flag = 1;
            }
        }
        if(!flag){
            h->vec[level-1].vec[ h->vec[level-1].wordCount + i ] = words[i];
            cantAdded++;
        }

    }
    h->vec[level-1].wordCount += cantAdded;
    return cantAdded;
}

/* Retorna cuántas palabras hay en un nivel, -1 si el nivel es inválido */
int size(const hangmanADT h, unsigned int level){
    if(h->maxLevel < level){
        return -1;
    }
    return h->vec[level -1].wordCount;
}

/* Retorna una palabra al azar de un nivel determinado, NULL si no hay palabras de ese nivel
** o si el nivel es inválido. 
*/
char * word(const hangmanADT h, unsigned int level){
    if(h->maxLevel < level || h->vec[level - 1].wordCount == 0){
        return NULL;
    }

    int index = (rand() % (h->vec[level - 1].wordCount)) + 1;
    return h->vec[level - 1].vec[index - 1];
}

/* Retorna todas las palabras de un nivel, o NULL si el nivel es inválido
** El último elemento del vector es el puntero NULL
*/
char ** words(const hangmanADT h, unsigned int level){
    if(h->maxLevel < level){
        return NULL;
    }
    int i = 0;
    char ** toReturn = malloc(sizeof(char *) * (h->vec[level-1].wordCount +1) );
    for( ; i < h->vec[level-1].wordCount ; i++){
        toReturn[i] = h->vec[level-1].vec[i];
    }
    toReturn[i] = NULL;
    return toReturn;
}

hangmanTest.c

#include "hangmanADT.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

int main(void){

hangmanADT h = newHangman(3);   // Los níveles válidos serán 1, 2 y 3
size(h, 1); // -> Retorna 0
size(h, 4); // -> Retorna -1

char * firstWords[] = {"ingenieria", "informatica", NULL};
assert(addWords(h, firstWords, 1) == 2); // -> Retorna 2
assert(size(h, 1) == 2); // -> Retorna 2
word(h, 1); // -> Retorna “ingenieria” o “informatica”
words(h, 1); // -> Retorna {“ingenieria”, “informatica”, NULL}
             // También podría retornar {“informatica”, “ingenieria”,  NULL}

assert(addWords(h, firstWords, 1) == 0); // -> Retorna 0

addWords(h, firstWords, 5); // -> Retorna -1
assert(size(h, 5) == -1); // -> Retorna -1
word(h, 5); // -> Retorna NULL
words(h, 5); // -> Retorna NULL;
words(h, 2); // -> Retorna {NULL}

char * secondWords[] = {"programacion", NULL};
addWords(h, secondWords, 3); // -> Retorna 1
assert(size(h, 3) == 1); // -> Retorna 1
word(h, 3); // -> Retorna “programacion”
words(h, 3); // -> Retorna {“programacion”, NULL}

// Ejemplo que muestra cómo se copian las palabras en el TAD
char v[20] = "cazador";
char * thirdWords[] = { v, NULL};
assert(addWords(h, thirdWords, 2) == 1); // -> Retorna 1

printf("%s\n", word(h, 2)); // -> Imprime “cazador”

strcpy(v, "venado");  // En la dirección v ahora hay otro string

printf("%s\n", word(h, 2)); // -> Imprime “venado”

char * lastWords[] = { "cazador", "colador", NULL};
assert(addWords(h, lastWords, 2) == 2); // -> Retorna 2 

return 0;
}

Use un vector donde cada elemento representa un nivel, y es una estructura con un vector dinamico de palabras y la cantidad de palabras por nivel. Esto hace que la funcion addWords no sea eficiente, porque busca en el vector si la palabra que se quiere agregar ya existe, pero hace que sea facil acceder a una posicion al azar. Seria mejor hacer una lista para las palabras y mantenerlas ordenadas? Como el test da el ejemplo de que se pueden guardar con cualquier orden no estoy segura. Desde ya muchas gracias.

[marcelogarberoglio]

La estructura es la correcta, para ahorrarte el for inicial, en vez de

new->vec = malloc(maxLevel*sizeof(struct elem));
    for(int i = 0 ; i < maxLevel ; i++){
        new->vec[i].vec = NULL;
        new->vec[i].wordCount = 0;
    }

podés hacer

new->vec = calloc(maxLevel, sizeof(struct elem));

En este for estás viendo si los punteros coinciden, no si la palabra está, deberías usar strcmp o strcasecmp

for(int j = 0 ; j <  h->vec[level-1].wordCount ; j++){
            if(h->vec[level-1].vec[j] == words[i]){
                flag = 1;
            }
        }

y modularizaría un poco, haciendo que la verificación la haga una función auxiliar.

[mariu23]

Ok, la funcion addWords modularizada queda asi:

#define BLOCK 10

static int alreadyExists(char ** vec, int wordCount , char * s2){
    for(int j = 0 ; j < wordCount ; j++){
        if(strcasecmp(vec[j], s2) == 0){
            return 1; 
        }
    }
    return 0;
}

int addWords(hangmanADT h, char * words[], unsigned int level){
    if(h->maxLevel < level){
        return -1;
    }
    int cantAdded = 0;
    for(int i = 0 ; words[i] ; i++){
        if(h->vec[level-1].wordCount % BLOCK == 0){ 
            h->vec[level-1].vec = realloc(h->vec[level-1].vec, sizeof(char *) * (h->vec[level-1].wordCount + BLOCK));
        }
        if(!alreadyExists(h->vec[level-1].vec, h->vec[level-1].wordCount, words[i])){ //le paso el vector de punteros a char - debe iterar con ese vector
            h->vec[level-1].vec[ h->vec[level-1].wordCount + i ] = words[i];
            cantAdded++;
        }
    }
    h->vec[level-1].wordCount += cantAdded;
    return cantAdded;
}

Entonces esta bien "sacrificar" la eficiencia del addWords (hacer que recorra el vector de palabras siempre que quiera agregar una nueva) para hacer que la funcion word tenga acceso directo con un indice sacado al azar? Porque al ser un hangman la funcion words se va a llamar muchas mas veces que la cantidad de palabras que se van a agregar, no?

[marcelogarberoglio]

Sí, es correcto. Y está bien hacer que addWord no sea tan eficiente, siempre y cuando eso permita que word sea eficiente ya que, como bien decís, se espera que una vez cargadas las palabras haya muchas consultas.