tp8 ej7. sopa de letras

[bleite12]

Hola, como estan? No tengo una consulta en especifico, agradeceria si alguien pudiera revisar y decirme si hay algun error grave. Seguro hay mas de uno porque no me pasan los asserts.

en la funcion , GuardoTodo(int i, int j,int numeroPalabra, char * diccionario[], posicion * misresultados, int direccion, int encontradas). no sabria decir si se pasa (posicion misresultados[]). o lo que ya le pase.

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

#define COLS 7
#define FILS 6

typedef enum
{
    DER = 0,
    IZQ,
    ABA,
    ARR,
    I_AR,
    I_AB,
    D_AR,
    D_AB
} Tdireccion;

typedef struct posicion {
    char * palabra;
    size_t fila;
    size_t columna;
    Tdireccion direccion;
} posicion;

posicion * resolverSopa(char *diccionario[], char sopa[][COLS]);
void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion ** misresultados, int direccion, int encontradas);
int RecorroDirecciones(int i, int j, char sopa[][COLS], char * diccionario[], int palabra);
posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados);
// NOTA: depende del orden en que realizan la busqueda, el testeo puede dar diferente
//       en esta prueba asumimos que se recorre el diccionario, y cada palabra se busca en la sopa de 
//       letras.
//.      Si en vez de hacerlo así recorren la matriz y por cada letra buscan si hay una palabra en el diccionario
//       que empiece con esa letra, tienen que cambiar el testeo para que coincida con el orden en que se encuentran.

int main(void) {
  char * diccionario[] = {"ARRE", "CANCION", "CAPA", "ERROR", "ORCO", "PERRO", "PERTINAZ", "REA", "RIO", ""};

  char sopa[FILS][COLS] =
     {{'X','X','X','O','X','X','X'},
      {'A','P','A','C','Y','Y','O'},
      {'Z','E','Z','R','Z','C','X'},
      {'E','R','R','O','R','X','X'},
      {'X','R','I','O','I','E','X'},
      {'X','O','X','X','O','X','X'}};

  struct posicion * res = resolverSopa(diccionario, sopa);
  // La cantidad de palabras encontradas debe ser 9
  int expected = 9;
  int count = 0;
  while ( res[count].palabra != NULL)
     printf("%s\n", res[count++].palabra);
  assert(count == expected);

  assert(strcmp(res[0].palabra,"ARRE")==0);
  assert(res[0].fila==1);
  assert(res[0].columna==2);
  assert(res[0].direccion==D_AB);

  assert(strcmp(res[3].palabra,"ORCO")==0);
  assert(res[3].fila==3);
  assert(res[3].columna==3);
  printf("%d\n", res[3].direccion);
  assert(res[3].direccion==ARR);

  assert(strcmp(res[4].palabra,"ORCO")==0);
  assert(res[4].fila==4);
  assert(res[4].columna==3);
  assert(res[4].direccion==D_AR);

  assert(strcmp(res[6].palabra,"REA")==0);
  assert(res[6].fila==3);
  assert(res[6].columna==2);
  assert(res[6].direccion==I_AR);
  free(res);
  puts("OK primera parte");

  char * diccionario2[] = {""};
  res = resolverSopa(diccionario2, sopa);
  // La cantidad de palabras encontradas debe ser 0
  expected = 0;
  count = 0;
  while ( res[count].palabra != NULL)
     printf("%s\n", res[count++].palabra);
  assert(count == expected);
  free(res); 
  puts("OK sin palabras encontradas");
  return 0;
}

posicion * resolverSopa(char *diccionario[], char sopa[][COLS]){
    //tengo que retornar la direccion de memoria de el vector de structs posicion.

    posicion * misresultados =NULL; 

    for(int i = 0 ; i<FILS ; i++ ){
        for(int j = 0 ; j<COLS ; j++ ){

            misresultados = buscopalabra(i, j, sopa, diccionario, (misresultados));
        }
    }

    return (misresultados);

}

posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados){

int direccionEncontrada, encontradas=0;

   for(int d = 0 ; diccionario[d][0] != '\0' ; d++ ){

        if(sopa[i][j]==diccionario[d][0]){
            //si coincide el primer caracter tengo que probar en todas las direcciones para ver si encuentro la palabra.
            //puedo crear una funcion que recorra direcciones.  
            //si da  es que entontro la palabra entonces me la guardo.
            //si da -1 no encontro nada y sigo probando con otras palabras.
            direccionEncontrada=RecorroDirecciones(i , j, sopa, diccionario, d);
            if(direccionEncontrada!=-1){
                //guardar palabra diccionario[d], el la posicion direccion encontrada.
                //tengo que hacer un realloc del struct.
                //la llamo en esta linea luego 
                misresultados = realloc(misresultados, sizeof(posicion) * (encontradas+1));
                GuardoTodo(i, j, d,  diccionario, &misresultados, direccionEncontrada, encontradas);
                encontradas++;

            }

        }

   }

   return misresultados;

}

int RecorroDirecciones(int i, int j, char sopa[][COLS], char * diccionario[], int palabra){
    int Iaux, Jaux=j, dir, d=1;
    static int Vfilas[] = {0, -1, -1, -1, 0, 1, 1, 1}; 
    static int Vcolum[] = {1, 1, 0, -1, -1, -1, 0, 1};
    int FlagDireccion=1;

    for(dir = 0  ; dir<8 ; ){

        for(Iaux = i, Jaux = j ; Iaux<FILS && Jaux<COLS ; Iaux += Vfilas[dir], Jaux += Vcolum[dir] ){

            if(sopa[Iaux][Jaux]!=diccionario[palabra][d++]){
                FlagDireccion = 0;
            }

        }

        if(FlagDireccion){//pregunto si el flag es 1 -> el flag no entro porque es valido.
            return dir; //retorna la direccion en la que encontro la palabra.
        }

        dir++;

    }

    return -1;//si llega aca es que nunca encontro la palabra.

}

void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion ** misresultados, int direccion, int encontradas){

    misresultados[encontradas] = malloc(sizeof(posicion) );
    misresultados[encontradas]->columna=j;
    misresultados[encontradas]->fila=i;
    strcpy(misresultados[encontradas]->palabra,diccionario[numeroPalabra]); 
    misresultados[encontradas]->direccion=direccion;

}

[marcelogarberoglio]

Aunque funcione no te va a pasar el test por esta nota que está antes del main // NOTA: depende del orden en que realizan la busqueda, el testeo puede dar diferente // en esta prueba asumimos que se recorre el diccionario, y cada palabra se busca en la sopa de // letras.

En todo caso fijate de imprimir las palabras que te devuelve, tal vez sean las mismas pero en otro orden, ya que vos recorrés la matriz, y por cada letra recorrés el diccionario. No es que esté mal, es lo mismo, pero el orden en que las encontrás va a diferir del orden en que las encontramos nosotros

Un error importante hay en GuardoTodo. En buscoPalabra definís bien el vector misResultados, ya que es un vector dinámico de estructuras posicion, pero en GuardoTodo lo usás como si fuera un vector de punteros a struct, y además copiás el string a un puntero que no está inicializado. Tendrías que pasarle la dirección de un struct para que la llene, como hicimos en clase con la función carga para la biblioteca, o sea

// Recibe el puntero al struct que hay que llenar
void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion * misresultados, int direccion){
    misresultados->columna=j;
    misresultados->fila=i;
    misresultados->palabra = diccionario[numeroPalabra]; // Copio el puntero, no hace falta copiar todo el string
    misresultados->direccion=direccion;
}

y la invocás de esta forma

       misresultados = realloc(misresultados, sizeof(posicion) * (encontradas+1));
      // le paso la dirección del struct a llenar
       GuardoTodo(i, j, d,  diccionario, misresultados + encontradas, direccionEncontrada);

Igual me parece que hay otros errores, fijate si con esto podés avanzar y cualquier duda avisanos

[bleite12]

