CareerCup

There's different ways to solve this problem.

1) Mathematical.
We can develop a recurrence relation based on our observations about the object. For example - random glass can have 1,2 or 3 glasses above it. Corner glass will have only 1 glass above it and it will be corner glass. So for amount of liquid overflown to the corner glass we can a formula

V = SL-1/3

,
where V is amount of liquid spilled from glass above into target glass and SL-1 is amount of liquid spilled from corner glass on level L-1 where L is level of corner glass. And here recurrence comes to a picture:

SL-1/3 = (SL-2 - 0.25)/3 = ((SL-3 -0.25)/3 -0.25)/3 and so on.

Solving this recurrence we can get general formula for amount of liquid spilled from corner glass on any level:

SL = ((B-1) * 0.75 - Sum(1 -> L-1)) (3^K*0.75) / 3^L

Having this formula we can easily have an answer for any corner glass just calculating the result.

On the other hand, for some glasses the relationships will be more complicated, that is - some of them have 2 glasses on above and some have 3. One of this glasses in its turn can have 1,2 or 3 glasses on above and so on. Describing this mathematically just burnt my brain and I failed to do this. Anyway I doubt you can do this in 1 hour of interview round.

2) Simulation.
As simple as it is, develop a program in which each iteration is pouring a bottle into top glass. The relationship will be like

pourWineIntoGlass(double amount) {
	if (this.amount + amount >= 0.25) {
		this.amount = 0.25
		amount = amount - 0.25 + this.amount 
	} else {
		this.amount += amount
		amount = 0
	}
	if (amount > 0) {
		for each glass below {
			glassBelow.pourWineIntoGlass(amount/3)	
		}
	}
}

Ta-daaa, this is it. To get the amount you just run the simulation B times, and do glass.getAmount(). Main minus is that you do HELL LOT OF OPERATIONS and you'll never get their result actually. So here we go to...

3) Optimized simulation
Look on option #1, recurrence goes from bottom to top and only glasses you need appear in recurrence. Let's have a look on it again:

V = Sparent1/3 + Sparent2/3 + Sparent3/3

where V is amount of wine spilled into glass total and S are amounts of wine spilled from glasses above. And we can solve this recursion programmatically, but not mathematically. Amount of wine spilled from glass #1 on level 1 is (B*0.75 - 0.25)/3 and this glass is parent for all glasses on level 2. Amount spilled from any glass on level two is equal to:

(((B*0.75) - 0.25 / 3 )- 0.25 )/ 3

And in your code you do following:

howMuchInTheGlass() {
	V = 0; 
	for each parent 
		V += spilledFrom(parent) / 3
	if V > 0.25 return 0.25 else return V
}

spilledFrom(glass) {
	if (glass is top glass) {
		return B*0.75 - 0.25
	}
	S = 0; 
	for each glass.parent
		S += spilledFrom(glass.parent)/3
	if S - 0.25 <= 0
		return 0
	else 
		return S-0.25
}

Ta-daaaa! There you'll only touch the glasses you need to touch.

class NewYearsEve{
        public static void main(String[] args) throws java.io.FileNotFoundException {
                java.util.Scanner sc = new java.util.Scanner(new java.io.File(args[0]));
                int count = sc.nextInt();
                for(int i = 1; i<=count; i++){
                        System.out.println(String.format("Case #%d: %.7f", i, quantity(sc.nextInt(), sc.nextInt(), sc.nextInt())));
                }
        }

        static double quantity(int B, int L, int N){
                double influx = influx(B, L, N);
                return 250.0*(influx > 1?1:influx);
        }

        static double influx(int B, int L, int N){
                double[][] influx = new double[L][];
                influx[0] = new double[1];
                influx[0][0] = 3.0*B;
                for(int level = 1; level < influx.length; level++){
                        influx[level] = new double[influx[level-1].length + level + 1];
                        for(int shift = 1, source = 0; shift <= level; shift++){
                                for(int j = 0; j<shift; j++, source++){
                                        int targetTop = source;
                                        int targetLeft = targetTop+shift;
                                        int targetRight = targetTop+shift+1;
                                        double residual = Math.max((influx[level-1][source]-1.0)/3.0, 0);
                                        influx[level][targetTop] += residual;
                                        influx[level][targetLeft] += residual;
                                        influx[level][targetRight] += residual;
                                }
                        }
                }
                return influx[L-1][N-1];
        }
}

Here is my Python solution. Please be aware that I have not added the "Reading" the test cases from a file and "Writing" them back, however the main method will receive the same input and output the required resultes. Therefore, just the file read/write was skipped. I have also considered the overflow as an integer division so 100ml / 3 = 33ml.

