Introduction
Generalized Puzzle:
A group of “n” people wish to cross a bridge at night. At most “m” people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross.
Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.
For e.g.
n=4,m=2
Speed of 4 peoplle are 1,2,5,10.
Task is to determine a strategy that gets all 4 people across the bridge in the minimum time.
Background
Why obvious solution is not optimal solution in many cases?
In obvious solution, we take highest & lowest to go to another side & returns with lowest person. Still, it’s not optimal in some cases. Reason is when highest goes with lowest on another side, time required is of highest. Then, Lowest returns . Now, when second highest goes with lowest, time required is of second highest. So, time is highest + second highest.
Suppose, highest goes with second highest, second highest time is covered by highest time & that’s why, time is only highest time. But if we return with second highest, it will be very loss of time. That’s why, while doing such things, make sure that, you have low time persons on the another side so that, they can return with the boat.
This means, we need to reserve the minimum time persons on the another side and this is the “reservation strategy”.
Reservation Strategy
As explained above, many times, optimal solution is obtained with the reservation strategy. But only obvious strategy or reservation strategy is not used for full solution. It’s used in batches and that batch size depends upon the capacity of the boat. Because, for the reservation strategy, we need to reserve low time persons for the return trip.
But how many people to reserve?
Optimal solution will only occur when in going trip, number of persons are maximum i.e. capacity of the boat. That’s why, in each batch, maximum “m” going trip & “m” return trips are done.
Let us solve the batch-1 by reservation strategy:
Time taken by above is 3+1+10+2+7+3= 26 sec
Now, we have solved by reservation strategy. Same number of trips we need to evaluate by the obvious strategy.
Let us solve batch-1 by obvious strategy:
Time taken by above is 10+1+8+1+6+1=27 sec.
Taking minimum of obvious & reservation strategy
After each batch, maximum “m*(m-1)” high time persons goes on the another side. In above example, after first batch, 5,6,7,8,9,10 are on another side. Strategy which takes minimum time to travel batch on another side is used. In the above example, reservation strategy takes 26 seconds & obvious strategy takes 27 seconds. So, we will use batch-1 by reservation strategy.
Solving full problem
Solving full problem is the summation of all batches. In each batch, the proper strategy chosen depends on the minimum time and summation of all time is the minimum time to cross the bridge.
Full example is explained as follows:
Using the code
Variable “np” is the total number of people, “bp” is the capacity of the boat & arr[np] gives the timing of “np”th person to cross the bridge.
We need to first sort the array in which timing values are saved i.e. arr[]
for (i= 0;i<np-1;i++)
{
position =i;
for (j= i+1;j<np;j++)
{
if(arr[position]>arr[j])
position=j;
}
if ( position != i )
{
swap =arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}
Now, following code will execute the batch by obvious strategy:
for(i=0;i<bp;i++)
{
chkn[0]=1;finish1++;count=1;
for(j=np-1;count<bp && j>=0;j--)
{
if(chkn[j]==0)
{
chkn[j]=1;finish1++; if(count==1) max=j;
count++;
}
}
ntime+=arr[max];
if(finish1==np) break;
else
{
chkn[0]=0;finish1--;
ntime+=arr[0];
}
}
Then, after that, code evaluates time by reservation strategy:
for(i=0;i<bp;i++)
{
for(k=0;k<bp;k++)
{
if(chkr[k]==1) {chkr[k]=0;;rtime+=arr[k];finish2--;break;}
}
if(i==bp-1) break;
count=0;
for(j=np-1;count<bp && j>=0;j--)
{
if(chkr[j]==0)
{
chkr[j]=1;finish2++;
if(count==0) max=j;
count++;
}
}
rtime+=arr[max];
if(finish2==np) break;
}
Then, we have taken the minimum of those:
time=min(ntime,rtime);
& do the above procedure for all the batches.
Showing Output
Now, we have calculated the minimum time. But how to show the Path in which we have travelled. Because, we’ve taken just minimum time. We‘ve not saved any path.
Solution is to create one array “idnfyarr[]”. If value of “idnfyarr[idnfy]”=1 then, do it by obvious strategy & if it is 2 then, do it by reservation strategy.
Output
O/p-1:
O/p-2:
O/p-3: