This is a post describing my solution for 617B - Chocolate.
For this problem, the key is viewing the act of breaking the candy bar as a sequential process with a number of decisions at each stage. Once we know how many decisions there are at each stage, we can apply the rule of product and multiply the number of decisions at each stage to arrive at the total number of possible outcomes.
The sequential process proceeds as follows:
- Start at the left side of the candy bar and march right
- Keep marching until we get between two nuts
- Make a break somewhere between the two nuts
- Go back to step 2
Step 3 is the only step where we can make multiple decisions. If there are n zeros between the two nuts, then we can give n zeros to the left nuts and 0 zeros to the right nuts, n-1 zeros to the left nut and 1 zeros to the right nut, and so on. In total, we have n decisions for this particular break.
To help visualize this process, consider the following diagram on the input sequence 10101:
We can make 2 breaks between the first and the second nut and 2 more breaks between the second and third nut for a total of 2*2 = 4 possible breaks.
