-
Notifications
You must be signed in to change notification settings - Fork 138
/
hanoi.pir
240 lines (199 loc) · 6.68 KB
/
hanoi.pir
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
# 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: