Rosetta

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1998). He can be contacted at [email protected].

The woman said, "If our friends in the FBI are telling the truth, this group is sending terrorism instructions over the Web." Our visitor had the inquisitive eyes of a mathematician, mixed with the reticence of a National Security Agency officer. She was also Ecco's longtime friend Karmen Simon. Ecco knew too well that he shouldn't ask questions. Whereas he had had trouble with the NSA in the past (see my book Codes, Puzzles, and Conspiracy) his friendship with Karmen overwhelmed his revulsion for the institution.

"They are not very sophisticated," Simon continued.

"A cursory analysis shows a single substitution code. But the problem is that the message is spread on a bunch of web pages. These have titles coming from dried fruits: raisin, date, fig, prune, apricot, pineapple, grapefruit, currant, and coconut. We believe the recipient is meant to lay out the pages in a specific order. The first question is which order?

"Our FBI friends tell us that this group, calling themselves 'Remember Waco' -- a group of antifederalists -- normally work from a template and we want to exploit that fact."

"What do you mean by a template?" Liane asked.

"Well, we have a kind of hyperrosetta stone," Simon responded.

"We know that the graph has nine pages numbered consecutively: 1 2 3 4 5 6 7 8 9. The message is laid out in numerical order on those nine pages. According to our informants, the hyperlinks are supposed to link the pages as follows:

(2 6

1 5

4 4

2 2

5 7

4 8

8 9

4 7

3 6

8 3

8 4

1 4

9 7

8 9

5 2

6 2

5 7

6 2

8 5

7 6)

"Each row represents a hyperlink.

"So, for example, page 2 has an href to itself and to page 6. At the same time, page 6 has two hyperlinks to page 2 and page 5 has one. That's the classic arrangement.

"The hrefs we actually see, however, come in an entirely different form:

(fig prune

grapefruit grapefruit

apricot currant

pineapple apricot

raisin currant

grapefruit currant

apricot pineapple

pineapple grapefruit

pineapple date

fig prune

pineapple raisin

coconut grapefruit

raisin currant

raisin coconut

prune fig

date fig

raisin prune

grapefruit pineapple

prune prune

currant fig)

"So, the first problem is to determine which dried fruit corresponds to page 1, which to page 2, and so on. All we know for sure is that the edges should correspond at least approximately, so if apricot is page 1, then apricot should point to two pages, corresponding to pages 4 and 5.

"What confuses things is that two hrefs may have been reversed according to our informants. We want to identify those two if possible.

"The second problem is to decode the message. Some think it's better to start with the decoding, under the theory that the decoding will help the ordering. I don't know.

"Since they change the messages more often than the links, we are certainly interested in the ordering in any case.

"Here is the text associated with each page:

apricot: "rrmlbgvp"

coconut: "6nlm4bgu"

currant: "rmar6mvx"

date: "8nb8vmhw"

fig: "xu6gllm7"

grapefruit: "wdddm3r8"

pineapple: "un6mx6m6"

prune: "rmx5mram"

raisin: "a7m9rgm9"

"Assuming you can order the pages, the message in ciphertext is just the concatenation of the messages in each page. We know from our agents that the code is a single substitution code in English mapping from all lowercase letters, all digits, and the space character to the same alphabet, viz all lowercase letters, all digits, and the space character. In this case, however, the encrypted text has no space character. That may or may not mean that the clear text has no blank spaces."

"The basic problem, Ecco, as I see it, is approximate graph isomorphism," I volunteered.

"It's perhaps made easier by the fact that some edges are represented multiple times. But the basic principle is the same. We want a mapping from fruit to page numbers and then we want to do a decoding."

"Quite right, Professor," Ecco said to me.

"I understand that your field hasn't quite decided how difficult even exact graph isomorphism is."

"True," I admitted. "No efficient, good algorithms are known, but the problem is not known to be hard either."

Reader: Your job is to solve these three problems: Find the correct ordering among the pages, identify the reversed edges if any, and then decrypt the message as much as possible (Hint: There are three 2s, two xs, and a v in the license plate).

