#codingexercise
We were discussing a sample problem of crossing the bridge.
There are 4 persons (A, B, C and D) who want to cross a bridge in night.
A takes 1 minute to cross the bridge.
B takes 2 minutes to cross the bridge.
C takes 5 minutes to cross the bridge.
D takes 8 minutes to cross the bridge.
There is only one torch with them and the bridge cannot be crossed without the torch. There cannot be more than two persons on the bridge at any time, and when two people cross the bridge together, they must move at the slower person’s pace.
Can they all cross the bridge in 15 minutes ?
Solution: A and B cross the bridge. A comes back. Time taken 3 minutes. Now B is on the other side.
C and D cross the bridge. B comes back. Time taken 8 + 2 minutes. Now C and D are on the other side.
A and B cross the bridge. Time taken is 2 minutes. All are on the other side.
Total time spent is 3 + 10 + 2 = 15 minutes.
Next we wanted to generalize this.
The combination chosen works for this example by observing the tradeoff between having at least one fast member available on the right to come back and the pairing of slow folks on the left to go to the right so that they are not counted individually.
We noted that they have overlapping subproblems.
We have left and right sides. The number of people on the left side can vary between 0 to a large number. The next move can either be from the left side to the right side or vice versa. Therefore we can maintain a dynamic programming table of that many rows and two columns. At any time, this table stores the minimum time it takes for that many number of people on the left side given that move so we need not recalculate. it. Also we don't just store the number of people, we actually store the bitmask so as to give the positions of the people present on the left side. With this we can immediately know the presence roll on the right side. Given that any one of the n people can make the move, we pick the one that yields the minimum time on recursion. We evaluate this for both moves separately since two can go in one direction and only one on return. We try for every pair and given that we have already exhausted the cases for a number less than the current iteration i from 0 to n-1, we try the pairing with numbers between i+1 to n-1. Finally, we return the minimum time.
To get the right mask value we can use:
int GetRightMask(int leftmask)
{
// use the 1s in all positions of the number and xor it with the left mask
return ((1 << n) - 1) ^ leftmask;
}
For the return path we are only selecting one person. We can find this one by iterating through 1 to n for those on the right side to find the recusive minimum time For the forward path, we have to pick a pair. The pair can be combined by selecting any one of the n people together with any of the candidate from those greater than i but less than n.
We were discussing a sample problem of crossing the bridge.
There are 4 persons (A, B, C and D) who want to cross a bridge in night.
A takes 1 minute to cross the bridge.
B takes 2 minutes to cross the bridge.
C takes 5 minutes to cross the bridge.
D takes 8 minutes to cross the bridge.
There is only one torch with them and the bridge cannot be crossed without the torch. There cannot be more than two persons on the bridge at any time, and when two people cross the bridge together, they must move at the slower person’s pace.
Can they all cross the bridge in 15 minutes ?
Solution: A and B cross the bridge. A comes back. Time taken 3 minutes. Now B is on the other side.
C and D cross the bridge. B comes back. Time taken 8 + 2 minutes. Now C and D are on the other side.
A and B cross the bridge. Time taken is 2 minutes. All are on the other side.
Total time spent is 3 + 10 + 2 = 15 minutes.
Next we wanted to generalize this.
The combination chosen works for this example by observing the tradeoff between having at least one fast member available on the right to come back and the pairing of slow folks on the left to go to the right so that they are not counted individually.
We noted that they have overlapping subproblems.
We have left and right sides. The number of people on the left side can vary between 0 to a large number. The next move can either be from the left side to the right side or vice versa. Therefore we can maintain a dynamic programming table of that many rows and two columns. At any time, this table stores the minimum time it takes for that many number of people on the left side given that move so we need not recalculate. it. Also we don't just store the number of people, we actually store the bitmask so as to give the positions of the people present on the left side. With this we can immediately know the presence roll on the right side. Given that any one of the n people can make the move, we pick the one that yields the minimum time on recursion. We evaluate this for both moves separately since two can go in one direction and only one on return. We try for every pair and given that we have already exhausted the cases for a number less than the current iteration i from 0 to n-1, we try the pairing with numbers between i+1 to n-1. Finally, we return the minimum time.
To get the right mask value we can use:
int GetRightMask(int leftmask)
{
// use the 1s in all positions of the number and xor it with the left mask
return ((1 << n) - 1) ^ leftmask;
}
For the return path we are only selecting one person. We can find this one by iterating through 1 to n for those on the right side to find the recusive minimum time For the forward path, we have to pick a pair. The pair can be combined by selecting any one of the n people together with any of the candidate from those greater than i but less than n.
No comments:
Post a Comment