  We present efficient algorithms for constructing a shortest path between two
states in the Tower of Hanoi graph, and for computing the length of the
shortest path. The key element is a finite-state machine which decides, after
examining on the average only 63/38 of the largest discs, whether the largest
disc will be moved once or twice. This solves a problem raised by Andreas Hinz,
and results in a better understanding of how the shortest path is determined.
Our algorithm for computing the length of the shortest path is typically about
twice as fast as the existing algorithm. We also use our results to give a new
derivation of the average distance 466/885 between two random points on the
Sierpinski gasket of unit side.
