Channels ▼
RSS

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 DrEcco@ddj.com.


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:

00020000000000000000

02222200000000000000

02222200000000000000

22222229000009050000

02222200090005555500

02222233300005555500

00020333330055555550

00003333333005555500

00003333333005555500

00103333333000059000

01110333330900090000

11111033394000000000

01110044444444400000

00100444444444449000

00004444444444444000

00044444444444444400

00444444444444444440

00444444444444444440

00444444444444444440

00444444444444444440

04444444444444484444

00444444444444444440

00444444444444444440

00444444444444444440

00444444444444444440

00044444444444444400

00094444444444444000

00009444444444440000

00000044444444400000

00000000004000000000

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:

000000000000

000000000000

000PP0000000

000110000000

000PP0000000

000000000000

000000000000

000000000000

00000000P100

000000000100

000000000000

000000000000

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:

111111110000

1111111P0000

1111111P0000

11111111P000

111111111PP1

111111111111

111111111111

111111111111

111111111111

111111111111

111111111111

111111111111

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.

DDJ


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.
 

Video