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



    gbergman%cartan@berkeley



#----------------------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


Done!

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