home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / sed / hanoi.sed < prev    next >
Encoding:
Text File  |  1992-12-02  |  3.5 KB  |  103 lines
  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
  103.