Channels ▼

Dr. Ecco's Omniheurist Corner

Feb02: Dr. Ecco's Omniheurist Corner

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); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); 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].

Sometimes, art imitates life. Joseph Conrad might smile at this particular imitation.

Ecco's visitor introduced himself as Austerlitz Toulemonde. "I am from the Napoleonic Society," he explained. "We use swords and firearms from the time of the Emperor. When it comes to small arms, we prefer Gribeauval pistols, ideally the 1806 models. When disagreements arise, we encourage duels, though only to the first touché. Also, our vests are made of kevlar. Even when we're wounded, no one is too badly hurt. Our members prefer modern surgeons to barbers.

"Now it happens that I have been caught in flagrant delit with the extremely charming wife of another member. To protect his honor, he has slapped me with his glove and we must duel tomorrow. In this duel, I am the challenged and he is the challenger.

"The basic duel scenario of our society is that there are two duelists. They start by standing 100 paces apart. The challenged has three bullets and the challenger has two.

"At 100 paces, the duelists have no chance of hitting one another, and duelist 1 has the option to shoot first. If duelist 1 shoots and misses or declines to shoot, then duelist 2 may choose to shoot. If duelist 2 shoots and misses or declines to shoot, then they advance towards one another by five paces each (10 paces together). At that point, each duelist takes his turn, first duelist 1 and then duelist 2. This continues as long as there are bullets in the guns. According to our society's rules, duelist 1 is always the challenger. I have the advantage of the extra bullet, however.

"The probability of hitting your opponent (and therefore winning) with a given bullet at distance d is (100-d)/100. So, at 100 paces, the probability is 0. At 0 paces, the probability is 1.

"My question to you is: What are my chances of winning, assuming neither of us can quit in the middle of the duel?"

"Well, if you as the challenged have one bullet left and the challenger has at least one, then you should shoot at 50 paces," Liane volunteered quickly. "If the challenger has no bullets left and you have one at 50 paces, you should hold your fire."

Reader: Before reading on, is Liane suggesting the impetuous?

Ecco smiled at his 13-year-old niece. "Would you like to explain?"

"Yes. At 50 paces, the challenged has a 0.5 chance of winning. If he misses, he will surely lose, but at least he has the 0.5 chance. Now, if the challenged decides not to shoot, then the challenger could win with a probability of 0.6 at 40 paces. Of course, if the challenger has no bullets left, then the challenged should wait until he is 0 paces away from the challenger to shoot." Liane answered with her customary self confidence.

Toulemonde nodded at Liane's answer. "Nicely done, belle fille," he said. "But I need to know what to do with my three bullets against his two, starting at 100 paces."

Ecco and Liane worked out the problem using a technique that Liane had recently picked up from her algorithms book Dynamic Programming. They concluded that Austerlitz would usually win. Can you tell by how much?

Reader: What if both started out with three bullets?

Last Month's Solution

To answer the general's original question in which no sprinkler should hit an area outside the farm and 10 of the 11 rare cacti should be spared, here are good places to put the sprinklers.

sprinkler 1: 11 2 range: 2

sprinkler 2: 3 3 range: 3

sprinkler 3: 8 7 range: 3.37

sprinkler 4: 20 10 range: 9

sprinkler 6: 6 15 range: 3

This covers 361 square meters with the following covering map, where 9s represent cacti that we spare and the 8 represents a cactus we water:































Reader Notes

Several readers improved on Liane's solution to the "Sprawl" problem (DDJ, November 2001). These included Michael Birken, Aaron R. Coleman, Alexander Fedorov, Andrew Palfreyman, Tim Chase, Stephen Waits, and Andrew Calafato.

Calafato and Waits suggested putting the parks at these locations (2,3), (2,4), (4,3), (4,4), and (8,8), giving two of the first owners very pleasant vistas and retarding full development for 17 years. This gives an initial configuration of:













Calafato described his approach as follows: "The heuristic I used was: Cover up the most central building so that no development will take place from the center. Then place the last park near the other developed pair, and place it towards the center (at (8,8)) so that construction has to go around it, taking a bit more time."

Birken found a solution that could retard sprawl indefinitely on 15 nonpark parcels starting with parks at: (3,8), (4,9), (4,10), (1,7), (2,7). That gives a final configuration of:













Andrew Palfreyman used an exhaustive search approach to show that if the Sprawler moves second, he can guarantee to cover all nonpark land in 11 years.


Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.