Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Calabaza


Nov99: 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), 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].


We have found a remarkable tribe in the jungles of Venezuela," the strongly built ethnobiologist Panta de Leon began in slightly accented English. De Leon had heard of Ecco from Natasha, the archaeologist of the Sudan. De Leon's motivation, we all decided later, was much more pure.

"The tribe has lived in near permanent isolation except for occasional, mostly unfriendly, exchanges with outsiders. They are fine singers and percussion musicians. Their principal musical instrument is a fruit gourd called (in Spanish) a Calabaza. This gourd is so central to their life in fact that they call themselves the Calabazas when meeting (friendly) outsiders. Recently, I discovered that they also use the Calabaza as a timepiece for the ritual they call -- I'm translating roughly -- 'Prayers to the Clock God'.

"Let me explain. Their's is one of the wettest, most mosquito-infested corners of the world. This has kept them safe. It also means that anything made of metal either rusts or is quickly impregnated with water.

"Many years ago, they found a group of explorers who had lost their way and then died of a poisonous fruit. One of the explorers had a watch, which the Calabazas brought back to the village. The watch worked for one moon, they say.

"The first day they had it, the tribal elders tried to figure out the meaning of the timepiece and they quickly concluded that it must be used for prayer. The explorers died because they hadn't prayed at the right time, they decided. Fascinated by the circular rhythm of the second hand, the elders directed the village artisan to create several gourds of the same size, each with a hole. They told the artisan that he should create the gourds so that a full gourd would drain completely in one minute when the hole was opened. Unfortunately, the village artisan found himself unable to carve a large enough hole without destroying the Calabaza. Instead, he created Calabazas having two holes.

"Opening one hole in a full Calabaza would cause the water to drain completely in 11 minutes. Opening both holes would cause it to drain in 5 minutes. These were exact times, to the second in fact -- a remarkable achievement considering that all his tools were handmade."

Liane perked up. "Why should two holes be more than twice as fast as one?" she asked.

"The vortex effect, I think," Ecco responded. "Two close holes will create a vortex and water will pass through both of them faster than the sum of the speeds of each hole alone."

De Leon nodded in agreement. "Whatever the reason, that was the effect. The village elders were unhappy with that, because they had already invented a full moon ritual in which percussion Calabazas would be hit every minute as the village women chanted.

"They told the artisan that he must figure out how to make a one-minute Calabaza by the next full moon. He told them that he could not, but that with five Calabazas, four assistants, a ready supply of water, and about an hour, he would be able to tell the drummers to hit their drums every minute exactly."

"How long does it take to fill an empty Calabaza?" Liane asked.

"Natasha told me you were clever," Panta said to the 11-year old. "Less than a second. One can just dip it into a big barrel. You can assume it takes no time."

"Well, then it shouldn't be so hard," Liane said. "For example, it's easy enough to measure six minutes. You start two Calabazas at the same time, opening one hole of one and two holes of the other. Six minutes is the time between the draining of the two-hole Calabaza and the draining of the one-hole Calabaza."

"I think you are on the right track," de Leon said. "But it is important that you figure this out today. You see, the full moon is about to come and the village artisan has taken terribly ill. They are counting on me to help them figure out what he did. They refuse to let me use my watch, as they revere the gourds as holy. Now for my personal appeal: As an ethnobiologist, I have made it my goal to win their confidence. They trust me so far and they have taught me about many wonderful herbs. They even have a remarkable medicine to enhance musical ability, seemingly without side effects, but I must stay with them longer before they will teach me about it. I would really like to help them with their problem first."

"Let me try a small example," Liane said. "Suppose that a one-hole Calabaza drained in three minutes and a two-hole Calabaza drained in two minutes (reversing the vortex effect for the sake of the example). Then it would be possible to measure minutes by allowing Calabaza A to drain in three minutes, B to drain in two minutes, and then repeatedly filling each Calabaza and draining it with two holes. So, A would mark times 3, 5, 7, 11, 13,...and B would mark times 2, 4, 6, 8, 10, 12,... Thus, it would be possible to mark minutes beginning two minutes after the procedure starts. Now let's try it for the gourds the artisan really builds."

Liane and Ecco talked for a while. Liane explained an idea. Ecco smiled.

"Mr. de Leon," Ecco said with a smile, "Liane has solved your puzzle. Five Calabazas seems to be the minimum possible. If five people follow this simple procedure, they will be able to mark single minutes starting 40 minutes after beginning the procedure."

