You enter a laboratory and see 5 insects arranged from left to right in alphabetical order, according to name:

Ant, Bee, Cricket, Dragonfly, Earwig.

By moving two adjacent insects at a time and inserting them elsewhere in the set (still adjacent, no rotations), can you find the fewest number of steps needed to place the insects in reverse alphabetical order? Each time you move an insect, the gap it leaves behind will be closed up.

Examples of legal and illegal moves:

Legal:
ABCDE -> CDABE
ABCDE -> ACDBE

Illegal:
ABCDE -> CBADE (as though the bugs got rotated, which is not allowed)
ABCDE -> CADBE (the bugs you are moving must stay adjacent)
ABCDE -> BDACE (the bugs you are moving must start adjacent)
ABCDE -> BADEC (you get the idea)

Credit for this problem goes to Cliff Pickover

ABCDE
ADEBC
EBADC
EDCBA

Posted by eric on 2005-05-06 16:29:24