Web Tutorial: The Tower of Hanoi (Part 2/3)

Hello, and welcome back. This part will be a little bit technical, but duh, it's a programming tutorial.

Let's declare another array, stack. This will be a two-dimensional array. It represents your Tower of Hanoi setup - there are three bases and rods, and each one has four slots. Four slots because we have four disks, right? Then create another array, top. Each element represents the current height of the stacked disks on each rod.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER 
DIM SHARED piece(4) AS STRING

Now, let's initialize the stack array. Use a nested For loop to ensure that every slot in each base and rod, is set to 0. And make sure that all elements of the top array are set to 0.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER
DIM SHARED piece(4) AS STRING

piece(1) = " 1 "
piece(2) = "  2  "
piece(3) = "   3   "
piece(4) = "    4    "

FOR i = 1 TO 3
    FOR j = 1 TO 4
        stack(i, j) = 0
    NEXT j

    top(i) = 0
NEXT i

drawstack

SUB drawpiece (pieceno)
COLOR 0, 0
FOR i = 1 TO (5 - pieceno)
    PRINT " ";
NEXT i

Up to now, we've been using the word "stack" to mean "base and rod", but today we'll go a bit further and implement a data structure stack. For that to happen, we must have a pop() function and a push() subroutine. First, let's create with the push() subroutine. It will accept two parameters - stackno, and value.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER
DIM SHARED piece(4) AS STRING

piece(1) = " 1 "
piece(2) = "  2  "
piece(3) = "   3   "
piece(4) = "    4    "

FOR i = 1 TO 3
    FOR j = 1 TO 4
        stack(i, j) = 0
    NEXT j

    top(i) = 0
NEXT i

drawstack

SUB push (stackno, value)

END SUB

SUB drawpiece (pieceno)
COLOR 0, 0
FOR i = 1 TO (5 - pieceno)
    PRINT " ";
NEXT i

stackno is the base and rod you are currently referencing. value is the number of the disk you are "pushing". Remember that in a stack, it's Last In First Out. When you "push", you are stacking a disk onto a rod, on top of any other disks that may be already there. When you "pop", you remove the disk at the top, that is, the most recently "pushed" disk.

So first, increment the element of the top array referenced by stackno.

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
END SUB

Then set the element of stack, referenced by stackno and the current value of the element of top you just incremented, to value. In layman's terms, that means you set the current topmost slot of the base and rod of stackno, to the disk you are "pushing".

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
END SUB

Now, in your drawstack() subroutine, alter this line to draw the pieces in that stack instead of just the rod.

SUB drawstack ()
FOR i = 1 TO 6
    LOCATE i + 1, 2

    FOR j = 1 TO 3
        IF i = 1 THEN
            drawpiece 0
        ELSE
            IF i = 6 THEN
                drawbase j
            ELSE
                drawpiece (stack(j, 6 - i))
            END IF
        END IF
    NEXT j
NEXT i
END SUB

Now try this. "Push" Disk 4 onto Stack 1, starting with the largest stack, just before the calling drawstack() subroutine.

push 1, 4

drawstack

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
END SUB

You just put the largest disk onto the first rod!

Now try this...

push 1, 4
push 1, 3

drawstack

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
END SUB

Here, you've stacked the second largest disk onto the first rod, right on top of the largest disk.

push 1, 4
push 1, 3
push 1, 2
push 1, 1

drawstack

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
END SUB

And so on. This, coincidentally, is the starting configuration of the Tower of Hanoi.

Now, let's do the "pop". For that, we'll need to declare another variable, openpiece. It holds the number of the disk that is currently not assigned to any rod. At any time, there can be only one of these.  Set the value to 0.

DIM SHARED stack(3, 4) AS INTEGER
DIM SHARED top(3) AS INTEGER
DIM SHARED piece(4) AS STRING
DIM SHARED openpiece AS INTEGER

piece(1) = " 1 "
piece(2) = "  2  "
piece(3) = "   3   "
piece(4) = "    4    "
openpiece = 0

In the push() subroutine, set openpiece to 0 after pushing. This indicates that no disks are unassigned to rods. It's not important now, but later it will be.

Now, let's create a function, pop(). It will accept a parameter stackno, which is the number of the rod you're trying to remove a disk from.

SUB push (stackno, value)
top(stackno) = top(stackno) + 1
stack(stackno, top(stackno)) = value
openpiece = 0
END SUB

FUNCTION pop (stackno)

END FUNCTION

Hold on... why is push() a subroutine and pop() a function?

Because when you pop a stack, you want to know the number of the disk you removed. Therefore the function will return that number. With push(), you don't need to return anything.

So yeah, first you assign the returned value to the number of the most recently "pushed" disk onto the rod (the stack array) indicated by stackno.

FUNCTION pop (stackno)
pop = stack(stackno, top(stackno))
END FUNCTION

Then you assign that slot in the stack array to 0, since that slot is no longer occupied. And decrement the appropriate element in the top array to say that there is one less disk in that rod now.

FUNCTION pop (stackno)
pop = stack(stackno, top(stackno))
stack(stackno, top(stackno)) = 0
top(stackno) = top(stackno) - 1
END FUNCTION

Let's modify the drawstack() subroutine to display the piece that is currently open. First, reset the color to white on black, and then move the cursor to below the drawn stack. And print the word "Open".

SUB drawstack ()
FOR i = 1 TO 6
    LOCATE i + 1, 2

    FOR j = 1 TO 3
        IF i = 1 THEN
            drawpiece 0
        ELSE
            IF i = 6 THEN
                drawbase j
            ELSE
                drawpiece (stack(j, 6 - i))
            END IF
        END IF
    NEXT j
NEXT i

COLOR 15, 0
LOCATE 9, 2
PRINT "Open ";
END SUB

Now, if the value of openpiece is 0, print something to indicate so. Otherwise, invoke the drawpiece() subroutine, passing in the value of openpiece as an argument.

COLOR 15, 0
LOCATE 9, 2
PRINT "Open ";

IF openpiece = 0 THEN
    PRINT "(none)         ";
ELSE
    drawpiece openpiece
END IF

Now, try this. After pushing all four disks onto the first rod, "pop" the first rod. And then call the drawstack() subroutine.

push 1, 4
push 1, 3
push 1, 2
push 1, 1
openpiece = pop(1)

drawstack

You just removed Disk 1 (the blue and smallest one) from the first rod.

Now try this... it pushes the unassigned disk (Disk 1) to the second rod, then removes the next disk from the first rod.

push 1, 4
push 1, 3
push 1, 2
push 1, 1
openpiece = pop(1)
push 2, openpiece
openpiece = pop(1)

drawstack

You're getting the hang of this...

Next

Game logic will tie everything up nicely, now that you've gotten the drawing subroutines and "pop" and "push" functionality out of the way.