lambdaway :: hanoi

5 | list | login |load

| |

_img https://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/AnimeHanoiNB.gif/440px-AnimeHanoiNB.gif

_h1 hanoi | [[hanoi2]] | [[hanoi3]]

_h2 1) algorithm

_p The goal is to move n disks from A to B, one at a time and never a bigger disk upon a smaller one. The key idea is to suppose that the problem is solved for n-1 disks. So:

{pre
.    A            B            C

=|=           |            |     1) move the n-1 upper disks ...
   ==|==          |            |     ... from A to C
  ===|===         |            |
 ====|====        |            |
=====|=====       |            |
_____|____________|____________|_____

|            |           =|=     2) move the lower disk ...
     |            |          ==|==    ... from A to B
     |            |         ===|===
     |            |        ====|====
=====|=====       |            |
_____|____________|____________|_____

|            |           =|=     3) move the n-1 upper disks ...
     |            |          ==|==    ... from C to B
     |            |         ===|===
     |            |        ====|====
     |       =====|=====       |
_____|____________|____________|_____

|           =|=           |
     |          ==|==          |
     |         ===|===         |
     |        ====|====        |
     |       =====|=====       |
_____|____________|____________|_____
}

_p Now we can apply {b recursively} this process to the (n-2) upper disks and just stop when n = 0.

_h2 2) pseudo code

{pre
move hanoi(n) from A to B via C
  if n = 0
  then stop
  else move hanoi(n-1) from A to C
       move disk n     from A to B
       move hanoi(n-1) from C to B
}

_h2 3) lambdatalk code

{pre
'{def hanoi
 {lambda {:n :a :b :c}
  {if {= :n 0}
   then 
   else {hanoi {- :n 1} :a :c :b}
         {div}move :n from :a to :b
        {hanoi {- :n 1} :a :c :b}}}} 
-> {def hanoi
 {lambda {:n :a :b :c}
  {if {= :n 0}
   then 
   else 
    {hanoi {- :n 1} :a :c :b}
           {div}move :n from :a to :b
    {hanoi {- :n 1} :a :c :b}}}}

'{hanoi 5 A B C}
->
{hanoi 5 A B C}
}
_p 2{sup 5}-1 = {- {pow 2 5} 1} moves