Fun with Clojure: Turning Cats into Dogs in Hanoi

This can be cast as a shortest path problem. Implementations on huge graphs (several million nodes), i.e. larger than the one defined by a dictionary, are very efficient and usually take advantage of both the source and destination rather than just performing breadth first search from the source. I can think of Andrew Goldberg's work, see e.g.

http://research.microsoft.com/en-us/people/goldberg/

In the fall of 1980 I taught my first class (AI) as a professor. The TA, Jeff Shrager, suggested this word problem, which he called dog-cat, as a good homework exercise for implementing the A* search algorithm. The students had to do it for three letter words in Lisp and on a Univac computer that the University of Pennsylvania’s Moore School had at the time. I’ve been using the problem on and off for 30 years now in homework assignments.

Never noticed before that Hanoi states are homomorphic to Sierpinski triangles. That's gorgeous. :-)