Find the amount of water in the i-th cup in the structure of the pyramid?

Question

This question was asked on the forum. Any suggestions?

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

1 2 3 4 5 6 

each cup has a capacity of C. You pour L liters of water on top. when cup 1 is filled, it is poured evenly into cup 2,3, and when they are filled, cups 4 and 6 receive water only from 2 and 3, respectively, but 5 receives water from the cups and so on. Now given C and L. What is the amount of water in the i-th cup?

Answer 1

Each glass has an inlet stream, the amount of water in the glass, and possibly some stream (overflow).

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

 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 input stream to the first level is L. The input stream from glass c at level r is Fin(c, r) and can 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 this glass:

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

And the outgoing stream:

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

I do not see any obvious formula for estimating A(c, r) without doing it recursively.

---

To go from index to 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) 

Answer 2

Some ideas: (1) It is important to know which two cups are the entrances to the ith cup. (2) It is important to know the minimum left that will bring you water on the left side and the Lright level will bring you water on the right side (3) So, you need to know which cups serve water to the goblet. This is simpler, think quickly if you start numbering from 0. The cup I will fill (i-1) * 2 + 1 and i * 2, which means that the cup kth will get water from (for k% 2 = 1) (k- 1) / 2 and (k + 1) / 2 (for k% 2 = 0) k / 2 and k / 2 + 1 (4) In this case, you must check that for any L you will calculate the difference L-Lleft and L-Lright. When the positive feed water is the result of dividing by 2 ^ n the calculated difference, where n is the cup level.

Answer 3

If you simulate a pyramid in a graph, the problem turns into the first width search. As you progress through each node, get your neighbors and save their overflow amount. If the neighbor was already found by the previous node (this will happen in case of 5 node, because node 2 and node 3 have an edge to it), you will have to update the overflow based on its capacity and what has already been filled (via node 2, assuming that node 2 passed to node 3).

Answer 4

To solve this problem, you can use the solution of a triangle with a pascal to calculate the binomial coefficient. We just need to fine-tune the algorithm and instead of calculating binomial coefficients calculate the water level. Given the i-th cup, we calculate the level and index to find out where the cup sits in the triangle.

Cups are modeled as

  0 Level 1 1 2 Level 2 3 4 5 Level 3 

getIndex () and getLevel () returns the index and level. Index and level start at 1.

 public static int getIndex(int i) { int totalNodes = i + 1; double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2; int level = (int)Math.floor(d); int total = ((level+1)*(level+2))/2; int index = 0; if(total==totalNodes) index = level; else{ level++; index = totalNodes - total - 1; } return ++index; } public static int getLevel(int i) { int totalNodes = i + 1; double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2; int level = (int)Math.floor(d); int total = ((level+1)*(level+2))/2; int index = 0; if(total==totalNodes) index = level; else{ level++; index = totalNodes - total - 1; } return ++level; } 

k is the k-th cup starting with 0. C is the capacity of the cup, L is the total water.

 public static double getWaterLevel(double C, double L, int k) { int n = getLevel(k); int index = getIndex(k); double[] water = new double[index+1]; water[1] = L; for(int i = 2; i <= n; i++) { boolean overflowed = false; for(int j = Math.min(i, index); j > 0; j--) { double over = 0; if(water[j]>C) over = (water[j]-C)/2; if(water[j-1]>C) over += (water[j-1]-C)/2; water[j] = over; if(!overflowed && over!=0) overflowed=true; } if(!overflowed) break; // no more overflow. stop } return water[index] > C ? C : water[index]; } 

Answer 5

Here is a simple and straightforward implementation:

 public class main { static float total_water = 50; static int N = 20; static glass[][] pyramid = new glass[N][N]; public static void main(String[] args) { build_pyramid(); pour_water(0, 0, total_water); print_pyramid(); print_total_water_stored(); } private static void print_total_water_stored() { float total = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) total += pyramid[i][j].filled; } System.out.println("total water stored= " + total); } private static void pour_water(int row, int col, float water) { if (water >= (pyramid[row][col].capacity - pyramid[row][col].filled)) { water -= (pyramid[row][col].capacity - pyramid[row][col].filled); pyramid[row][col].filled = pyramid[row][col].capacity; pour_water(row + 1, col, water / 2); pour_water(row + 1, col + 1, water / 2); } else { pyramid[row][col].filled += water; } } public static void build_pyramid() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) pyramid[i][j] = new glass(1); } } public static void print_pyramid() { for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) System.out.print(pyramid[i][j].filled + " "); System.out.println(); } } } class glass { float capacity; float filled; glass(float cap) { capacity = cap; filled = 0; } }