12 de Marzo, 2010

Misioneros y caníbales, en C

Porque no hay dos sin tres, después de resolver el puzzle de los misioneros y los caníbales en Ruby y volver a hacerlo en Perl, lo he implementado en C: miscan.c.

Para mi sorpresa me ha resultado más fácil y rápido de implementar que en Perl, aunque depurar los fallos ha sido más complicado (Segmentation fault y a tirar de gdb, claro :P).

Además he usado la GList de la librería glib2 para la parte del backtracking, por simplificar (me podría haber implementado una lista doblemente enlazada para el caso, pero seamos realistas... ahí no hay diversión :D).

Como siempre, tener acceso a bajo nivel a la memoria y punteros tiene ventajas e inconvenientes, pero además he podido confirmar dos cosas:

$ time ./misio_can.pl 
Resultado: 
M: 3 C: 3 |\____/ ~~~~~~~~~~| M: 0 C: 0
M: 2 C: 2 |~~~~~~~~~~ \____/| M: 1 C: 1
M: 3 C: 2 |\____/ ~~~~~~~~~~| M: 0 C: 1
M: 3 C: 0 |~~~~~~~~~~ \____/| M: 0 C: 3
M: 3 C: 1 |\____/ ~~~~~~~~~~| M: 0 C: 2
M: 1 C: 1 |~~~~~~~~~~ \____/| M: 2 C: 2
M: 2 C: 2 |\____/ ~~~~~~~~~~| M: 1 C: 1
M: 0 C: 2 |~~~~~~~~~~ \____/| M: 3 C: 1
M: 0 C: 3 |\____/ ~~~~~~~~~~| M: 3 C: 0
M: 0 C: 1 |~~~~~~~~~~ \____/| M: 3 C: 2
M: 1 C: 1 |\____/ ~~~~~~~~~~| M: 2 C: 2
M: 0 C: 0 |~~~~~~~~~~ \____/| M: 3 C: 3

real	0m0.043s
user	0m0.021s
sys	0m0.006s

$ time ./miscan 
Resuelto, 12 pasos:
M: 3 C: 3 |  \__/ ~~~~~~~~~  | M: 0 C: 0
M: 2 C: 2 |  ~~~~~~~~~ \__/  | M: 1 C: 1
M: 3 C: 2 |  \__/ ~~~~~~~~~  | M: 0 C: 1
M: 3 C: 0 |  ~~~~~~~~~ \__/  | M: 0 C: 3
M: 3 C: 1 |  \__/ ~~~~~~~~~  | M: 0 C: 2
M: 1 C: 1 |  ~~~~~~~~~ \__/  | M: 2 C: 2
M: 2 C: 2 |  \__/ ~~~~~~~~~  | M: 1 C: 1
M: 0 C: 2 |  ~~~~~~~~~ \__/  | M: 3 C: 1
M: 0 C: 3 |  \__/ ~~~~~~~~~  | M: 3 C: 0
M: 0 C: 1 |  ~~~~~~~~~ \__/  | M: 3 C: 2
M: 0 C: 2 |  \__/ ~~~~~~~~~  | M: 3 C: 1
M: 0 C: 0 |  ~~~~~~~~~ \__/  | M: 3 C: 3

real	0m0.003s
user	0m0.000s
sys	0m0.002s

Aparte de que es evidente que un programa en C es más rápido que uno en Perl (no me he podido resistir a hacer la comparación :D), y de que la canoa que he dibujado en C es más churro que la canoa en Perl; el resultado obtenido es distinto.

Las dos soluciones son válidas (recordamos que buscamos una solución culquiera), pero son claramente distintas. ¿Alguien sabe decirme por qué?

Anotación por Juan J. Martínez, clasificada en: programming, c.

Hay 2 comentarios

Gravatar

Buenas...

La diferencia está en la definición de los viajes posibles.

Los dos primeros componentes del vector @viajes en Perl no son los mismos que el vector viajes[5][2] en C.

por Joaquín Ferrero, en 2010-03-13 02:04:28

Gravatar

Por eso dan resultados diferentes, porque cambia el orden de los viajes posibles a probar.

Bien visto :)

por Juanjo, en 2010-03-13 09:02:13

Los comentarios están cerrados: los comentarios se cierran automáticamente una vez pasados 30 días. Si quieres comentar algo acerca de la anotación, puedes hacerlo por e-mail.

Algunas anotaciones relacionadas: