Protected: live classes
March 7, 2018
Merge alternate nodes of the two lists
May 7, 2018

Water overflowing from glass arranged in form of triangle

wine glassGlasses are arranged in the form of triangle (on top of each other) as shown below:

          1
       2     3
    4     5     6
  7    8     9    10
 ....................
......................

Liquid is poured into 1st glass (Glass no. 1). When it is full, then extra liquid will flow into the glasses 2 and 3 in equal quantities. When glass 2 and 3 are full, liquid will flow into glasses 4, 5 and 6.
From Glass-2 it will flow equally into 4 and 5 and from glass 3 it will flow equally into glass 5 and 6. Hence Glass-5 will get more liquid (from both Glass-2 & Glass-3) as shown in the image on the right.
If capacity of each glass is C and you pour N liters of liquid in Glass-1, then how much liquid will be there in each glass?

Pascal’s Triangle


Solution:

The solution to this can be though in terms of Pascal’s triangle. On the top water is coming directly into glass-1. At level-2 water will be equally divided into two glasses.

At level-3, water will come in 3 glasses, and the ratio of water will be 1:2:1. i.e the middle glass will get twice as much water as the left and right (this does not change the capacity, just the water flowing in it).

and so on…

so, If we have 7 liters of water, then:
    At level-1, 7 liters of water will flow and 1 liter out of it will be consumed.
    At level-2  6 liters of water will flow and 2 liters out of it will be consumed.
    At level-3, 4 liter of water will flow and 3 liters out of it will be consumed.
    At level-4, 1 liter of water will flow only thru glass-2 of level-3
                and hence this 1 liter will flow equally into 2nd and 3rd glass at level-4.

If we can visualize this, then the solution is simple. For simplicity sake we will use a two-dimensional array data structure (and not tree, which it may look like). In this case, half of the array will be wasted (gray cells in below diagram), so its not efficient in terms of memory consumption, but for the time being lets focus on algorithm.

wineGlasses_2

ith level will have i glasses.

Below is the code which will fill the glasses array with exact amount of water. The function fillWaterInGlasses, returns the total number of levels till which we will have water in the glasses.

Code:

#define MAX_LEVEL 100
double glasses[MAX_LEVEL][MAX_LEVEL];
/** Fill the global array glasses with the actual amount of water
 *  that will come in each glass.
 *  return the total level till water comes in the glasses.
 */
int fillWaterInGlasses(double C, double N)
{
    // Pour total water in top glass initially.
    glasses[0][0] = N;
    int level=0;
    bool waterInLevel = true;
    while(waterInLevel)
    {
        waterInLevel = false;
        // For each glass in the level.
        for(int j=0; j<=level; j++)
        {
            // If the glass has more liquid then it can store
            // then pour it to glasses under it.
            if(glasses[level][j] > C)
            {
                double extraWater = glasses[level][j] - C;
                glasses[level][j] = C;
                glasses[level+1][j] += extraWater / 2;
                glasses[level+1][j+1] += extraWater / 2;
                waterInLevel = true;
            }
        }
        level++;
    }
    return level-1;
}

If we call the function for N=10, and C=1 (capacity of each glass is 1 liter, and 10 liters of water is poured from top) as below:

int main()
{
    int level = fillWaterInGlasses(1, 10);
    for(int i=0; i<=level; i++)
    {
        for(int j=0; j<=level; j++)
            cout << " " << glasses[i][j];
        cout << endl;
    }
}

Then the output will be:

wine_result

Which actually means (writing output only till 2 decimal places because of space):

                 1
            1         1
        1        1         1
   0.37     1         1       0.37
 0    0.31      0.62      0.31     0

Please let me know your comments / feedback / suggestions.

1 Comment

  1. Ayush Jain says:

    Nice job SIr! Very great explaination !

Leave a Reply

Your email address will not be published. Required fields are marked *