A couple months ago I came across the bridge and torch problem at a careers fair in Oxford. A young tech company called QuBit used it as a brain teaser challenge for would be software engineers to solve before submitting their CVs for job openings. The brain teaser has been called the “bridge crossing problem” and “missionaries and cannibals problem” elsewhere, hthey all refer to the same challenge. Having not come across the problem before, I decided to give it a shot.
Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. Because it’s night, the torch has to be used when crossing the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 7 minutes, and D in 10 minutes. When two people cross the bridge together, they must move at the slower person’s pace. The question is, can they all get across the bridge in 17 minutes or less?
t1, t2, t3, … , tN-1, tN.
In his paper entitled “Crossing the bridge at night”, Rote points out that the optimal strategy will depend on the relative size of {2t2} and {t1 + tN-1}. For instance, when the crossing times in seconds are {1,2,7,10}, the optimal crossing strategy to minimise time is:
crossing time = 17 seconds.
This can be generalised as follows: start with the two smallest numbers, get them across the bridge, and (always) return with the smallest number. Then take the largest pair of numbers across the bridge and return with the smallest number of all those already accross the bridge. Repeat until all numbers have crossed.
If however the crossing times are {1,20,21,22}, the above strategy will be sub-optimal because : {2t2} > {t1 + tN-1}, i.e 40 > 22. Using the first strategy we get:
crossing time = 83 seconds.
The optimal strategy in this case is to do the following:
crossing time = 65 seconds!
The second part of the QuBit challenge was to code up a function to find the minimum time required to cross the bridge given the following times: {1,6,10,13,15,16,17}. I used the R language to code up the function, and it looks like so:
#function to solve for minimum bridge crossing time
min.bridge.crossing.time 1){
if(l==2){
p2 = sort(c(p2,p1[c(1,2)])) #let final two cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(1,2)]) #increment total time
p1 = p1[c(-1,-2)]
}
if(l==3){
p2 = sort(c(p2,p1[c(1,3)])) #let final two cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(1,3)]) #increment total time
p1 = p1[c(-1,-3)]
p1 = sort(c(p1,p2[1])) #let t1 cross over back to initial position and sort at same time
tot.time = tot.time + p2[1] #increment total time
p2 = p2[-1]
}
if(l>=4){
if( (2*p1[2]) p2 = sort(c(p2,p1[c(1,2)])); #let t1 & t2 cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(1,2)]); #increment total time
p1 = p1[c(-1,-2)];
p1 = sort(c(p1,p2[1])); #let t1 cross over back to initial position and sort at same time
tot.time = tot.time + p2[1]; #increment total time
p2 = p2[-1];
l = length(p1);
p2 = sort(c(p2,p1[c(l-1,l)])); #let largest two times cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(l-1,l)]); #increment total time
p1 = p1[-c(l-1,l)];
p1 = sort(c(p1,p2[1])); #let smallest time in p2 cross over back to initial position and sort at same time
tot.time = tot.time + p2[1]; #increment total time
p2 = p2[-1];} else{
p2 = sort(c(p2,p1[c(1,l)])); #let t1 & t2 cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(1,l)]); #increment total time
p1 = p1[c(-1,-l)];
p1 = sort(c(p1,p2[1])); #let t1 cross over back to initial position and sort at same time
tot.time = tot.time + p2[1]; #increment total time
p2 = p2[-1];
l = length(p1);
p2 = sort(c(p2,p1[c(1,l)])); #let largest two times cross bridge into p2, and sort at same time
tot.time = tot.time + max(p1[c(1,l)]); #increment total time
p1 = p1[c(-1,-l)];
p1 = sort(c(p1,p2[1])); #let smallest time in p2 cross over back to initial position and sort at same time
tot.time = tot.time + p2[1]; #increment total time
p2 = p2[-1];}
}
l = length(p1) #update number still to corss bridge
}
tot.time
}
This code might not be the best written code, but it gets the job done! To test it, use:
#test it! min.bridge.crossing.time(c(1,2,7,10)) #answer = 17 min.bridge.crossing.time(c(1,6,10,13,15,16,17)) # answer = 75 min.bridge.crossing.time(sample(c(1:1000),round(runif(1,1,1000)))) #can solve for n number of crossing times
The code for this can be found at my github repository.
(not necessarily in that order!). The last ten years has been an extraordinary journey from the sandy shores of my homeland – St Vincent, to marking time on HMF drill squares, followed by countless hours preparing cell cultures during my undergraduate degree in London, and finally to the dreamy spires of Oxford for a DPhil in Statistics.
