Asombrosa solución del problema

Pues si, no se si alguien lo ha intentado pero la resolución es asombrosa. Parece mentira que la cosa pueda funcionar y seguramente la mayoría dude de que funcione:

Creamos un fichero de texto llamado hanoi.lsp por ejemplo.

(defun hanoi (num-discos torre-origen torre-auxiliar torre-destino)
    (when (> num-discos 0)
        (hanoi (1- num-discos) torre-origen torre-destino torre-auxiliar)
        (format t "~%Mover disco superior de la torre ~D a la torre ~D."
            torre-origen torre-destino)
        (hanoi (1- num-discos) torre-auxiliar torre-origen torre-destino)
    )
    T
)

Cargamos la función en el interprete lisp:
> (load 'hanoi)

y ya podemos verlo en funcionamiento:

Para 5 discos, torre 1 de origen, torre 2 auxiliar y torre 3 destino...

> (hanoi 5 1 2 3)

El resultado para (hanoi 4 1 2 3) es el siguiente:

> (hanoi 4 1 2 3)                                 
                                                  
Mover disco superior de la torre 1 a la torre 2.  
Mover disco superior de la torre 1 a la torre 3.  
Mover disco superior de la torre 2 a la torre 3.  
Mover disco superior de la torre 1 a la torre 2.  
Mover disco superior de la torre 3 a la torre 1.  
Mover disco superior de la torre 3 a la torre 2.  
Mover disco superior de la torre 1 a la torre 2.  
Mover disco superior de la torre 1 a la torre 3.  
Mover disco superior de la torre 2 a la torre 3.  
Mover disco superior de la torre 2 a la torre 1.  
Mover disco superior de la torre 3 a la torre 1.  
Mover disco superior de la torre 2 a la torre 3.  
Mover disco superior de la torre 1 a la torre 2.  
Mover disco superior de la torre 1 a la torre 3.  
Mover disco superior de la torre 2 a la torre 3.  
T

Lo más importante es que para estas soluciones mágicas hay que asegurarse bien de que se pueda solucionar recursivamente. En el caso de HANOI era fácil, ya que es el problema recursivo más clásico de todos.

Saludos.

Continuación de Torres de Hanoi en Lisp...

En el post anterior planteé el problema e hice un planteamiento inicial, pero no llegué a terminarlo. En este post espero llegar a la resolución en pseudocódigo.

Dejé el tema planteando el problema para 4 discos.
Recordemos que el planteamiento de 3 discos se puede resumir así:

1. Si hay 3 discos en la torre A, conseguir mover los 2 de arriba a la torre B.
2. Una vez que estén en la torre B, mover el disco grande de la torre A a la C.
3. Para terminar mover los 2 discos de la torre B a la torre C.

Sabiendo que hay solución RECURSIVA, ¿podemos extrapolar esta solución a N discos?

Sería tanto como decir que si hay 4 discos tenemos que hacer...

1. Conseguir como podamos mover los 3 discos más pequeños a la torre B.
2. Mover el disco más grande de la torre A a la C.
3. Mover los 3 discos más pequeños de la torre B a la C

Ahora nos centramos en el problema de como mover los 3 discos más pequeños de la Torre A y colocarlos perfectamente en la Torre B. Esto antes de escribirlo voy a pensarlo...

1. Mover el más pequeño a la torre B.
2. Mover el mediano a la torre C.
3. Mover el pequeño a la C encima del mediano.
4. Mover el grande a la B.
5. Mover el pequeño a la A.
6. Mover el mediano a la B.
7. Mover el pequeño a la B.

¡Eh, para, para!
Ya veo la luz...
Resulta que el caso de 3 discos es un caso muy similar al de 4.

En ambos casos se hace lo siquiente:

1. Miramos cuantos discos hay en la Torre A. Movemos todos menos el más grande a la
   Torre C.
2. Mover el disco más grande de todos a la torre B.
   
3. Mover los otros discos a la torre B.

¡UY! Ahora veo otra cosa. Antes me he centrado en mover los discos de forma ordenada a la torre C, y en cambio en otras ocasiones tengo que mover de forma ordenada a la torre B. Sin embargo el algoritmo curiosamente es el mismo. Voy a simplificar renombrando las torres. En lugar de torre A, B y C, las llamaré torre origen, destino y auxiliar. Esto se debe a que dependiendo del movimiento general que queramos hacer las torres origen, destino y auxiliar varían.

Por lo tanto, para mover una pirámide de discos de ORIGEN a DESTINO debemos hacer lo siguiente:

1. Si hay N discos, hay que mover N-1 discos de ORIGEN a AUXILIAR.
2. El disco más grande de todos lo movemos directamente de ORIGEN a DESTINO.
3. Por último movemos los N-1 discos de AUXILIAR a DESTINO.

Ya vemos que el caso más sencillo va a ser el de 2 discos.
Luego en el de 3 discos hay que mover primero los 2 de arriba como hemos visto y luego mover el que queda.
Con 4, hay que mover los 3 de arriba (como hemos visto en la línea anterior) y por último el más grande.
Así hasta el infinito.

En el post de mañana la solución lisp.
A ver si alguien se anima y cuelga la solución en forma de comentario...

Saludos.

Torres de Hanoi en Lisp

Hola,

La ventaja de que nadie siga tu blog es que puedes cambiar de tema sin que nadie se flipe.

Por eso vuelvo al tema del Lisp. Que yo recuerde la última vez lo deje en la función fibonacci recursiva.

Hoy vamos a resolver el primer problema puramente recursivo. Y ¿eso que significa? Que no se si está matematicamente demostrado o no (creo que SI, pero tampoco importa), pero cualquier problema que se puede resolver de forma recursiva puede resolverse también de forma no recursiva.

Ahora bien, en un problema puramente recursivo lo que ocurre es que la solución revursiva es sencilla de entender y en cambio la no recursiva se vuelve enormemente complicada.

Pensemos en el problema tal y como lo planteé en su día: http://aitoreus.blogspot.com/2006/02/torres-de-hanoi.html

O sea, tenemos 3 torres. Las llamaremos A, B y C.
Hay 64 discos montados en la torre A que hay que llevar a la torre C.
Las reglas son 2:

1. No se puede mover más de un disco cada vez.
2. No se puede colocar un disco mayor sobre otro menor.

No lo he dicho, pero los 64 discos que inicialmente están en la torre A se encuentran cumpliendo la regla 2.

Tenemos una pista buenísima y es que el problema es RECURSIVO.

O sea, podemos encontrar la solución pensando en verde.

Ummm,

Como empezaríamos a hacerlo manualmente...

Espera tengo una idea, en temas de recursividad muchas veces hay que simplificar el problema.

Si sólo hubiera un disco en la torre A... Movemos el disco a la torre C y problema terminado.

Si hay 2 discos. Movemos el primero (el más pequeño) a la torre B. Luego el segundo (el más grande que estaba debajo) a la torre C. Por último el pequeño a la torre C y problema terminado.

Si hay 3 discos. ¿Movemos el primero a la torre B?. Bueno, entonces el siguiente disco (el mediano de los 3) va a la torre C. Luego estamos obligados a colocar el pequeño de la torre B en la torre C. Una vez hecho esto podemos sacar el grande y ponerlo en B. Ahora bien, hay que librar la torre C de los 2 discos y eso nos lleva a un montón de movimientos. Era mejor hacer exactamente lo mismo pero empezando a mover a la torre C. Así los 2 discos pequeños se quedan colocaditos en B y la C está libre para el grande.

Bueno, ya sólo queda mover el grande al C, el pequeño al A, el mediano al C y el pequeño al C.

¿Que ocurre en el caso de 4 discos? Ahora si que toca pensar, ya que el número de movimientos puede ser brutal.

Sorpresas en Ruby

Jo, hacía tiempo que no echaba un vistazo a la evolución de este lenguaje y me encuentro con lo siguiente:

Breaking News! (20th November 2007)

Ruby.NET version 0.9 has just been released

Casi no me lo puedo creer. ¿Seguro que Ruby.NET significa Ruby sobre .NET?

Miro mejor en el sitio del proyecto (http://rubydotnet.googlegroups.com/web/Home.htm), y efectivamente es un bombazo, ya que según afirman...

1. Ruby se ejecuta de forma nativa sobre .NET.
2. Se pueden hacer desarrollo conjuntos con otros lenguajes .NET.
3. Puede utilizar toda la funcionalidad ofrecida por la plataforma .NET (incluidas las herramientas de depuración, framework, librerías de clases, etc. etc).

En los próximos días haremos unas pruebas a ver que tal va la cosa.

Saludos.

8 lenguajes de programación que deberías aprender

Que conste que el título no es mío.

Es un artículo que se encuentra en http://www.tufuncion.com/diferentes-lenguajes-programacion



En el gráfico que muestran llama la atención el bajón que según parece sufre Java y lo que no es tan sorprendente la recuperación de .NET. Digo que no es sorprendente porque digamos que la plataforma de Microsoft llegó tarde y comenzó bajo la sobra del primero.

En cuanto a la parte baja ruby pasa a python por primera vez, aunque no nos engañemos, probablemente se deba al uso en su lugar de nacimiento, esto es Japón.

Saludos.

La venganza de los nerds.

En el año 2002, Paul Graham presentó una ponencia en el foro de investigación ICAD (http://dev.icad.org/).

El término NERD hace referencia a un tipo de persona experto en un tema pero con dificultades en sus relaciones sociales. En la wikipedia tenemos una definición más exacta: http://es.wikipedia.org/wiki/Nerds

La versión traducida al castellano se encuentra en http://kapcoweb.com/p/static/docs/la-venganza-de-los-nerds/la-venganza-de-los-nerds.html
y tiene interés en general para todos a los que nos gusta observar las diferencias entre lenguajes de programación.

Entre otras cosas hace una crítica feroz al "jefe de cabello picudo" que según nos dice "combina milagrosamente dos cualidades que son comunes por sí solas, pero rara vez son vistas juntas: (a) él no sabe nada en absoluto sobre tecnología, y (b) él siempre tiene opiniones imponentes al respecto.

Saludos.