Acertijo

[Daniel Garcia]

El mar, 21-10-2008 a las 21:12 +0200, Arnau Sanchez escribió:
> Daniel Garcia Moreno escribió:
> 
> > Hola, hace poco recibí un correo electrónico con un acertijo y me puse a
> > implementar una solución en python, pero no he conseguido sacar la
> > solución en un tiempo aceptable. Hice una implementación en Haskell que
> > tarda sobre 20 minutos en resolverlo, pero en python tarda mucho más.
> > 
> > ¿Alguien sabe cómo resolverlo? Ya sea de manera funcional o
> > procedimental.
> 
> He probado tu código, pero tras un buen rato corriendo me ha dicho '[]', 
> seguramente hice algo mal.

No creo, seguramente en mi código haya alguna condición de más.

> 
> En cualquier caso, en recuerdo a los viejos tiempos de instituto en que nos 
> ponían problemas de este tipo (para hacerlos a mano), he preparado una posible 
> solución:
> 
> http://tokland.freehostia.de/acertijo.py
> 
> $ time python acertijo.py
> [['swedish', 'white', 5, 'dog', 'blue', 'beer'],
>   ['german', 'green', 4, 'fish', 'prince', 'coffee'],
>   ['english', 'red', 3, 'bird', 'pall', 'milk'],
>   ['danish', 'blue', 2, 'horse', 'blends', 'tea'],
>   ['norwegian', 'yellow', 1, 'cat', 'durn', 'water']]
> 
> real	0m2.339s
> user	0m2.132s
> sys	0m0.016s
> 
> ¿Es ésa la solución? Tarda poco más de 2 segundos, pero sin duda se podría 
> optimizar.

Sí, esta es.

> Diría que tú implementación va muy lenta porque tratas todas las pistas de la 
> misma forma, cuando de hecho se pueden separar en dos: a) las que indican 
> relaciones directas (las uso como estado inicial de la matriz, lo que ahorra 
> muchas iteraciones) y b) las pistas relativas a la posición de las casas (esto 
> sí que tiene que ser implementado por código).
> 
> La solución es funcional, excepto una asignación en la matriz (que se puede 
> hacer funcional, pero no sería muy idiomático en Python)
> 
> Eso sí, código sin comentar, sin tests, en fin, un desastre :-p

Estudiaré el código

------------ próxima parte ------------
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes