Find the amount of water in ith cup in a pyramid structure?
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)