Brute Force Iterativo

[N0body]

Esto va para principalmente para Littlehorse, que me había pedido (hace mucho mucho mucho tiempo, quizás ni se acuerde) un brute force iterativo (yo había posteado uno recursivo).

Y aquí va:

Código (c) [Seleccionar] Expandir

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

int main(int argc, char *argv[])
{
  int contadores[50], len, cant, i;
  char caracteres[200], pass[50];

  printf ("Ingrese los caracteres a usar para la contrasena: ");
  scanf ("%s", caracteres);

  printf ("Ingrese la longitud de la contraseña: ");
  scanf ("%i", &len);

  cant = strlen (caracteres);

  /*contadores = (int *) malloc (sizeof (int) * (len+1) );
  pass = (char *) malloc (len+1);*/

  for (i=0 ; i<len ; i++)
    {
        pass[i] = caracteres[0];
        contadores[i] = 0;
    }
  contadores[i] = 0;
  pass [i] = '\0';
    //Inicio bucle

    while (!contadores[len])
    {
        printf ("%s\n", pass);

        for (i=0;contadores[i]==cant-1;i++)
            pass[i] = caracteres [contadores[i] = 0];

        pass[i] = caracteres [++contadores[i]];
    }

  /*free (contadores);
  free (pass);*/

  system("PAUSE");
  return 0;
}

[Littlehorse]

Lo recuerdo por supuesto, debo tener muchos defectos pero la mala memoria seguro no es uno! 

Has hecho algunas mediciones de tiempo a ver que tal? 

Un gusto verte por acá otra vez.

Saludos!

[Gallu]

Que es lo que hace exactemente éste programa? , la verdad no entiendo su finalidad .

[biribau]

Me ha costado entenderlo, pero el bucle interno es simplemente una propagación del acarreo de una suma, un incremento de uno. Lo que hace es generar todas las combinaciones de claves posibles de una longitud con un set de caracteres. Por qué no usas malloc/free, que lo tienes comentado?
Aunque no veo como integrarlo, tendría más sentido en perl, que puedes pasarle el comando de encriptacion.

[Gallu]

O sea que es un generador de contraseñas .... ya veo 

[N0body]

Resultando la próxima combinación: 2111

El bucle interior hace que cuando la primera cifra esté en 0 (último digito en nuestra lista de cifras a utilizar) la vuelve a 1 (al principio) y avanza una la siguiente cifra.

Osea que si está 0111 lo convertirá a 1211

A su vez ese bucle se fija si esta segunda cifra no estaba (en el momento de hacerla avanzar) en su última letra y si lo fuese avanza la tercer.

Osea que si está en 0011 lo convertirá a 1121



¿Más o menos como un humano obtendría todas las combinaciones no?

Claro que detrás de esto, cuando se plasma el algoritmo pensado a código se usan recursos adicionales, como un vector de largo "longitud de password"+1 para que vaya indicando en que posición de la lista de los caracteres que combinaremos, está ubicado cada caracter de nuestra contraseña. (Se entiende mejor leyendo el código).
Así si nuestra lista es: "12ab"
Y nuestra contraseña es de 3 dígitos

Cuando el programa (entre todas las combinaciones que muestre) imprima: 1ba
Los números del vector explicado serán (en este orden) 0 3 2 (ya que el 1, es la letra

• de "12ab", b es la letra [3] y a la letra [2] )
  
  No es inútil este vector adicional, como verán ya que no siempre tendrán listas de caracteres a usar (o listas "fuentes" como me gusta llamarles) que son continuas en la tabla ASCII. Porque de ser así (de ser una lista continua como "abcdefg") no usaría el vector numérico del que hablaba y iría sumando +1 para hacer que la "a" se convierta en "b", la "b" en "c", etc hasta "g".
  Pero en listas como "12ab" si sumo +1 a '2' obtengo '3' y no 'a'
  
  ¡Espero que se haya entendido! (cualquier cosa, está el código,pero no comentado)
  
  
  
  
  Y para Littlehorse que me pidió  las mediciones aquí están:
  
  Caracteres usado: "1234567890" (osea 10).
  Longitud de password: 7.
  Osea un total de 10^7 combinaciones, diez millones. Me pareció un número razonable. Ni muy mucho (porque cerré casi todo para hacer el test y no quería pasar mucho tiempo despegado de la pc xD), ni muy poco (porque si es poco pequeñas fluctuaciónes en la velocidad del procesador, procesos que activan, etc; influyen en mayor medida)
  Resultados:
  
  Iterativo:432
  Recusivo:593
  Diferencia: 2 min 41 segundos
  Por eso sigo defendiendo A MUERTE la iteración! xD

