Hanoi
Existe un juego matemático muy famoso llamado Las Torres de Hanoi donde se deben transpasar un número determinado de discos (cada uno mayor al anterior) de una “torre” a otra utilizando una “torre” auxiliar sin que un disco grande quede encima de uno más pequeño (lo más fácil si no se conoce el juego es visitar la página de la Wikipedia que enlazo, porque no consigo explicarlo más claro en un párrafo).
Esta mañana he estado hablando con varias personas del examen de mañana de Desarrollo Sistemático de Programas (que no es más que un curso de algoritmos y complejidad, pero bueno) y he recordado lo sencilla que es la solución del problema de las Torres de Hanoi y he decidido hacerlo en Ruby (por practicar):
def hanoi(discos, desde, hasta, usando)
if discos > 1
hanoi(discos-1, desde, usando, hasta)
hanoi(1, desde, hasta, usando)
hanoi(discos-1, usando, hasta, desde)
else
print desde, ‘>’, hasta, “\n”
end
end
El código (una vez llamado, como por ejemplo hanoi 3, 1, 2, 3) imprimirá la lista de movimientos (de la “torre” x a la “torre” y) para el número de discos indicados (el primero parámetro), los tres parámetros restantes son la “torre” donde están todos los discos inicialmente, la “torre” donde deben acabar y la “torre” auxiliar.
No hay backtracking (simplemente recursividad), pero quizá sirva para inspirar mañana algo en el examen.
Buscando en Google he encontrado Hanoimania!, un repositorio de implementaciones de las Torres de Hanoi: su implementación en Ruby es parecida (y eso que yo creía que se podría eliminar el if... else con algo “mágico” de Ruby).
Ver entradas relacionadas
- No se han encontrado entradas relacionadas
7 de Septiembre de 2006 a las 19:42
Seminario practico de ruby ya!!!
7 de Septiembre de 2006 a las 22:43
Como aludido de tener mañana examen de esta maravillosa asignatura que como sigamos así, desaparecerá en breve (en 1º no dan haskell, y nos entra todos los temas menos backtracking de solucion optima y divide y vencerás…..) haciendo estudios sobre los últimos exámenes se nota claramente que el nivel de tipo test es amplio, incluso llegando a la totalidad….
No busques lo de las torres, veríamos más la luz si esta mañana o por la tarde te hubieras infiltrado en el despacho de “estos” y nos cuelgas aquí, en pdf, el enunciado de mañana. Si lo tienes en otro formato, pues bueno, que le vamos a hacer.
P.D. Seminario práctico de Ruby YA! Las segundas partes me encantan
7 de Septiembre de 2006 a las 23:16
¿En primero ya no se da Haskell? Pues una verdadera lástima, sobre todo si quieren mantener su status de carrera seria. Siguiendo ese camino convertirán la carrera en una carrera Java de las que tanto abundan en otros sitios.
PD: Sí, yo también quiero un seminario de Ruby. Encargaros que venga Matz o Dave Thomas y yo co-presento con gusto (sobre todo si el otro prepara las transparencias).
7 de Septiembre de 2006 a las 23:52
¿Qué Dave Thomas quieres?
¿El modelo cantante?,¿el empresario?,¿el modelo jugador de futbol? o ¿el Dave Thomas industrialista? ¿el geografo? ¿o el programador?
Creo que este se diferencia de los demás,porque tiene un sombrero nuevo….
8 de Septiembre de 2006 a las 01:03
Me ha dicho “yuki” que el sabado se puede pasar por el “kine” (palabras textuales) para ver Clerks2; por otra parte dave no me coge el movil, mañana lo sigo intentando.
8 de Septiembre de 2006 a las 01:20
alfrodo: ¡Ups! Corregido (eso pasa por poner enlaces a la Wikipedia sin mirar).
Gandalfj: errrr… perfecto… supongo.
8 de Septiembre de 2006 a las 09:47
Una pena si quitaran haskell.. estos días ha habido movimiento desepero por aquí, se notaba que el examen estaba próximo. Por cierto, una curiosidad relacionada. Para quien esté a tiempo, la asignatura se llama “Diseño de sistemas de control discreto”, no tiene examen, no hay que ir a clase, y toda la nota cae en esta práctica (programar un robot para que pueda realizar movimientos y demostrar dicha programación con el ejemplo de las torres :-D)
8 de Septiembre de 2006 a las 13:20
¿Y en qué curso está, oh Gran Deigote?
8 de Septiembre de 2006 a las 16:28
deigote: ¡Esta genial! Yo me cogí Robótica y no he visto más que esquemas de robots garabateados en la pizarra, como me gustaría saber las asignaturas que están bien antes de cagarla. Una pregunta ¿el robot “veía” o hacía los movimientos “a lo tonto”? ¿y la pieza de la mitad qué le pasó?
alfrodo: Libre de Elección de 5º.
8 de Septiembre de 2006 a las 16:59
No es de libre, es optativa (de 5º, si), por lo menos cuando yo la hice
lo cual es incluso mejor.
El robot no veía, la asignatura se basa más en aplicar la programación concurrente que otra cosa. La práctica consiste en programar una interfaz al robot (en ADA o C) que permita moverlo a posiciones específicas. Dicha interfaz, por debajo, tiene un objeto protegido que representa los 4 ejes del robot y 4 tareas encargadas de solicitar los movimientos para que dichos ejes muevan el robot a las posiciones solicitadas. El usuario de la interfaz solo tiene que pedir un movimiento a la posición concreta y la velocidad de dicho movimiento.
Luego era cuestión de hacer un programa con la lista de posiciones de la torre. Precisamente el hecho de ser tan manual hizo que la prueba del video casi fallase (por los pelos :-D), ya que debíamos colocar las piezas en su sitio con buena precisión
La asignatura no era la pera, pero sí era entretenida y muy “libre” (en el sentido de hacerla totalmente a tu bola).
PD: Con comentarios tan largos la vista previa live se realentiza un pelín :-)…
8 de Septiembre de 2006 a las 17:29
Por cierto, veo por aquí movimiento de “fin de examen” así que.. ¿cómo ha ido :D?
8 de Septiembre de 2006 a las 19:14
Interesante, lo que no entiendo muy bien es lo que comentas de la programación concurrente y porqué os afectaba si érais los únicos que manajábais el robot. ¿Supongo que tendrá algo que ver con tener que recibir y enviar ordenes al mismo tiempo?
Lo del la vista previa, he estado probando con tu comentario y no va del todo mal (en mi Safari, pero Firefox siempre ha sido mejor en JavaScript que Safari). Si mal no recuerdo se actualiza cada cierto tiempo, aunque creo que la versión de tu blog es más inteligente y utilizaría menos recursos (y por lo que vi del código te muestra el resultado verdadero, no como esta, que te muestra algunas cosas y otras no).
8 de Septiembre de 2006 a las 23:04
Sobre lo del robot, es concurrente porque cada eje es independiente y tienes que pararlo cuando llega a las coordenadas (haciendo polling, creo que esa es la clave de la concurrencia, el robot no envía ninguna orden), tienes cuatro tareas, una por eje. El robot solo tiene sensores en el tope del eje y un contador de pulsos. Inicialmente hay que hacer una medida para caracterizar el movimiento del robot (100% a mano, con una regla de las de Intercysa :D), y luego a partir de ahi decirle “¿cuantos pulsos llevas?” “30″, “pues sigue” o “pues parate”, eso cada tarea. Sin concurrencia, el robot sólo movería un eje en cada momento, ya que tendrías que hacer espera activa
si, es un poco cutre, pero los profes aseguran que los robots industriales tienen un funcionamiento similar (u¬¬)
Sobre la vista previa, no sé, yo me bajé un plugin (en el about de mi blog puedes ver una lista) y lo modifiqué porque por defecto estaba en actualizar cada vez que pulsabas una tecla (en mi blog se realentizaba infinitamente más, sobre todo al poner blockquotes, que tienen una imagen de fondo y tal).
24 de Noviembre de 2007 a las 03:52
alguien me puede decir como hacer un programa en haskell de las torres de hanoi que imprima los movimientos porfa
25 de Noviembre de 2007 a las 23:56
1. Haz tus propios deberes.
2. Si no quieres hacerlos no intentes que te los hagan otros.
3. La función de más arriba (con mínimos conocimientos de Haskell) debe ser casi igual en casi todos los lenguajes de programación (excepto quizá la parte de imprimir, que si mal no recuerdo en Haskell se hacía con mónadas y esas cosas).