parrotcode: Towers of hanoi Contents | IMCC

# 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```