algorithm - Find the amount of water in ith cup in a pyramid structure?

Question

This question was asked in a forum. Any suggestions?

There is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on.. It looks something like this

  1
 2 3
4 5 6

every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on. Now given C and L .Find the amount of water in ith cup ?

Answer 1

Each glass has an incoming flow, an amount of water in the glass, and maybe some outgoing flow (overflow).

If each glass can contain 1 unit of water, and you pour 15 units of water, you get the following (overflow amount in parenthesis):

Incoming flow = 15, capacity = 1

Level 1:               1(14)
Level 2:           1(6)     1(6)
Level 3:       1(2)     1(5)     1(2)
Level 4:    1(1)   1(2.5)  1(2.5)    1(1)
Level 5:   1  1(0.75)  1(1.5)  1(0.75)   1
Level 6:  0 0.375 1(0.125) 1(0.125) 0.375 0
Level 7: 0 0  0.0625   0.125    0.0625   0 0

The incoming flow to the first level is L. The incoming flow from glass c on level r is Fin(c, r), and could be written as:

Fin(0, r) = 0
Fin(r+1, r) = 0
Fin(1, 1) = L
Fin(c, r) = Fout(c - 1, r - 1)/2 + Fout(c, r - 1)/2

The amount of water in that glass is:

A(c, r) = Min(C, Fin(c, r))

And the outgoing flow is:

Fout(c, r) = Max(0, Fin(c, r) - C)

I don't see any obvious formula for evaluating A(c, r) without doing it recursively.

---

To get from an index to a row and glass position, you can do:

index = r*(r-1)/2 + c

r = floor((1 + sqrt(8*index - 7))/2)
c = index - r*(r-1)/2

(indexes start with 1)