11590Srgrimes# Towers of Hanoi in sed. 21590Srgrimes# 31590Srgrimes# @(#)hanoi.sed 8.1 (Berkeley) 6/6/93 499355Stjr# $FreeBSD: releng/11.0/usr.bin/sed/tests/hanoi.sed 99400 2002-07-04 05:16:19Z tjr $ 51590Srgrimes# 61590Srgrimes# 71590Srgrimes# Ex: 81590Srgrimes# Run "sed -f hanoi.sed", and enter: 91590Srgrimes# 1099355Stjr# :abcd: : :<CR> 111590Srgrimes# 1299355Stjr# note -- TWO carriage returns were once required, this will output the 131590Srgrimes# sequence of states involved in moving 4 rings, the largest called "a" and 141590Srgrimes# the smallest called "d", from the first to the second of three towers, so 151590Srgrimes# that the rings on any tower at any time are in descending order of size. 161590Srgrimes# You can start with a different arrangement and a different number of rings, 171590Srgrimes# say :ce:b:ax: and it will give the shortest procedure for moving them all 181590Srgrimes# to the middle tower. The rules are: the names of the rings must all be 191590Srgrimes# lower-case letters, they must be input within 3 fields (representing the 201590Srgrimes# towers) and delimited by 4 colons, such that the letters within each field 211590Srgrimes# are in alphabetical order (i.e. rings are in descending order of size). 221590Srgrimes# 231590Srgrimes# For the benefit of anyone who wants to figure out the script, an "internal" 241590Srgrimes# line of the form 251590Srgrimes# b:0abx:1a2b3 :2 :3x2 261590Srgrimes# has the following meaning: the material after the three markers :1, :2, 271590Srgrimes# and :3 represents the three towers; in this case the current set-up is 281590Srgrimes# ":ab : :x :". The numbers after a, b and x in these fields indicate 291590Srgrimes# that the next time it gets a chance, it will move a to tower 2, move b 301590Srgrimes# to tower 3, and move x to tower 2. The string after :0 just keeps track 311590Srgrimes# of the alphabetical order of the names of the rings. The b at the 321590Srgrimes# beginning means that it is now dealing with ring b (either about to move 331590Srgrimes# it, or re-evaluating where it should next be moved to). 341590Srgrimes# 351590Srgrimes# Although this version is "limited" to 26 rings because of the size of the 361590Srgrimes# alphabet, one could write a script using the same idea in which the rings 371590Srgrimes# were represented by arbitrary [strings][within][brackets], and in place of 381590Srgrimes# the built-in line of the script giving the order of the letters of the 391590Srgrimes# alphabet, it would accept from the user a line giving the ordering to be 401590Srgrimes# assumed, e.g. [ucbvax][decvax][hplabs][foo][bar]. 411590Srgrimes# 421590Srgrimes# George Bergman 431590Srgrimes# Math, UC Berkeley 94720 USA 441590Srgrimes 451590Srgrimes# cleaning, diagnostics 461590Srgrimess/ *//g 471590Srgrimes/^$/d 481590Srgrimes/[^a-z:]/{a\ 491590SrgrimesIllegal characters: use only a-z and ":". Try again. 501590Srgrimesd 511590Srgrimes} 521590Srgrimes/^:[a-z]*:[a-z]*:[a-z]*:$/!{a\ 531590SrgrimesIncorrect format: use\ 5499400Stjr\ : string1 : string2 : string3 :<CR>\ 551590SrgrimesTry again. 561590Srgrimesd 571590Srgrimes} 581590Srgrimes/\([a-z]\).*\1/{a\ 591590SrgrimesRepeated letters not allowed. Try again. 601590Srgrimesd 611590Srgrimes} 621590Srgrimes# initial formatting 631590Srgrimesh 641590Srgrimess/[a-z]/ /g 651590SrgrimesG 661590Srgrimess/^:\( *\):\( *\):\( *\):\n:\([a-z]*\):\([a-z]*\):\([a-z]*\):$/:1\4\2\3:2\5\1\3:3\6\1\2:0/ 671590Srgrimess/[a-z]/&2/g 681590Srgrimess/^/abcdefghijklmnopqrstuvwxyz/ 691590Srgrimes:a 701590Srgrimess/^\(.\).*\1.*/&\1/ 711590Srgrimess/.// 721590Srgrimes/^[^:]/ba 731590Srgrimess/\([^0]*\)\(:0.*\)/\2\1:/ 741590Srgrimess/^[^0]*0\(.\)/\1&/ 751590Srgrimes:b 761590Srgrimes# outputting current state without markers 771590Srgrimesh 781590Srgrimess/.*:1/:/ 791590Srgrimess/[123]//gp 801590Srgrimesg 811590Srgrimes:c 821590Srgrimes# establishing destinations 831590Srgrimes/^\(.\).*\1:1/td 841590Srgrimes/^\(.\).*:1[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ 851590Srgrimes/^\(.\).*:1[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ 861590Srgrimes/^\(.\).*:1[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ 871590Srgrimes/^\(.\).*:2[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ 881590Srgrimes/^\(.\).*:2[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ 891590Srgrimes/^\(.\).*:2[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ 901590Srgrimes/^\(.\).*:3[^:]*\11/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\32/ 911590Srgrimes/^\(.\).*:3[^:]*\12/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\31/ 921590Srgrimes/^\(.\).*:3[^:]*\13/s/^\(.\)\(.*\1\([a-z]\).*\)\3./\3\2\33/ 931590Srgrimesbc 941590Srgrimes# iterate back to find smallest out-of-place ring 951590Srgrimes:d 961590Srgrimess/^\(.\)\(:0[^:]*\([^:]\)\1.*:\([123]\)[^:]*\1\)\4/\3\2\4/ 971590Srgrimestd 981590Srgrimes# move said ring (right, resp. left) 991590Srgrimess/^\(.\)\(.*\)\1\([23]\)\(.*:\3[^ ]*\) /\1\2 \4\1\3/ 1001590Srgrimess/^\(.\)\(.*:\([12]\)[^ ]*\) \(.*\)\1\3/\1\2\1\3\4 / 1011590Srgrimestb 1021590Srgrimess/.*/Done! Try another, or end with ^D./p 1031590Srgrimesd 104