On: Puzzle: Sort Vector

[endtime]

Why would you use a blind search rather than A*? It's not hard (edit: actually, maybe it is) to come up with a heuristic for this problem.

Also, your memo table wouldn't work for large vectors...

Edit 2: Even worse, the branching factor of that search tree would be O(n!).

[spaghetti → endtime]

Right about the larger vectors. I don't know A*. What's an example heuristic for this puzzle?

[endtime → spaghetti]

It's actually not easy to come up with an admissible heuristic for this, because of the reversal operator. I'm about to be late for dinner at a friend's so I don't have time to come up with something now, but if no one has by the time I'm back I'll think about it.

Edit: How about the sum of the differences of adjacent elements - n - 2? This seems to capture the notion that something reversed but in order is okay. I still don't think this is admissible though.

Well, here's an admissible one. Count how many adjacent elements are not the element to the left + 1, and divide that sum by 2. Pretty sure that'd work.