The idea is to create a graph where each top glass has as connections the glasses it will overflow to. This way we can propagate the overflow to lower layers by looking if the above glass has more than 250ml. If so, we get the overflow, divide by 3 and add that to the connection glass. The next step would be similar to a Breath Search where we add the lower glasses to a queue e use the same overflow algorithm for them.

from collections import deque

class Glass(object):
    def __init__(self, value, row):
        self._value = value
        self._row = row
        self._connections = []
        self._fill = 0

    @staticmethod
    def new_years_eve(bottles = 1, levels = 1, glass = 1):
        if bottles < 1 or levels < 1 or glass < 1: raise ValueError()

        full_distribution = Glass._distribute(levels, bottles, 750, 250)

        if full_distribution.has_key((levels, glass)):
            return full_distribution[(levels, glass)]._fill
        else: raise ValueError("No such Level/Glass")
        
    @staticmethod
    def _distribute(levels, bottles, bottle_size, glass_size):
        graph = Glass._build_graph(1, levels)

        ml = bottles * bottle_size
        entry_node = graph[(1,1)]
        entry_node._fill = ml
        queue = deque()
        queue.append(entry_node)

        while len(queue) > 0:
            glass = queue.popleft()
            if glass._fill > glass_size:
                to_divide = glass._fill - glass_size
                glass._fill = glass_size
                for node in glass._connections:
                    node._fill += to_divide / len(glass._connections)
                    queue.append(node)

        return graph    


    @staticmethod
    def _build_graph(current_level, max_level):
        if current_level < 1: raise ValueError()

        current_nodes = Glass._level_nodes(current_level)

        result = dict()
        if current_level < max_level:
            sub_graph = Glass._build_graph(current_level + 1, max_level)
            result = sub_graph
            for node in current_nodes:
                node._connections.append(sub_graph[(current_level + 1, node._value)])
                node._connections.append(sub_graph[(current_level + 1, node._value + node._row)])
                node._connections.append(sub_graph[(current_level + 1, node._value + node._row + 1)])
        
        for node in current_nodes:
            result[(current_level, node._value)] = node
        return result


    @staticmethod
    def _level_nodes(level):
        nodes = []
        last = 0
        row = 1
        while row <= level:
            for i in range(row):
                last += 1
                nodes.append(Glass(last, row))
            row += 1
        return nodes


print Glass.new_years_eve()
print Glass.new_years_eve(bottles = 3, levels = 4, glass = 5)
print Glass.new_years_eve(bottles = 3, levels = 3, glass = 6)
print Glass.new_years_eve(bottles = 5, levels = 4, glass = 10)
print Glass.new_years_eve(bottles = 3, levels = 4, glass = 8)

T = int(input())

t = 1

MAX_LEVEL = 400

next_level = [0]

for i in range(1, MAX_LEVEL):  # level 1 to 400 - 1
    for j in range(i):
        next_level += [i]

MAX_CUPS = MAX_LEVEL * (MAX_LEVEL+1) // 2

