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