# Copyright (C) 2001-2008, Parrot Foundation. =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: