News for hackers. Stuff that matters.
Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by merraksh on Sunday October 03, 2010 @04:15PM (#1753497)
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/

Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by jkkramer on Sunday October 03, 2010 @04:39PM (#1753550)
Thanks for the Goldberg pointer. I have a rudimentary bidirectional, parallel BFS working which I'll be blogging about once it's ready. It runs very fast even on huge graphs.
Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by finin on Sunday October 03, 2010 @09:20PM (#1754194)
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.
Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by leif on Sunday October 03, 2010 @02:58PM (#1753332)
Never noticed before that Hanoi states are homomorphic to Sierpinski triangles. That's gorgeous. :-)
Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by phob on Sunday October 03, 2010 @05:50PM (#1753716)
isomorphic?
Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by leif on Sunday October 03, 2010 @07:31PM (#1753983)
An isomorphism requires a metric, which metric do you mean?

I'm talking group homomorphic, though they're also topologically isomorphic, a.k.a. homeomorphic.

Re:Fun with Clojure: Turning Cats into Dogs in Hanoi by phob on Monday November 08, 2010 @05:08AM (#1881982)
Saying that two groups are homomorphic doesn't tell me much more than there exists a group homomorphism... As far as I know, isomorphism implies one can be transformed into the other through renaming.

I don't know anything about topology, so I'll take your word for it.