recursiontowers-of-hanoiapldyalog

Dyalog APL - Towers of Hanoi - does not loop properly

I cannot make it work in Dyalog APL

 solve←{
     n a c b←⍵
     n≤0:⍬
     solve(n-1)a b c
     ⎕←'Move disk from' a 'to' c
     solve(n-1)b c a
 }

 solve 4 'A' 'C' 'B'

It loops from the first solve (n-1) a b c but never goes to line 4.

The same code works in JavaSCript:

solve = (n, a, c, b) => {
    if (n <= 0) return
    solve(n-1, a, b, c)
    console.log(`Move disk from ${a} to ${c}`)
    solve(n-1, b, c, a)
}

solve(4, 'A', 'C', 'B')

When I print the input params it shows:

 solve←{
     n a c b←⍵
     ⎕←n a c b
     n≤0:⍬
     solve(n-1)a b c
     ⎕←'Move disk from' a 'to' c
     solve(n-1)b c a
 }

4 ACB
3 ABC
2 ACB
1 ABC
0 ACB

Any ideas?

Solution

  • A dfn will return on the first non-assignment. Both your recursive calls are non-assignments, so the function doesn't return where you think it does. You can tweak it slightly like so:

    solve←{
    (n a c b)←⍵
    n≤0:⍬
    _←∇(n-1)a b c                 ⍝ Capture and ignore result
    ⎕←'Move disk from' a 'to' c
    _←∇(n-1)b c a                 ⍝ Capture and ignore result
    ⍬                             ⍝ Return empty vector
}

    Note the use of ∇ for recursion -- this is a shorthand for the current dfn. If I run this modified version, I get:

         solve 4 'A' 'C' 'B'
 Move disk from A to B
 Move disk from A to C
 Move disk from B to C
 Move disk from A to B
 Move disk from C to A
 Move disk from C to B
 Move disk from A to B
 Move disk from A to C
 Move disk from B to C
 Move disk from B to A
 Move disk from C to A
 Move disk from B to C
 Move disk from A to B
 Move disk from A to C
 Move disk from B to C

    Roger Hui wrote a paper on this problem that's well worth a read: https://www.jsoftware.com/papers/50/50_38.htm