I have three buckets. They do not contain the same amount of water and they can contain up to 50 liters each.

Now I want to add more water to the buckets. This amount may vary from time to time, and might also be more than 50 x 3 liters. My goal is to fill the buckets with the new water so they have about an equal amount in each of the buckets - as close to equal as possible, but it's not a criterion. And also without exceeding the upper limit of 50.

Is there a simple and easy-to-read algorithm that would balance (as much as possible) the amount of water in the buckets?

• I always know how much water there already is in each bucket.
• I always know how much new water I get.
• Water already in buckets cannot be touched
• Equal water level is not a criterion, but further from the limits is desirable

CodePudding user response：

Yes, there is a simple algorithm as follows:

1. Sort the buckets by the amount of water. Let's call them a, b, c sorted none-decreasing.
2. The total amount of water that you need to balance them is (c - b) (c - a) = 2*c - b - a. Let's call the needed amount t.
3. If the available water is less than t, it is not possible to balance the buckets.
4. Otherwise, add c - b to b and c - a to a.

Update based on the new contraints in the edit:

If you have enough water to bring the amount of water in the lesser filled buckets to the level of the more full bucket, the previous algorithm works just fine.

But in case there isn't enough water available to make all three equal (note that this can be calculated up front as described above), first fill the bucket with the smallest amount of water up until it is equal to the middle one. Then divide the remaining amount of available water and distribute it equally between the two buckets that are equal but have less water than the other.

The intuition is this: When you add to the smallest bucket up until you reach the middle one, you are decreasing the absolute difference between the three by 2 for each added liter. That's because the smallest is approaching the middle and the largest one.

Example:

a, b, c = 5, 3, 1
available_water = 4
difference = (5 - 3)   (5 - 1)   (3 - 1) = 8

add 2 to the smallest:
a, b, c = 5, 3, 3
available_water = 2
difference = (5 - 3)   (5 - 3)   (3 - 3) = 4
Note that we reduced the difference by 2 times the amount of used water

add 1 to each of the smaller buckets:
a, b, c = 5, 4, 4
available_water = 0
difference = (5 - 4)   (5 - 4) = 2

Now if we didn't follow this algorithm and just arbitrary used the water:

add 2 to the middle bucket:
a, b, c = 5, 5, 1
available_water = 2
difference = (5 - 5)   (5 - 1)   (5 - 1) = 8

add 2 to the smallest one:
a, b, c = 5, 5, 3
available_water = 0
difference = (5 - 5)   (5 - 3)   (5 - 3) = 4