The Daily Click ::. Forums ::. Non-Klik Coding Help ::. Bridge and Torch problem in C++ -- Want a job in programming? )
 

Post Reply  Post Oekaki 
 

Posted By Message

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 03:34:11 -

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

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 03:34:58 -

// ================================================================================================

// Bridge and Torch Problem
// Michael Hadzic
// ================================================================================================

#include <iostream>

// ------------------------------------------------------------------------------------------------
// Prototypes
// ------------------------------------------------------------------------------------------------

char* getFilename(char*);
void print();
void print(char*);
void print(int, int);
void print(int, int, int);

// ------------------------------------------------------------------------------------------------
// 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
// --------------------------------------------------------------------------------------------

intNmbr = prmNmbr - 1;
intTime = 0;
intWait = intNmbr;
blnWait = true;
intSped = static_cast <int*> (malloc(sizeof(int) * intNmbr));
blnCros = static_cast <bool*> (malloc(sizeof(bool) * intNmbr));

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
// --------------------------------------------------------------------------------------------

bool blnUpdt;

do
{
blnUpdt = false;

for(int a = 0; a < intNmbr - 1; a++)
{
if(intSped[a] > intSped[a + 1])
{
int intTemp = intSped[a];
intSped[a] = intSped[a + 1];
intSped[a + 1] = intTemp;

blnUpdt = true;
}
}
} while(blnUpdt);

// --------------------------------------------------------------------------------------------
// 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(!blnCros[0] && !blnCros[1])
{
blnCros[0] = true;
blnCros[1] = true;

intWait -= 2;
intTime += intSped[1];

print(1, 2, intSped[1]);
}

// ------------------------------------------------------------------------------------
// If the fastest is on the left and the second fastest on the right, move the slowest
// ------------------------------------------------------------------------------------

else
{
int intSlo1 = -1;
int intSlo2 = -1;

for(int a = intNmbr - 1; a >= 0; a--)
{
if(!blnCros[a])
{
if(intSlo1 < 0)
{
intSlo1 = a;
}
else if(intSlo2 < 0)
{
intSlo2 = a;
}
}
}

blnCros[intSlo2] = true;
blnCros[intSlo1] = true;

intWait -= 2;
intTime += intSped[intSlo1];

print(intSlo2 + 1, intSlo1 + 1, intSped[intSlo1]);
}

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
// ------------------------------------------------------------------------------------

else
{
blnCros[1] = false;

intWait++;
intTime += intSped[1];

print(2, intSped[1]);
}

blnWait = true;
}
}

// --------------------------------------------------------------------------------------------
// Finalise
// --------------------------------------------------------------------------------------------

char* chrTime = static_cast <char*> (malloc(sizeof(char) * (intTime / 10)));
itoa(intTime, chrTime, 10);

std::cout << "FINISHED IN: " << chrTime;

if(intTime == 1)
{
std::cout << " minute" << std::endl;
}
else
{
std::cout << " minutes" << std::endl;
}

return EXIT_SUCCESS;
}

// ================================================================================================
// Get the name of the program from the complete path
// ================================================================================================

char* getFilename(char* prmPath)
{
for(int a = strlen(prmPath) - 1; a >= 0; a--)
{
if(prmPath[a] == '\\' || prmPath[a] == '/')
{
char* chrFile = static_cast <char*> (malloc(sizeof(char) * (strlen(prmPath) - a)));

for(int b = a + 1; b < strlen(prmPath); b++)
{
chrFile[b - (a + 1)] = prmPath[b];
}

chrFile[strlen(prmPath) - (a + 1)] = '\0';
return chrFile;
}
}

return prmPath;
}

// ================================================================================================
// 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
// ================================================================================================

void print(char* prmMesg)
{
std::cout << prmMesg << ":\n";

print();
return;
}

// ================================================================================================
// Print a message when a person has returned
// ================================================================================================

void print(int prmPsn1, int prmSped)
{
char* chrPsn1 = static_cast <char*> (malloc(sizeof(char) * (prmPsn1 / 10)));
char* chrSped = static_cast <char*> (malloc(sizeof(char) * (prmSped / 10)));

itoa(prmPsn1, chrPsn1, 10);
itoa(prmSped, chrSped, 10);

std::cout << "Person " << chrPsn1 << " returns in " << chrSped;

if(prmSped == 1)
{
std::cout << " minute:\n";
}
else
{
std::cout << " minutes:\n";
}

print();
return;
}

// ================================================================================================
// Print a message when two people cross
// ================================================================================================

void print(int prmPsn1, int prmPsn2, int prmSped)
{
char* chrPsn1 = static_cast <char*> (malloc(sizeof(char) * (prmPsn1 / 10)));
char* chrPsn2 = static_cast <char*> (malloc(sizeof(char) * (prmPsn2 / 10)));
char* chrSped = static_cast <char*> (malloc(sizeof(char) * (prmSped / 10)));

itoa(prmPsn1, chrPsn1, 10);
itoa(prmPsn2, chrPsn2, 10);
itoa(prmSped, chrSped, 10);

std::cout << "Person " << chrPsn1 << " and person " << chrPsn2 << " cross in " << chrSped;

if(prmSped == 1)
{
std::cout << " minute:\n";
}
else
{
std::cout << " minutes:\n";
}

print();
return;
}
Mike

 
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 03:39:30 -

Image

Download the source AND compiled EXE here: http://www.create-games.com/shadowcaster/misc/bridgeandtorch.zip

Mike

 
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert

Kris

Possibly Insane

Registered
  17/05/2002
Points
  2017
4th June, 2004 at 07:04:32 -

looks handy, thanks for that. i'll have a read later

PS. did you learn your C++ with a SAMS book by any chance?

Image 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

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 08:36:03 -

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

Kris

Possibly Insane

Registered
  17/05/2002
Points
  2017
4th June, 2004 at 09:10:50 -

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

Jack



Registered
  15/09/2002
Points
  14
4th June, 2004 at 11:03:07 -

Nah, the STL rocks. I love it.

Just had to add that.

 
Jack!

ChrisB

Crazy?

Registered
  16/08/2002
Points
  5457
4th June, 2004 at 11:12:52 -

At least you know where you are with STL. Who needs the extra Windows-only stuff when you can have cross-platform compatibility ;P

 
n/a

Klikmaster

Master of all things Klik

Registered
  08/07/2002
Points
  2599

Has Donated, Thank You!You've Been Circy'd!VIP MemberPS3 Owner
4th June, 2004 at 12:54:22 -

Lol, I have SAMS book, "Learn C++ in 21 days"

 
n/a

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 18:55:41 -

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

Long John Kickbag



Registered
  26/08/2002
Points
  148
4th June, 2004 at 19:03:41 -

My code: www.clicksplat.com/BandT.zip . With a more user friendly interface. Didn't test it fully but it seems to work fine.

 
Resize! - www.clicksplat.com/comparison.html

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
4th June, 2004 at 19:13:01 -

Here's a screenshot of Erik's version:

Image

Mike

 
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert

- Yelnek -



Registered
  03/05/2003
Points
  1016

VIP MemberI am an April Fool
5th June, 2004 at 03:23:03 -



I have no clue what the code means but what it can due is awesome!
Haha nice work man!

P.S. GO FLAMES GO!!!!!!!!!!!!

 
"I have dreamed a dream... But now that dream is gone from me."








Tigerworks

Klik Legend

Registered
  15/01/2002
Points
  3882
5th June, 2004 at 06:38:55 -

What's a functor?

 
- Tigerworks

Batchman



Registered
  08/08/2003
Points
  231
5th June, 2004 at 07:15:32 -

when i read the subject for the first time i understood that the code had to accept any number of person ...

 
n/a

Long John Kickbag



Registered
  26/08/2002
Points
  148
5th June, 2004 at 07:25:51 -

From what I understand, functors are functions created as classes (in C++ at least and are created by operator overloading) so that you can point to them and their data. So you can create call-back events and stuff.

 
Resize! - www.clicksplat.com/comparison.html

Josh Whelchel

Musician

Registered
  01/06/2002
Points
  73

I am an April Fool
5th June, 2004 at 13:32:28 -

printf is MUCH more effecient then all that itoa garble your using. Just thought you'd like to know that (;

 
Last time I was on this site it said I was "16."

ChrisB

Crazy?

Registered
  16/08/2002
Points
  5457
5th June, 2004 at 14:13:25 -

It's also ANSI C compliant, unlike all that itoa garble you're using

 
n/a

ShadowCaster

Possibly Insane

Registered
  02/01/2002
Points
  2203
5th June, 2004 at 19:40:15 -

std::cout can actually print ints without conversion to char*s first. The reason I'm converting them is I originally had my functions doing other things that required them as char*s, but I changed it so that it didnt do that anymore and forgot to change that part of my code back

Erik C is correct

Mike

 
"Now I guess we're... 'Path-E-Tech Management'" -Dilbert
   

Post Reply



 



Advertisement

Worth A Click