Ya casi que me quedo "bien", pero no se porque encuentra palabras en cualquier lugar. Pense que era porque quedaba puesto el flag de encontrar palabra pero sinceramente ni idea. Aprecio cualquier tipo de correccion.

me falto arreglar la funcion imprime para que imprima la direccion y no el numero de direccion.

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

#define COLS 7
#define FILS 6

typedef enum
{
    DER = 0,
    IZQ,
    ABA,
    ARR,
    I_AR,
    I_AB,
    D_AR,
    D_AB
} Tdireccion;

typedef struct posicion {
    char * palabra;
    size_t fila;
    size_t columna;
    Tdireccion direccion;
} posicion;

posicion * resolverSopa(char *diccionario[], char sopa[][COLS]);
void  GuardoTodo2(int i, int j,int numeroPalabra,  char * diccionario[], posicion ** misresultados, int direccion, int  encontradas);
int RecorroDirecciones(int i, int j, char sopa[][COLS], char * diccionario[], int palabra);
posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados, int * encontradas);
void imprimirResultados(posicion * misresultados);

int main(void) {
  char * diccionario[] = {"ARRE", "CANCION", "CAPA", "ERROR", "ORCO", "PERRO", "PERTINAZ", "REA", "RIO", ""};

  char sopa[FILS][COLS] =
     {{'X','X','X','O','X','X','X'},
      {'A','P','A','C','Y','Y','O'},
      {'Z','E','Z','R','Z','C','X'},
      {'E','R','R','O','R','X','X'},
      {'X','R','I','O','I','E','X'},
      {'X','O','X','X','O','X','X'}};

  struct posicion * res = resolverSopa(diccionario, sopa);

    // Liberar la memoria asignada para cada palabra en cada struct posicion
    for (int i = 0; res[i].palabra != NULL; i++) {
        free(res[i].palabra); // Liberar la memoria asignada para la palabra dentro del struct
    }

    // Liberar la memoria del arreglo de estructuras
    free(res);

  return 0;
}

posicion * resolverSopa(char * diccionario[], char sopa[][COLS]){

    int encontradas = 0;
    posicion * misresultados =NULL; 

    for(int i = 0 ; i<FILS ; i++ ){
        for(int j = 0 ; j<COLS ; j++ ){

            misresultados = buscopalabra(i, j, sopa, diccionario, (misresultados), &encontradas);

        }
    }

    misresultados = realloc(misresultados, sizeof(posicion) * (encontradas + 1));
    misresultados[encontradas].palabra = NULL; // Indicador de final de arreglo.
    imprimirResultados(misresultados);
    return misresultados;
}

posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados, int * encontradas){

int direccionEncontrada;

   for(int d = 0 ; diccionario[d][0] != '\0' ; d++ ){

        if(sopa[i][j]==diccionario[d][0]){

            direccionEncontrada=RecorroDirecciones(i , j, sopa, diccionario, d);
            if(direccionEncontrada!=-1){

                misresultados = realloc(misresultados, sizeof(posicion) * (*encontradas+1));
                GuardoTodo2(i, j, d,  diccionario,&misresultados , direccionEncontrada, *encontradas);
                (*encontradas)++;

            }
        }
   }
   return misresultados;
}

int RecorroDirecciones(int i, int j, char sopa[][COLS], char * diccionario[], int palabra){
    int Iaux, Jaux=j, dir, d=1;
    static int Vfilas[] = {0, -1, -1, -1, 0, 1, 1, 1}; 
    static int Vcolum[] = {1, 1, 0, -1, -1, -1, 0, 1};

    for(dir = 0  ; dir<8 ; ){
    int  FlagDireccion = 1;

        for(Iaux = i, Jaux = j ; Iaux<FILS && Jaux<COLS && Iaux>=0 && Jaux>=0 && d < strlen(diccionario[palabra]) ; Iaux += Vfilas[dir], Jaux += Vcolum[dir] ){
            if(sopa[Iaux][Jaux]!=diccionario[palabra][d++]){
                FlagDireccion = 0;
            }
        }

        if(FlagDireccion){//pregunto si el flag es 1 -> el flag no entro porque es valido.
            return dir; //retorna la direccion en la que encontro la palabra.
        }
        dir++;
    }
    return -1;//si llega aca es que nunca encontro la palabra.
}

