NAME ^

examples/pir/hanoi.pir - Towers of hanoi

SYNOPSIS ^

You may pass in the height of the tower:

    % ./parrot examples/pir/hanoi.pir 5

The default is 3.

DESCRIPTION ^

Towers of Hanoi (http://www.cut-the-knot.org/recurrence/hanoi.shtml) is a combinatorial puzzle. The PIR shows manipulation of arrays of integers.

Data Structure ^

towers is a FixedPMCArray PMC with three elements. Each element is a ResizableIntegerArray PMC which represents a tower (column) of Hanoi. Each integer element of the array represents a single disk, where the integer value is the size of the disk. The top of the tower is at the highest index; since a larger disk cannot be placed on top of a smaller one, it follows that the tower array must always be sorted in descending order. This lends itself naturally to use of the push and pop operations for moving disks.

So this situation (after the first move)

           |        |
     ====  |        |
    ====== |        |   ==

is represented as

    [[3, 2], [], [1]]

In pseudocode:

    sub main() {
        size = argv[0] || 3
        int towers[] = [[size..1], [], []]
        move_stack(size, 0, 2, 1)

        sub move_stack(n_to_move, start, target, storage) {
            if (n_to_move == 1) {
                move_one(start, target)
            }
            else {
                # Move all but the largest disk to storage.
                move_stack(n_to_move-1, start, storage, target)
                # Move the largest disk to the target.
                move_one(start, target)
                # Move all but the largest disk from storage to target.
                move_stack(n_to_move-1, storage, target, start)
            }
        }

        sub move_one(start_col, dest_col) {
            # Do the move
            push(towers[dest_col], pop(towers[start_col]));

            # Print the results
            print(towers);
        }
    }

TODO ^

Replace I6 etc. with mnemonic register names.

HISTORY ^

 First version               Tony Payne            2002-15-05
 Converted to PIR            Bernhard Schmalhofer  2005-10-20
 Use PCC instead of bsr/ret  Bob Rogers            2008-04-06


 parrot