usr.bin/sed/TEST/hanoi.sed

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