[biribau]

Un consejo que convendrá saber: Recursividad > iteración siempre, es más expresiva, hay cosas recursivas que no pueden hacerse iterativas, pero todas las iterativas pueden hacerse recursivas. Iteración sólo podrá ser mejor en eficiencia, cuestión que depende puramente de la implementación.

Por eso conviene saber utilizarla cuanto más mejor. Practíquenla! 

[N0body]

Correctísimo lo que dices.
Te dejo en este caso el código del Brute Force recursivo y vas a ver que el planteamiento en ambos casos difiere muchísimo. En el iterativo es como ya lo expliqué anteriormente, y el recursivos es más como una anidación de "n" sentencias for. "n" es variable y por lo tanto esto es sólo posible gracias a la recursividad.

Código (c) [Seleccionar] Expandir

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

void brute_force (char caracteres[], int cant, int pos, char *password)
    {

        if (pos==-1)
            {
            printf ("%s\n", password);
            return;
            }
        int i;
        for (i=0;i<cant;i++)
            {
            password[pos]=caracteres[i];
            brute_force (caracteres, cant, pos-1, password);
            }
        return;

    }

int main(int argc, char *argv[])
{
    char caracteres[256], *password;
    int longitud, cantidad;
    double tiempo;
    time_t t1, t2;

    printf ("Ingrese los caracteres a usar: ");
    scanf ("%s", caracteres);
    cantidad = strlen(caracteres);

    printf ("Ingrese la longitud maxima de la contraseña: ");
    scanf ("%i", &longitud);

    password = (char*) malloc (longitud*sizeof(char));

    time (&t1);
        password[longitud]= '\0';
    brute_force (caracteres, cantidad, longitud-1, password);
    time (&t2);
    tiempo = difftime (t2, t1);
    printf ("\tTiempo: %7.2f\n\n", tiempo);
    free (password);
    system("PAUSE");
    return 0;
}

Hay veces en que no te das cuenta como resolver un problema y verdaderamente recursivamente puede ser resuelto.

Se destacan, además, muchos métodos de ordenamientos recursivos.

Hay veces en que conviene utilizarla y hay veces en las que un planteamiento se debe hacer en forma recursiva... Por eso conviene saber COMO y CUANDO implementarla, darse cuenta rápido.

Pero también hay abusos a ella, haciéndose cosas que se podrían tranquilamente y casi sin ningún cambio, iterativamente.
Pero como vemos, en este programa, si bien el recursivo y el iterativo "hacen" lo mismo; el problema está planteado de diferentes formas...

[biribau]

Tienes razón en todo,
sólo quiero añadir una cosa, dije que hay cosas recursivas que no se pueden hacer iterativas, no es del todo cierto, se puede simular con un algoritmo iterativo y "algo más", concretamente una pila LIFO por ejemplo, de hecho así lo hace a bajo nivel un procesador, el intel x86 por ejemplo(call xx == push eip+a; jmp xx)

Tambien es útil saber esto a veces para optimizar códigos(llamada a procedimientos suele ser más cara ya que se suelen meter en pila más cosas y ejecutar prólogos y epílogos, todo esto se puede ahorrar intenciodamente)

Gran código, otra ventaja de la recurisividad es que apuesto a que te costó mucho menos tiempo programarlo que el iterativo. A mi me costó menos entenderlo(me parece más fácil de leer). A veces también hay que tener en cuenta el tiempo que perdiste programándolo y depurándolo, no sólo el tiempo en que hace su tarea. En suma, cual gana?

[N0body]

 Para concluir, diría que no se puede decir que un método gane al otro. Son herramientas, con sus respectivas ventajas y desventajas.
Y quería destacar una cosa en la conclusión:
Hay que aprender a usar la recursividad cuando hay que hacerlo. Hay muchos casos que este mecanismo (el de la recursividad) debe ser usado para plasmar cierta resolución del problema y muchas veces, si no se tiene práctica, uno no se da cuenta de como hacerlo