Bridge and Torch problem in R

November 8, 2011
By

(This article was first published on undercover_neRd » R, and kindly contributed to R-bloggers)

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
There are several variations of the problem, but in general it goes something like this:

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
There are several ways to go about solving this problem, but I like the approach taken by Rote (2002). Let’s label the waiting times as follows:

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:

+{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 : {2t2} > {t1 + tN-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[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.


To leave a comment for the author, please follow the link and comment on his blog: undercover_neRd » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , , , , ,

Comments are closed.