void  GuardoTodo2(int i, int j,int numeroPalabra,  char * diccionario[], posicion ** misresultados, int direccion, int  encontradas){

    // Crear una variable auxiliar para acceder más fácilmente al elemento
    posicion * resultado = &(*misresultados)[encontradas]; // es medio auxiliar.
    resultado->columna = j;
    resultado->fila = i;
    resultado->direccion = direccion;
    // Reservar memoria para almacenar la palabra
    resultado->palabra = malloc(strlen(diccionario[numeroPalabra]) + 1);
    strcpy(resultado->palabra, diccionario[numeroPalabra]);

}

void imprimirResultados(posicion * misresultados) {
    int index = 0;
    while (misresultados[index].palabra != NULL) {
        printf("Palabra: %s\n", misresultados[index].palabra);
        printf("Fila: %zu\n", misresultados[index].fila);
        printf("Columna: %zu\n", misresultados[index].columna);
        printf("Dirección: %d\n", misresultados[index].direccion);
        printf("--------------------------\n");
        index++;
    }
}

////////////
Palabra: ORCO
Fila: 0
Columna: 3
Dirección: 1
--------------------------
Palabra: ARRE
Fila: 1
Columna: 0
Dirección: 1
--------------------------
Palabra: PERRO
Fila: 1
Columna: 1
Dirección: 1
--------------------------
Palabra: PERTINAZ
Fila: 1
Columna: 1
Dirección: 2
--------------------------
Palabra: ARRE
Fila: 1
Columna: 2
Dirección: 1
--------------------------
Palabra: CANCION
Fila: 1
Columna: 3
Dirección: 2
--------------------------
Palabra: CAPA
Fila: 1
Columna: 3
Dirección: 1
--------------------------
Palabra: ORCO
Fila: 1
Columna: 6
Dirección: 2
--------------------------
Palabra: ERROR
Fila: 2
Columna: 1
Dirección: 1
--------------------------
Palabra: REA
Fila: 2
Columna: 3
Dirección: 1
--------------------------
Palabra: RIO
Fila: 2
Columna: 3
Dirección: 1
--------------------------
Palabra: CANCION
Fila: 2
Columna: 5
Dirección: 3
--------------------------
Palabra: CAPA
Fila: 2
Columna: 5
Dirección: 2
--------------------------
Palabra: ERROR
Fila: 3
Columna: 0
Dirección: 1
--------------------------
Palabra: REA
Fila: 3
Columna: 1
Dirección: 1
--------------------------
Palabra: RIO
Fila: 3
Columna: 1
Dirección: 1
--------------------------
Palabra: REA
Fila: 3
Columna: 2
Dirección: 1
--------------------------
Palabra: RIO
Fila: 3
Columna: 2
Dirección: 1
--------------------------
Palabra: ORCO
Fila: 3
Columna: 3
Dirección: 1
--------------------------
Palabra: REA
Fila: 3
Columna: 4
Dirección: 1
--------------------------
Palabra: RIO
Fila: 3
Columna: 4
Dirección: 1
--------------------------
Palabra: REA
Fila: 4
Columna: 1
Dirección: 1
--------------------------
Palabra: RIO
Fila: 4
Columna: 1
Dirección: 1
--------------------------
Palabra: ORCO
Fila: 4
Columna: 3
Dirección: 1
--------------------------
Palabra: ERROR
Fila: 4
Columna: 5
Dirección: 2
--------------------------
Palabra: ORCO
Fila: 5
Columna: 1
Dirección: 1
--------------------------
Palabra: ORCO
Fila: 5
Columna: 4
Dirección: 1
--------------------------

[marcelogarberoglio]

