Towers of Hanoi in troff
------------------------


The "Hacker Test" (a "Purity Test for programmers") asks whether one
can solve the Towers of Hanoi problem in various ways.  The final
option: "...using the troff text formatter?"

I was inspired by this challenge while I was interning for the Unix
expert and author Paul Abrahams in 1995.  Paul quickly located (in his
well-stocked Unix library) the extensive discussion of troff in the
BSD operating system documentation, and away I went.

So, I can solve the Towers of Hanoi using the troff text formatter:


.de sl
.ie \\$1-1 \{\
.sl \\$1-1 \\$2 \\$4 \\$3
\\$2 to \\$3,
.sl \\$1-1 \\$4 \\$3 \\$2
.\}
.el \\$2 to \\$3,
..


This defines a macro called "sl" (short for "solve") which prints out
the steps necessary to solve the Towers of Hanoi.  You can invoke this
macro as

.sl n a b c

where n is a positive integer giving the number of discs on the first
peg, and a, b, and c are arbitrary strings which will be used as the
names of the three pegs.  (You can use "a", "b", and "c" if you like.)

So, for instance,

.sl 4 a b c

(i.e. "solve four discs, pegs 'a', 'b', 'c'") will make troff generate
a document containing

a to c, a to b, c to b, a to c, b to a, b to c, a to c, a to b, c
to b, c to a, b to a, c to b, a to c, a to b, c to b,

which is, in fact, the series of steps you'd want to follow to
transfer a stack of four pegs from "a" to "b" within the rules of the
Tower of Hanoi game.

This works under troff on SunOS and GNU groff on any platform.  You
can try it most conveniently with "troff -a" on your favorite Unix
system.

As far as I can remember, I've never actually used troff for any other
purpose.

	-- Seth Schoen