Dig

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].

A few minutes after I arrived in Ecco's apartment, the doorbell rang. A slim, fit woman in her late twenties entered, introducing herself simply as Natasha.

"My last name need not concern you," she explained as she looked us over, sizing us up with her penetrating blue eyes. "I've come to ask your help, Dr. Ecco," Natasha went on. She didn't sit down, though she did balance her briefcase on the back of a chair, "But first, I want to give you a little background."

"We are ready," Ecco said with a smile.

"Heinrich Schliemann, the German grocer turned archaeologist, followed the Iliad to discover Troy. Later, he thought he found Agamemnon's tomb in Mycenae," Natasha began. "He was wrong about Agamemnon, but he did find five tombs sculpted in gold, so they probably weren't shepherd graves. His excavation techniques were controversial, to say the least. He didn't shy away from dynamite if a hill was in the way. He also neglected to share the treasures of the Trojan jewel factory with the Ottoman Empire in spite of his promises to the Sultan. The Ottomans protested and demanded 10,000 gold francs. He gave them 50,000 instead. He was a man in a rush.

"Well, I'm a modern archaeologist, so you'd expect me to be a brush and silk kerchief kind of digger. Usually, I am, but not this time. You see, I'm excavating in the Sudan. The country is in a state of civil war and the authorities are deeply corrupt. So, I'm a woman in a rush. I'm going back tomorrow and I expect my team there to have found 12 large specimens. We want to smuggle them out of the country a few at a time and keep them until the Sudan has a responsible government."

"You're a thief," 10-year-old Liane said, ever tactful.

Ecco nodded, "Quite possibly, Liane. How do we know, Natasha, that you're telling the truth?"

Natasha looked unperturbed and reached into her briefcase. "You don't know I'm telling the truth, but here is a stack of my publications. I am known as a great preserver. The specimens will in fact go into a private collection, because the U.S. government doesn't want problems with the government of the Sudan over the issue. But I assure you we are doing this only to preserve the finds, not to exploit them."

"Why can't you just leave them in the ground?" Liane asked.

"The site is exposed now," Natasha said. "We are convinced the site will be looted if we delay."

"What can we do for you then?" Ecco said without enthusiasm.

"Well," Natasha replied. "As I said, there are 12 possible finds. We want to identify each of them with a positive whole number. When we phone our home base we want to use the sum of the numbers corresponding to the finds to tell our colleagues which ones to prepare for. They may respond with other sums to tell us which ones they are ready for. We think it's better to send a sum rather than a sequence of numbers because it will attract less attention."

"Please give us an example," Ecco said.

"Suppose, for example, that there were only three possible finds and we labeled them 10, 11, and 12, respectively," Natasha replied. "Then, 22 would represent the objects labeled 10 and 12, whereas 33 would represent all three objects. Altogether, the following sums are possible, each of which represents a unique set of objects: One object could be 10, 11, 12; two objects could be 21, 22, 23; three objects could be 33 (10+11+12). On the other hand, if we had four possible finds, the encoding 10, 11, 12, 13 wouldn't work because 23, for example, could result from either 10+13 or 11+12. We want every possible sum to mean a different combination."

"That's easy enough if we can use big numbers," Liane said. "For example, 10, 100, 1000, 10000."

"Correct, but that's just the thing," Natasha replied. "We want the largest possible sum to be as small a number as possible. If someone hears us talking about numbers in the billions, they may think we are bank robbers."

"Big difference," Liane said in a loud whisper.

"But if every subset of 12 is possible, then the highest possible sum must be over 4000," Ecco said.

Reader: Why should this be?

"I see," Natasha said after she heard his argument. "That's okay, in fact, because these finds are so big that we might not be able to take out more than three at a time. Can you find a labeling that would guarantee us a low sum?"

Ecco found a way to give positive whole number labels to the 12 objects such that any subset of the objects of size 3 or less could be described by the sum of the labels and that sum would uniquely identify the subset.

Reader: Find a labeling giving the smallest maximum sum in that case. Ecco was able to find a labeling such that the sum of any three never exceeded around 1400.

After hearing this answer, Natasha looked preoccupied. "Come to think of it," she said. "We may be able to get four specimens out at a time."

