The Capacity C Torch Problem

I stumbled upon the Capacity C Torch problem, and found it really interesting.
I'll start off with a few resources:

1. http://aps.cs.nott.ac.uk/2008/05/06/the-capacity-c-torch-problem-2/


2. http://www.tutor.ms.unimelb.edu.au/bridge/


3. http://en.wikipedia.org/wiki/Bridge_and_torch_problem


4. http://www.springerlink.com/content/935641175550x527/

Problem Definition:
There is a group (G) of people that wishes to cross a bridge in the dark. Each person takes a certain amount of time to cross the bridge. There is only 1 torch available. The bridge can hold at most C people at any one time. Every time a group of people cross the bridge, they need to carry the torch with them. One torch is sufficient to light the path for at most C people at a time. When multiple people cross at the same time, the entire group moves at the speed of the slowest person in the group. Given the values for G, C and the time that each person takes to cross, find the least amount of time that would be required to get the whole group across to the other side.

Expected Complexity of the solution: This solution can be solved using a computer program having a run-time complexity of O(n²), where n is the number of people in the group G [ |G| = n ].

Solution:
Step-1: Let us first concentrate only on how we will divide up the people into sets and in what order we will take them across(from size A to side B). We shall re-visit the problem of which person to get back to bring the torch back from side B to side A.

Let us take some values for the variables G and C.

Example-1: Let |G|=15 and C=5

In this case, we can easily divide people into 3 sets of size 5 each.

We'll sort all the people according to the time they take and group them starting from the slowest person. It can be seen that it is beneficial to club all the slow people together. So, we group the 15^th, 14^th, 13^th, 12^th and 11^th person in one group, and so on..

We'll take the 1^st group(the one with the 5 fastest people) and move them across first. Since someone needs to come back with the torch, it had rather be the quickest person, so we make sure he is across so that he can return.

We then take the 2nd group followed by the 3rd.

Example-2: Let |G|=16 and C=5

In this case, we are left with 1 person after dividing into sets of 5 each. No matter what we do, we will have 4 sets to deal with. We also note that it makes no sense to move just 1 person across. So, the way we make sets is {2,4,5,5}.
Why not divide as {3,3,4,4}? Well, if we do it like the latter case, then the 1^st group will have the time of the 3^rd person, and not the 2^nd like in the former case. In both case, everything else remains the same, except if the 3^rd person is slower than the 2^nd one, we will have increased the total time required to cross. This is why we optimally divide in the former way.

Example-3: Let |G|=17 and C=5

Again, in this case, we optimally divide as {2,5,5,5}. We note that no other division is possible.

Example-4: Let |G|=18 and C=5

Again, in this case, we optimally divide as {3,5,5,5}. We note that no other division is possible.

Example-5: Let |G|=19 and C=5

Again, in this case, we optimally divide as {4,5,5,5}. We note that no other division is possible.


Step-2: Now, we shall concentrate on the problem of which people should bring the torch back from side B to side A, so that the next group on side A can cross the bridge to side B. Let us call these people torch bearers. The same problem also asks and how many at a time to bring back (i.e. How many torch bearers should move from side B to side A without returning) when sets of people are being transferred from side A to side B.

[This is where you should try figuring out for yourself whether you will send 1, 2, 3, 4, 5 (or more) groups at a time (without the torch bearers returning to side B)]

For example, suppose we have a group of people, [1,1,1,1,1,1,4,5,6,7] and C=3.
It is easy to see that once we have 2 people across, we can always get more across without having the torch bearers coming back to side B.

If we decide to work such that every time 2 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1(1^st torch bearer from B to A) + 1(2^nd torch bearer from B to A) + 1(1 and 2 back from side A to side B) = 3/1 (since we were able to get only 1 set across).

If we decide to work such that every time 3 torch bearers cross over to side A, they return to side B, we get the following scenario: The mean cost of transferring a set from side A to side B, and back would be 1 + 1 + 1 + 1(1, 2 and 3 back from side A to side B) = 4/2 (since we were able to get 2 sets across).

Similarly, if we decide to work such that every time 5 torch bearers cross over to side A, they return to side B, we get the following scenario. The mean cost of transferring a set from side A to side B would be 5+1(1, 2 and 3 back from side A to side B)+1(1 from side B to side A)+1(1, 4 and 5 back from side A to side B) = 8/4 (since we were able to get 4 sets across).

We observe that the mean cost went down if we took more torch bearers at a time. However, it is also easy to see that this is not always true. It depends entirely on the time that each torch bearer takes to cross the bridge.

We could also have a case where we have more than 3 torch bearers crossing from B to A, without coming back (like we sent 5 torch bearers at once in the example above).

We can NOT make a greedy choice as to how many sets to take across. i.e. How many torch bearers to send from B to A without them returning. This is where dynamic programming comes to the rescue.

Suppose |G|=47 and C=5
We will optimally divide into sets {2,5,5,5,5,5,5,5,5,5}.

The best way to take all 10 sets across is the best of:

1. The best way to take all across without any torch bearer coming back unless all initial groups are across


2. The best way to take the first 9 groups plus the best way to take the last group


3. The best way to take the first 8 groups plus the best way to take the last 2 groups


4. ...


5. The best way to take the first group plus the best way to take the last 9 groups

The cost for computing these values using dynamic programming or memoization is O(n²). We can use these techniques because there are many overlapping sub-problems, and the other requirements for dynamic programming match.

We can pre-compute the cost required to take 1, 2, 3, 4, etc... groups at a time and store it in a lookup table. The time required to do this is O(n²).

Thus, we can solve the whole problem in time O(n²).