franvinas / taller1-tp1

0 stars 0 forks source link

Esto es un poco ineficiente #25

Open fedemgp opened 3 years ago

fedemgp commented 3 years ago

https://github.com/franvinas/taller1-tp1/blob/5c86accb887b25b72b850cb5a132fc02b24ccf09/common_game_state.c#L35-L36

Hablando de complejidad algorítmica, la función hangman_contains_letter tiene una complejidad temporal O(n^2) (por el ciclo for de esa función y por este memchr). Esto se podría haber solucionado primero seteando la letra adivinada en sus respectivas posiciones, y luego de terminar de iterar el string, chequear que no haya mas letras por adivinar.

// asumo que hangman_t tiene un atributo guesse_word, inicialmente inicializado a N chars idénticos de valor '_',
// un atributo secret_word con la palabra secreta y len (la longitud de la palabra secreta)
static bool hangman_contains_letter(hangman_t *self, char c) {
    bool guess = false;
    for (int i = 0; i < self->len; i++) {
        if (self->secret_word[i] == c) {
            guess = true;
            self->guessed_word[i] = c;
        }
    }
    if (!guess) self->tries --:
    if (memchr(self->guessed_word, EMPTY_LETTER, self->len) == NULL)) self->game_over = true;

    return guess;
}
fedemgp commented 3 years ago

Esta implementación tendría complejidad O(n). Esto es un tema que vas a ver en detalle en teoría de algoritmos (si la hacés) por lo que no se te bajará puntos por esto, pero tenelo en cuenta.

fedemgp commented 3 years ago

(aunque es un tema que debería haber sido presentado en algoritmos 2)

fedemgp commented 3 years ago

Notar que la clase hangman se encarga deimplementar la lógica del juego, y es el único en hacerlo. Tu TDA game_state sería un objeto sin comportamiento, un DTO hecho y derecho (y tiene sentido hacer un TDA 'simple' sin lógica, para facilitar el manejo del mensaje que se serializa)