xref: /freebsd/usr.bin/sed/tests/hanoi.sed (revision bdd1243df58e60e85101c09001d9812a789b6bc4)
1# Towers of Hanoi in sed.
2#
3#	@(#)hanoi.sed	8.1 (Berkeley) 6/6/93
4# $FreeBSD$
5#
6#
7# Ex:
8# Run "sed -f hanoi.sed", and enter:
9#
10#	:abcd: : :<CR>
11#
12# note -- TWO carriage returns were once required, this will output the
13# sequence of states involved in moving 4 rings, the largest called "a" and
14# the smallest called "d", from the first to the second of three towers, so
15# that the rings on any tower at any time are in descending order of size.
16# You can start with a different arrangement and a different number of rings,
17# say :ce:b:ax: and it will give the shortest procedure for moving them all
18# to the middle tower.  The rules are: the names of the rings must all be
19# lower-case letters, they must be input within 3 fields (representing the
20# towers) and delimited by 4 colons, such that the letters within each field
21# are in alphabetical order (i.e. rings are in descending order of size).
22#
23# For the benefit of anyone who wants to figure out the script, an "internal"
24# line of the form
25#		b:0abx:1a2b3 :2   :3x2
26# has the following meaning: the material after the three markers :1, :2,
27# and :3 represents the three towers; in this case the current set-up is
28# ":ab :   :x  :".  The numbers after a, b and x in these fields indicate
29# that the next time it gets a chance, it will move a to tower 2, move b
30# to tower 3, and move x to tower 2.  The string after :0 just keeps track
31# of the alphabetical order of the names of the rings.  The b at the
32# beginning means that it is now dealing with ring b (either about to move
33# it, or re-evaluating where it should next be moved to).
34#
35# Although this version is "limited" to 26 rings because of the size of the
36# alphabet, one could write a script using the same idea in which the rings
37# were represented by arbitrary [strings][within][brackets], and in place of
38# the built-in line of the script giving the order of the letters of the
39# alphabet, it would accept from the user a line giving the ordering to be
40# assumed, e.g. [ucbvax][decvax][hplabs][foo][bar].
41#
42#			George Bergman
43#			Math, UC Berkeley 94720 USA
44
45# cleaning, diagnostics
46s/  *//g
47/^$/d
48/[^a-z:]/{a\
49Illegal characters: use only a-z and ":".  Try again.
50d
51}
52/^:[a-z]*:[a-z]*:[a-z]*:$/!{a\
53Incorrect format: use\
54\	: string1 : string2 : string3 :<CR>\
55Try again.
56d
57}
58/\([a-z]\).*\1/{a\
59Repeated letters not allowed.  Try again.
60d
61}
62# initial formatting
63h
64s/[a-z]/ /g
65G
66s/^:\( *\):\( *\):\( *\):\n:\([a-z]*\):\([a-z]*\):\([a-z]*\):$/:1\4\2\3:2\5\1\3:3\6\1\2:0/
67s/[a-z]/&2/g
68s/^/abcdefghijklmnopqrstuvwxyz/
69:a
70s/^\(.\).*\1.*/&\1/
71s/.//
72/^[^:]/ba
73s/\([^0]*\)\(:0.*\)/\2\1:/
74s/^[^0]*0\(.\)/\1&/
75:b
76# outputting current state without markers
77h
78s/.*:1/:/
79s/[123]//gp
80g
81:c
82# establishing destinations
83/^\(.\).*\1:1/td
84/^\(.\).*:1[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/
85/^\(.\).*:1[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/
86/^\(.\).*:1[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/
87/^\(.\).*:2[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/
88/^\(.\).*:2[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/
89/^\(.\).*:2[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/
90/^\(.\).*:3[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/
91/^\(.\).*:3[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/
92/^\(.\).*:3[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/
93bc
94# iterate back to find smallest out-of-place ring
95:d
96s/^\(.\)\(:0[^:]*\([^:]\)\1.*:\([123]\)[^:]*\1\)\4/\3\2\4/
97td
98# move said ring (right, resp. left)
99s/^\(.\)\(.*\)\1\([23]\)\(.*:\3[^ ]*\) /\1\2 \4\1\3/
100s/^\(.\)\(.*:\([12]\)[^ ]*\) \(.*\)\1\3/\1\2\1\3\4 /
101tb
102s/.*/Done!  Try another, or end with ^D./p
103d
104