while t <= T:
    print("Case #"+str(t)+": ", end="")
    t+=1
    lines = input().split()
    b = int(lines[0])
    l = int(lines[1])
    n = int(lines[2])
    level = 1
    cups = [[0 for i in range(MAX_CUPS+1)] for j in range(l+2)]
    cups[1][1] = 750 * b
    while level <= l:
        # print("     level", level)
        # print(level * (level + 1) // 2 + 1)
        for i in range(1, level * (level + 1) // 2 + 1):
            # print(i)
            if cups[level][i] > 250:
                rem = cups[level][i] - 250
                # print("    rem", rem)
                cups[level][i] = 250
                cups[level+1][i] += rem / 3
                cups[level+1][i + next_level[i]] += rem / 3
                cups[level+1][i + next_level[i]+1] += rem / 3
        level += 1

    # print(cups[3])
    print(cups[l][n])

For any given value of 'Kth' glass at level 'L', we can find the three glasses just below it(those glasses who would get equal amount of overflow liquid from the above glass).

The three glasses below glass #K at level L would be:
K, K + L and K + L + 1 of course at level (L+1).

Suppose we want to calculate the amount of liquid in glass K at level L
One way to calculate it would be to calculate the amount of liquid in each of the glass at level L and return the amount in Kth glass. Since we know the glass # below each glass, starting from glass 1 level 1 we can easily calculate this.
Problem : Too much space and calculation of unnecessary values.

If we have a way to determine the glasses above the given glass in the question, it would be very easy to calculate the liquid present in it.
As in if the glass in question is #K at level L, all we need is to find the # of glass at level (L-1) and similarly till we reach the top level.
Please suggest.

#include <stdio.h>
#include <stdlib.h>

#define BOTTLE_CONTENT 750
#define GLASS_CONTENT 250

struct Testcases
{
	int numBottles;
	int totalcontent;
	int glassLevel;
	int numGlassesOnLevel;
	int glassNumber;
};

int quantityinGlass(Testcases *test)
{
	int quantity = 0, i = 0;
	int sum = 0, prevsum = 0;
	int numglasses = 0;

	for( i = 1; i <= test->glassLevel; i++ )
	{
		numglasses = (i * (i + 1)) / 2;
		prevsum = sum;
		sum += numglasses * GLASS_CONTENT;

		if( sum > test->totalcontent )
		{
			break;
		}
	}

	if( test->glassLevel > i )
	{
		goto exit;
	}
	else
	{
		quantity = (test->totalcontent - prevsum) / test->numGlassesOnLevel;
		if( quantity > GLASS_CONTENT )
			quantity = GLASS_CONTENT;
	}

exit:
	return quantity;
}

void main()
{
	int numTests = 0, i = 0;

	Testcases **testcases = NULL;

	printf("Enter number of testcases: ");
	scanf("%d", &numTests);

	if( numTests < 0 && numTests > 10 )
	{
		goto exit;
	}

	testcases = (struct Testcases **)malloc(numTests * sizeof(struct Testcases *));
	
	for( i = 0; i < numTests; i++ )
	{
		testcases[i] = NULL;
	}

	for( i = 0; i < numTests; i++ )
	{
		testcases[i] = (struct Testcases *)malloc(sizeof(struct Testcases));
		printf("Enter number of Bottles: ");
		scanf("%d", &(testcases[i]->numBottles));

		testcases[i]->totalcontent = testcases[i]->numBottles * BOTTLE_CONTENT;

		printf("Enter level of glass: ");
		scanf("%d", &(testcases[i]->glassLevel));

		testcases[i]->numGlassesOnLevel = (((testcases[i]->glassLevel + 1) * testcases[i]->glassLevel) / 2);

		printf("Enter number of glass on level %d: ", testcases[i]->glassLevel);
		scanf("%d", &(testcases[i]->glassNumber));

		while( testcases[i]->glassNumber < 1 || testcases[i]->glassNumber > testcases[i]->numGlassesOnLevel )
		{
            printf("Invalid number of glass. Enter again for level %d: ", testcases[i]->glassLevel);
			scanf("%d", &(testcases[i]->glassNumber));
		}
	}

	for( i = 0; i < numTests; i++ )
	{
		printf("\nCase %d: %dml\n", i+1, quantityinGlass(testcases[i]));
	}
exit:

	for( i = 0; i < numTests; i++ )
	{
		if( testcases && testcases[i] )
		{
			free(testcases[i]);
			testcases[i] = NULL;
		}
	}

	if( testcases )
	{
		free(testcases);
		testcases = NULL;
	}

	return;
}

I think the key point is, for each level, before any glass being fully filled, no glass under this level will get any wine in it. And in one level, once the first glass is fully filled, all glasses in the above level are all fully filled. This can be proved.

My idea is :
1. First, for each level, compute the total wine when any glass is fully filled.
2. With that, we can know when we use such amount of bottle, k-th level is fully filled, some glasses in k+1 th level is fully filled, and some glasses in k+2-th level has wine.
3. Simulate left wine.

Java implementation

public static void fill(HashMap<String, Double> map,int L,int N,double capacity){
		String key = "L"+L+"N"+N;
		if(!map.containsKey(key)){
			map.put(key, 0.0);
		}
		if(map.get(key)<0.25){
			double c = 0.25-map.get(key);
			if(capacity>=c){
				capacity = capacity - c;
				map.put(key, 0.25);
			}else{
				map.put(key, map.get(key)+capacity);
				capacity = 0.0;
			}
		}
		if(capacity>0.0){
			fill(map,L+1,N,capacity/3.0);
			int p = (int)(Math.log(N)/Math.log(2)) + 1;
			fill(map,L+1,N+p,capacity/3.0);
			fill(map,L+1,N+p+1,capacity/3.0);
		}
	}
	public static double capacity(int B,int L,int N){
		HashMap<String, Double> tower = new HashMap<String, Double>();
		fill(tower,1,1,B*0.75);
		return tower.containsKey("L"+L+"N"+N) ? tower.get("L"+L+"N"+N) : 0.0;
	}