Ecco and Liane worked on the problem for many minutes. As Ecco handed the written solution to Simon, he smiled and said, "Personally, I like dates better than figs."

Last Month's Solution

The solution to the "Joints In Space" problem required Ecco and Liane to propose a rectanguloid design consisting of a 4×4×3 arrangement of the cubes.

Given this, each cube can be identified by three coordinates. For example, (4,3,1,E) means that company E is in position (4,3,1).

Here is an assignment that obeys Tyler's original constraints:

(1,1,1,A) (1,3,2,J)

(2,1,1,A) (2,3,2,A)

(3,1,1,A) (3,3,2,C)

(4,1,1,B) (4,3,2,E)

(1,2,1,A) (1,4,2,F)

(2,2,1,A) (2,4,2,E)

(3,2,1,C) (3,4,2,E)

(4,2,1,C) (4,4,2,K)

(1,3,1,A) (1,1,3,L)

(2,3,1,D) (2,1,3,A)

(3,3,1,C) (3,1,3,M)

(4,3,1,E) (4,1,3,M)

(1,4,1,F) (1,2,3,L)

(2,4,1,D) (2,2,3,E)

(3,4,1,G) (3,2,3,E)

(4,4,1,G) (4,2,3,E)

(1,1,2,H) (1,3,3,E)

(2,1,2,A) (2,3,3,E)

(3,1,2,C) (3,3,3,E)

(4,1,2,C) (4,3,3,E)

(1,2,2,I) (1,4,3,N)

(2,2,2,A) (2,4,3,E)

(3,2,2,C) (3,4,3,E)

(4,2,2,C) (4,4,3,O)

Reader Notes

Natasha's "Dig" problem (DDJ, February 1999) engendered many clever responses. For this problem, however, machine triumphed over (wo)man in the sense that the best solutions I received were all programmed by some kind of search procedure.

The following all suggested an improved approach over Dr. Ecco's: Jon Beal, Jimmy Hu, Ted Alper, Richard W. Lipp, Michael Williams, Dave Weiblen, Pearl Pauling, Jim Greer, Dan Hirschberg, Paul DeMarco, Bob Harris, Jean-Francois Halleux, Christian Tanguy, Sam A. Virgillo, Dr. Burghart Hoffrichter, Christopher Oliver, Allan Vasenius, Charles Taylor, Koos du Toit, Martin Brown Kent Donaldson, Onno Waalewijn, Yves Piguet, Michael S. VanVertloo, Rodney P. Meyer, Benjamin C. Chaffin, Serguie Patchkovskii, Bharat Chandramouli, Hans Knorr, and Christopher Mills. The best answers in the case in which all items must have a positive integer label came from Ben Chaffin.

Ben's labeling when at most three objects can be taken was: 2, 4, 8, 16, 32, 60, 73, 116, 207, 230, 341, and 452. This yields a trim maximum sum of 1023. (Ecco's solution was quite a bit worse at 1401.) Ben's positive integer labeling for up to four objects yielded a maximum sum of 2556: 16, 18, 19, 20, 24, 32, 64, 128, 237, 420, 712, and 1187.

Many readers thought negative numbers wouldn't help yield a smaller maximum, but a few intrepid readers showed this to be wrong. The basic algorithm is to use negative numbers and then take the absolute value of any resulting sum. This guarantees a nonnegative answer, of course. The real cleverness is to ensure unique decodability. Dan Hirschberg showed that when at most three choices can be made, then negative numbers can reduce the maximum sum to 734: 2, 3, 4, 8, 16, 30, 56, 110, 173, 244, 317, -626.

In the best solution, Ted Alper then showed that negative numbers can reduce the maximum sum of 1527 for up to four choices: Alper: 2, 3, 4, 8, 16, 32, 61, 116, 224, 416, 771, -1468.

Since I know of no proof of minimality for any of these sequences, a clever reader may find a better solution than the ones mentioned earlier. For that reason, I've written a checking program in K that I will send to anyone who wants it. The program takes a sequence and the number of choices that can be made and sees whether the sequence results in the unique decodability of subset sums.

DDJ