sed can do Towers of Hanoi

Article 3064 of net.unix: 
ion: version B 2.10.2 9/18/84; site masscomp.UUCP
From: gbergman@ucbtopaz.CC.Berkeley.ARPA
Newsgroups: net.unix
Subject: sed can do Towers of Hanoi
Date: 21 Nov 84 04:20:04 GMT
Organization: Univ. of Calif., Berkeley CA USA

If you put the 60-line sed script near the end of this message in a file, e.g. sed.hanoi, and then do
sed -f sed.hanoi
and type in, say
:abcd: : :<CR><CR>
(notice-- TWO carriage returns-- a peculiarity of sed), then it will output the sequence of states involved in moving 4 rings, the largest called "a" and the smallest called "d", from the first to the second of three towers, so that the rings on any tower at any time are in descending order of size. You can start with a different arrangement and a different number of rings, say :ce:b:ax: and it will still give the shortest procedure for moving them all to the middle tower. The rules are: the names of the rings must all be lower-case letters, they must be input within 3 fields (representing the towers) delimited by 4 colons, such that the letters within each field are in alphabetical order (= rings in descending order of size).
For the benefit of anyone who wants to figure out the script, I will explain that an "internal" line of the form
b:0abx:1a2b3 :2 :3x2
has the following meaning: the material after the three markers :1 :2 :3 represents the three towers; in this case the current set-up is :ab : :x :. The numbers after a, b and x in these fields indicate that the next time it gets a chance, it will move a to tower 2, move b to tower 3, and move x to tower 2. The string after :0 just keeps track of the alphabetical order of the names of the rings. The b at the beginning means that it is now dealing with ring b (either about to move it, or re-evaluating where it should next be moved to).
Although this version is "limited" to 26 rings because of the size of the alphabet, one could write a script using the same idea in which the rings were represented by arbitrary [strings][within][brackets], and in place of the built-in line of the script giving the order of the letters of the alphabet, it would accept from the user a line giving the ordering to be assumed, e.g. [ucbvax][decvax][hplabs][foo][bar].
While on the subject, I will repeat at the very end of this note a much shorter file to do Towers of Hanoi using troff that a friend posted for me a year or so ago, before I was on a machine that subscribed to the net. If you put it in a file "troff.hanoi", and do nroff -rr5 troff.hanoi, it will output instructions for moving 5 rings from tower 1 to tower 2; generally, just put the desired number of rings after the -rr on the command line. In this case, you don't have a choice of initial state, aside from choosing the number of rings.
Have fun!

George Bergman

Math, UC Berkeley 94720 USA

ucbvax!ucbcartan!gbergman (if your mailer can

digest a 9-letter name; if not maybe:)

ucbvax!cartan:gbergman or


#----------------------sed.hanoi------------------------------ # cleaning, diagnostics s/ *//g /^$/d /[^a-z:]/{a\ Impermissible characters: use only a-z and ":". Try again. d } /^:[a-z]*:[a-z]*:[a-z]*:$/!{a\ incorrect format: use\ \ : string1 : string2 : string3 :<CR><CR>\ Try again. d } /\([a-z]\).*\1/{a\ Repeated letters not allowed. Try again. d } # initial formatting h s/[a-z]/ /g G s/^:\( *\):\( *\):\( *\):\n:\([a-z]*\):\([a-z]*\):\([a-z]*\):$/:1\4\2\3:2\5\1\3:3\6\1\2:0/ s/[a-z]/&2/g s/^/abcdefghijklmnopqrstuvwxyz/ :a s/^\(.\).*\1.*/&\1/ s/.// /^[^:]/ba s/\([^0]*\)\(:0.*\)/\2\1:/ s/^[^0]*0\(.\)/\1&/ :b # outputting current state without markers h s/.*:1/:/ s/[123]//gp g :c # establishing destinations /^\(.\).*\1:1/td /^\(.\).*:1[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ /^\(.\).*:1[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ /^\(.\).*:1[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ /^\(.\).*:2[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ /^\(.\).*:2[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ /^\(.\).*:2[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ /^\(.\).*:3[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ /^\(.\).*:3[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ /^\(.\).*:3[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ bc # iterate back to find smallest out-of-place ring :d s/^\(.\)\(:0[^:]*\([^:]\)\1.*:\([123]\)[^:]*\1\)\4/\3\2\4/ td # move said ring (right, resp. left) s/^\(.\)\(.*\)\1\([23]\)\(.*:\3[^ ]*\) /\1\2 \4\1\3/ s/^\(.\)\(.*:\([12]\)[^ ]*\) \(.*\)\1\3/\1\2\1\3\4 / tb s/.*/Done! Try another, or end with ^D./p d #------------------end sed.hanoi------------------------------
.\"------------------troff.hanoi---------------------------------- .de H .nr d \\$1-1 .if \\nd .H \\nd \\$2 \\$4 \\$3
Transfer ring \\$1 from tower \\$2 to tower \\$3.
.nr d \\$1-1 .if \\nd .H \\nd \\$4 \\$3 \\$2

Initial state:  \nr rings all on tower A; #1 on top.
.H \nr A B C


Usenet/Mail file converted on Thursday, July 20, 1995
 by by, version 1.2b3

Carl Hommel,