Reader: Is five Calabazas really a minimum? Can you invent a procedure that involves filling Calabazas and watching them drain such that it is possible to mark single minutes starting 40 minutes into the procedure? Assume that it is easy to tell when a Calabaza drains. Can you do it better (either with fewer Calabazas or fewer minutes)?

After Panta de Leon left, Ecco turned to me. "Suppose one hole will cause the gourd to drain in n minutes and two holes will cause the gourd to drain in the minute below half of n (for example, if it takes n=20 minutes to drain with one hole, then two holes requires the integer below (20/2)=9 minutes; if it takes n=21 minutes with one hole, then with two holes it takes the integer below (21/2)=10 minutes). Are there any numbers n that make marking minutes impossible?"

Reader: Which values of n would be troublesome, if any? If none, then map out a procedure that can always mark minutes, assuming you have enough gourds.

Last Month's Solution

Best val: 1801 and deviation for that ordering is: 64

Object Alice Brad Carla
27 18 33 61
14 49 35 52
7 7 6 49
19 42 13 1
25 64 1 124
6 17 10 17
16 14 7 36
5 2 16 0
2 4 29 33
23 75 9 11
12 3 18 5
29 34 29 3
15 15 22 101
11 41 26 5
13 45 22 11
10 36 2 30
30 37 12 11
3 131 72 62
24 10 33 44
4 9 28 42
17 34 31 47
8 56 1 45
21 30 4 20
22 11 59 39
9 80 4 27
28 7 11 28
18 4 87 24
26 12 19 19
1 71 203 21
20 42 158 32

Deviation of 1 and highest value for this deviation is: 1780

Object Alice Brad Carla
6 17 10 17
18 4 87 24
21 30 4 20
1 71 20 321
30 37 12 11
8 56 1 45
28 7 11 28
13 45 22 11
11 41 26 5
16 14 7 36
15 15 22 101
10 36 2 30
3 131 72 62
25 64 1 124
4 9 28 42
14 49 35 52
29 34 29 3
24 10 33 44
26 12 19 19
2 4 29 33
22 11 59 39
27 18 33 61
5 2 16 0
9 80 4 27
23 75 9 11
12 3 18 5
7 7 6 49
19 42 13 1
20 42 158 32
17 34 31 47

Reader Notes

Dr. Ecco's solution for "Laser Shuttles" (DDJ, August 1999) was not the best possible. Fortunately, several clever readers found better ones. In the best solutions, no astronaut will be required to take more than three hops to go from site to site and the total number of edges is 45.

  • Alan Dragoo's solution is a nice example (http://members.aol.com/adragoo/ laser.jpg).
  • Burghart Hoffrichter pointed out: "By counting the number of horizontal and vertical edges in each rectangle and one diagonal per rectangle and the sides of the triangles, one sees that 45 is the maximum number of nonintersecting edges."

  • Brian Nelson thought that deregulation might bring about a reduction in the number of edges.

  • Kees Rijnierse suggested that putting the stations slightly off the grid might make even better solutions possible, but did not know how.

  • Denis Birnie of Transportation & Traffic Systems Ltd (Christchurch, New Zealand) suggested several other optimization criteria. Among them: Is there a 4-hop-to-anywhere network such that every journey can be completed by at least 2 routes with only the start and end stations in common? If not, is there a 4-hop primary and 5-hop secondary network?

Other readers who demonstrated 45 edge/3-hop designs included: C. Brock Rooney, Pearl Pauling, Rodney Meyer, Peter Scholz, Brian Nelson, Tapani Lindgren, Todd Ginsberg, Ted Alper, Mike White, Vernon R. Brown, Stephen A. Slezic, Kiia Kallio, Tom Rokicki, Matthew D. Ahl, Andy W. Desplenter, Mark Taylor, Kees Rijnierse, Forest Wilkinson, and Doug Newhort (who minimized the average length as well, http:// members.home.net/dmewhort/3hub.htm).

Still others demonstrated 45 edge/4-hop designs: James Waldby, Christopher W. Curtis, Burghart Hoffrichter, Jason Patterson, Douglas Price, Magne Oestlyngen, John Porter, Bob Morton, Greg Smith, Kees Rijnierse, Denis Birnie, Carey Bingham, Kevin Fox, Steve Bourassa, David Stevenson, Jeffrey A. Hallman, and John Grant.

DDJ


Copyright © 1999, Dr. Dobb's Journal

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.