I need a hint to start on this programming puzzle

Question

You have a room-full of balances and weights. Each balance weighs ten pounds and is considered perfectly balanced when the sum of weights on its left and right sides are exactly the same. You have placed some weights on some of the balances, and you have placed some of the balances on other balances. Given a description of how the balances are arranged and how much additional weight is on each balance, determine how to add weight to the balances so that they are all perfectly balanced.

There may be more than one way to balance everything, but always choose the way that places additional weight on the lowest balances.

The input file will begin with a single integer, N, specifying how many balances there are. Balance 0 is specified by lines 1 and 2, balance 1 is specified by lines 3 and 4, etc... Each pair of lines is formatted as follows:

WL <balances> WR <balances> 

WL and WR indicate the weight added to the left and right sides, respectively. is a space-delimited list of the other balance that are on that side of this balance. may contain zero or more elements.

Consider the following input:

4 0 1 0 2 0 0 3 3 0 0 0  Balance 0 has balance 1 on its left side and balance 2 on its right side Balance 1 has balance 3 on its right side Balance 2 has three pounds on its left side Balance 3 has nothing on it 

Since balance 3 has nothing on it it is already perfectly balanced, and weighs a total of 10 pounds. Balance 2 has no other balance on it, so all we need to do is balance it by putting three pounds on its right side. Now it weighs a total of 16 pounds. Balance 1 has balance three on its right side, which weighs 10 pounds, so we just put 10 pounds on its left side. Balance 1 weighs a total of 30 pounds. Balance 0 has balance 1 on its left side (30 pounds), and balance 2 on its right side (16 pounds), we can balance it by adding 14 pounds to the right side.

The output should be N lines long, with the nth line listing the weight added to the nth balance, formatted as follows:

<index>: <weight added to left side> <weight added to right side> 

So the output for this problem would be:

0: 0 14 1: 10 0 2: 0 3 3: 0 0 

I tried but I'm really bad at programming I guess. Where should I start? please don't post the solution; I want to learn.

Answer 1

This is your tree

           (0)      -------------            |           |      (2)         (1)  ---------    -------     |       |    |     | [3p]     ..   ..   (3)                   ------                   |     |                  ...    .. 

Your logic should create this tree in the memory with every node containing the following data structure.

BalanceIdx: Integer;    //The balance index number if any. -1 indicates none InitialPounds: Integer; //Initial weight in the node  AddedPounds: Integer;   //The weight you added when processing. Default is 0 TotalWeight: Integer;   //**Total weight of a node including all its children. This is also our indication that a particular branch is already traversed. Default is -1 

We are talking about a recursive function which basically knows that it has only two paths or no path to follow when in any node of the tree. Each recursion is considered sitting on a plate of a balance.

Here is the logic.

1. Start from the root and travel until you find a node which has no path to go from.

2. Update the TotalWeight of it with the help of it's InitialPounds.

3. Now see if the node's other sibling has it's TotalWeightset. If NO, set the root of your recursive function there and execute.

4. If YES, calculate the difference and update the AddedPounds of where you sit. Now go to the parent and update its TotalWeight. (don't forget to add 10p for the balance(s)). Then go to the grand parent and repeat 3.

Once the recursive function completes traversing the whole tree, you have AddedPounds recorded in each node. Use another recursive function to construct the output.

This answer is for a starter which you have asked for.

Answer 2

SPOILER ALERT: Full solution included (except for reading the input)

This question is quite old, and looked fun, so I just went and solved it (in C, not PHP like this is tagged), after a few hint-like opening paragraphs. I used verbose variable names and commented, so it should work as pseudocode. I was going to write C-like pseudocode, but never hit anything that was worth summarizing.

---

The main complication to this problem is that you can't use binary trees, because a single balance can have multiple other balances on either or both of its pans. Probably the easiest approach here is linked-lists of nodes, where each node has left and right children, and also a sibling pointer. To get all the balances sitting on the left pan of a balance, the traverse the linked list of sibling pointers starting with the left child of the node for the balance you're looking at.

Since the input format assigns numbers to all the balances, it's easiest to just use those indices into an array of structs. If you can assume there are less than 2^31 balances, you can save memory by using 32bit ints instead of 64bit pointers. (Negative indices are a sentinel for empty, like a NULL pointer in pointer-based tree/list implementations)

struct balance {     // weights sitting directly on the pans of this balance     float weight_left, weight_right;  // or unsigned int; the question only said the balance-count was an int.  I assumed the balance-IDs were int, too      // optionally: float adjustment;  // For recording our changes.  negative or positive for adding to left or right balance.      // references to other balances: negative means empty-list, otherwise index into an array.     int next;           // linked-list of sibling balances on the same pan of a parent     int left, right;    // list-heads for balances on the left and right pan }; 

When they say you should add weight to the "lowest" balance, I guess they mean the root is at the bottom. It's not a tree of hanging balances suspended from something.

You're allowed to add weights to balances that are already carrying balances. So there's no complication about adding weight to empty pans at leaves of the tree. (That would require dividing the weight in a way that kept every subtree balanced individually).

So this looks quite simple to solve recursively.

• A subtree can be balanced on its own, without any information about any other balances.
• It doesn't matter what combination of weights and other balances makes up the load on the left and right pans. You just need those two totals. Balance by adding weight directly to the lighter pan.
• Balance a balance after balancing the all its sub sub-trees. You can total up the weights of the sub-trees while balancing them.

So the algorithm is:

static const float BALANCE_WEIGHT = 10.0f;  // return total weight of the balance and everything on it, including the 10.0f that this balance weighs // modify the .weight_left or .weight_right of every node that needs it, in the subtrees of this node float balance(struct balance storage[], int current) {     float lweight = 0, rweight = 0;      // C++ can make this more readable:     // struct balance &cur = storage[current];      // loop over all the left and then right children, totalling them up     // depth-first search, since we recurse/descend before doing anything else with the current     for (int i = storage[current].left ; i >= 0 ; i = storage[i].next )         lweight += balance(storage, i);      for (int i = storage[current].right; i >= 0 ; i = storage[i].next )         rweight += balance(storage, i);       lweight += storage[current].weight_left;     rweight += storage[current].weight_right;      float correction = fabsf(rweight - lweight);      // modify the data structure in-place with the correction.     // TODO: print, or add to some other data structure to record the changes     if (lweight < rweight) {         storage[current].weight_left += correction;     } else {         storage[current].weight_right += correction;     }      return BALANCE_WEIGHT + rweight + lweight + correction; } 

To record what changes you made, either use an extra field in the data structure, or destroy the original data as you come back up from the depth-first balancing (since it's no longer needed). e.g. store .weight_left = correction; .weight_right = 0; if the left needs weight added, otherwise do the reverse.

---

This implementation would use less stack space if there was a global array, instead of each recursive call having to pass the storage pointer around. That's an extra value that has to get saved/restored in a register-call ABI, and directly takes up extra space in a stack-call ABI like 32bit x86.

All the calculations involving the current node's weight_left and weight_right happen at the end, rather than reading them at the start and then having to re-read them for the += read-modify-write. A compiler couldn't make this optimization, because it can't know that the data structure doesn't have cycles, causing balance(subtree) to modify one of those weights.

For some reason, x86 gcc 5.2 -O3 compiles this to really huge code. It's more sane with -O2. clang does ok with -O3, but misses some optimizations.