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