Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), and 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].
Dr. Roger Windswift of the Center for Disease Control had chosen his career of ethnobiologist well. Kayaker, underwater photographer, naturalist, entirely comfortable in the jungle or makeshift lab, he looked cooped in by Ecco's MacDougal Street apartment. After shaking our hands, he paced the room as he described his problem, touching objects to sense their texture without interrupting his train of thought. His story unfolded in academic innocence.
"In the mid 1980s, Jeffrey Palmer and L.A. Herbon showed that cabbages and turnips, while close in sequence, differ from each other mostly through a series of reversals," he said.
I saw Ecco's face settle into an expression of bemused indifference.
"A reversal of a string between positions x and y," Windswift continued, "is a permutation of the string in which the subsequence between x and y is reversed but nothing else is changed.
So, starting with a string whose indexes are numbered from 0 to n:
0 1 2 3...x x+1...y-1 y y+1...n,
he obtains a new string with a reversal in the middle:
0 1 2 3...y y-1...x+1 x y+1...n.
We denote such permutations by the low and high indexes of the reversed subsequence, in the above case (x,y). For example, given the string abcdefg the reversal (2,4) yields abedcfg (leave ab alone, reverse cde, and leave fg alone).
"A strain of bacteria closely related to anthrax has recently appeared. We suspect that it was manufactured."
He stopped his pace for a moment and swept his eyes to each of us.
Windswift went on. "Fortunately, this particular strain does not appear to be contagious, but we want to be ready for the next one. Our strategy will be to create antidotes by doing reversals of some secret bacteria that we have. This will serve as a kind of vaccine.
"We have recently developed a technique that will transform a bacteria population A into a new one B that is identical to A except for one reversal that we can control. The technique takes a day to complete. If we want to do five reversals, we will need five days."
"Is there no way to work on many reversals at the same time?" Liane asked.
Windswift looked at the 10-year-old girl for a moment, then said, "Good question. As far as we can tell, the answer is no. That's why we're here. We need to create these antidotes as fast as possible. That means we have to figure out the fewest number of reversals to transform some critical protein sequence to another one, all in vivo."
"Could you give us an example of a reversal problem?" Liane asked.
"Sure, I'll give one that I had trouble doing efficiently. Find the smallest number of reversals that take abcdefg to cfegbad. I challenge you to do it in three reversals," Windswift answered.
Liane thought for a minute and then wrote down:
(0,2), producing "cbadefg"
(1,5), producing "cfedabg"
(3,6), producing "cfegbad"
"Nice job, Liane," Ecco said chuckling. "Well, Dr. Windswift, you can see we have the talent to do rapid, directed evolution. Please give us a real problem now."
"Very well," Windswift said. "But please understand that the sequence I'm concerned with is the start of a critical binding sequence for memory. Please be careful not to reveal this information."
"Yeah, yeah," Ecco said with a smile.
"Here is the start sequence:
mhtvkllcvvfsclcavawasshrqpchsp
"We want to produce the following sequence through as few reversals as possible:
awavchtfrhsscpchvmsvkllvqlcasp
"Can you do it in under 14 reversals? Two weeks is about all the time we have, but we can do 14 reversals in two weeks."
Ecco and Liane worked on the problem for a while. Liane came up with a solution first.
"I can do a few better than you asked for, Dr. Windswift. I've written it down in steps so you can follow it easily. Along with each step, I write the low and high indexes of the subsequence being reversed."
Reader: can you do better than 14? How small a number of reversals can you find?
"Wow," Windswift said. "Do you have any time after school to do some consulting?"
"My uncle keeps me busy enough, thanks," Liane answered sweetly.
Windswift left, but returned a month later. "The anthrax manufacturers have found a new mutation path. Not only can they cause reversals in subsequences, but they can cause subsequences to rotate by one to the right. For example, given the sequence:
abcdefg
the rotation (1,4) would yield
afbcdeg
(the f moves to position 1 and bcde are moved one to the right; remember that the sequence starts at 0).
Fortunately, we've found a process to do a rotation in a day, but now our mathematical problem is to figure out the shortest possible combination of rotations and reversals to transform one sequence to another. This seems hard to us."
"Could be. Please let's have a try," Ecco said.
"Here are the sequences," Windswift said. Start again with:
mhtvkllcvvfsclcavawasshrqpchsp
but end this time with:
mhtcskaavvwalcsfvqpchspshrvcll
Reader: Try to find a short sequence of rotations and reversals to get the ending string from the starting string. Remember that the rotations take a subsequence and rotate it by one position to the right.
Ecco worked on the problem for several minutes in silence. Then he raised his head and asked: "Is there any reason to believe that it is easier to rotate just after reversing?"
"Not that I know of," Windswift said. "Why do you ask?"
"No reason, I just suggest you discuss this possibility with your chemists," Ecco said, as he handed Windswift an eight-step transformation.
Two months later, a small item in a newspaper reported a disease outbreak following a pistachio party in Los Angeles. An unidentified scientist from the Center for Disease Control was on the scene. A few days later, health officials issued an advisory that certain kinds of pistachios should be avoided and a second advisory that people with rashes behind their ears should call CDC in Atlanta. Then the news media returned to its twin obsessions with the stock market and sex scandals.
Last Month's Solution
Here is what Ecco and Liane came up with after 15 exchanges:
0 0 0 0 0 0 0 0 0 0
2 2 2 2 0 0 0 0 0 0
2 2 1 2 2 0 0 0 1 0
2 2 1 1 2 2 0 1 1 1
1 1 1 2 2 2 0 1 1 1
1 2 1 2 2 0 0 1 1 1
1 2 1 2 0 0 1 1 1 1
1 2 1 2 0 0 1 1 1 1
1 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1
Here were the exchanges:
1. exchange (0 8) for (2 6)
2. exchange (0 8) for (5 9)
3. exchange (7 4) for (6 2)
4. exchange (3 8) for (8 3)
5. exchange (8 5) for (6 0)
6. exchange (0 6) for (6 1)
7. exchange (9 0) for (0 3)
8. exchange (9 1) for (3 4)
9. exchange (2 6) for (8 1)
10. exchange (4 7) for (4 5)
11. exchange (9 8) for (1 4)
12. exchange (1 9) for (3 9)
13. exchange (7 8) for (0 5)
14. exchange (9 5) for (2 5)
15. exchange (2 9) for (8 6)
Reader Notes
Readers verified that the best solution with the original scoring to the Mates problem (July 1998) was:
tent 1: alan,mike
tent 2: dave,isaac,larry
tent 3: emily,gwenyth,hillary
tent 4: bob,carol,jack,nick
tent 5: felicia,kris,olivia,petra
yielding a total score of 175.
For the case when the campers' preferences dropped by four points (among those with expressed preferences), the best assignment was:
tent 1: alan,issac
tent 2: carol,jack,nick
tent 3: kris,larry,mike
tent 4: bob,felicia,olivia,petra
tent 5: dave,emily,gwenyth,hillary
yielding a total score of 92 (better than the one Dr. Ecco revealed).
Paolo Friedli wondered what Dr. Ecco would have done if there had been 60 kids and 20 tents. I suggested simulated annealing, but there are some excellent genetic-algorithm readers out there.
For example, Mike Williams suggested the following genetic style technique:
arbitrarily assign people to tents
calculate and store happiness
repeat
randomly move some people around
calculate potential happiness
if better than previous best
store best and update current configuration
until tired of trying
Readers who solved this problem include:
Gary Knowles
Michael S. VanVertloo
Andrew Lipson (who considered the problem a bit easy)
Terrence E. Vaughn
Roger Alley
Jean-Francois Halleux
Greg Walker
Jack Boudreau
Mathew Davies (who thought that Dr. Ecco might be suggesting film titles)
Carl Smotricz
Earl Paddon
Onno Waalewijn
Yannick Heneault
Scott McKinney
Iulian Kakulidis
Michael Williams
Manuel Alvarez Fernandez
Tamas Visegrady
Paolo Friedli
Franco Venturi (who also showed that the maximum two-day score if one can't change bunkmates is 262)
Dan Falk
David Seaman
Lee Thomason
Steve Worley
DDJ
Copyright © 1998, Dr. Dobb's Journal
