13 de Abril, 2011

Misioneros y caníbales, en Python

Continúa la saga, después de implementar la solución al problema de los misioneros y los caníbales en Ruby, y luego en Perl y en C, ahora me he puesto con Python: miscan.py.

Las reglas del puzzle son las mismas:

Tres misioneros y tres caníbales quieren cruzar un río. Solo hay una canoa que puede ser usada por una o dos personas, ya sean misioneros o caníbales.

Hay que tener cuidado en que en ningún momento el número de caníbales supere al de misioneros en ninguna de las dos orillas, o se los comerán.

Python es el lenguaje con el que trabajo a diario, así que ha resultado interesante revisar conocimientos probando una implementación diferente.

La estrategia al final es la que he empleado en las otras implementaciones, utilizando backtracking, de forma que partiendo de un estado inicial se intenta llegar al estado final probando viajes posibles.

Si en un estado agotamos todas las posibilidades sin encontrar un estado válido nuevo (osea, que no volvemos a un estado ya visitado), descartamos esa solución y probamos con los viajes que nos quedaban en el estado anterior.

El juego acaba cuando nos quedamos atascados en un estado sin viajes viables (no pasará :P), o llegamos al estado final deseado.

Lo más destacable es que he utilizado un objeto para los estados. No es que sea necesario, pero simplifica las operaciones gracias a que podemos utilizar el interfaz del objeto para interactuar con él como con cualquier otro tipo de Python:

  • __str__(self): nos permite usar print sin más para visualizar un estado en bonito.
  • __eq__(self, other): para comparar objetos con el operador == habitual (he implementado __ne__ por completar, pero no es necesario).
  • viaja(self, gente): aplica un viaje, devolviendo un nuevo objeto Estado (sí, los caníbales son gente también :P).

Además he usado excepciones para validar los estados, list() para hacer una copia simple de una lista, y copy.deepcopy() para copiar el vector de vectores que contiene los estados, porque Python, al igual que Ruby y Perl, trabaja con referencias y no hace copias de todos los tipos.

Nuevamente, el orden en el que se toman los viajes posibles afecta al resultado:

$ ./miscan.py 
Tenemos un resultado!
M: 3 C: 3 | \___/~~~~~~~~ | M: 0 C: 0
M: 3 C: 1 | ~~~~~~~~\___/ | M: 0 C: 2
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

En este caso los responsables son dos métodos de las listas: append y pop, que permiten trabajar con la lista como si fuera una pila, pero apilando y desapilando elementos al final de la lista, y no al principio como pasa en Ruby y en Perl.

La verdad es que ha sido entretenido, porque no es el tipo de problema que resuelvo cada día. Aún me falta para que se me acaben los lenguajes, ¿la siguiente versión quizás en Javascript? ¿Alguien se anima?

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

Hay 4 comentarios

Gravatar

Yo voy a intentarlo en javaScript. Estoy aprendiendo ese lenguaje ahora y me vendrá bien. En cuanto estudie como funcionan los objetos, me pondré con ello.

por yabu, en 2011-04-14 11:57:42

Gravatar

@yabu: si tienes oprtunidad, échale un ojo a: JavaScript: The Good Parts

A mi me ha abierto los ojos completamente hacia un mundo de posibilidaes ;)

por Juanjo, en 2011-04-14 12:02:25

Gravatar

Me ha impresionado la implementación en python, esperaba algo mucho más sencillo. La verdad, he tardado lo suyo en entenderlo completamente.

Soberbio y de muy interesante lectura, sobre todo el código fuente con la solución.

por r0sk, en 2011-04-19 09:23:01

Gravatar

Gracias!

La verdad es que ha quedado más compacto que las otras versiones, pero sin intención, porque quería que fuera legible.

por Juanjo, en 2011-04-19 09:39:14

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: