kernelthread.com

sed

The Towers of Hanoi implemented as a sed script.

The pattern space in sed can be used as a stack, the hold space will work as scratch area, and there exists conditional branching. These are enough for implementing Hanoi. Here is how to use it:

echo xxx | hanoi.sed # or echo xxx | sed -f hanoi.sed

Each 'x' represents one additional disk to solve the problem for. Thus, for n disks, you will use 'xxxx...x' (n times). The above example solves the problem for 3 disks. The towers are named '1', '2' and '3', and the disks are to be moved from tower '1' to tower '3' using tower '2' as intermediate.

#! /usr/bin/sed -f # # The Towers Of Hanoi # sed # Copyright (C) 2001 Amit Singh. All Rights Reserved. # http://hanoi.kernelthread.com # # usage: # echo xx* | sed -f hanoi.sed # use N 'x's for N disks, for example: # echo xxx | sed -f hanoi.sed will solve for 3 disks # :M s/^xx*$/:n:3:2:1:&:/g t B a\ usage: echo xx* | sed -f hanoi.sed. For example, xxx represents 3 disks. d :B /^:$/ { d;q; } h;s/^:[yn]:\([123]\):[123]:\([123]\):x*:.*/\2 --> \1/g;x /^:y:[123]:[123]:[123]:x*:.*$/b ~0 /^:n:[123]:[123]:[123]:x:.*/b 1 s/:n:\([123]\):\([123]\):\([123]\):x\(x*\):\(.*\)/:n:\2:\1:\3:\4:y:\1:\2:\3:x\4:\5/g b B :1 x;p;x s/^:n:[123]:[123]:[123]:x:\(.*\)/:\1/g b B :~0 x;p;x s/^:y:\([123]\):\([123]\):\([123]\):x\(x*\):\(.*\)$/:n:\1:\3:\2:\4:\5/g b B :E

Finally, consider the "beautified" version below:

s~^xx*$~:n:3:2:1:&:~;tB;d;:B;/^:$/d;h s~^:.:\(.\):.:\(.\):*:.*~\2 --> \1~;x /^:y:.:.:.:*:.*/b0;/^:n:.:.:.:x:.*/b1 s~:n:\(.\):\(.\):\(.:x*\)x:\(.*\)~:n:\2:\1:\3:y:\1:\2:\3x:\4~ bB;:1;x;p;x;s~^:n:.:.:.:x:\(.*\)~:\1~;bB;:0;x;p;x s~^:y:\(.\):\(.\):\(.\):x\(x*:*\)~:n:\1:\3:\2:\4~ bB

Download

hanoi.sed