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?