Today I only studied a little bit. I had too much other stuff to do. But I did manage to find a nice brain teaser from GeeksForGeeks.org.
Imagine a champagne pyramid, but in only two dimensions. Like this:
Level 1: 1 Level 2: 1 2 Level 3: 1 2 3
Of course, we could have as many levels of this "pyramid" as we liked.
All the glasses are the same. When you overfill Level 1 glass 1, the overflow goes half to the left (Level 2 glass 1) and half to the right (Level 2 glass 2). Every time a glass is overfilled, half the overflow goes to the left and half to the right.
Find a method to tell me how much champagne is in any glass, when I tell you how much I poured into the top glass.
For instance, if I say I poured 4 glassfuls, and I want to know about Level 3 glass 3, you'd tell me it had 0.25 glassfuls.
My middle daughter had some trouble with the overflow not spilling. I told her to imagine that the glasses were actually pitchers, with spouts on either side. It seemed to help. We also decided to use "cup" instead of "glass", because it's also a unit of volume. Better yet, it's shorter.
If you've got kids in any advanced algebra class, you start seeing Pascal's Triangle everywhere. I can definitely see it here; it specifies the relative rate of filling for any cup. But that doesn't help me much.
For the first few minutes, I kept trying to use Pascal's Triangle. I added numbers together, I tested all kinds of solutions... all dead ends.
Next I tried to solve an easier problem: how much water needed to be poured into the top before it started overflowing into any particular level of the pyramid? Also non-helpful.
I eventually gave up on any mathematical answer.
Time to make a program.
My first, naive impulse was to make a tree. You fill the first cup, allocate some new cups on the next level, assign them each half of the overflow, and go to the next node in a breadth-first iteration, continuing until you run out of water.
Okay, that would work, but it's too far. You should actually stop as soon as you run out of water, or you've reached the level of your cup.
Regardless, it's a linear solution. O(n) time complexity, with O(1) storage. I think I can do better.
The tree structure is also a little complicated for this problem. Even though it looks ideal -- that pyramid looks just like a tree -- I'll be asked to retrieve the cup by its level and index. That's not ideal for a tree.
I decided to try a recursive algorithm, using NO storage. To make that work, I'd step backwards from my cup, calling a "flow through" method for my left and right parents. A call to a cup outside the bounds of the level would just return 0. The call to the top cup just returns the total amount of water. Every other call adds half of each parent's "flow through", minus the 1c required to fill the parent. (So, if 1.5c flows through one parent, I get half of 0.5c from him.)
[code] package pascalcups; /** * Assuming a pyramid of cups, pour a given number of cupfuls of liquid into * the topmost cup. Find how much liquid is in any cup by its row and index. * * This method works, and it looks really efficient... but the debug output * shows that at row 2, higher nodes can be visited multiple times. * * There must be a better way. * * @author judebert * */ public class Attempt1 { public static void main(String args[]) { int row = -1; int cup = -1; double water = -1.0; if (args.length < 3) { usage(); System.exit(-1); } try { row = Integer.valueOf(args[0]); } catch (NumberFormatException e) { System.out.println("Error getting row of cup! " + e); usage(); System.exit(-2); } try { cup = Integer.valueOf(args[1]); } catch (NumberFormatException e) { System.out.println("Error getting index of cup! " + e); usage(); System.exit(-3); } try { water = Float.valueOf(args[2]); } catch (NumberFormatException e) { System.out.println("Error getting amount of water! " + e); usage(); System.exit(-4); } if (row < 0 || cup < 0) { System.out.println("Row and cup must be at least 0!"); System.exit(-5); } System.out.println("Finding water in cup " + cup + " in row " + row + " from pouring " + water + " cupfuls into top cup..."); double through = pouredInto(row, cup, water); System.out.println("" + Math.min(1.0, through)); } private static void usage() { System.out.println("This program finds the amount of liquid in a " + "particular cup in a pyramid."); System.out.println("You must provide the row and index of the " + "cup, as well as the number of "); System.out.println("cupfuls of water poured into the top cup."); System.out.println("We're all programmers here: the top cup is " + "the 0th cup in the 0th row."); } private static double pouredInto(int row, int cup, double total) { double volume = 0.0; // The top cup tries to hold all the water, and spills over if (row == 0 && cup == 0) { System.out.println("I (0,0) got a total of " + total + " cupfuls."); return total; } // Rather than error, just assume a 'virtual cup' that holds nothing // Note that each row has (row + 1) cups, with (row) the highest index. if (cup < 0 || cup > row) { return 0.0; } // I get half the overflow of my parents. double overflow = 0.0; double left = pouredInto(row - 1, cup - 1, total); if (left > 1.0) { overflow = (left - 1) / 2; volume += overflow; System.out.println("My left cup (" + (row - 1) + "," + (cup - 1) + ") contributed " + overflow + " cupfuls."); } double right = pouredInto(row - 1, cup, total); if (right > 1.0) { overflow = (right - 1) / 2; volume += overflow; System.out.println("My right cup (" + (row - 1) + "," + cup + ") contributed " + overflow + " cupfuls."); } System.out.println("I (" + row + "," + cup + ") got a total of " + volume + " cupfuls."); return volume; } } [/code]Well, that does get me zero storage. Unless the stack counts -- which it does, so I really ought to remove that useless "total" parameter.
So, no advantage in storage, and time complexity O(n^2) in the worst case -- because it visits some nodes more than once! If my right parent is the same as another node's left parent, that parent is getting visited twice. And that happens all the way up the tree. Ick!
Well, that can be fixed. I could use a 2D array for memoization. I'd make the array, fill it with a sentinel value (-1 is my favorite), and before calculating a value I could check if there was already a value in the array and return it.
While in most languages, a 2D array would take up a lot of extra space, Java implements it as an array of Objects. So my first level could have an array with 1 element, my second level an array with 2 elements, and so on.
That would reduce the time complexity, especially for very large numbers of cups. I guess that makes it O(log n). But I think I can do better.
Time to switch to a linear technique. I'll still use a 2D array, and I'll create it dynamically as I go. I'll loop through the levels, but I'll skip any cups that aren't involved in the calculation.
Not involved? How can I tell? Well, check this out:
0: A 1: B C 2: D E F 3: * G H * 4: * * I * *
If I'm interested in Level 4, cup 2 (counting like a programmer!), then I don't need to worry about my neighbors. They're not contributing to my water level.
In the next level up, I only need to worry about my parents, not their neighbors. The difference in our level is 1; I only need to worry about the cup at my index and my index + 1.
In the next level up, the level difference is 2. I only need to worry about the cups at my index through my index + 2.
So, as I pour the water through the levels, I've can determine the minimum and maximum cup for each level. I can skip any cup that's not involved.
That reduces the number of calculations to less than the number of cups (or at least no more than the number of cups for small numbers, my worst case). I'm down to O(log n) time and O(n) space!
Of course, I'd also quit early if I ran out of water. (Sneaky, sneaky users!) And I don't really need to keep around more than two levels of the array at a time (the one I'm filling and the one that's getting the overflow). Hmmm... that sounds like a tree could be useful. But I don't think there are any other optimizations to make.
Anybody got a better idea? Let me know. Especially if you can figure it out mathematically!