Reader: What would be the smallest maximum sum in that case? Liane was able to find a labeling that ensured that the sum of any four or fewer items was under 3000.

Natasha asked a few questions, made some notes on the written solutions, then left.

Ecco turned to Liane and me, "I understood why Natasha wouldn't want fractions and I suppose she wouldn't permit negative numbers to be reported over the phone, but I wonder if we could find a way to use negative numbers to good effect. Maybe some labels could be positive in some cases (for example, if the sum it participates in would be negative otherwise) and negative in others. I wonder whether we could get a better solution in that case."

Reader: If negative labels are allowed and labels can be positive or negative depending on the context, can you achieve better results for the aforementioned two questions?

Dr. Ecco never told me whether this idea, in fact, helped.

Last Month's Solution

The solution to the "Fair Swedes" problem, which involved mapping of original districts to new district numbers, is shown in Table 1. A graphical representation of Dr. Ecco's 28 district solution superimposed on the original map is shown in Figure 1. Thus, all areas having the same number will belong to the same district no matter what the original numbers were.

Reader Notes

Many readers found clever solutions to the "Directed Evolution" problems (November 1998). Here I cite those who found the best solutions to the two problems. Some people used computers and others used pencil and paper. The best algorithms using reversals are polynomial, but are quite tricky.

The first problem demanded a solution using reversals only. The best answers I received required nine steps. The first such solution came from Eric Haines who proposed the following:

start: mhtvkllcvvfsclcavawasshrqpchsp

1: (12,19) mhtvkllcvvfsawavaclcsshrqpchsp

2: (9,14) mhtvkllcvawasfvvaclcsshrqpchsp

3: (7,14) mhtvkllvfsawavcvaclcsshrqpchsp

4: (3,8) mhtfvllkvsawavcvaclcsshrqpchsp

5: (4,23) mhtfrhssclcavcvawasvkllvqpchsp

6: (1,12) mvaclcsshrfthcvawasvkllvqpchsp

7: (5,24) mvaclqvllkvsawavchtfrhsscpchsp

8: (2,27) mvhcpcsshrfthcvawasvkllvqlcasp

9: (0,17) awavchtfrhsscpchvmsvkllvqlcasp

Eric also pointed out that this puzzle is similar to those in the games section of the out-of-print book What to Do After You Hit Return: A Computer Games Book from the People's Computer Company (People's Computer Company and Hewlett-Packard, 1975). The pages he sent me talked about reversals that started from the beginning of the string, and thus were a little easier than these general reversals. Eric's Perl code for solving the problem is available at http:// www.lightlink.com/erich/nov98_pl.txt and from DDJ (see "Resource Center," page 5).

Other readers who matched Eric's feat were: Steve Myers, Creig Smith, Ted Alper, Charles Taylor, Dean Clamons, Tom Dinger, Oscar Schoof, Geldenhuys Jaco, Serguei Patchkovskii, and Onno Waalewijn.

Dr. Burghart Hoffrichter was the first to present a seven-step solution for the second problem and to point out that rotations didn't help:

start mhtvkllcvvfsclcavawasshrqpchsp

rev ( 5,29): mhtvkpshcpqrhssawavaclcsfvvcll

rev (11,25): mhtvkpshcpqvfsclcavawasshrvcll

rev ( 5,22): mhtvksawavaclcsfvqpchspshrvcll

rev ( 3,11): mhtcavawaskvlcsfvqpchspshrvcll

rev ( 6,11): mhtcavvksawalcsfvqpchspshrvcll

rev ( 4, 8): mhtcskvvaawalcsfvqpchspshrvcll

rev ( 6, 9): mhtcskaavvwalcsfvqpchspshrvcll

Most readers agreed, though Creig Smith's solution did use one rotation. Other readers who showed a seven-step solution were: Michael Van Vertloo, Steve Myers, Don Vilen, Ted Alper, Charles Taylor and the Wang Global Banking Solutions team of Bruce Oscarson, Curtis Cooley, Dale Bennett, Tom Dinger, Oscar Schoof, Geldenhuys Jaco, Serguei Patchkovskii, and Onno Waalewijn.

A Final Note

The ingenuity of DDJ readers makes this a truly delightful column to write. If you have a good solution, please send it early in the month when the issue comes out, because I have to submit my discussion of reader solutions during that same month.

DDJ