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