Question

Algorithms question (Please help if you can)

There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. (The flashlight must be walked back and forth; it cannot be thrown, for example.)

Each person walks at a different speed:

person 1 ---> 1 minute to cross the bridge; person 2 ---> 2 minutes; person 3---> 5 minutes, person 4 ---> 10 minutes. A pair must walk together at the rate of the slowest person. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If a person 4 returns a flashlight then, a total of 20 minutes have passed, and you failed the mission.

Describe one of the possible algorithms in words.

Answer 1

person 1 ---> 1 min

person 2 ---> 2 min

person 3 ---> 5 min

person 4 ---> 10 min

first person 1 and 2 will cross : total time 2 min

One will return and then person 3 and 4 will cross : total time = 1 min for person 1 to return + 10 minutes to 3 and 4 to cross = 13 minutes

Now person 2 will return from other side and take person 1 with him = 17 min total

P1 P2 P3 P4 -------------------------------  

P3 P4 ---------------------------------- P1 P2 : 2 min

P1 ---------------------------------- P2 P3 P4 : 13 min

P1 P2 ---------------------------------- P3 P4 : 15 min

----------------------------------- P1 P2 P3 P4 : 17 min