%!
%% 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