FryingHamburgers

Problem:

TopCoder Problem Statement - FryingHamburgers

Single Round Match 159 Round 1 - Division I, Level One

Overview:

Optimize the time it takes to cook a number of hamburgers given the number of burgers, and the size of a grill.

Java Source:

01: public class FryingHamburgers {
02: 
03:  private static final int MINS_PER_SIDE = 5;
04:  private static final int MINS_PER_BURGER = 2 * MINS_PER_SIDE;
05: 
06:  public int howLong(int panSize, int hamburgers) {
07: 
08:   // If there are no hamburgers, it takes no time.
09:   if (hamburgers == 0)  return 0;
10: 
11:   // All the hamburgers can fit on one pan.
12:   if (hamburgers <= panSize)  return MINS_PER_BURGER;
13: 
14:   // The hamburgers divide evenly by panSize
15:   if ((hamburgers % panSize) == 0)  {
16:    return (hamburgers / panSize) * MINS_PER_BURGER;
17:   }
18: 
19:   /*
20:   * If the remainder is <= panSize, we can use the trick described in
21:   * the tests to save the cooking time of one side.
22:   */
23:   if ((hamburgers % panSize) <= (panSize / 2))  {
24:    return ((hamburgers / panSize + 1) * MINS_PER_BURGER)
25:      - MINS_PER_SIDE;
26:   }
27: 
28:   // Worst case, we just cook one side, then the other.
29:   return (hamburgers / panSize + 1) * MINS_PER_BURGER;
30: 
31:  }
32: }

Notes:

This is the sort of nasty little problem that you might encounter during a programming interview. I've seen it asked with 3 burgers and a grill that holds two. That's easy enough to explain. Coding it up for the general case is quite a bit trickier. It's also very likely that you'll pass the given examples, and then fail during the challenge phase, since it's so easy to make a mistake in the logic that goes undetected.

There are essentially five cases to think about:

1. hamburgers == 0. This is trivial, if there are no burgers, it takes no time
2. hamburgers <= panSize. Again, pretty trivial. We can put all burgers on the pan at once. Flip them after 5 minutes, and they'll be done in 10. There's no way to shorten this.
3. (hamburgers % panSize) == 0. The number of burgers divides evenly by the panSize. Similar to the above case, but we repeat the process until all hamburgers are gone.
4. Here's out special case. If the remainder of the burgers when divided by the pan size is <= half the pans size: (hamburgers % panSize) <= (panSize / 2), then we can use a trick. We flip over half the burgers, set the other half of the burgers aside, and fill the pan with a new set of burgers. This can save us the time it takes to cook one side of a burgers.
5. Failing the above cases, we fall back to the number of burgers divided by the size of the pan times how long it takes to cook a burger.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

All Solutions and descriptions are now available on GitHub at https://github.com/pmonkelban/TopCodingSolutions