Acertijo

[Arnau Sanchez]

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.

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.

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

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