ChampagneTower.java

package array;

/**
 * Created by gouthamvidyapradhan on 28/03/2019
 * We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the
 * 100th row.  Each glass holds one cup (250ml) of champagne.
 *
 * Then, some champagne is poured in the first glass at the top.  When the top most glass is full, any excess liquid
 * poured will fall equally to the glass immediately to the left and right of it.  When those glasses become full,
 * any excess champagne will fall equally to the left and right of those glasses, and so on.  (A glass at the bottom
 * row has it's excess champagne fall on the floor.)
 *
 * For example, after one cup of champagne is poured, the top most glass is full.  After two cups of champagne are
 * poured, the two glasses on the second row are half full.  After three cups of champagne are poured, those two
 * cups become full - there are 3 full glasses total now.  After four cups of champagne are poured, the third row
 * has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.
 *
 *
 *
 * Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is
 * (both i and j are 0 indexed.)
 *
 *
 *
 * Example 1:
 * Input: poured = 1, query_glass = 1, query_row = 1
 * Output: 0.0
 * Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will
 * be no excess liquid so all the glasses under the top glass will remain empty.
 *
 * Example 2:
 * Input: poured = 2, query_glass = 1, query_row = 1
 * Output: 0.5
 * Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is
 * one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid
 * equally, and each will get half cup of champange.
 *
 *
 * Note:
 *
 * poured will be in the range of [0, 10 ^ 9].
 * query_glass and query_row will be in the range of [0, 99].
 *
 * Solution: Calculate for every glass and for each row at a time. Use the value from the previous row to calculate the
 * current value.
 * @see PascalsTriangle
 */
public class ChampagneTower {
    /**
     * Main method
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(new ChampagneTower().champagneTower(4, 2, 1));
    }

    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] A = new double[query_row + 1][query_row + 1];
        A[0][0] = poured;
        for(int i = 1; i <= query_row; i ++){
            for(int j = 0; j <= query_row; j ++){
                if(A[i - 1][j] > 1.0){
                    A[i][j] += (A[i - 1][j] - 1.0) / 2;
                }
                if(j == 0) continue;
                if(A[i - 1][j - 1] > 1.0){
                    A[i][j] += (A[i - 1][j - 1] - 1.0) / 2;
                }
            }
        }
        if(A[query_row][query_glass] > 1.0) return 1;
        else return A[query_row][query_glass];
    }
}