hanoi.pir

# Copyright (C) 2001-2008, Parrot Foundation.
# $Id$

=head1 NAME

examples/pir/hanoi.pir - Towers of hanoi

=head1 SYNOPSIS

You may pass in the height of the tower:

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

The default is 3.

=head1 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.

=head1 Data Structure

C<towers> is a C<FixedPMCArray> PMC with three elements.  Each element is a
C<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 C<push> and C<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);
        }
    }

=head1 TODO

Replace $I6 etc. with mnemonic register names.

=head1 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

=cut

# Towers of hanoi in Parrot Intermediate Representation
.sub "hanoi" :main
        .param pmc argv
        .local int size

        ## Create some lexical bindings.
        .local pmc size_pmc, print_towers
        .lex "size", size_pmc
        ## Note that we don't need to do find_lex on the closures; functions are
        ## sought using find_name, which looks at outer lexical scopes.
        .lex "print_towers", print_towers
        print_towers = get_hll_global 'print_towers'
        print_towers = newclosure print_towers
        .local pmc move_one, move_stack
        .lex "move_one", move_one
        move_one = get_hll_global 'MOVE'
        move_one = newclosure move_one
        .lex "move_stack", move_stack
        move_stack = get_hll_global 'MOVE_STACK'
        move_stack = newclosure move_stack

        # Check number of command line arguments
        $I0 = argv
        if $I0 < 2 goto USE_DEFAULT_SIZE
        $S5 = argv[1]
        size = $S5
        if size < 1 goto INVALID_SIZE
        print "Building a tower of size "
        print size
        print ".\n"
        goto SIZE_IS_NOW_KNOWN
INVALID_SIZE:
        print "Given tower size is invalid.\n"
        goto USE_DEFAULT_SIZE
USE_DEFAULT_SIZE:
        print "Using default size 3 for tower.\n"
        size = 3
SIZE_IS_NOW_KNOWN:
        size_pmc = new 'Integer'
        size_pmc = size
        print "\n"

        .local pmc towers
        .lex "towers", towers
        new towers, 'FixedPMCArray'
        set towers, 3
        new $P1, 'ResizableIntegerArray'
        new $P2, 'ResizableIntegerArray'
        new $P3, 'ResizableIntegerArray'
        set towers[0], $P1
        set towers[1], $P2
        set towers[2], $P3
        ## towers = [[],[],[]]

        .local int i
        i = size
loop_populate:
        push $P1, i
        dec i
        if i > 0 goto loop_populate
        ## towers = [[...,3,2,1],[],[]]

        # uncomment to print initial layout
        # print_towers(towers)

        ## Now solve it.
        move_stack(size, 0, 2, 1)
        .return ()
.end

## Print the current state of the towers array.
.sub print_towers :outer(hanoi)
        .param pmc towers       # an array

        ## Only PMCs can be stored as lexical variables, but we need an int.
        .local pmc tower_size_pmc
        tower_size_pmc = find_lex "size"
        .local int tower_size
        tower_size = tower_size_pmc

        .local pmc stack
        .local int i, j, stack_size, tos
        i = tower_size
        dec i
loop_rows:
        j = 0
loop_cols:
        .local int disk_size, n_spaces
        stack = towers[j]
        stack_size = stack
        disk_size = 0
        if stack_size <= i goto print_it
        disk_size = stack[i]                 # disk_size = towers[j][i]
print_it:
        n_spaces = tower_size - disk_size
        repeat $S0, " ", n_spaces
        print $S0
        $I6 = mul disk_size, 2                # $I6 = disk_size * 2
        repeat $S1, "=", $I6
        print $S1
        print $S0

        inc j
        if j == 3 goto done_loop
        print " | "
        goto loop_cols
done_loop:
        print "\n"
        dec i
        if i >= 0 goto loop_rows
        print "\n"
.end

## Take the topmost disk off the start_col stack, and put it on the dest_col
## stack.  The way we've defined the data structures makes this trivial.
.sub MOVE :outer(hanoi)
        .param int start_col
        .param int dest_col

        .local pmc towers
        towers = find_lex "towers"

        .local pmc start_stack, dest_stack
        .local int disk
        start_stack = towers[start_col]
        disk = pop start_stack
        dest_stack = towers[dest_col]
        push dest_stack, disk
        print_towers(towers)
.end

## Move n_to_move disks from start_col to target_col, using storage_col
## for temporary storage if needed.
.sub MOVE_STACK :outer(hanoi)
        .param int n_to_move
        .param int start_col
        .param int target_col
        .param int storage_col

        if n_to_move > 1 goto move_multiple
        move_one(start_col, target_col)
        .return ()
move_multiple:
        dec n_to_move
        ## Move all but the largest disk to storage.
        move_stack(n_to_move, start_col, storage_col, target_col)
        ## Move the largest disk to the target.
        move_one(start_col, target_col)
        ## Move all but the largest disk from storage to target.
        move_stack(n_to_move, storage_col, target_col, start_col)
.end

# Local Variables:
#   mode: pir
#   fill-column: 100
# End:
# vim: expandtab shiftwidth=4 ft=pir: