Hey all
It's pretty obvious that most large software companies will give you a small test when you go for a job -- Microsoft used to give some programmers a task of solving the Bridge and Torch problem (as I call it), that is, until everyone found out that they ask the Bridge and Torch problem and they stopped because it would be pretty easy to memorise the code and just recite it
The basic problem is this: A group of people want to cross a bridge which is strong enough only to support two people at once. It's night and they need a torch to cross, so when two people cross one person needs to return so the next two have a torch to light their path.
Each person crosses the bridge at a different speed, and the two people crossing must do so at the speed of the slower person.
In what order should they cross in order to minimise the time taken for them all to reach the other side?
For example, if you have four people, one person takes one minute to cross the bridge, another takes two minutes, another takes five minutes and another takes ten minutes (because he is scared of heights) then you could find the solution like this:
- People 1 and 2 cross in 2 minutes
- Person 1 returns in 1 minute
- People 3 and 4 cross in 10 minutes
- Person 2 returns in 2 minutes
- People 1 and 2 cross in 2 minutes
TOTAL: 17 Minutes
If you want to do this problem yourself, then dont read what I have below as it pretty much gives it away, before infact providing the complete code solution. If you're an avid programmer, and are thinking about doing this as a profession, then I suggest you try to solve it yourself first!
This problem seems easy enough -- and when solving by hand it is quite straight-forward. But how would you program a general solution? The reason this is such a good question to ask a programmer is because, although as I already mentioned the problem is easy to do by hand, a computer obviously cant see patterns people do automatically. The way someone, as a programmer, would first try to solve the problem is to program it to check every contingency. This seems logical to solve the problem, but when you start programming this you'll see just how awful this becomes very quickly.
At one stage someone actually did program this completely to check every single possibility. The program took several hours to execute on a small problem containing only four people wanting to cross the bridge. The scalability of the program was quite hidious... at the worst point it was something to the extent of 2^n, which any programmer should know, if you have university/college education and you make code with that sort of scalability, then programming isnt for you.
But if some forethought is put into the problem then you can work out a minimal case for finding out the solution in any situation and for any number of people. If you can ask yourself a few questions before you start any programming task, rather than diving straight in, then it's always going to improve your code in large-scale or complex projects.
In this case, you might ask yourself "what case will never yield a low time?" and you could come to the conclusion -- sending someone over the bridge who takes a long time then sending them back again. If you stick to only the fastest people who go back across the bridge, then you're going to improve the speed of your code greatly.
You then might ask "How do I make sure there is always a fast person carrying the torch back?" The solution to this is simple -- When the torch is on the side with the people who havent crossed, and the two fastest people are also on that side, then both of them should go across straight away.
Is that the only way to minimise the algorithm? The answer is no -- when someone slow is crossing the bridge, who do you take across with them? Someone fast to bring the torch back? No, you take the second slowest person. This way you can take two slow people across and only increase the time substantially once, rather than twice when you need to later bring the other slow person across.
You can see that, in the above example, I have done this to find the solution. I challenge anyone to find a faster order to bring them across the bridge
In my next post I'll include the complete code for doing this. If you havent done so already, now you have the idea for how to create the code efficiently, try making it yourself first!
Mike¿
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert
// ================================================================================================
// Bridge and Torch Problem
// Michael Hadzic
// ================================================================================================
// ------------------------------------------------------------------------------------------------
// Global variables
// ------------------------------------------------------------------------------------------------
int intNmbr; // The number of people
int intTime; // The time taken so far
int intWait; // Number of people waiting to cross
bool blnWait; // True if torch is with waiting people
int* intSped; // Time taken for each person to cross
bool* blnCros; // True if a person has crossed
// ------------------------------------------------------------------------------------------------
// Main function
// ------------------------------------------------------------------------------------------------
int main(int prmNmbr, char** prmArgs)
{
system("cls");
// --------------------------------------------------------------------------------------------
// Check that data was entered, and if not, display help information
// --------------------------------------------------------------------------------------------
if(prmNmbr < 4)
{
std::cout << "Bridge and Torch Problem\n";
std::cout << "By Michael Hadzic\n\n";
std::cout << "A group of people need to cross a bridge in the dark.\n";
std::cout << "The bridge can only support two people at a time, and\n";
std::cout << "they only have one torch which needs to be returned\n";
std::cout << "before the next two people can cross.\n\n";
std::cout << "Each person crosses the bridge at a different speed,\n";
std::cout << "and the two people crossing must travel at the speed\n";
std::cout << "of the slower person. How can they minimize the time\n";
std::cout << "taken for everyone to make it to the other side?\n\n";
std::cout << "Enter the times for each person at the command line;\n";
std::cout << "you must enter at least three, for example:\n\n";
std::cout << "\"" << getFilename(prmArgs[0]) << "\" 1 2 5 10" << std::endl;
exit(EXIT_SUCCESS);
}
// --------------------------------------------------------------------------------------------
// Set global variables
// --------------------------------------------------------------------------------------------
for(int a = 1; a < prmNmbr; a++)
{
intSped[a - 1] = atoi(prmArgs[a]);
blnCros[a - 1] = false;
if(intSped[a - 1] < 1)
{
std::cout << "A person cannot cross the bridge in " << intSped[a - 1] << " minutes." << std::endl;
exit(EXIT_SUCCESS);
}
}
// --------------------------------------------------------------------------------------------
// Sort people by the time it takes them to cross
// --------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------
// Print information
// --------------------------------------------------------------------------------------------
for(int b = 0; b < intNmbr; b++)
{
std::cout << "Person " << b + 1 << " takes: " << intSped[b] << " min\n";
}
std::cout << std::endl;
// --------------------------------------------------------------------------------------------
// Move the two fastest, then return the fastest
// Move the two slowest, then return the fastest
// --------------------------------------------------------------------------------------------
print("Start");
while(intWait > 0)
{
if(blnWait)
{
// ------------------------------------------------------------------------------------
// If the two fastest are on the left, move them to the right
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// If the fastest is on the left and the second fastest on the right, move the slowest
// ------------------------------------------------------------------------------------
blnWait = false;
}
else
{
// ------------------------------------------------------------------------------------
// If the fastest is on the right, move it back
// ------------------------------------------------------------------------------------
if(blnCros[0])
{
blnCros[0] = false;
intWait++;
intTime += intSped[0];
print(1, intSped[0]);
}
// ------------------------------------------------------------------------------------
// If the fastest is on the left, move the second fastest
// ------------------------------------------------------------------------------------
// ================================================================================================
// Get the name of the program from the complete path
// ================================================================================================
// ================================================================================================
// Print the current location of each person
// ================================================================================================
void print()
{
for(int a = 0; a < intNmbr; a++)
{
if(!blnCros[a])
{
std::cout << a + 1 << " ";
}
}
std::cout << "=-=";
for(int b = 0; b < intNmbr; b++)
{
if(blnCros[b])
{
std::cout << " " << b + 1;
}
}
std::cout << "\n" << std::endl;
return;
}
// ================================================================================================
// Print a message
// ================================================================================================
// ================================================================================================
// Print a message when a person has returned
// ================================================================================================
// ================================================================================================
// Print a message when two people cross
// ================================================================================================
looks handy, thanks for that. i'll have a read later
PS. did you learn your C++ with a SAMS book by any chance?
Edited by the Author.
"Say you're hanging from a huge cliff at the top of mt. everest and a guy comes along and says he'll save you, and proceeds to throw religious pamphlets at you while simultaniously giving a sermon." - Dustin G
Kris: I actually learned it on my own at the start... very minimally; then we were taught everything you need to know plus a whole lot of stuff that I could live my entire life without needing to know about the STL at uni. C++ is my favourite language, but wow, there is so much stuff in there that I'm sure no one ever uses
Did you learn C++ with a SAMS book? I've never read one before, but a lot of people swear by them.
Mike
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert
yeah, a bit of it, but the examples got a bit too long to follow so I stopped and just found an online tutorial. Your style just looks a lot like SAMS', that's all
"Say you're hanging from a huge cliff at the top of mt. everest and a guy comes along and says he'll save you, and proceeds to throw religious pamphlets at you while simultaniously giving a sermon." - Dustin G
Oh, the STL is great, I admit, but who will ever need functors? Seriously? Our lecturer even said they were useless when she taught them to us. Someone asked "when would you ever use this?" and she said "never. It was designed to make code easier, but you never actually need them, and I would recommend you never use them. But sometimes people make code that uses it so you need to know about it" That's just one example
Mike
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert
Advertisement
Post Reply
Mike 
¿
Edited by the Author.
