| blob | e58a967f1a4eb00e9d871b4891d0013d9e06799c |
1 # Towers of Hanoi in sed.
2 #
3 # from: @(#)hanoi.sed 8.1 (Berkeley) 6/6/93
4 # $NetBSD: hanoi.sed,v 1.3 1997/01/09 20:21:35 tls Exp $
5 #
6 #
7 # Ex:
8 # Run "sed -f hanoi.sed", and enter:
9 #
10 # :abcd: : :<CR><CR>
11 #
12 # note -- TWO carriage returns, a peculiarity of sed), 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
45 # cleaning, diagnostics
46 s/ *//g
47 /^$/d
48 /[^a-z:]/{a\
49 Illegal characters: use only a-z and ":". Try again.
50 d
51 }
52 /^:[a-z]*:[a-z]*:[a-z]*:$/!{a\
53 Incorrect format: use\
54 \ : string1 : string2 : string3 :<CR><CR>\
55 Try again.
56 d
57 }
58 /\([a-z]\).*\1/{a\
59 Repeated letters not allowed. Try again.
60 d
61 }
62 # initial formatting
63 h
64 s/[a-z]/ /g
65 G
66 s/^:\( *\):\( *\):\( *\):\n:\([a-z]*\):\([a-z]*\):\([a-z]*\):$/:1\4\2\3:2\5\1\3:3\6\1\2:0/
67 s/[a-z]/&2/g
68 s/^/abcdefghijklmnopqrstuvwxyz/
69 :a
70 s/^\(.\).*\1.*/&\1/
71 s/.//
72 /^[^:]/ba
73 s/\([^0]*\)\(:0.*\)/\2\1:/
74 s/^[^0]*0\(.\)/\1&/
75 :b
76 # outputting current state without markers
77 h
78 s/.*:1/:/
79 s/[123]//gp
80 g
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/
93 bc
94 # iterate back to find smallest out-of-place ring
95 :d
96 s/^\(.\)\(:0[^:]*\([^:]\)\1.*:\([123]\)[^:]*\1\)\4/\3\2\4/
97 td
98 # move said ring (right, resp. left)
99 s/^\(.\)\(.*\)\1\([23]\)\(.*:\3[^ ]*\) /\1\2 \4\1\3/
100 s/^\(.\)\(.*:\([12]\)[^ ]*\) \(.*\)\1\3/\1\2\1\3\4 /
101 tb
102 s/.*/Done! Try another, or end with ^D./p
103 d