%!
%% towers of hanoi in PostScript
%% copyright 2001, by Dylan James McNamee
%% Creative Commons license, attribution please
%% solve_hanoi takes, on the stack
%% number of discs, start-post, end-post, middle-post
%% leaves nothing on the stack
/solve_hanoi {
4 dict begin
/middlepost exch def
/endpost exch def
/startpost exch def
/count exch def
count 1 eq
{ startpost endpost move_disc }
{ count 1 sub startpost middlepost endpost solve_hanoi %% solve n-1
draw_towers
startpost endpost move_disc %% move the bottom disc
draw_towers
count 1 sub middlepost endpost startpost solve_hanoi %% solve n-1 again
}
ifelse
end
} def
%% init_hanoi takes
%% number_of_discs
%% fills the globals "posts" and "stacks" with the data structures needed by
%% solve_hanoi
/init_hanoi {
/numdiscs exch def
/halfdiscs numdiscs 2 div def
/drawiter 0 def
posts 0 [ numdiscs -1 1 { } for ] put
posts 1 [ 1 1 numdiscs { pop 0 } for ] put
posts 2 [ 1 1 numdiscs { pop 0 } for ] put
stacks 0 numdiscs put
} def
%% move_disc takes on the stack
%% start-post, end-post
%% leaves nothing
/move_disc {
exch
pop_disc
push_disc
% posts (<move) == pstack (move>) == pop
} def
/posts [ [] [] [] ] def
/stacks [ 0 0 0 ] def
%% push takes
%% post-number, value
%% leaves nothing
/push_disc {
%% c code equivalent of this routine:
%% posts[stacks[post]] = value
%% stacks[post]++;
%% (in push) == pstack (in push) ==
/value exch def
/post exch def
%% first push the disc onto the correct post
%% put:
posts %% this posts array
post get
stacks post get %% index into this post
value %% the value
put
%% now increment that post's stack-top
%% put:
stacks %% stacks array
post %% index into stacks
stacks post get 1 add
put
} def
%% pop_disc takes
%% post-number
%% leaves the value, popped from that stack
/pop_disc {
/post exch def
% put: (decrement stack pointer)
stacks
post
% get:
stacks
post
get 1 sub
put
%% place top disc of this post on stack
% get: - get the top disc
% get: - get this post's discs
posts
post
get
% get: - get this stack's index
stacks
post
get
get
% put: - clear the vacated spot
posts
post
get
stacks
post
get
0
put
} def
/draw_towers {
draw_towers_horiz
} def
/draw_towers_vert {
gsave
[ 0 1 2 ] { draw_tower } forall
% space out sets of towers:
grestore
%% vertically, with wrap
currentpoint
exch pop 100 gt {
0 numdiscs 2 add scale mul -1 mul rmoveto
} {
userdict begin %% eek -- we're modifying a global within a recursive namespace
/cur-x numdiscs scale mul 4 mul cur-x add def
cur-x cur-y
%% (<wrapping) == pstack (wrapping>) ==
moveto
end
} ifelse
} def
/draw_towers_horiz {
[ 0 1 2 ] { draw_tower } forall
userdict begin /drawiter drawiter 1 add def
drawiter 16 lt {
numdiscs scale mul 0 rmoveto
} {
/cur-y cur-y numdiscs scale mul 4 mul sub def
cur-x cur-y moveto
/drawiter 0 def
} ifelse
end
} def
%% draw_tower draws a post (passed on the stack)
/draw_tower {
draw_post
posts exch get { draw_disc } forall
% space the towers out
numdiscs scale mul scale add numdiscs scale mul -1 mul rmoveto
} def
/draw_post {
gsave 0.6 setgray 0 numdiscs scale mul rlineto stroke grestore
% halfdiscs scale mul 0 moveto
} def
/draw_disc {
% (draw_disc) == pstack (draw_disc) ==
/discsize exch scale mul def
/halfsize discsize 2 div def
halfsize -1 mul 0 rmoveto discsize 0 rlineto gsave stroke grestore
halfsize -1 mul scale rmoveto
} def
6 init_hanoi
/scale 1 def
scale 2 div setlinewidth
/cur-y 700 def
/cur-x 100 def
cur-x cur-y moveto
draw_towers
% [3 2 1] { draw_disc } forall
%% stacks posts numdiscs
%% (before) == pstack (before) ==
%% pop pop pop
%% number of discs, start-post, end-post, middle-post
numdiscs 0 2 1 solve_hanoi
draw_towers
%% stacks posts
%% (after) == pstack (after) ==
%% pop pop
showpage