Seguís haciéndolo complicado, no sé por qué desechaste la versión de guardoTodo que te escribí. De hecho reservás copias para las palabras, pero si mirás el test las palabras no se liberan, por eso en la versión que yo te pasé copio el puntero, no la palabra completa.

Algo parecido hacés con buscopalabra, que en vez de pasarle la palabra (un char*) le pasás el vector de palabras y el índice.

En recorridoDirecciones me parece que no volvés el d a cero luego de buscar en una dirección. Si las funciones fueran más simples (por ejemplo en recorridoDirecciones que reciba sólo la palabra, y que llame a una función para uqe busque en una dirección), no sólo sería menos probable cometer errores sino que sería más fácil encontrarlos y corregirlos.

[bleite12]

Una consulta sobre la funcion que me pasaste vos. no entiendo porque no es necesario asignar memoria con un malloc a la nueva palabra.

// Recibe el puntero al struct que hay que llenar
void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion * misresultados, int direccion){
    misresultados->columna=j;
    misresultados->fila=i;
    misresultados->palabra = diccionario[numeroPalabra]; // Copio el puntero, no hace falta copiar todo el string
    misresultados->direccion=direccion;
}

[marcelogarberoglio]

Porque el diccionario está en el main, en el vector de punteros a char. En la solución simplemente copiás el puntero a char. Como son strings constantes no hay problema con eso, no es que una vez que te dan las palabras encontradas las quieras modificar, ya sea pasarlas a mayúsculas o algo así. La pista para saber si tenés que retornar una copia de la palabra (hacer malloc y strlen) o no la obtenés del testeo. En nuestro test sólo se hace free(res) que es el vector de estructuras. Si en el tesst estuviera eso que vos escribiste

  // Liberar la memoria asignada para cada palabra en cada struct posicion
    for (int i = 0; res[i].palabra != NULL; i++) {
        free(res[i].palabra); // Liberar la memoria asignada para la palabra dentro del struct
    }

    // Liberar la memoria del arreglo de estructuras
    free(res);

entonces sí habría que hacer malloc y strcpy. Ahora bien, si querés cambiar el test y dejarlo así para probar cómo hacer las copias de strings, entonces podés dejarlo. Pero en el parcial asegurate de ver bien el test, para determinar si tenés que reservar memoria y copiar los strings o directamente copiar el puntero a char

[marcelogarberoglio]

Aclaración adicional: yo me estoy basando en el test que publicamos nosotros, que está en https://drive.google.com/drive/folders/1i8lqkl9lQ08rAT1zFHKPXh6CGjzC0vac

Para entender bien qué pide el ejercicio, además del enunciado tendrían que mirar el test que publicamos

[bleite12]

clarisimo gracias. ya lo modifique y no me da ningun problema de memoria.

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

#define COLS 7
#define FILS 6

typedef enum
{
    DER = 0,
    IZQ,
    ABA,
    ARR,
    I_AR,
    I_AB,
    D_AR,
    D_AB
} Tdireccion;

typedef struct posicion {
    char * palabra;
    size_t fila;
    size_t columna;
    Tdireccion direccion;
} posicion;

posicion * resolverSopa(char *diccionario[], char sopa[][COLS]);
posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados, int * encontradas);
void imprimirResultados(posicion * misresultados);
void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion * misresultados, int direccion);
int RecorroDirecciones2(int i, int j, char sopa[][COLS], char * diccionario[], int palabra);

int main(void) {
  char * diccionario[] = {"ARRE", "CANCION", "CAPA", "ERROR", "ORCO", "PERRO", "PERTINAZ", "REA", "RIO", ""};

  char sopa[FILS][COLS] =
     {{'X','X','X','O','X','X','X'},
      {'A','P','A','C','Y','Y','O'},
      {'Z','E','Z','R','Z','C','X'},
      {'E','R','R','O','R','X','X'},
      {'X','R','I','O','I','E','X'},
      {'X','O','X','X','O','X','X'}};

  struct posicion * res = resolverSopa(diccionario, sopa);

    // Liberar la memoria del arreglo de estructuras
    free(res);

  return 0;
}

posicion * resolverSopa(char * diccionario[], char sopa[][COLS]){

    int encontradas = 0;
    posicion * misresultados =NULL; 

    for(int i = 0 ; i<FILS ; i++ ){
        for(int j = 0 ; j<COLS ; j++ ){

            misresultados = buscopalabra(i, j, sopa, diccionario, (misresultados), &encontradas);

        }
    }

    misresultados = realloc(misresultados, sizeof(posicion) * (encontradas + 1));
    misresultados[encontradas].palabra = NULL; // Indicador de final de arreglo.
    imprimirResultados(misresultados);
    return misresultados;
}

posicion * buscopalabra(int i, int j, char sopa[][COLS], char * diccionario[], posicion * misresultados, int * encontradas){

int direccionEncontrada;

   for(int d = 0 ; diccionario[d][0] != '\0' ; d++ ){

        if(sopa[i][j]==diccionario[d][0]){

            direccionEncontrada=RecorroDirecciones2(i , j, sopa, diccionario, d);
            if(direccionEncontrada!=-1){

                misresultados = realloc(misresultados, sizeof(posicion) * (*encontradas+1));
                // le paso la dirección del struct a llenar
                GuardoTodo(i, j, d,  diccionario, misresultados + *encontradas, direccionEncontrada);
                (*encontradas)++;

            }
        }
   }
   return misresultados;
}

// Recibe el puntero al struct que hay que llenar
void  GuardoTodo(int i, int j,int numeroPalabra,  char * diccionario[], posicion * misresultados, int direccion){
    misresultados->columna=j;
    misresultados->fila=i;
    misresultados->palabra = diccionario[numeroPalabra]; // Copio el puntero, no hace falta copiar todo el string
    misresultados->direccion=direccion;
}

void imprimirResultados(posicion * misresultados) {
    int index = 0;
    while (misresultados[index].palabra != NULL) {
        printf("Palabra: %s\n", misresultados[index].palabra);
        printf("Fila: %zu\n", misresultados[index].fila);
        printf("Columna: %zu\n", misresultados[index].columna);
        printf("Dirección: %d\n", misresultados[index].direccion);
        printf("--------------------------\n");
        index++;
    }
}

int RecorroDirecciones2(int i, int j, char sopa[][COLS], char * diccionario[], int palabra) {
    static int Vfilas[] = {0, -1, -1, -1, 0, 1, 1, 1}; 
    static int Vcolum[] = {1, 1, 0, -1, -1, -1, 0, 1};

    for (int dir = 0; dir < 8; dir++) {
        int Iaux = i;
        int Jaux = j;
        int d = 1; // Empieza en 1 porque el primer carácter ya coincidió
        int FlagDireccion = 1;//reset del flag en todas las direcciones.(esto me fallo en la version anterior creo.)
        while (d < strlen(diccionario[palabra]) ) {
            Iaux += Vfilas[dir];
            Jaux += Vcolum[dir];

        // Verificar si la posición está dentro de los límites
            if (Iaux < 0 || Iaux >= FILS || Jaux < 0 || Jaux >= COLS) {
                FlagDireccion = 0; // Si sale de los límites, la dirección no es válida.
                break; // Salir del bucle while.
            }
            // Comparar el siguiente carácter
            if (sopa[Iaux][Jaux] != diccionario[palabra][d]) {
                FlagDireccion = 0;
                break; // sale de el bucle while
            }
            d++; //pruebo con el siguiente caracter.

        }//luego veo si el flag quedo en 1 -> la palabra fue encontrada y ya puedo dejar de probar distintas direcciones.

        if (FlagDireccion) {
            return dir; // Retorna la dirección si la palabra fue encontrada completamente
        }
    }//si el flag se puso en 0-> pruebo otra direccion

    return -1; // Si no se encontró la palabra entonces llegue hasta aca.)( se me terminaron las direcciones)
}

[marcelogarberoglio]

Genial, me alegro de haber sido claro, cualquier duda adicional avisanos.