Fog Creek Software
Discussion Board




Is the glass half-empty, or half-full?

You have a number of drinking glasses, each glass filled with an amount of drinking water. There are no completely full, and no completely empty glasses. Also, no two glasses contain the same amount of water.

Your job is to come to as many completely full glasses of water as possible, in as little time as possible, by pouring from one glass to another. What do you think is the most efficient procedure?

Stefaan R. M. Meeuws
Saturday, December 06, 2003

At any given time, pour the water in the second-most-full glass into the most-full glass.

This algorithm guaranteed that you would make a full glass in that step if it is possible to do so.

Please post any counter examples you find.

JHY
Sunday, December 07, 2003

This is actually a live example. I sometimes volunteer in a hospital, and it is after lunch that all the water bottles return to the kitchen.

I then have to make as many full bottles as possible from the collected bottles (about 15 of them).

Until now I poured the least filled bottle in the most filled bottle till I get a full bottle. Then I move on.

It strikes me your solution is more efficient. I don't think it can be beat.

I say this is a "live" example 'cos even though I'd want to submit more counter examples, I don't have one at the ready.

Stefaan R. M. Meeuws
Sunday, December 07, 2003

I am a little worried that the water bottles are not emptied and cleaned before being refilled, especially in a hospital environment. :p

Oli
Monday, December 08, 2003

except that you have to sort the bottles to choose one. wouldnt 'most efficient' be just pick each non full bottle and empty it into a non-empty bottle. or are we saying that sorting the bottles is a free operation?

PS maybe they autoclave the bottles and the water before sending them back out... or maybe the recycled water is just for visitors, or people with no health insurance...

david clark
Friday, December 12, 2003

>>wouldn't 'most efficient' be just pick each non-full bottle and empty it into a non-empty bottle?

Pouring randomly does not guarantee efficiency.  Imaging having three glasses of 60%, 40%, and 30% full.

You choose randomly by pouring
30% into 60% --> 90%
40% into 90% --> 100% and 30%.

A more efficient method would be pouring
40% into 60% --> 100%
30% untouched.

I assume pouring once is more efficient than pouring twice, although we have transferred the same amount of water.

As a side note, the "live example", by the way it was described, does seem controversial, resulting in readers focusing more on sanitation concerns and the well being of the patients than on the water pouring problem, thus causing responses to deviate from the topic.  However, the "live example" does not illegitimatize the problem nor does it change its solution.  If I had the same water-pouring job, I would be wondering about the most efficient method, too.  This is not to say once I know the solution I would follow it strictly like a machine, but it would not keep me from wondering and asking questions and finding solutions.

JHY
Saturday, December 13, 2003

THY asks:
"Please post any counter examples you find."

Your solution probably does minimize the number of "moves", but it does not
minimize the volume of water transfered.

Example: we have 3 - 16 oz bottles, one containing 15 oz of water,
one 14 oz, and one 13 oz. The "THY" solution takes only
2 moves, but transfers 4 oz of water. Stefan's solution also takes
2 moves, but transfers only 3 oz of water.

jeff
Friday, December 26, 2003

Isn't the glass and bottle problem different as the glasses are all different sizes and the bottles are all the same size.

I do think the bottles should be cleaned once in a while at least.

Philip Albert
Tuesday, January 27, 2004

I would split the glasses into two groups down the middle and reserve one side as the group to fill and the other as the group to empty.

As I went I'd toss the empty ones over my shoulder and put full ones off to the side.

If either group ran out of glasses I'd take a couple from the other group to even things out.

When I volunteered at a hospital we did the same thing with bedpans.

Marc Peabody
Thursday, January 29, 2004

Change the word "glass" into "bottle", and "glasses" into "bottles", and you'll see the situation as it exists in reality.

I just thought my sentences would work better if I said "glass" instead of "bottle".

I must admit at first I didn't quite get the retoric that followed on hygiene and so. Now, months after I posted the question I re-read it, and I feel .. er .. stoopid.

Stefaan R. M. Meeuws
Friday, January 30, 2004

No, pouring from the second most full to the most full doesn't work--

Consider four eight-ounce glasses, filled with 7, 6, 2, and 1 ounces respectively.

Pouring from the second-most full to the most full glass you would have three steps

7 6 2 1
8 5 2 1
8 7 0 1
8 8 0 0

But is is possible to do it in two steps:

7 6 2 1
8 6 2 0
8 8 0 0

Ham Fisted
Thursday, February 05, 2004

I suppose unless one can easily find 2 glasses (if they exist) that could be combined exactly into a completely full glass, then there is no simple one sentence algorithm that solves this problem.

In the mean time, go with your instincts and pour water from bottle A into bottle B if you think A and B make a completely full bottle.  Practice makes perfect.

JHY
Thursday, February 05, 2004

*  Recent Topics

*  Fog Creek Home