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. Having not come across the problem before, I decided to give it a shot.

**Problem**

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?

**Solution**

t_{1}, t_{2}, t_{3}, … , t_{N-1}, t_{N}.

In his paper entitled “Crossing the bridge at night”, Rote points out that the optimal strategy will depend on the relative size of *{2t _{2}}* and

*{t*. For instance, when the crossing times in seconds are

_{1}+ t_{N-1}}*{1,2,7,10}*, the optimal crossing strategy to minimise time is:

*+{1,2},*

*-{1},*

*+{7,10},*

*-{2},*

*+{1,2},*

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 : *{2t _{2}} > {t_{1} + t_{N-1}}*, i.e

*40 > 22*. Using the first strategy we get:

*+{1,20},*

*-{1},*

*+{22,21},*

*-{20},*

*+{1,20},*

crossing time = 83 seconds.

The optimal strategy in this case is to do the following:

*+{1,22}*

*-{1}*

*+{1,21}*

*-{1}*

*+{1,20}*

crossing time = 63 seconds!

**R code**

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)) #let final two cross bridge into p2, and sort at same time tot.time = tot.time + max(p1) #increment total time p1 = p1 } if(l==3){ p2 = sort(c(p2,p1)) #let final two cross bridge into p2, and sort at same time tot.time = tot.time + max(p1) #increment total time p1 = p1 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)); #let t1 & t2 cross bridge into p2, and sort at same time tot.time = tot.time + max(p1); #increment total time p1 = p1; 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)); #let largest two times cross bridge into p2, and sort at same time tot.time = tot.time + max(p1); #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)); #let t1 & t2 cross bridge into p2, and sort at same time tot.time = tot.time + max(p1); #increment total time p1 = p1; 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)); #let largest two times cross bridge into p2, and sort at same time tot.time = tot.time + max(p1); #increment total time p1 = p1; 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.