Planet Packing

What’s the shortest string of letters that contains the words ONE, TWO, and THREE, each spelled out in order but not necessarily using adjacent letters? It can be done in eight letters — THRWONEE is one example — and it turns out that no shorter solution is possible.

In 2001, A. Ross Eckler set out to do the same thing with the names of the planets, from MERCURY through PLUTO. He got down as far as 26 letters, MNVESARCPJLUPITHOURYANUSER, and to my knowledge no one has found a shorter solution.

Dana Richards offered a discussion of the problem from a computing perspective later that year. He found that Eckler’s task is related to a problem in Garey and Johnson’s 1979 Computers and Intractability.

“Why would planet packing be found in a serious computer science book?” he writes. “It turns out to be an important problem with applications to data compression, DNA sequencing, and job scheduling. … The first practical thing is to abandon all hope of solving the problem with a fast algorithm that always gets the optimal answer.”

(A. Ross Eckler, “Planet Packing,” Word Ways 34:2 [May 2001], 157.)